I though of the following problem; I did not have time to seriously think about and I probably won't, but rather than forgetting it I thought, maybe, someone will like it so I decided to post it here.
Two people have chosen a word in a given list of words $L$. They do not choose the words in order to maximize something: the words are chosen for exogeneous reasons (see Examples below). What is the best strategy to detect if both chosen words are different, while minimizing the information given (so that the other one cannot guess your word)?
For example, let say $L$ is an English dictionary, person P1 chooses "a" and person P2 chooses "question". The strategy could be to give the number of letters, but then it will be easy (in the sense of high probability) for P2 to guess P1's word "a". It could also be the letter of highest rank, i.e. a for P1 and t for P2.
Edit Examples of application:
- two people want to make sure they are not offering each other the exact same product (without revealing what their presents is).
- two people want to make sure their birthdays is not the same month.
- two pregnant sisters want to make sure they are not giving the same first name to their newborn (and want to wait the birth to give out the name).
I would say a strategy that is "binary search-like". For words, "is your word in the first half or last half of the list", if both are yes, or both no, subdivide further. For dates, "is your birthday in the first half of the year or last half of the year". Again, if both yes or both no, subdivide further.
I don't have a proof, but this seems like it would give away the least amount of information before determining the choices were different.