Inspired by the party game [Mafia](http://en.wikipedia.org/wiki/Mafia_(party_game)), in particular those situations where nobody is clearly innocent or guilty and the group wants to decide on someone random to eliminate.


Suppose n people each have their own personal random number generator (a machine which generates a 0 or 1 at the push of a button, each with equal likelihood), that these random number generators (henceforth RNGs) operate independently from each other, and, most critically, that each RNG can only be read by its owner. They would like to, as a group, decide on one of two courses of action, and they'd like to do so randomly with 50% probability for each choice.


But, a complication: some members of this group are secretly saboteurs, and they have their own preferences for which of the two options to pick. They'll do anything in their power to sway the decision in a particular direction. On the other hand, the non-saboteurs all have one goal in mind: to make this decision process truly unbiased, to wrench the control from those saboteurs. Nobody knows who the saboteurs are (but let's say there aren't very many of them), and nobody knows which of the two options they're trying to sway things towards.


Is there a strategy the group can employ to remove all bias from the selection process? All anyone can do is talk, push the button on his or her own RNG, and tell the results to the others (though they might not believe it).


EDIT: As a further clarification, the players can't all talk at once. So it's not enough to for everyone to pick a number and sum them mod 2, since the last person to give the number might be a saboteur.



Untrustworthy people picking a random number
The group agrees on a strong hash function H. Each person in sequence generates a number x and reveals H(x). Then each person in sequence reveals x. If all hashes can be verified, then the first bit of sum(x) mod 1 is used.


