My mother-in-law Margie and her sister Posy had the following conversation:
POSY: Let me treat the lunch.
MARGIE: No, we should pay half.
POSY: No, I want to treat.
MARGIE: No, I insist.
This went on for quite a while. The question is NOT how to avoid infinite loops- my solution to that is easy- if someone offers to treat, I say YES and if someone offers to pay 1/2 I say YES, not because I'm cheap, but to avoid infinite loops.
Here is the question. It is not clear if Posy really wanted to treat lunch, or is just being polite. Its not clear if Margie really wants to pay half or is just being polite. SO, is their some protocol where the probability of both getting they DO NOT WANT is small (or both getting what they want is large), and the other one does not find out what they really want. Here is an attempt which does not work.
- Margie has a coin. Margies coin is OFFER with prob p, and DO NOT OFFER with prob 1-p. If she really wants to make the offer to treat then p is large, else p is small. Could be p=3/4 or p=1/4 for examples.
- Posy has a similar coin.
- Margie flips, Posy Flips.
- If Margie's coin says OFFER, than make the offer. If not the don't.
- Same with Posy.
In solutions you may offer or point me to we can of course assume access to random coins, and that neither Posy nor Margie can factor or take discrete log.