Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader Election

Suppose that $n$ players want to elect a random leader and they communicate by posting messages to a common broadcast channel. This problem is called leader election, and it is fundamental to the distributed systems and cryptography literature. Recently, it has attracted renewed interests due to its promised applications in decentralized environments.

In a game theoretically fair leader election protocol, roughly speaking, we want that even majority coalitions cannot increase its own chance of getting elected, nor hurt the chance of any honest individual. The folklore tournament-tree protocol, which completes in logarithmically many rounds, can easily be shown to satisfy game theoretic security. To the best of our knowledge, no sub-logarithmic round protocol was known in the setting that we consider.

We show that by adopting an appropriate notion of approximate game-theoretic fairness, and under standard cryptographic assumption, we can achieve $(1-1/2^{\Theta(r)})$-fairness in $r$ rounds for $\Theta(\log \log n) \leq r \leq \Theta(\log n)$, where $n$ denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as $O(\log \log n)$ rounds. We also prove a lower bound showing that logarithmically many rounds is necessary if we restrict ourselves to perfect'' game-theoretic fairness and protocols that are very similar in structure'' to the tournament-tree protocol.

Although leader election is a well-studied problem in other contexts in distributed computing, our work is the first exploration of the round complexity of game-theoretically fair leader election in the presence of a possibly majority coalition. As a by-product of our exploration, we suggest a new, approximate game-theoretic fairness notion, called ``approximate sequential fairness'', which provides a more desirable solution concept than some previously studied approximate fairness notions.