Fair Distribution Protocols or How the Players Replace Fortune

There are n ≥ 2 players P₁, P₂, …, P_n, each of them having a finite alphabet A₁, …, A_n, and there is a probability distribution p on A = A₁ × ⋯ × A_n. The players want to choose a ∈ 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 ∈ 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 ≥ 4. As an application it is shown that a correlated equilibrium of a noncooperative n-person game (n ≥ 4) coincides with a Nash equilibrium of an extended game involving, in addition, plain conversations only.