Document Open Access Logo

Digraph k-Coloring Games: From Theory to Practice

Authors Andrea D'Ascenzo , Mattia D'Emidio , Michele Flammini , Gianpiero Monaco

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.20.pdf
  • Filesize: 5.87 MB
  • 18 pages

Document Identifiers

Author Details

Andrea D'Ascenzo
  • Department of Computer Science, Information Engineering and Mathematics, University of L'Aquila, Italy
Mattia D'Emidio
  • Department of Computer Science, Information Engineering and Mathematics, University of L'Aquila, Italy
Michele Flammini
  • Gran Sasso Science Institute, L'Aquila, Italy
Gianpiero Monaco
  • Department of Computer Science, Information Engineering and Mathematics, University of L'Aquila, Italy

Cite AsGet BibTex

Andrea D'Ascenzo, Mattia D'Emidio, Michele Flammini, and Gianpiero Monaco. Digraph k-Coloring Games: From Theory to Practice. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SEA.2022.20

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
  • Theory of computation → Quality of equilibria
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Algorithmic Game Theory
  • Coloring Games
  • Experimental Algorithmics
  • Exact vs Approximate Nash Equilibria
  • Decentralized Dynamics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Eugenio Angriman, Alexander van der Grinten, Moritz von Looz, Henning Meyerhenke, Martin Nöllenburg, Maria Predari, and Charilaos Tzovas. Guidelines for experimental algorithmics: A case study in network analysis. Algorithms, 12(7):127, 2019. URL: https://doi.org/10.3390/a12070127.
  2. Elliot Anshelevich and Shreyas Sekar. Approximate equilibrium and incentivizing social coordination. In Proceedings of the 28th Conference on Artificial Intelligence (AAAI 2014), pages 508-514, 2014. Google Scholar
  3. Krzysztof R. Apt, Bart de Keijzer, Mona Rahn, Guido Schäfer, and Sunil Simon. Coordination games on graphs. Int. J. Game Theory, 46(3):851-877, 2017. URL: https://doi.org/10.1007/s00182-016-0560-8.
  4. Haris Aziz and Rahul Savani. Hedonic games. In Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, pages 356-376. Cambridge University Press, 2016. URL: https://doi.org/10.1017/CBO9781107446984.016.
  5. Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. In Proceedings of the 11th ACM Conference on Electronic Commerce (EC 2010), pages 73-82, 2010. Google Scholar
  6. Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. J. Artif. Intell. Res., 62:315-371, 2018. URL: https://doi.org/10.1613/jair.1.11211.
  7. Vittorio Bilò, Angelo Fanelli, Michele Flammini, and Luca Moscardelli. Graphical congestion games. Algorithmica, 61(2):274-297, 2011. Google Scholar
  8. Lawrence E. Blume. The statistical mechanics of best-response strategy revision. Games and Economic Behavior, 11(2):111-145, 1995. URL: https://doi.org/10.1006/game.1995.1046.
  9. Béla Bollobas. Random Graphs. Cambridge University Press, 2001. Google Scholar
  10. Michele Borassi and Emanuele Natale. Kadabra is an adaptive algorithm for betweenness via random approximation. ACM J. Exp. Algorithmics, 24, February 2019. URL: https://doi.org/10.1145/3284359.
  11. Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos H. Papadimitriou. Zero-sum polymatrix games: A generalization of minmax. MOR, 41(2):648-655, 2016. Google Scholar
  12. Ioannis Caragiannis, Angelo Fanelli, and Nick Gravin. Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games. In Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT 2014), pages 49-60, 2014. Google Scholar
  13. Raffaello Carosi, Simone Fioravanti, Luciano Gualà, and Gianpiero Monaco. Coalition resilient outcomes in max k-cut games. In Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2019), volume 11376 of Lecture Notes in Computer Science, pages 94-107. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-10801-4_9.
  14. Raffaello Carosi, Michele Flammini, and Gianpiero Monaco. Computing approximate pure nash equilibria in digraph k-coloring games. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2017), pages 911-919. ACM, 2017. Google Scholar
  15. Raffaello Carosi and Gianpiero Monaco. Generalized graph k-coloring games. Theory Comput. Syst., 64(6):1028-1041, 2020. URL: https://doi.org/10.1007/s00224-019-09961-9.
  16. Matthew Cary, Aparna Das, Benjamin Edelman, Ioannis Giotis, Kurtis Heimerl, Anna R. Karlin, Scott Duke Kominers, Claire Mathieu, and Michael Schwarz. Convergence of position auctions under myopic best-response dynamics. ACM Trans. Econ. Comput., 2(3), 2014. Google Scholar
  17. Annalisa D'Andrea, Mattia D'Emidio, Daniele Frigioni, Stefano Leucci, and Guido Proietti. Experimental evaluation of dynamic shortest path tree algorithms on homogeneous batches. In Joachim Gudmundsson and Jyrki Katajainen, editors, Proceedings of the 13th International Symposium on Experimental Algorithms (SEA 2014), volume 8504 of Lecture Notes in Computer Science, pages 283-294. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07959-2_24.
  18. Gianlorenzo D'Angelo, Mattia D'Emidio, and Daniele Frigioni. Distance queries in large-scale fully dynamic complex networks. In Veli Mäkinen, Simon J. Puglisi, and Leena Salmela, editors, Proceedings of the 27th International Workshop on Combinatorial Algorithms (IWOCA 2016), volume 9843 of Lecture Notes in Computer Science, pages 109-121. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-44543-4_9.
  19. Gianlorenzo D'Angelo, Mattia D'Emidio, and Daniele Frigioni. Fully dynamic 2-hop cover labeling. J. Exp. Algorithmics, 24(1):1.6:1-1.6:36, 2019. URL: https://doi.org/10.1145/3299901.
  20. Argyrios Deligkas, John Fearnley, and Rahul Savani. Tree polymatrix games are ppad-hard. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:14. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.38.
  21. Argyrios Deligkas, John Fearnley, Rahul Savani, and Paul Spirakis. Computing approximate nash equilibria in polymatrix games. Algorithmica, 77(2):487-514, 2017. URL: https://doi.org/10.1007/s00453-015-0078-7.
  22. Mattia D'Emidio. Faster algorithms for mining shortest-path distances from massive time-evolving graphs. Algorithms, 13(8):191, 2020. Google Scholar
  23. B. Curtis Eaves. Polymatrix games with joint constraints. SIAM Journal on Applied Mathematics, 24(3):418-423, 1973. Google Scholar
  24. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pages 604-612. ACM, 2004. Google Scholar
  25. Michal Feldman and Ophir Friedler. A unified framework for strong price of anarchy in clustering games. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), volume 9135 of Lecture Notes in Computer Science, pages 601-613. Springer, 2015. Google Scholar
  26. Moran Feldman, Liane Lewin-Eytan, and Joseph (Seffi) Naor. Hedonic clustering games. ACM Trans. Parallel Comput., 2(1), 2015. URL: https://doi.org/10.1145/2742345.
  27. Martin Gairing and Rahul Savani. Computing stable outcomes in hedonic games with voting-based deviations. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pages 559-566, 2011. Google Scholar
  28. Laurent Gourvès and Jérôme Monnot. The max k-cut game and its strong equilibria. In Proceedings of the 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), volume 6108 of Lecture Notes in Computer Science, pages 234-246. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-13562-0_22.
  29. Martin Hoefer. Cost sharing and clustering under distributed competition. PhD thesis, University of Konstanz, 2007. Google Scholar
  30. Joseph T. Howson. Equilibria of polymatrix games. Management Science, 18(5):312-318, 1972. Google Scholar
  31. Joseph T. Howson and Robert W. Rosenthal. Bayesian equilibria of finite two-person games with incomplete information. Management Science, 21(3):313-315, 1974. Google Scholar
  32. Michael J. Kearns, Michael L. Littman, and Satinder P. Singh. Graphical models for game theory. In Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence (UAI 2001), pages 253-260, 2001. Google Scholar
  33. Jeremy Kun, Brian Powers, and Lev Reyzin. Anti-coordination games and stable graph colorings. In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT 2013), pages 122-133, 2013. Google Scholar
  34. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
  35. Catherine C. McGeoch. A Guide to Experimental Algorithmics. Cambridge University Press, 2012. Google Scholar
  36. Douglas A. Miller and Steven W. Zucker. Copositive-plus lemke algorithm solves polymatrix games. Operations Research Letters, 10(5):285-290, 1991. URL: https://doi.org/10.1016/0167-6377(91)90015-H.
  37. Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019), pages 873-881. International Foundation for Autonomous Agents and Multiagent Systems, 2019. Google Scholar
  38. Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. Stable outcomes in modified fractional hedonic games. Auton. Agents Multi Agent Syst., 34(1):4, 2020. URL: https://doi.org/10.1007/s10458-019-09431-z.
  39. Dov Monderer and Lloyd S. Shapley. Potential games. Games and Economic Behavior, 14(1):124-143, 1996. Google Scholar
  40. Robin A. Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. J. ACM, 57(2), 2010. Google Scholar
  41. Panagiota N. Panagopoulou and Paul G. Spirakis. A game theoretic approach for efficient graph coloring. In Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008), pages 183-195, 2008. Google Scholar
  42. Dominik Peters and Edith Elkind. Simple causes of complexity in hedonic games. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 617-623, 2015. Google Scholar
  43. Svatopluk Poljak. Integer linear programs and local search for max-cut. SIAM J. Comput., 24(4):822-839, 1995. Google Scholar
  44. Mona Rahn and Guido Schäfer. Efficient equilibria in polymatrix coordination games. In Proceedings of 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), pages 529-541, 2015. Google Scholar
  45. Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In Proceedings of the 29th Conference on Artificial Intelligence (AAAI 2015), pages 4292-4293. AAAI Press, 2015. Google Scholar
  46. Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput., 20(1):56-87, 1991. Google Scholar
  47. Joel Spencer. Asymptotic lower bounds for ramsey functions. Discrete Mathematics, 20:69-76, 1977. URL: https://doi.org/10.1016/0012-365X(77)90044-9.
  48. Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508-530, 2016. URL: https://doi.org/10.1017/nws.2016.20.
  49. Brian Swenson, Ryan Murray, and Soummya Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 56(4):2734-2767, 2018. Google Scholar
  50. Brian Woodbury Swenson. Myopic Best-Response Learning in Large-Scale Games. PhD thesis, Carnegie Mellon University, 2017. URL: https://doi.org/10.1184/R1/6720788.v1.
  51. Elena B. Yanovskaya. Equilibrium points in polymatrix games. Lithuanian Mathematical Journal, 8(2):381-384, 1968. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact