COLLECI1VECOIN FLIPPING, ROBUST VOTING SCHEMES AND MINIMA OF BANZHAF VALUFS (Preliminary Report)
Michael Ben-Or, Nathan Linial · 1985
The po.wer of players in a collective decision process is a central issue in Mathematical Economics and Game Theory. Similar issues arise in Computer Science in the study of distributed, fault tolerant computations when several processes, some perhaps faulty, have to reach agreement. In the present article we study voting schemes which are relatively immune to the presence of unfair players. In particular, we discuss bow to pedorm collective coin flipping which is only slightly biased despite the pres ence of unfair players. Mathematically this corresponds to problems concerning the minima of Banzhaf values in certain n -person games. These are measures of power studied in Game Theory. It is quite remarkable that while dictatorial voting games are, of course, the most sensitive to the presence of unfair players, some voting schemes that we propose here are significantly more ro bust than majority voting.