FAIR DISTRIBUTION PROTOCOLS OR HOW THE PLAYERS REPLACE FORTUNE

There are n greater-than-or-equal-to 2 players P1, P2, .... P(n), each of them having a finite alphabet A1,..., A(n), and there is a probability distribution p on A = A1 X ... X A(n). The players want to choose a is-an-element-of A according to p in such a way that P(k) knows only the kth component, a(k), of a. This can be done with the help of an impartial person or "fortune" who chooses a is-an-element-of A according to p and informs P(k) on a(k) only. But what happens if no such person is available? Can the players find a procedure that replaces fortune? It is proved here that the answer is yes when n greater-than-or-equal-to 4. As an application it is shown that a correlated equilibrium of a noncooperative n-person game (n greater-than-or-equal-to 4) coincides with a Nash equilibrium of an extended game involving, in addition, plain conversations only.