**Abstract.** We do a game-theoretic analysis of leader election, under the assumption

that each agent prefers to have some leader than to have no leader at all. We

show that it is possible to obtain a fair Nash equilibrium, where each agent has

an equal probability of being elected leader, in a completely connected network,

in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In

the asynchronous setting, Nash equilibrium is not quite the right solution concept.

Rather, we must consider ex post Nash equilibrium; this means that we

have a Nash equilibrium no matter what a scheduling adversary does. We show

that ex post Nash equilibrium is attainable in the asynchronous setting in all the

networks we consider, using a protocol with bounded running time. However,

in the asynchronous setting, we require that n > 2. We can get a fair e-Nash

equilibrium if n = 2 in the asynchronous setting, under some cryptographic assumptions

(specifically, the existence of a pseudo-random number generator and

polynomially-bounded agents), using ideas from bit-commitment protocols. We

then generalize these results to a setting where we can have deviations by a coalition

of size k. In this case, we can get what we call a fair k-resilient equilibrium

if n > 2k; under the same cryptographic assumptions, we can a get a k-resilient

equilibrium if n = 2k. Finally, we show that, under minimal assumptions, not

only do our protocols give a Nash equilibrium, they also give a sequential equilibrium

[23], so players even play optimally off the equilibrium path.

Guests: Danny Dolev and Joseph Y. Halpern

Host: Stefan Schmid

Podcast: Play in new window | Download