I have a puzzle:
Two groups want to break a tied vote using a
simple coin flip, however the only coin they have
available is a biased coin (i.e., one side will come
up more often than the other). To make matters
worse nobody in the room knows (or is willing to
admit) how the coin is biased.Assuming that the coin has two distinct sides,
design a method for using only this coin to
determine a fair outcome between the two parties.
Initially, I thought, since neither party knows how the coin is biased, then either party could simply randomly guess which side the coin will land on and then they will receive a 50% chance they are correct (and 50% chance they are incorrect). This is assuming they are not influenced by any knowledge that they know for how the coin is biased when randomly deciding (or rather they do not know how it is biased). I even performed a simulation on this for a large amount of trials (live demo in python).
However, I stumbled upon this wikipedia article, which mentions an alternative method.
If a cheat has altered a coin to prefer one side over another (a biased coin), the coin can still be used for fair results by changing the game slightly. John von Neumann gave the following procedure:
- Toss the coin twice.
- If the results match, start over, forgetting both results.
- If the results differ, use the first result, forgetting the second.
I'm just curious: is my method of solving the puzzle a viable solution? It seems so, but I'm not 100% certain.
Best Answer
If you have the ability to generate a random value with 50% probability in your head, then you can just pick one of the two outcomes and you don't need a coin at all.
Also, I think implicit in this problem is the possibility that one of the parties knows how the coin is biased and will secretly use this to their advantage. If you have a fair protocol that will worke with a biased coin then you can still produce a fair outcome despite secret knowledge.