On the Convergence Time in Graphical Games : A Locality-Sensitive Approach
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
24
Series
27th International Conference on Principles of Distributed Systems, OPODIS 2023, pp. 1-24, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 286
Abstract
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 an agent’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 constant-round local algorithms. 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 intuitive notion of “time-constrained” inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.Description
Publisher Copyright: © Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid;
Keywords
best-response dynamics, distributed computing, mechanism design, Nash equilibria
Other note
Citation
Hirvonen, J, Schmid, L, Chatterjee, K & Schmid, S 2024, On the Convergence Time in Graphical Games : A Locality-Sensitive Approach . in A Bessani, X Defago, J Nakamura, K Wada & Y Yamauchi (eds), 27th International Conference on Principles of Distributed Systems, OPODIS 2023 ., 11, Leibniz International Proceedings in Informatics, LIPIcs, vol. 286, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-24, International Conference on Principles of Distributed Systems, Tokyo, Japan, 06/12/2023 . https://doi.org/10.4230/LIPIcs.OPODIS.2023.11