In graphical games a network is used to model the structure of a game: the utility of each player only depends on the actions of its neighbours in the network. When a game converges to a Nash equilibrium, the players are implicitly solving the computational task of finding a Nash equilibrium. Many systems modelled by graphical games are naturally decentralised, and we want to understand how hard it is for a distributed system to compute Nash equilibria.

The Nash equilibria of graphical games are locally verifiable: an assignment of strategies is stable if and only if it is stable around each player. This family of locally verifiable problems has been intensely studied in distributed computing, and in recent years a relatively mature complexity theory has emerged. This allows us to determine which Nash equilibria of a graphical game are efficiently computable and to analyse the properties of these equilibria.

We recently formalised this connection between game theory and distributed computing (see https://arxiv.org/abs/2102.13457). I will illustrate how equilibria can be analysed using examples (e.g. the public goods game of Bramoullé and Kranton (2007)), and discuss potential future research, including mechanism design based on efficient distributed algorithms.