Distributed Protocols for Leader Election: a Game-Theoretic Perspective

Ittai Abraham, Danny Dolev, and Joseph Y. Halpern

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

Leave a Reply

Your email address will not be published.

163,337 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>