On the Convergence Time in Graphical Games : A Locality-Sensitive Approach

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorHirvonen, Juhoen_US
dc.contributor.authorSchmid, Lauraen_US
dc.contributor.authorChatterjee, Krishnenduen_US
dc.contributor.authorSchmid, Stefanen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.editorBessani, Alyssonen_US
dc.contributor.editorDefago, Xavieren_US
dc.contributor.editorNakamura, Junyaen_US
dc.contributor.editorWada, Koichien_US
dc.contributor.editorYamauchi, Yukikoen_US
dc.contributor.groupauthorHelsinki Institute for Information Technology (HIIT)en
dc.contributor.groupauthorProfessorship Uitto J.en
dc.contributor.organizationKorea Advanced Institute of Science and Technologyen_US
dc.contributor.organizationInstitute of Science and Technology Austriaen_US
dc.contributor.organizationTechnical University of Berlinen_US
dc.date.accessioned2024-03-06T10:39:20Z
dc.date.available2024-03-06T10:39:20Z
dc.date.issued2024-01en_US
dc.descriptionPublisher Copyright: © Juho Hirvonen, Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid;
dc.description.abstractGraphical 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.en
dc.description.versionPeer revieweden
dc.format.extent24
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationHirvonen, 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.11en
dc.identifier.doi10.4230/LIPIcs.OPODIS.2023.11en_US
dc.identifier.isbn978-3-95977-308-9
dc.identifier.issn1868-8969
dc.identifier.otherPURE UUID: 98f1fd60-02f1-4ccd-8914-3e347fd3ca64en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/98f1fd60-02f1-4ccd-8914-3e347fd3ca64en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85184149826&partnerID=8YFLogxK
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/136846460/On_the_Convergence_Time_in_Graphical_Games_-_A_Locality-Sensitive_Approach.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/126932
dc.identifier.urnURN:NBN:fi:aalto-202403062567
dc.language.isoenen
dc.relation.ispartofInternational Conference on Principles of Distributed Systemsen
dc.relation.ispartofseries27th International Conference on Principles of Distributed Systems, OPODIS 2023en
dc.relation.ispartofseriespp. 1-24en
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics, LIPIcs ; Volume 286en
dc.rightsopenAccessen
dc.subject.keywordbest-response dynamicsen_US
dc.subject.keyworddistributed computingen_US
dc.subject.keywordmechanism designen_US
dc.subject.keywordNash equilibriaen_US
dc.titleOn the Convergence Time in Graphical Games : A Locality-Sensitive Approachen
dc.typeA4 Artikkeli konferenssijulkaisussafi
dc.type.versionpublishedVersion

Files