Coin-Flipping Games Immune against Linear-Sized Coalitions

Perfect information coin-ipping and leader-election games arise naturally in the study of fault tolerant distributed computing and have been considered in many di erent scenarios. Answering a question of Ben-Or and Linial we prove that for every c < 1 there are such games on n players in which no coalition of cn players can in uence the outcome with probability greater than some universal constant times c. (Note that we actually prove this statement only for all c < 1=3, but since our universal constant is bigger than 3 the above is trivial for c 1=3.) We show that a random protocol of a certain length has this property and give an explicit construction as well.