Document Open Access Logo

Smoothed Efficient Algorithms and Reductions for Network Coordination Games

Authors Shant Boodaghians, Rucha Kulkarni, Ruta Mehta

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.73.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • Network Coordination Games
  • Smoothed Analysis

Metrics

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

Abstract

We study the smoothed complexity of finding pure Nash equilibria in Network Coordination Games, a PLS-complete problem in the worst case, even when each player has two strategies. This is a potential game where the sequential-better-response algorithm is known to converge to a pure NE, albeit in exponential time. First, we prove polynomial (respectively, quasi-polynomial) smoothed complexity when the underlying game graph is complete (resp. arbitrary), and every player has constantly many strategies. The complete graph assumption is reminiscent of perturbing all parameters, a common assumption in most known polynomial smoothed complexity results. We develop techniques to bound the probability that an (adversarial) better-response sequence makes slow improvements to the potential. Our approach combines and generalizes the local-max-cut approaches of Etscheid and Röglin (SODA `14; ACM TALG, `17) and Angel, Bubeck, Peres, and Wei (STOC `17), to handle the multi-strategy case. We believe that the approach and notions developed herein could be of interest in addressing the smoothed complexity of other potential games. 
Further, we define a notion of a smoothness-preserving reduction among search problems, and obtain reductions from 2-strategy network coordination games to local-max-cut, and from k-strategy games (k arbitrary) to local-max-bisection. The former, with the recent result of Bibak, Chandrasekaran, and Carlson (SODA `18) gives an alternate O(n^8)-time smoothed algorithm when k=2. These reductions extend smoothed efficient algorithms from one problem to another.

Cite As Get BibTex

Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Smoothed Efficient Algorithms and Reductions for Network Coordination Games. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.73

Author Details

Shant Boodaghians
  • University of Illinois at Urbana-Champaign, Urbana, IL, USA
Rucha Kulkarni
  • University of Illinois at Urbana-Champaign, Urbana, IL, USA
Ruta Mehta
  • University of Illinois at Urbana-Champaign, Urbana, IL, USA

Funding

All three authors acknowledge support from NSF grant CCF 1750436.

Acknowledgements

We would like to thank Pravesh Kothari for the insightful discussions in the initial stages of this work.

