Loading ...
Sorry, an error occurred while loading the content.

966[Computational Complexity] Crypto problem inspired by politness

Expand Messages
    Dec 5 10:54 AM
      The following happened- a common event, but it inspired a crypto question (probably already known and answered) but I would like your comments or pointer to what is known.

      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.
      1. 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.
      2. Posy has a similar coin.
      3. Margie flips, Posy Flips.
      4. If Margie's coin says OFFER, than make the offer. If not the don't.
      5. Same with Posy.
      The bad scenarios- that they both get what they don't want, has prob 1/8. However, if they do this alot then Margie and Posy will both have a good idea of what the other really wants.

      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.

      Posted By GASARCH to Computational Complexity at 12/05/2007 12:47:00 PM