Juho Hirvonen

interaction seminar

Juho Hirvonen

Aalto University
Understanding graphical games through theory of distributed computing

IBD Salle 23

Îlot Bernard du Bois - Salle 23

5-9 boulevard Maurice Bourdet
13001 Marseille

Thursday, November 25 2021| 12:00pm to 1:00pm

Gaëtan Fournier: gaetan.fournier[at]univ-amu.fr
Evgeny Tsodikovich: evgeny.tsodikovich[at]univ-amu.fr


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.