Can I read Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory on EtoBox?

Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory by Hirvonen, Juho; Schmid, Laura; Chatterjee, Krishnendu; Schmid, Stefan is a scholarly article available to read on EtoBox.

What is Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory about?

Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though a player's payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of "natural" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with a constant-round local algorithm. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intu

Author

Hirvonen, Juho; Schmid, Laura; Chatterjee, Krishnendu; Schmid, Stefan

Published

2021

Language

EN