IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v186y2020i3d10.1007_s10957-020-01729-3.html
   My bibliography  Save this article

Finding the Strong Nash Equilibrium: Computation, Existence and Characterization for Markov Games

Author

Listed:
  • Julio B. Clempner

    (National Polytechnic Institute)

  • Alexander S. Poznyak

    (Center for Research and Advanced Studies)

Abstract

This paper suggests a procedure to construct the Pareto frontier and efficiently computes the strong Nash equilibrium for a class of time-discrete ergodic controllable Markov chain games. The procedure finds the strong Nash equilibrium, using the Newton optimization method presenting a potential advantage for ill-conditioned problems. We formulate the solution of the problem based on the Lagrange principle, adding a Tikhonov’s regularization parameter for ensuring both the strict convexity of the Pareto frontier and the existence of a unique strong Nash equilibrium. Then, any welfare optimum arises as a strong Nash equilibrium of the game. We prove the existence and characterization of the strong Nash equilibrium, which is one of the main results of this paper. The method is validated theoretically and illustrated with an application example.

Suggested Citation

  • Julio B. Clempner & Alexander S. Poznyak, 2020. "Finding the Strong Nash Equilibrium: Computation, Existence and Characterization for Markov Games," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 1029-1052, September.
    • Handle: RePEc:spr:joptap:v:186:y:2020:i:3:d:10.1007_s10957-020-01729-3
    DOI: 10.1007/s10957-020-01729-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-020-01729-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10957-020-01729-3?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. Guesnerie, Roger & Oddou, Claude, 1981. "Second best taxation as a game," Journal of Economic Theory, Elsevier, vol. 25(1), pages 67-91, August.
    2. Demange, Gabrielle, 1994. "Intermediate preferences and stable coalition structures," Journal of Mathematical Economics, Elsevier, vol. 23(1), pages 45-58, January.
    3. Clempner, Julio B. & Poznyak, Alexander S., 2016. "Solving the Pareto front for multiobjective Markov chains using the minimum Euclidean distance gradient-based optimization method," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 119(C), pages 142-160.
    4. Greenberg Joseph & Weber Shlomo, 1993. "Stable Coalition Structures with a Unidimensional Set of Alternatives," Journal of Economic Theory, Elsevier, vol. 60(1), pages 62-82, June.
    5. Konishi, Hideo & Le Breton, Michel & Weber, Shlomo, 1997. "Equilibria in a Model with Partial Rivalry," Journal of Economic Theory, Elsevier, vol. 72(1), pages 225-237, January.
    6. Ichiishi, Tatsuro, 1981. "A Social Coalitional Equilibrium Existence Lemma," Econometrica, Econometric Society, vol. 49(2), pages 369-377, March.
    7. Clempner, Julio B. & Poznyak, Alexander S., 2015. "Computing the strong Nash equilibrium for Markov chains games," Applied Mathematics and Computation, Elsevier, vol. 265(C), pages 911-927.
    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. Julio B. Clempner, 2021. "A Proximal/Gradient Approach for Computing the Nash Equilibrium in Controllable Markov Games," Journal of Optimization Theory and Applications, Springer, vol. 188(3), pages 847-862, March.
    2. Julio B. Clempner, 2023. "A Dynamic Mechanism Design for Controllable and Ergodic Markov Games," Computational Economics, Springer;Society for Computational Economics, vol. 61(3), pages 1151-1171, March.
    3. Julio B. Clempner & Alexander S. Poznyak, 2021. "Analytical Method for Mechanism Design in Partially Observable Markov Games," Mathematics, MDPI, vol. 9(4), pages 1-15, February.

    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. Barbera, Salvador & Gerber, Anke, 2003. "On coalition formation: durable coalition structures," Mathematical Social Sciences, Elsevier, vol. 45(2), pages 185-203, April.
    2. Fan‐Chin Kung, 2006. "An Algorithm for Stable and Equitable Coalition Structures with Public Goods," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 8(3), pages 345-355, August.
    3. Fan-chin Kung, 2005. "Formation of Collective Decision-Making Units: Stability and a Solution," Game Theory and Information 0505002, University Library of Munich, Germany, revised 21 Jun 2005.
    4. Tayfun Sönmez & Suryapratim Banerjee & Hideo Konishi, 2001. "Core in a simple coalition formation game," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(1), pages 135-153.
    5. Fan-chin Kung, 2013. "Public Good Coalitions and Membership Exclusion," Economics Bulletin, AccessEcon, vol. 33(2), pages 1390-1395.
    6. Konishi, Hideo & Le Breton, Michel & Weber, Shlomo, 1997. "Pure Strategy Nash Equilibrium in a Group Formation Game with Positive Externalities," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 161-182, October.
    7. Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February.
    8. Gabrielle Demange, 2017. "The stability of group formation," Revue d'économie politique, Dalloz, vol. 127(4), pages 495-516.
    9. Fan-Chin Kung, 2010. "Coalition formation with local public goods and group-size effect," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(4), pages 573-583, October.
    10. Popp, Alexandru W. A., 2009. "Efficient coalition formation and stable coalition structures in a supply chain environment," MPRA Paper 18277, University Library of Munich, Germany.
    11. Antoni Rubi-Barcelo, 2013. "Categorical Segregation from a Game Theoretical Approach," Annals of Economics and Finance, Society for AEF, vol. 14(1), pages 85-120, May.
    12. Le Breton, Michel & Weber, Shlomo, 2004. "Group Formation with Heterogeneous Sets," IDEI Working Papers 288, Institut d'Économie Industrielle (IDEI), Toulouse.
    13. Arnold, Tone & Wooders, Myrna, 2002. "Dynamic Club Formation with Coordination," Economic Research Papers 269414, University of Warwick - Department of Economics.
    14. Alison Watts, 2007. "Formation of segregated and integrated groups," International Journal of Game Theory, Springer;Game Theory Society, vol. 35(4), pages 505-519, April.
    15. Allouch, Nizar & Conley, John P. & Wooders, Myrna, 2009. "Anonymous price taking equilibrium in Tiebout economies with a continuum of agents: Existence and characterization," Journal of Mathematical Economics, Elsevier, vol. 45(9-10), pages 492-510, September.
    16. Matthias Dahm, 2010. "Free mobility and taste-homogeneity of jurisdiction structures," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 259-272, March.
    17. Effrosyni Diamantoudi & Licun Xue, 2003. "Farsighted stability in hedonic games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 21(1), pages 39-61, August.
    18. Anna Bogomolnaia & Michel Le Breton & Alexei Savvateev & Shlomo Weber, 2008. "Heterogeneity Gap in Stable Jurisdiction Structures," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 10(3), pages 455-473, June.
    19. Watts, Alison, 2006. "Formation of Segregated and Integrated Groups," Coalition Theory Network Working Papers 12171, Fondazione Eni Enrico Mattei (FEEM).
    20. Brams, S.J. & Jones, M.A. & Kilgour, D.M., 1999. "The Paradox of Disconnected Coalitions," Working Papers 99-19, C.V. Starr Center for Applied Economics, New York University.

    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:joptap:v:186:y:2020:i:3:d:10.1007_s10957-020-01729-3. 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.