Distributed Protocols for Leader Election: A Game-Theoretic Perspective

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 -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 [Kreps and Wilson 1982], so players even play optimally off the equilibrium path.