article

Lipschitz Games

Authors:

Eran ShmayaAuthors Info & Claims

Mathematics of Operations Research, Volume 38, Issue 2

Pages 350 - 357

https://doi.org/10.1287/moor.1120.0557

Published: 01 May 2013 Publication History

Abstract

The Lipschitz constant of a finite normal-form game is the maximal change in some player's payoff when a single opponent changes his strategy. We prove that games with small Lipschitz constant admit pure ε-equilibria, and pinpoint the maximal Lipschitz constant that is sufficient to imply existence of a pure ε-equilibrium as a function of the number of players in the game and the number of strategies of each player. Our proofs use the probabilistic method.

References

[1]

Al-Najjar, NI and Smorodinsky, R, "Pivotal players and the characterization of influence," J. Econom. Theory, v92, pp. 318-342, 2000.

[2]

Alon, N and Spencer, JH, The Probabilistic Method, John Wiley & Sons, Hoboken, NJ, 2008.

[3]

Carmona, G, "On the purification of Nash equilibria of large games," Econom. Lett., v85, pp. 215-219, 2004.

[4]

Carmona, G, "Purification of Bayesian-Nash equilibria in large games with compact type and action spaces," J. Math. Econom., v44, pp. 1302-1311, 2008.

[5]

Carmona, G and Podczeck, K, "On the existence of pure-strategy equilibria in large games," J. Econom. Theory, v144, pp. 1300-1319, 2009.

[6]

Carmona, G and Podczeck, K, "Ex-post stability of Bayes--Nash equilibria of large games," Games Econom. Behav., v74, pp. 418-430, 2012.

[7]

Cartwright, E and Wooders, M, "On equilibrium in pure strategies in games with many players," Internat. J. Game Theory, v38, pp. 137-153, 2009.

[8]

Daskalakis, C and Papadimitriou, C, "Computing equilibria in anonymous games," 48th Annual IEEE Sympos. Foundations Comput. Sci., IEEE Computer Society, Washington, DC, pp. 83-93, 2007.

Digital Library

[9]

Deb, J and Kalai, E, "Stability in large Bayesian games with heterogeneous players," 2010.

[10]

Gradwohl, R and Reingold, O, "Partial exposure in large games," Games Econom. Behav., v68, pp. 602-613, 2010.

[11]

Jackson, MO, Social and Economic Networks, Princeton University Press, Princeton, NJ, 2008.

Digital Library

[12]

Kalai, E, "Large robust games," Econometrica, v72, pp. 1631-1665, 2004.

[13]

Ledoux, M, The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, v89, American Mathematical Society, Providence, RI, 2001.

[14]

Milgrom, P and Roberts, J, "Rationalizability, learning, and equilibrium in games with strategic complementarities," Econometrica, v58, pp. 1255-1277, 1990.

[15]

Monderer, D and Shapley, LS, "Potential games," Games Econom. Behav., v14, pp. 124-143, 1996.

[16]

Rashid, S, "Equilibrium points of nonatomic games: Asymptotic results," Econom. Lett., v12, pp. 7-10, 1983.

[17]

Rosenthal, RW, "A class of games possessing pure-strategy Nash equilibria," Internat. J. Game Theory, v2, pp. 65-67, 1973.

Digital Library

[18]

Rubinstein, A, "Comments on the interpretation of game theory," Econometrica, v59, pp. 909-924, 1991.

[19]

Schmeidler, D, "Equilibrium points of nonatomic games," J. Statist. Phys., v7, pp. 295-300, 1973.

[20]

"Brouwer, Tarski and the existence of Nash equilibrium," 2010.

[21]

Zhou, L, "A simple proof of the Shapley-Folkman theorem," Econom. Theory, v3, pp. 371-372, 1993.

Cited By

Sharma DWooldridge MDy JNatarajan S(2024)No internal regret with non-convex loss functionsProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i13.29412(14919-14927)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i13.29412
Anagnostides ISandholm TOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On the interplay between social welfare and tractability of equilibriaProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668295(49927-49959)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668295
Goldberg PKatzman M(2023)PPAD-complete approximate pure Nash equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.114218980:COnline publication date: 20-Nov-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114218
Show More Cited By

Lipschitz Games

Recommendations

PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games
Algorithmic Game Theory
Abstract
Lipschitz games, in which there is a limit $λ$ (the Lipschitz value of the game) on how much a player’s payoffs may change when some other player deviates, were introduced about 10 years ago by Azrieli and Shmaya. They showed via the probabilistic ... $\sqrt{}$
PPAD-complete approximate pure Nash equilibria in Lipschitz games
Abstract
Lipschitz games, in which there is a limit λ (the Lipschitz value of the game) on how much a player's payoffs may change when some other player deviates, were introduced about 10 years ago by Azrieli and Shmaya. They showed via the probabilistic ...
Strategy purification and thresholding: effective non-equilibrium approaches for playing large games
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2

There has been significant recent interest in computing effective strategies for playing large imperfect-information games. Much prior work involves computing an approximate equilibrium strategy in a smaller abstract game, then playing this strategy in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematics of Operations Research

Mathematics of Operations Research Volume 38, Issue 2

05 2013

184 pages

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 May 2013

Received: 31 January 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sharma DWooldridge MDy JNatarajan S(2024)No internal regret with non-convex loss functionsProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i13.29412(14919-14927)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i13.29412
Anagnostides ISandholm TOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On the interplay between social welfare and tractability of equilibriaProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668295(49927-49959)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668295
Goldberg PKatzman M(2023)PPAD-complete approximate pure Nash equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.114218980:COnline publication date: 20-Nov-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.114218
Goldberg PKatzman M(2023)Lower bounds for the query complexity of equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.113931962:COnline publication date: 22-Jun-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113931
Peretz RSchreiber ASchulte-Geers E(2022)The Lipschitz constant of perturbed anonymous gamesInternational Journal of Game Theory10.1007/s00182-021-00793-x51:2(293-306)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s00182-021-00793-x
Rachmilevitch S(2022)Symmetry and approximate equilibria in games with countably many playersInternational Journal of Game Theory10.1007/s00182-015-0479-545:3(709-717)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s00182-015-0479-5
Goldberg PKatzman M(2022)PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz GamesAlgorithmic Game Theory10.1007/978-3-031-15714-1_10(169-186)Online publication date: 12-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-15714-1_10
Goldberg PKatzman M(2021)Lower Bounds for the Query Complexity of Equilibria in Lipschitz GamesAlgorithmic Game Theory10.1007/978-3-030-85947-3_9(124-139)Online publication date: 21-Sep-2021
https://dl.acm.org/doi/10.1007/978-3-030-85947-3_9
Garg VJaakkola TDaumé HSingh A(2020)Predicting deliberative outcomesProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525257(3408-3418)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525257
Babichenko Y(2020)Informational bounds on equilibria (a survey)ACM SIGecom Exchanges10.1145/3381329.338133317:2(25-45)Online publication date: 28-Jan-2020
https://dl.acm.org/doi/10.1145/3381329.3381333
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents