Computing better approximate pure Nash equilibria in cut games via semidefinite programming. (English) Zbl 07844625
Saha, Barna (ed.) et al., Proceedings of the 55th annual ACM SIGACT symposium on theory of computing, STOC ’23, Orlando, FL, USA, June 20–23, 2023. New York, NY: Association for Computing Machinery (ACM). 710-722 (2023).
MSC:
| 68Qxx | Theory of computing |
Keywords:
approximate pure Nash equilibrium; cut games; randomized rounding; semidefinite programmingReferences:
| [1] | Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. 2008. On the impact of combinatorial structure on congestion games. J. ACM, 55, 6 (2008), 25:1-25:22. https://doi.org/10.1145/1455248.1455249 10.1145/1455248.1455249 · Zbl 1325.91010 |
| [2] | Noga Alon and Assaf Naor. 2006. Approximating the Cut-Norm via Grothendieck’s Inequality. SIAM J. Comput., 35, 4 (2006), 787-803. https://doi.org/10.1137/S0097539704441629 10.1137/S0097539704441629 · Zbl 1096.68163 |
| [3] | Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. 2008. The Price of Stability for Network Design with Fair Cost Allocation. SIAM J. Comput., 38, 4 (2008), 1602-1623. https://doi.org/10.1137/070680096 10.1137/070680096 · Zbl 1173.91321 |
| [4] | Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, and Alexander Skopalik. 2008. Fast convergence to nearly optimal solutions in potential games. In Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008. ACM, 264-273. https://doi.org/10.1145/1386790.1386832 10.1145/1386790.1386832 |
| [5] | Maria-Florina Balcan, Avrim Blum, and Yishay Mansour. 2009. Improved equilibria via public service advertising. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009. SIAM, 728-737. https://dl.acm.org/doi/10.5555/1496770.1496850 · Zbl 1422.91047 |
| [6] | Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. 2009. Nash Dynamics in Congestion Games with Similar Resources. In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings (Lecture Notes in Computer Science, Vol. 5929). Springer, 362-373. https://doi.org/10.1007/978-3-642-10841-9_33 10.1007/978-3-642-10841-9_33 |
| [7] | Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. 2010. Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. In Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010. ACM, 73-82. https://doi.org/10.1145/1807342.1807353 10.1145/1807342.1807353 |
| [8] | Vittorio Bilò and Mauro Paladini. 2016. On the performance of mildly greedy players in cut games. J. Comb. Optim., 32, 4 (2016), 1036-1051. https://doi.org/10.1007/s10878-015-9898-2 10.1007/s10878-015-9898-2 · Zbl 1414.91070 |
| [9] | Ioannis Caragiannis and Angelo Fanelli. 2021. On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. J. Comput. Syst. Sci., 117 (2021), 40-48. https://doi.org/10.1016/j.jcss.2020.10.007 10.1016/j.jcss.2020.10.007 · Zbl 1480.91023 |
| [10] | Ioannis Caragiannis, Angelo Fanelli, and Nick Gravin. 2017. Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games. Algorithmica, 77, 4 (2017), 1143-1158. https://doi.org/10.1007/s00453-016-0143-x 10.1007/s00453-016-0143-x · Zbl 1409.91010 |
| [11] | Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. 2011. Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011. IEEE Computer Society, 532-541. https://doi.org/10.1109/FOCS.2011.50 10.1109/FOCS.2011.50 · Zbl 1292.91012 |
| [12] | Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. 2015. Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure. ACM Trans. Economics and Comput., 3, 1 (2015), 2:1-2:32. https://doi.org/10.1145/2614687 10.1145/2614687 · Zbl 1292.91012 |
| [13] | Moses Charikar and Anthony Wirth. 2004. Maximizing Quadratic Programs: Extending Grothendieck’s Inequality. In 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings. IEEE Computer Society, 54-60. https://doi.org/10.1109/FOCS.2004.39 10.1109/FOCS.2004.39 |
| [14] | Steve Chien and Alistair Sinclair. 2011. Convergence to approximate Nash equilibria in congestion games. Games Econ. Behav., 71, 2 (2011), 315-327. https://doi.org/10.1016/j.geb.2009.05.004 10.1016/j.geb.2009.05.004 · Zbl 1209.91020 |
| [15] | George Christodoulou, Vahab S. Mirrokni, and Anastasios Sidiropoulos. 2012. Convergence and approximation in potential games. Theor. Comput. Sci., 438 (2012), 13-27. https://doi.org/10.1016/j.tcs.2012.02.033 10.1016/j.tcs.2012.02.033 · Zbl 1251.91008 |
| [16] | Robert Elsässer and Tobias Tscheuschner. 2011. Settling the Complexity of Local Max-Cut (Almost) Completely. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 6755). Springer, 171-182. https://doi.org/10.1007/978-3-642-22006-7_15 10.1007/978-3-642-22006-7_15 · Zbl 1332.68072 |
| [17] | Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. 2004. The complexity of pure Nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. ACM, 604-612. https://doi.org/10.1145/1007352.1007445 10.1145/1007352.1007445 · Zbl 1192.91042 |
| [18] | Uriel Feige and Michel X. Goemans. 1995. Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. In Third Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings. IEEE Computer Society, 182-189. https://doi.org/10.1109/ISTCS.1995.377033 10.1109/ISTCS.1995.377033 |
| [19] | Matthias Feldotto, Martin Gairing, and Alexander Skopalik. 2014. Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria. In Web and Internet Economics - 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings (Lecture Notes in Computer Science, Vol. 8877). Springer, 30-43. https://doi.org/10.1007/978-3-319-13129-0_3 10.1007/978-3-319-13129-0_3 · Zbl 1404.91049 |
| [20] | Martin Gairing, Kostas Kollias, and Grammateia Kotsialou. 2020. Existence and Efficiency of Equilibria for Cost-Sharing in Generalized Weighted Congestion Games. ACM Trans. Economics and Comput., 8, 2 (2020), 11:1-11:28. https://doi.org/10.1145/3391434 10.1145/3391434 · Zbl 1447.91013 |
| [21] | Yiannis Giannakopoulos, Georgy Noarov, and Andreas S. Schulz. 2022. Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses. Math. Oper. Res., 47, 1 (2022), 643-664. https://doi.org/10.1287/moor.2021.1144 10.1287/moor.2021.1144 · Zbl 1489.91014 |
| [22] | Michel X. Goemans, Li (Erran) Li, Vahab S. Mirrokni, and Marina Thottan. 2006. Market sharing games applied to content distribution in ad hoc networks. IEEE J. Sel. Areas Commun., 24, 5 (2006), 1020-1033. https://doi.org/10.1109/JSAC.2006.872884 10.1109/JSAC.2006.872884 |
| [23] | Michel X. Goemans and David P. Williamson. 1995. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM, 42, 6 (1995), 1115-1145. https://doi.org/10.1145/227683.227684 10.1145/227683.227684 · Zbl 0885.68088 |
| [24] | David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. 1988. How Easy is Local Search? J. Comput. Syst. Sci., 37, 1 (1988), 79-100. https://doi.org/10.1016/0022-0000(88)90046-3 10.1016/0022-0000(88)90046-3 · Zbl 0655.68074 |
| [25] | Elias Koutsoupias and Christos H. Papadimitriou. 2009. Worst-case equilibria. Comput. Sci. Rev., 3, 2 (2009), 65-69. https://doi.org/10.1016/j.cosrev.2009.04.003 10.1016/j.cosrev.2009.04.003 · Zbl 1303.91012 |
| [26] | Michael Lewin, Dror Livnat, and Uri Zwick. 2002. Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings (Lecture Notes in Computer Science, Vol. 2337). Springer, 67-82. https://doi.org/10.1007/3-540-47867-1_6 10.1007/3-540-47867-1_6 · Zbl 1049.90535 |
| [27] | Dov Monderer and Lloyd S. Shapley. 1996. Potential Games. Games and Economic Behavior, 14, 1 (1996), 124-143. https://doi.org/10.1006/game.1996.0044 10.1006/game.1996.0044 · Zbl 0862.90137 |
| [28] | Noam Nisan and Amir Ronen. 2001. Algorithmic Mechanism Design. Games Econ. Behav., 35, 1-2 (2001), 166-196. https://doi.org/10.1006/game.1999.0790 10.1006/game.1999.0790 · Zbl 0996.68251 |
| [29] | James B. Orlin, Abraham P. Punnen, and Andreas S. Schulz. 2004. Approximate Local Search in Combinatorial Optimization. SIAM J. Comput., 33, 5 (2004), 1201-1214. https://doi.org/10.1137/S0097539703431007 10.1137/S0097539703431007 · Zbl 1101.68601 |
| [30] | Robert W. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2 (1973), 65-67. https://doi.org/10.1007/BF01737559 10.1007/BF01737559 · Zbl 0259.90059 |
| [31] | Tim Roughgarden and Éva Tardos. 2002. How bad is selfish routing? J. ACM, 49, 2 (2002), 236-259. https://doi.org/10.1145/506147.506153 10.1145/506147.506153 · Zbl 1323.90011 |
| [32] | Alejandro A. Schäffer and Mihalis Yannakakis. 1991. Simple Local Search Problems That are Hard to Solve. SIAM J. Comput., 20, 1 (1991), 56-87. https://doi.org/10.1137/0220004 10.1137/0220004 · Zbl 0716.68048 |
| [33] | Vipin Ravindran Vijayalakshmi and Alexander Skopalik. 2020. Improving Approximate Pure Nash Equilibria in Congestion Games. In Web and Internet Economics - 16th International Conference, WINE 2020, Beijing, China, December 7-11, 2020, Proceedings (Lecture Notes in Computer Science, Vol. 12495). Springer, 280-294. https://doi.org/10.1007/978-3-030-64946-3_20 10.1007/978-3-030-64946-3_20 · Zbl 1533.91031 |
| [34] | Uri Zwick. 2000. Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans. Manuscript. http://www.cs.tau.ac.il/ zwick/online-papers.html |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
