Coin-flipping games immune against linear-sized coalitions

Perfect information coin-flipping and leader-election games arise naturally in the study of fault tolerant distributed computing and have considered in many different scenarios. This paper answers a question of Ben-Or and Linial by proving that for every c < 1 there are such games on n players in which no coalition of cn players can influence the outcome with probability greater than some universal constant times c. (Note that this paper actually proves this statement only for all c < 1/3, but since its universal constant is bigger than 3 the above is trivial for c ≥ 1/3.) This paper shows that a random protocol of a certain length has this property and gives an explicit construction as well.