IDEAS home Printed from https://ideas.repec.org/p/hal/wpaper/hal-04993589.html
   My bibliography  Save this paper

Nash equilibria are extremely unstable in most games under the utility-taking gradient dynamics

Author

Listed:
  • Aviad Heifetz

    (Open University of Israël)

  • Jorge Peña

    (TSE-R - Toulouse School of Economics - UT Capitole - Université Toulouse Capitole - UT - Université de Toulouse - EHESS - École des hautes études en sciences sociales - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement)

Abstract

In the standard continuous-time choice-taking gradient dynamics in smooth two-player games, each player implicitly assumes that their opponent momentarily main-tains their last choice. Contrastingly, in the utility-taking gradient dynamics each player implicitly assumes that their opponent momentarily maintains their utility level, by marginally adjusting their choice to that effect. Somewhat surprisingly, employing a transversality argument we find that, in an open and dense set of smooth games, this dynamics is undefined at Nash equilibria. This occurs because, at a Nash equilibrium, the opponent's indifference curve is not locally a function of one's own strategy, mak-ing it impossible to specify an opponent's adjustment that would maintain their utility in response to one's own marginal deviation from Nash behavior. Furthermore, when approaching a Nash equilibrium of such a generic game, the utility-taking gradient dy-namics either accelerates without bound towards the equilibrium or diverges away from it with unbounded speed.

Suggested Citation

  • Aviad Heifetz & Jorge Peña, 2025. "Nash equilibria are extremely unstable in most games under the utility-taking gradient dynamics," Working Papers hal-04993589, HAL.
  • Handle: RePEc:hal:wpaper:hal-04993589
    Note: View the original document on HAL open archive server: https://hal.science/hal-04993589v1
    as

    Download full text from publisher

    File URL: https://hal.science/hal-04993589v1/document
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Colin Camerer & Linda Babcock & George Loewenstein & Richard Thaler, 1997. "Labor Supply of New York City Cabdrivers: One Day at a Time," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 112(2), pages 407-441.
    2. Vincent P. Crawford & Juanjuan Meng, 2011. "New York City Cab Drivers' Labor Supply Revisited: Reference-Dependent Preferences with Rational-Expectations Targets for Hours and Income," American Economic Review, American Economic Association, vol. 101(5), pages 1912-1932, August.
    3. Young, H. Peyton, 2004. "Strategic Learning and its Limits," OUP Catalogue, Oxford University Press, number 9780199269181, Decembrie.
    4. Kalai, Ehud & Lehrer, Ehud, 1993. "Rational Learning Leads to Nash Equilibrium," Econometrica, Econometric Society, vol. 61(5), pages 1019-1045, September.
    5. Lambertini,Luca, 2018. "Differential Games in Industrial Economics," Cambridge Books, Cambridge University Press, number 9781107164680, January.
    6. Sergiu Hart & Andreu Mas-Colell, 2013. "Simple Adaptive Strategies:From Regret-Matching to Uncoupled Dynamics," World Scientific Books, World Scientific Publishing Co. Pte. Ltd., number 8408, March.
    7. Rashida Hakim & Jason Milionis & Christos Papadimitriou & Georgios Piliouras, 2024. "Swim till You Sink: Computing the Limit of a Game," Papers 2408.11146, arXiv.org.
    8. Drew Fudenberg & David K. Levine, 1998. "The Theory of Learning in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262061945, December.
    9. Sergiu Hart & Andreu Mas-Colell, 2013. "Uncoupled Dynamics Do Not Lead To Nash Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 7, pages 153-163, World Scientific Publishing Co. Pte. Ltd..
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sergiu Hart & Yishay Mansour, 2013. "How Long To Equilibrium? The Communication Complexity Of Uncoupled Equilibrium Procedures," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 10, pages 215-249, World Scientific Publishing Co. Pte. Ltd..
    2. Burkhard C. Schipper, 2022. "Strategic Teaching and Learning in Games," American Economic Journal: Microeconomics, American Economic Association, vol. 14(3), pages 321-352, August.
    3. Babichenko, Yakov & Rubinstein, Aviad, 2022. "Communication complexity of approximate Nash equilibria," Games and Economic Behavior, Elsevier, vol. 134(C), pages 376-398.
    4. Germano, Fabrizio & Lugosi, Gabor, 2007. "Global Nash convergence of Foster and Young's regret testing," Games and Economic Behavior, Elsevier, vol. 60(1), pages 135-154, July.
    5. Dean P Foster & Peyton Young, 2006. "Regret Testing Leads to Nash Equilibrium," Levine's Working Paper Archive 784828000000000676, David K. Levine.
    6. Burkhard Schipper, 2015. "Strategic teaching and learning in games," Working Papers 151, University of California, Davis, Department of Economics.
    7. Vivaldo M. Mendes & Diana A. Mendes & Orlando Gomes, 2008. "Learning to Play Nash in Deterministic Uncoupled Dynamics," Working Papers Series 1 ercwp1808, ISCTE-IUL, Business Research Unit (BRU-IUL).
    8. Jindani, Sam, 2022. "Learning efficient equilibria in repeated games," Journal of Economic Theory, Elsevier, vol. 205(C).
    9. Philippe Jehiel, 2022. "Analogy-Based Expectation Equilibrium and Related Concepts:Theory, Applications, and Beyond," PSE Working Papers halshs-03735680, HAL.
    10. Saran, R.R.S. & Serrano, R., 2010. "Ex-Post regret learning in games with fixed and random matching: the case of private values," Research Memorandum 032, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    11. Jacques Durieu & Philippe Solal, 2012. "Models of Adaptive Learning in Game Theory," Chapters, in: Richard Arena & Agnès Festré & Nathalie Lazaric (ed.), Handbook of Knowledge and Economics, chapter 11, Edward Elgar Publishing.
    12. Chernov, G. & Susin, I., 2019. "Models of learning in games: An overview," Journal of the New Economic Association, New Economic Association, vol. 44(4), pages 77-125.
    13. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Oct 2024.
    14. Saran, Rene & Serrano, Roberto, 2014. "Ex-post regret heuristics under private values (I): Fixed and random matching," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 97-111.
    15. J. Jordan, 2009. "Communication complexity and stability of equilibria in economies and games," Review of Economic Design, Springer;Society for Economic Design, vol. 13(1), pages 115-135, April.
    16. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    17. A. Banerji & Neha Gupta, 2011. "Do Auction Bids Betray Expectations-Based Reference Dependent Preferences? A Test, Experimental Evidence, And Estimates Of Loss Aversion," Working papers 206, Centre for Development Economics, Delhi School of Economics.
    18. Tsakas, Elias & Voorneveld, Mark, 2009. "The target projection dynamic," Games and Economic Behavior, Elsevier, vol. 67(2), pages 708-719, November.
    19. Berger, Thor & Chen, Chinchih & Frey, Carl Benedikt, 2018. "Drivers of disruption? Estimating the Uber effect," European Economic Review, Elsevier, vol. 110(C), pages 197-210.
    20. Yoo, Seung Han, 2014. "Learning a population distribution," Journal of Economic Dynamics and Control, Elsevier, vol. 48(C), pages 188-201.

    More about this item

    Keywords

    Gradient dynamics;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:wpaper:hal-04993589. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.