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.
The question does not seem well defined. If Posy offers and Margie accepts, them Posy pays for everything. If Margie offers and Posy accepts then they each pay half. But what is supposed to happen if they both offer? What is supposed to happen if they both accept (and neither offers)?
ReplyDeleteBetter defined:
ReplyDeletePosy flips: will offer to
pay the whole thing or not
IF she offers to pay
then Margie flips and will
offer to pay half or not.
If Posy does not offer
then Margie does not
flip, and they each pay
half.
If Posy offers and Margie
does not, then Posy pays
for it all.
If Posy offers and Margie
offers, they split.
(With this my estimate
of 1/8 may be wrong).
MANY variants are possible- and some may
be interesting.
if both want the same thing all the time (say split), a protocol has to choose that thing *often*. If on the other hand they want different things the protocol can serve one person not more than half of the time. Therefore no protocol can really work.
ReplyDeleteyour mother-in-law can't factor or take discrete log? clearly, you must upgrade to a quantum mother-in-law
ReplyDeleteHere's how I would formalize.
ReplyDeleteLet bit x be the event
[A wants to pay full].
Let y be the event
[B wants A to pay full].
A holds x and B holds y. Then they hold a protocol which, as I understand it, is desired to (w.h.p.) output the result 'A pays' (call this '1') when x = 1 and y = 1;
to output the result 'split the bill' (call this '0') when x = 0, y = 0;
and to behave arbitrarily otherwise.
So it seems as though 'zero-knowledge distributed consensus' would be the term of art for this problem.
Here's one view of the limits faced by such a protocol. Fix any protocol P(x, y) which respects the consensus with probability, say, .9.
ReplyDeleteLet p be the probability that the protocol outputs 1 when (x, y) = (1, 0). Say p is at most 1/2 (the other case is similar).
Suppose I'm A, holding x = 1. Then the two random variables
P(1, 0), P(1, 1)
have statistical distance at least .4. This means that, e.g., if A is a Bayesian and believes that B is equally likely to hold 0 or 1, then after seeing the protocol output, A can expect to guess B's bit correctly with probability at least .7. This holds regardless of complexity-theoretic assumptions.
If anyone's interested, I did a blog tutorial awhile back about the various equivalent notions of statistical distance, used in inferences of the type above:
http://andysresearch.blogspot.com/2007/08/another-public-service-announcement.html
I guess I should note, two RVs *can* be statistically distant yet computationally indistinguishable; but not if they're 0/1-valued.
ReplyDeleteAndy makes a good point that the output of the proposed mechanism will by definition reveal statistical information about the input. This sort of thing comes up when studying privacy-preserving data release -- there are some functions that by definition, if you wish to 'usefully' release, you cannot insist on indistinguishability in the typical cryptographic sense.
ReplyDeleteThis question is one of the things that distinguishes recent work on privacy preserving data release from classical crypto -- the question not only of how to compute the value of some function without revealing anything other than the output of the function (something like k-anonymity), but also which functions can be computed while preserving privacy, and which cannot. For example, using standard techniques, we could all compute our average salaries without revealing anything other than our average salaries -- but when you leave the room, and we run the computation again, we have all learned your salary.
In this case, it seems that 'usefulness' and 'privacy' conflict . Using Andy's formulation, if we hold (x=1, y=1), the event A pays occurs with probability > 0.9, and if (x=0, y=0) it occurs with probability < 0.1. So consider the set of inputs (x=1,y=1), (x=1,y=0), (x=0,y=0). The probability of A paying must jump by at least 0.4 between one of these profiles, and so there will necessarily be a significant 'privacy violation' somewhere.