License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.20
URN: urn:nbn:de:0030-drops-165540
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16554/
D'Ascenzo, Andrea ;
D'Emidio, Mattia ;
Flammini, Michele ;
Monaco, Gianpiero
Digraph k-Coloring Games: From Theory to Practice
Abstract
We study digraph k-coloring games where agents are vertices of a directed unweighted graph and arcs represent agents' mutual unidirectional idiosyncrasies or conflicts. Each agent can select one of k different colors, and her payoff in a given state is given by the number of outgoing neighbors with a different color. Such games model lots of strategic real-world scenarios and are related to several fundamental classes of anti-coordination games. Unfortunately, the problem of understanding whether an instance of the game admits a pure Nash equilibrium is NP-complete [Jeremy Kun et al., 2013]. Therefore, in the last few years a relevant research focus has been that of designing polynomial time algorithms able to compute approximate Nash equilibria, i.e., states in which no agent, changing her strategy, can improve her payoff by some bounded multiplicative factor. The only two known algorithms in this respect are those in [Raffaello Carosi et al., 2017]. While they provide theoretical guarantees, their practical performance over real-world instances so far has not been investigated. In this paper, under the further motivation of the lack of practical approximation algorithms for the problem, we experimentally evaluate the above algorithms with the conclusion that, while they were suitably designed for achieving a bounded worst case behavior, they generally have a poor performance. Therefore, we next focus on classical best-response dynamics, and show that, despite of the fact that they might not always converge, they are very effective in practice. In particular, we provide a strong empirical evidence that they outperform existing methods, since surprisingly they quickly converge to exact Nash equilibria in almost all instances arising in practice. This also shows that, while this class of games is known to not always possess pure Nash equilibria, in almost all cases such equilibria exist and can be efficiently computed, even in a distributed uncoordinated way by a decentralized interaction of the agents.
BibTeX - Entry
@InProceedings{dascenzo_et_al:LIPIcs.SEA.2022.20,
author = {D'Ascenzo, Andrea and D'Emidio, Mattia and Flammini, Michele and Monaco, Gianpiero},
title = {{Digraph k-Coloring Games: From Theory to Practice}},
booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)},
pages = {20:1--20:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-251-8},
ISSN = {1868-8969},
year = {2022},
volume = {233},
editor = {Schulz, Christian and U\c{c}ar, Bora},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16554},
URN = {urn:nbn:de:0030-drops-165540},
doi = {10.4230/LIPIcs.SEA.2022.20},
annote = {Keywords: Algorithmic Game Theory, Coloring Games, Experimental Algorithmics, Exact vs Approximate Nash Equilibria, Decentralized Dynamics}
}