References

  1. Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei. Local max-cut in smoothed polynomial time. In ACM Symposium on Theory of Computing, pages 429-437, 2017. Google Scholar
  2. Elliot Anshelevich, Anirban Dasgupta, Eva Tardos, and Tom Wexler. Near-optimal network design with selfish agents. In ACM Symposium on Theory of Computing, pages 511-520, 2003. Google Scholar
  3. Radhika Arava. Social Network Analysis Using Coordination Games. arXiv preprint, 2017. URL: http://arxiv.org/abs/1708.09570.
  4. D. Arthur and S. Vassilvitskii. Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method. SIAM J. on Computing, 39(2):766-782, 2009. Google Scholar
  5. Imre Bárány, Santosh Vempala, and Adrian Vetta. Nash equilibria in random games. Random Struct. Algorithms, 31(4):391-405, December 2007. Google Scholar
  6. Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The Relative Complexity of NP Search Problems. J. Comput. Sys. Sci., 57(1):3-19, 1998. Google Scholar
  7. Rene Beier and Berthold Vöcking. Random Knapsack in Expected Polynomial Time. J. Comput. Syst. Sci., 69(3):306-329, November 2004. Google Scholar
  8. Ali Bibak, Charles Carlson, and Karthekeyan Chandrasekaran. Improving the smoothed complexity of FLIP for max cut problems. In ACM-SIAM SODA, pages 897-916, 2019. Google Scholar
  9. N. Bitansky, O. Paneth, and A. Rosen. On the Cryptographic Hardness of Finding a Nash Equilibrium. In IEEE FOCS, pages 1480-1498, 2015. Google Scholar
  10. Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta. Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.02280.
  11. Joris Broere, Vincent Buskens, Jeroen Weesie, and Henk Stoof. Network effects on coordination in asymmetric games. Scientific reports, 7(1):17016, 2017. Google Scholar
  12. Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. In ACM-SIAM Symposium on Discrete Algorithms, pages 217-234, 2011. Google Scholar
  13. X. Chen, X. Deng, and S.-H. Teng. Computing Nash Equilibria: Approximation and Smoothed Complexity. In IEEE Symposium on Foundations of Computer Science, pages 603-612, 2006. Google Scholar
  14. Syngjoo Choi, Douglas Gale, Shachar Kariv, and Thomas Palfrey. Network architecture, salience and coordination. Games and Economic Behavior, 73(1):76-90, 2011. Google Scholar
  15. Bruno Codenotti, Stefano De Rossi, and Marino Pagan. An Experimental Analysis of Lemke-Howson Algorithm. arXiv preprint, 2008. URL: http://arxiv.org/abs/0811.3247.
  16. Valentina Damerow, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, and Christian Sohler. Smoothed Motion Complexity. In Algorithms - ESA, pages 161-171, 2003. Google Scholar
  17. C. Daskalakis, P. Goldberg, and C. Papadimitriou. The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39(1):195-259, 2009. URL: https://doi.org/10.1137/070699652.
  18. Argyrios Deligkas, John Fearnley, Tobenna Peter Igwe, and Rahul Savani. An Empirical Study on Computing Equilibria in Polymatrix Games. In AAMAS, pages 186-195, 2016. Google Scholar
  19. Stéphane Durand and Bruno Gaujal. Complexity and Optimality of the Best Response Algorithm in Random Potential Games. In Algorithmic Game Theory, pages 40-51, 2016. Google Scholar
  20. Glenn Ellison. Learning, local interaction, and coordination. Econometrica: Journal of the Econometric Society, pages 1047-1071, 1993. Google Scholar
  21. Matthias Englert, Heiko Röglin, and Berthold Vöcking. Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP. Algorithmica, 68(1):190-264, 2014. Google Scholar
  22. Michael Etscheid and Heiko Röglin. Smoothed analysis of local search for the maximum-cut problem. ACM Transactions on Algorithms (TALG), 13(2):25, 2017. Google Scholar
  23. Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar. The Complexity of Pure Nash Equilibria. In ACM Symposium on Theory of Computing, pages 604-612, 2004. Google Scholar
  24. Michal Feldman and Tami Tamir. Conflicting congestion effects in resource allocation games. Operations research, 60(3):529-540, 2012. Google Scholar
  25. Tobias Harks, Martin Hoefer, Max Klimm, and Alexander Skopalik. Computing pure Nash and strong equilibria in bottleneck congestion games. Math. Prog., 141(1):193-215, 2013. Google Scholar
  26. Ramesh Johari and John N Tsitsiklis. Efficiency loss in a network resource allocation game. Mathematics of Operations Research, 29(3):407-435, 2004. Google Scholar
  27. David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? Journal of Computer and System Sciences, 37(1):79-100, 1988. Google Scholar
  28. David Karger and Krzysztof Onak. Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. In ACM-SIAM Symposium on Discrete Algorithms, volume 7, pages 1207-1216, 2007. Google Scholar
  29. Dharshana Kasthurirathna, Mahendra Piraveenan, and Michael Harré. Influence of topology in the evolution of coordination in complex networks under information diffusion constraints. The European Physical Journal B, 87(1):3, 2014. Google Scholar
  30. Bodo Manthey and Rüdiger Reischuk. Smoothed Analysis of Binary Search Trees. In Algorithms and Computation, pages 483-492, 2005. Google Scholar
  31. Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-143, 1996. Google Scholar
  32. Andrea Montanari and Amin Saberi. The spread of innovations in social networks. National Academy of Sciences, 107(47):20196-20201, 2010. Google Scholar
  33. Heiko Röglin. The Complexity of Nash Equilibria, Local Optima, and Pareto-Optimal Solutions. Fakultät für Math., Informatik und Naturw. der RWTH, 2008. Google Scholar
  34. Heiko Röglin and Berthold Vöcking. Smoothed analysis of integer programming. Mathematical Programming, 110(1):21-56, June 2007. Google Scholar
  35. Robert W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International J. of Game Theory, 2(1):65-67, 1973. Google Scholar
  36. T. Roughgarden and É. Tardos. How Bad is Selfish Routing? J. ACM, 49(2):236-259, 2002. Google Scholar
  37. Tim Roughgarden. Routing Games, 2007. Google Scholar
  38. Aviad Rubinstein. Settling the Complexity of Computing Approximate Two-player Nash Equilibria. SIGecom Exch., 15(2):45-49, February 2017. Google Scholar
  39. Rahul Savani and Bernhard von Stengel. Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. In IEEE FOCS, pages 258-267, 2004. Google Scholar
  40. Alejandro A. Schäffer and Mihalis Yannakakis. Simple Local Search Problems That Are Hard to Solve. SIAM J. Comput., 20(1):56-87, February 1991. Google Scholar
  41. Daniel A. Spielman and Shang-Hua Teng. Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. J. ACM, 51(3):385-463, May 2004. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact