Untrustworthy people picking a random number Inspired by the party game Mafia, 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.
 A: What Tom said. Have everyone place their bit into a sealed envelope, open them all up, and take the parity of the bits. (Determine if the sum of the bits is even or odd). So long as at least one of the bits was random, the resulting parity will be random. To see this, imagine it is known that person 1 is honest, but it is unknown whether everyone else is. Imagine that everyone else flips their bits first. This fixes a parity on the other bits, and person 1's bit now (at random) uniquely determines the parity of their sum. 
Note: Its important that everyone first place their bits into sealed envelopes before any of them are read, to prevent a dishonest party from specifically choosing their bit at the end to manipulate the sum.
If you don't have an envelope and you believe in one-way functions, you can use a bit commitment scheme: http://en.wikipedia.org/wiki/Commitment_scheme
Edit: Check out this classic paper, "Coin Flipping by Telephone" http://portal.acm.org/citation.cfm?id=1008911
A: If the final outcome doesn't need to be perfectly unbiased, but instead may have a bias of up to say 10 percent, then there are good algorithms, even if the people have unlimited computational power (which renders cryptographic methods ineffective).  For example, the following baton-passing algorithm works well.  At the start, give the baton to an arbitrary person (say the first person).  At each step, the current baton-holder gives the baton to a random person who has not yet held the baton.  Whoever receives the baton last gets to make the collective coin flip.
If the number of saboteurs is fewer than $n / \log n$, then this algorithm is known to produce a low-biased coin.  Mike Saks proposed and analyzed this algorithm, and Miki Ajtai and Nati Linial refined the analysis.  Here are the references:
M. Saks (1989), A robust non-cryptographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics 2, pages 240-244.
M. Ajtai and N. Linial (1993), The influence of large coalitions, Combinatorica 13, pages 129-145.
You can find a scanned copy of the Ajtai-Linial paper at Linial's homepage:
http://www.cs.huji.ac.il/~nati/. 
Babu Narayanan and I showed that there exists an algorithm that can handle up to 49 percent of the players being saboteurs and yet still produces a low-biased coin.  Here is the reference:
R. Boppana and B. Narayanan (2000), Perfect-Information Leader Election with Optimal Resilience, SIAM Journal on Computing 29:4, pages 1304-1320.
A: Suppose that there is a process for solving the problem that involves each of $k$ players (possibly including repetition) showing a number, these numbers being combined in a predetermined deterministic fashion.  Either the last player can modify the outcome, or the last player can't. In the latter case, look at player $k-1$ and so on; either you eventually get to a player who can alter the outcome or there is no such player.  If there is no such player, the outcome is constant. If there is such a player, and that player is a saboteur, then the outcome can be rigged.
So unless the players can determine who are saboteurs, there is no such process.
A: 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.
A: In this article it is shown how to select a bit string of length $n$ with entropy close to $n$ by two parties. One party could be adversary. More precisely, it is possible to design a protocol that produces a string of entropy $n - O(1)$ in $4 \log^* n$ rounds.
A: Go to each player in turn and learn what their number is.  It is OK if the other players hear.  Use your own RNG to decide whether you 'AND' or 'OR' the players bit with the 'group bit' you have thus far.  Because no player knows how their bit will be interpreted, they lose any power over the outcome.
