IDEAS home Printed from https://ideas.repec.org/a/spr/joecth/v42y2010i1p193-236.html
   My bibliography  Save this article

Computing equilibria: a computational complexity perspective

Author

Listed:
  • Tim Roughgarden

Abstract

No abstract is available for this item.

Suggested Citation

  • Tim Roughgarden, 2010. "Computing equilibria: a computational complexity perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 193-236, January.
    • Handle: RePEc:spr:joecth:v:42:y:2010:i:1:p:193-236
    DOI: 10.1007/s00199-009-0448-y
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s00199-009-0448-y
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s00199-009-0448-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Sergiu Hart, 2013. "Adaptive Heuristics," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 11, pages 253-287, World Scientific Publishing Co. Pte. Ltd..
    2. Judd, Kenneth L., 1997. "Computational economics and economic theory: Substitutes or complements?," Journal of Economic Dynamics and Control, Elsevier, vol. 21(6), pages 907-942, June.
    3. Aumann, Robert J., 1974. "Subjectivity and correlation in randomized strategies," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 67-96, March.
    4. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    5. Gilboa, Itzhak & Zemel, Eitan, 1989. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, Elsevier, vol. 1(1), pages 80-93, March.
    6. Francis Chu & Joseph Halpern, 2001. "On the NP-completeness of finding an optimal strategy in games with common payoffs," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(1), pages 99-106.
    7. H. M. Amman & D. A. Kendrick & J. Rust (ed.), 1996. "Handbook of Computational Economics," Handbook of Computational Economics, Elsevier, edition 1, volume 1, number 1.
    8. Michael J. Todd, 1976. "Orientation in Complementary Pivot Algorithms," Mathematics of Operations Research, INFORMS, vol. 1(1), pages 54-66, February.
    9. Bénédicte Vidaillet & V. d'Estaintot & P. Abécassis, 2005. "Introduction," Post-Print hal-00287137, HAL.
    10. Peter Cramton & Yoav Shoham & Richard Steinberg, 2004. "Combinatorial Auctions," Papers of Peter Cramton 04mit, University of Maryland, Department of Economics - Peter Cramton, revised 2004.
    11. Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    12. Ehud Kalai, 1987. "Bounded Rationality and Strategic Complexity in Repeated Games," Discussion Papers 783, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    13. Bona, Jerry L. & Santos, Manuel S., 1997. "On the Role of Computation in Economic Theory," Journal of Economic Theory, Elsevier, vol. 72(2), pages 241-281, February.
    14. Paul Milgrom, 2009. "Assignment Messages and Exchanges," American Economic Journal: Microeconomics, American Economic Association, vol. 1(2), pages 95-113, August.
    15. McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142, Elsevier.
    16. Xiaotie Deng & Christos H. Papadimitriou, 1994. "On the Complexity of Cooperative Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 257-266, May.
    17. Itzhak Gilboa & Ehud Kalai & Eitan Zemel, 1989. "The Complexity of Eliminating Dominated Strategies," Discussion Papers 853, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    18. Gilboa, Itzhak, 1988. "The complexity of computing best-response automata in repeated games," Journal of Economic Theory, Elsevier, vol. 45(2), pages 342-352, August.
    19. Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1.
    20. Koller, Daphne & Megiddo, Nimrod, 1992. "The complexity of two-person zero-sum games in extensive form," Games and Economic Behavior, Elsevier, vol. 4(4), pages 528-552, October.
    21. Babaioff, Moshe & Feldman, Michal & Nisan, Noam & Winter, Eyal, 2012. "Combinatorial agency," Journal of Economic Theory, Elsevier, vol. 147(3), pages 999-1034.
    22. Thomas Quint & Martin Shubik, 1994. "A Model of Migration," Cowles Foundation Discussion Papers 1088, Cowles Foundation for Research in Economics, Yale University.
    23. Juliane Dunkel & Andreas S. Schulz, 2008. "On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 851-868, November.
    24. Ehud Kalai & Eitan Zemel, 1982. "Totally Balanced Games and Games of Flow," Mathematics of Operations Research, INFORMS, vol. 7(3), pages 476-478, August.
    25. Abraham Neyman, 1998. "Finitely Repeated Games with Finite Automata," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 513-552, August.
    26. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
    27. Sandholm, William H., 2001. "Potential Games with Continuous Player Sets," Journal of Economic Theory, Elsevier, vol. 97(1), pages 81-108, March.
    28. Eaves, B. Curtis & Schmedders, Karl, 1999. "General equilibrium models and homotopy methods," Journal of Economic Dynamics and Control, Elsevier, vol. 23(9-10), pages 1249-1279, September.
    29. Foster, Dean P. & Vohra, Rakesh V., 1997. "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 40-55, October.
    30. Sergiu Hart & Yishay Mansour, 2006. "The Communication Complexity of Uncoupled Nash Equilibrium Procedures," Levine's Bibliography 122247000000001299, UCLA Department of Economics.
    31. Rahul Savani & Bernhard Stengel, 2006. "Hard-to-Solve Bimatrix Games," Econometrica, Econometric Society, vol. 74(2), pages 397-429, March.
    32. Patrick Bourke, 2006. "The RL2 chart versus the np chart for detecting upward shifts in fraction defective," Journal of Applied Statistics, Taylor & Francis Journals, vol. 33(1), pages 1-15.
    33. McLennan, Andrew & Tourky, Rabee, 2010. "Simple complexity from imitation games," Games and Economic Behavior, Elsevier, vol. 68(2), pages 683-688, March.
    34. Itzhak Gilboa & Ehud Kalai & Eitan Zemel, 1993. "The Complexity of Eliminating Dominated Strategies," Mathematics of Operations Research, INFORMS, vol. 18(3), pages 553-565, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kalandrakis, Tasos, 2015. "Computation of equilibrium values in the Baron and Ferejohn bargaining model," Games and Economic Behavior, Elsevier, vol. 94(C), pages 29-38.
    2. Halpern, Joseph Y. & Pass, Rafael & Seeman, Lior, 2019. "The truth behind the myth of the Folk theorem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 479-498.
    3. Bernhard Stengel, 2010. "Computation of Nash equilibria in finite games: introduction to the symposium," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 1-7, January.
    4. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    5. repec:dau:papers:123456789/882 is not listed on IDEAS
    6. Tim Roughgarden & Inbal Talgam-Cohen, 2018. "Approximately Optimal Mechanism Design," Papers 1812.11896, arXiv.org, revised Aug 2020.
    7. Tamás Fleiner & Zsuzsanna Jankó & Ildikó Schlotter & Alexander Teytelboym, 2023. "Complexity of stability in trading networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 629-648, September.
    8. Matthew J. Robbins & Sheldon H. Jacobson & Uday V. Shanbhag & Banafsheh Behzad, 2014. "The Weighted Set Covering Game: A Vaccine Pricing Model for Pediatric Immunization," INFORMS Journal on Computing, INFORMS, vol. 26(1), pages 183-198, February.
    9. Papadimitriou, Christos, 2015. "The Complexity of Computing Equilibria," Handbook of Game Theory with Economic Applications,, Elsevier.
    10. Aziz, Haris & Brandt, Felix & Harrenstein, Paul, 2013. "Pareto optimality in coalition formation," Games and Economic Behavior, Elsevier, vol. 82(C), pages 562-581.

    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. P. Herings & Ronald Peeters, 2010. "Homotopy methods to compute equilibria in game theory," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 42(1), pages 119-156, January.
    2. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    3. Conitzer, Vincent & Sandholm, Tuomas, 2008. "New complexity results about Nash equilibria," Games and Economic Behavior, Elsevier, vol. 63(2), pages 621-641, July.
    4. F. Forges & B. von Stengel, 2002. "Computionally Efficient Coordination in Games Trees," THEMA Working Papers 2002-05, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    5. Govindan, Srihari & Wilson, Robert, 2004. "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1229-1241, April.
    6. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    7. 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..
    8. Sergiu Hart & Yishay Mansour, 2006. "The Communication Complexity of Uncoupled Nash Equilibrium Procedures," Levine's Bibliography 122247000000001299, UCLA Department of Economics.
    9. Jugal Garg & Ruta Mehta & Vijay V. Vaziranic, 2018. "Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 996-1024, August.
    10. Etessami, Kousha, 2021. "The complexity of computing a (quasi-)perfect equilibrium for an n-player extensive form game," Games and Economic Behavior, Elsevier, vol. 125(C), pages 107-140.
    11. Bernhard von Stengel & Françoise Forges, 2008. "Extensive-Form Correlated Equilibrium: Definition and Computational Complexity," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 1002-1022, November.
    12. Sergiu Hart & Andreu Mas-Colell, 2013. "Stochastic Uncoupled Dynamics And Nash Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 8, pages 165-189, World Scientific Publishing Co. Pte. Ltd..
    13. Sacha Bourgeois-Gironde, 2017. "How regret moves individual and collective choices towards rationality," Chapters, in: Morris Altman (ed.), Handbook of Behavioural Economics and Smart Decision-Making, chapter 11, pages 188-204, Edward Elgar Publishing.
    14. Herings, P. J. J. & Polemarchakis, H., 2002. "Equilibrium and arbitrage in incomplete asset markets with fixed prices," Journal of Mathematical Economics, Elsevier, vol. 37(2), pages 133-155, April.
    15. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    16. Chiara Scarampi & Richard Fairchild & Luca Fumarco & Alberto Palermo & Neal Hinvest, 2021. "Social Metacognition: A Correlational Device for Strategic Interactions," Working Papers 2111, Tulane University, Department of Economics.
    17. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    18. Doraszelski, Ulrich & Kryukov, Yaroslav & Borkovsky, Ron N., 2008. "A User's Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," CEPR Discussion Papers 6733, C.E.P.R. Discussion Papers.
    19. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March.
    20. Michael Foley & Rory Smead & Patrick Forber & Christoph Riedl, 2021. "Avoiding the bullies: The resilience of cooperation among unequals," PLOS Computational Biology, Public Library of Science, vol. 17(4), pages 1-18, April.

    More about this item

    Keywords

    Equilibrium computation; Computational complexity; NP-completeness; PPAD-completeness; C61; C63; C68;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis
    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C68 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computable General Equilibrium Models

    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:spr:joecth:v:42:y:2010:i:1:p:193-236. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.