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

symposium articles: A differentiable homotopy to compute Nash equilibria of n -person games

Author

Listed:
  • P. Jean-Jacques Herings

    (Department of Economics, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, THE NETHERLANDS)

  • Ronald J.A.P. Peeters

    (Department of Economics, Universiteit Maastricht, P.O. Box 616, 6200 MD Maastricht, THE NETHERLANDS)

Abstract

The literature on the computation of Nash equilibria in n-person games is dominated by simplicial methods. This paper is the first to introduce a globally convergent algorithm that fully exploits the differentiability present in the problem. It presents an everywhere differentiable homotopy to do the computations. The homotopy path can therefore be followed by several numerical techniques. Moreover, instead of computing some Nash equilibrium, the algorithm is constructed in such a way that it computes the Nash equilibrium selected by the tracing procedure of Harsanyi and Selten. As a by-product of our proofs it follows that for a generic game the tracing procedure defines a unique feasible path. The numerical performance of the algorithm is illustrated by means of several examples.

Suggested Citation

  • P. Jean-Jacques Herings & Ronald J.A.P. Peeters, 2001. "symposium articles: A differentiable homotopy to compute Nash equilibria of n -person games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(1), pages 159-185.
    • Handle: RePEc:spr:joecth:v:18:y:2001:i:1:p:159-185
    Note: Received: December 21, 1999; revised version: December 27, 2000
    as

    Download full text from publisher

    File URL: http://link.springer.de/link/service/journals/00199/papers/1018001/10180159.pdf
    Download Restriction: Access to the full text of the articles in this series is restricted
    ---><---

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

    Citations

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


    Cited by:

    1. Bich, Philippe & Fixary, Julien, 2022. "Network formation and pairwise stability: A new oddness theorem," Journal of Mathematical Economics, Elsevier, vol. 103(C).
    2. Yiyin Cao & Yin Chen & Chuangyin Dang, 2024. "A Variant of the Logistic Quantal Response Equilibrium to Select a Perfect Equilibrium," Journal of Optimization Theory and Applications, Springer, vol. 201(3), pages 1026-1062, June.
    3. Peixuan Li & Chuangyin Dang & P. Jean-Jacques Herings, 2024. "Computing perfect stationary equilibria in stochastic games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 78(2), pages 347-387, September.
    4. Yang Zhan & Peixuan Li & Chuangyin Dang, 2020. "A differentiable path-following algorithm for computing perfect stationary points," Computational Optimization and Applications, Springer, vol. 76(2), pages 571-588, June.
    5. Jean-Jacques Herings, P., 2002. "Universally converging adjustment processes--a unifying approach," Journal of Mathematical Economics, Elsevier, vol. 38(3), pages 341-370, November.
    6. P. Herings & Ronald Peeters, 2005. "A Globally Convergent Algorithm to Compute All Nash Equilibria for n-Person Games," Annals of Operations Research, Springer, vol. 137(1), pages 349-368, July.
    7. Cao, Yiyin & Dang, Chuangyin & Xiao, Zhongdong, 2022. "A differentiable path-following method to compute subgame perfect equilibria in stationary strategies in robust stochastic games and its applications," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1032-1050.
    8. Chuangyin Dang & P. Jean-Jacques Herings & Peixuan Li, 2022. "An Interior-Point Differentiable Path-Following Method to Compute Stationary Equilibria in Stochastic Games," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1403-1418, May.
    9. Yiyin Cao & Yin Chen & Chuangyin Dang, 2024. "A Differentiable Path-Following Method with a Compact Formulation to Compute Proper Equilibria," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 377-396, March.
    10. Herings, P. Jean-Jacques, 2024. "Globally and universally convergent price adjustment processes," Journal of Mathematical Economics, Elsevier, vol. 113(C).
    11. Bich, Philippe & Fixary, Julien, 2024. "Oddness of the number of Nash equilibria: The case of polynomial payoff functions," Games and Economic Behavior, Elsevier, vol. 145(C), pages 510-525.
    12. Herings, P. Jean-Jacques & Zhan, Yang, 2021. "The computation of pairwise stable networks," Research Memorandum 004, Maastricht University, Graduate School of Business and Economics (GSBE).
    13. Dang, Chuangyin & Herings, P. Jean-Jacques & Li, Peixuan, 2020. "An Interior-Point Path-Following Method to Compute Stationary Equilibria in Stochastic Games," Research Memorandum 001, Maastricht University, Graduate School of Business and Economics (GSBE).
    14. Dang, Chuangyin & Meng, Xiaoxuan & Talman, Dolf, 2015. "An Interior-Point Path-Following Method for Computing a Perfect Stationary Point of a Polynomial Mapping on a Polytope," Discussion Paper 2015-019, Tilburg University, Center for Economic Research.
    15. Cao, Yiyin & Dang, Chuangyin, 2022. "A variant of Harsanyi's tracing procedures to select a perfect equilibrium in normal form games," Games and Economic Behavior, Elsevier, vol. 134(C), pages 127-150.

    More about this item

    Keywords

    Computation of equilibria - Noncooperative game theory - Tracing procedure.;

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games

    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:18:y:2001:i:1:p:159-185. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.