Coin-flipping games immune against linear-sized coalitions

Noga Alon, Moni Naor

Research output: Contribution to journalConference article

3 Scopus citations

Abstract

It is proved that for every c < 1 there are perfect-information coin-flipping and leader-election games on n players in which no coalition of cn players can influence the outcome with probability greater than some universal constant times c. It is shown that a random protocol of a certain length has this property, and an explicit construction is given as well.

Original languageEnglish (US)
Pages (from-to)46-54
Number of pages9
JournalIEEE Transactions on Industry Applications
Volume27
Issue number1 pt 1
StatePublished - Jan 1 1991
Externally publishedYes
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering

Cite this