The idea came up from a discussion I had with my friends.
Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember the types of cards each one has. The problem is that it is even hard to divide the cards uniformly by using only our brains.
To divide them properly, each one should not know the types of cards others have. By introducing a 'dealer', it becomes easy. We can ask the dealer to tell each person what cards they will have. But the dealer then can't participate in the game. The question is that how can players divide the deck uniformly by themselves.
I think it is important to specify the exact condition for the problem. This is what I have in mind.
- Each person can uniformly choose a number from a finite set of numbers
- All players trust each other. That is, if they agreed on a particular procedure on dividing cards, they will actually follow the procedure.
- The procedure would consist of a sequence of data transfer from one person to other. The receiver will remember the data exactly, and it is impossible to forget it.
- By the end of the procedure, the conditional probability distribution of cards given all the information each person knows should be uniform.
This is far from clear mathematical formulation. So the first question is:
How can we formulate this problem exactly into mathematical language? For example, how can we define the concept of data transfer?
The question is easy when there are only two people and two cards. One can just simply grab one and pass the other. But the question seems much harder for even three people and three cards.
How can three individuals divide three cards uniformly? Or if it is impossible, are there any proof?
I think this can be a more fundamental question.
Can two people having their own number from 1, 2 or 3, interact with each other to conclude that whether they have same or different numbers, but gain no more information about their opponent's number?
Any suggestions for clarification are welcomed. Fixing grammar mistakes and awkward expressions are much welcomed too.
This is a partial answer. It is a little vague, to talk about the uniform division of cards. But if all players trust each other then there is an easy way to do it.
Starting with the player that is choosing the card, each player chooses a number, the choosing player does not divulge his number but others do. Then after all numbers are uttered, the choosing player then uses a uniformifying function like bitwise xor on the numbers and creates his card. The only player that knows this number is him, and any change in any of others' decisions could have changed his card.
Then we can repeat the process again with other players, but the problem is that we might get repeated numbers.
If repeated cards are a problem then for determining whether two people have the same number, we use the secure multiparty computation framework. In that framework, a function $F(x, y)$ can be calculated without revealing any other information about $x$ or $y$.