IDEAS home Printed from https://ideas.repec.org/p/bie/wpaper/382.html
   My bibliography  Save this paper

A simplicial algorithm approach to Nash equilibria in concave games

Author

Listed:
  • Haake, Claus-Jochen

    (Center for Mathematical Economics, Bielefeld University)

  • Su, Francis Edward

    (Center for Mathematical Economics, Bielefeld University)

Abstract

In this paper we demonstrate a new method for computing approximate Nash equilibria in n-person games. Strategy spaces are assumed to be represented by simplices, while payoff functions are assumed to be concave. Our procedure relies on a simplicial algorithm that traces paths through the set of strategy profiles using a new variant of Sperner's Lemma for labelled triangulations of simplotopes, which we prove in this paper. Our algorithm uses a labelling derived from the satisficing function of Geanakoplos (2003) and can be used to compute approximate Nash equilibria for payoff functions that are not necessarily linear. Finally, in bimatrix games, we can compare our simplicial algorithm to the combinatorial algorithm proposed by Lemke & Howson (1964).

Suggested Citation

  • Haake, Claus-Jochen & Su, Francis Edward, 2011. "A simplicial algorithm approach to Nash equilibria in concave games," Center for Mathematical Economics Working Papers 382, Center for Mathematical Economics, Bielefeld University.
    • Handle: RePEc:bie:wpaper:382
    as

    Download full text from publisher

    File URL: https://pub.uni-bielefeld.de/download/2315652/2319825
    File Function: First Version, 2006
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Robert M. Freund, 1986. "Combinatorial Theorems on the Simplotope that Generalize Results on the Simplex and Cube," Mathematics of Operations Research, INFORMS, vol. 11(1), pages 169-179, February.
    2. Herings, P. Jean-Jacques & van den Elzen, Antoon, 2002. "Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games," Games and Economic Behavior, Elsevier, vol. 38(1), pages 89-117, January.
    3. G. van der Laan & A. J. J. Talman, 1982. "On the Computation of Fixed Points in the Product Space of Unit Simplices and an Application to Noncooperative N Person Games," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 1-13, February.
    4. Robert Becker & Subir Chakrabarti, 2005. "Satisficing behavior, Brouwer’s Fixed Point Theorem and Nash Equilibrium," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 26(1), pages 63-83, July.
    5. John Geanakoplos, 2003. "Nash and Walras equilibrium via Brouwer," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 21(2), pages 585-603, March.
    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. Talman, A.J.J., 1991. "Intersection theorems on the unit simplex and the simplotope," Other publications TiSEM 3d9e52e1-2498-49ac-928b-2, Tilburg University, School of Economics and Management.
    2. van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 2007. "Combinatorial Integer Labeling Thorems on Finite Sets with an Application to Discrete Systems of Nonlinear Equations," Other publications TiSEM 264c28a5-10b6-44e1-9694-4, Tilburg University, School of Economics and Management.
    3. Eaves, C. & van der Laan, G. & Talman, A.J.J. & Yang, Z.F., 1996. "Balanced Simplices on Polytopes," Other publications TiSEM 21c51445-984c-4466-9e6a-6, Tilburg University, School of Economics and Management.
    4. G. Laan & A. J. J. Talman & Z. Yang, 2010. "Combinatorial Integer Labeling Theorems on Finite Sets with Applications," Journal of Optimization Theory and Applications, Springer, vol. 144(2), pages 391-407, February.
    5. 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.
    6. Klaus Abbink & Jordi Brandts, 2002. "24," UFAE and IAE Working Papers 523.02, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
      • Jordi Brandts & Klaus Abbink, 2004. "24," Levine's Bibliography 122247000000000073, UCLA Department of Economics.
    7. Chu, Junfei & Hou, Tianteng & Li, Feng & Yuan, Zhe, 2024. "Dynamic bargaining game DEA carbon emissions abatement allocation and the Nash equilibrium," Energy Economics, Elsevier, vol. 134(C).
    8. P. J. J. Herings & A. J. J. Talman, 1998. "Intersection Theorems with a Continuum of Intersection Points," Journal of Optimization Theory and Applications, Springer, vol. 96(2), pages 311-335, February.
    9. Abbink, Klaus & Brandts, Jordi, 2008. "24. Pricing in Bertrand competition with increasing marginal costs," Games and Economic Behavior, Elsevier, vol. 63(1), pages 1-31, May.
    10. Stauber, Ronald, 2011. "Knightian games and robustness to ambiguity," Journal of Economic Theory, Elsevier, vol. 146(1), pages 248-274, January.
    11. Salvador Barberà & Geoffroy de Clippel & Alejandro Neme & Kareen Rozen, 2022. "Order-k rationality," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 73(4), pages 1135-1153, June.
      • Kareen Rozen & Alejandro Neme & Geoffroy De Clippel & Salvador BarberÃ, 2019. "Order-k Rationality," Working Papers 1130, Barcelona School of Economics.
      • Salvador Barberà & Geoffroy De Cleppel & Alejandro Neme & Kareen Rozeen, 2020. "Order-k Rationality," Working Papers 4, Red Nacional de Investigadores en Economía (RedNIE).
      • Salvador Barber‡ & Geoffroy de Clippel & Alejandro Neme & Kareen Rozen, 2020. "Order-k Rationality," Working Papers 2020-10, Brown University, Department of Economics.
    12. Chakrabarti, Subir K., 2014. "On the robustness of the competitive equilibrium: Utility-improvements and equilibrium points," Journal of Mathematical Economics, Elsevier, vol. 55(C), pages 36-47.
    13. P. J. J. Herings & G. A. Koshevoy & A. J. J. Talman & Z. Yang, 2004. "General Existence Theorem of Zero Points," Journal of Optimization Theory and Applications, Springer, vol. 120(2), pages 375-394, February.
    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. Kairui Zuo & Jiancheng Guan, 2017. "Measuring the R&D efficiency of regions by a parallel DEA game model," Scientometrics, Springer;Akadémiai Kiadó, vol. 112(1), pages 175-194, July.
    16. Yiyin Cao & Chuangyin Dang & Yabin Sun, 2022. "Complementarity Enhanced Nash’s Mappings and Differentiable Homotopy Methods to Select Perfect Equilibria," Journal of Optimization Theory and Applications, Springer, vol. 192(2), pages 533-563, February.
    17. Hofkes, M.W., 1988. "A simplicial algorithm to solve the nonlinear complementarity problem on Sn x Rm+," Serie Research Memoranda 0049, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    18. Alexis Toda, 2015. "Bayesian general equilibrium," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 58(2), pages 375-411, February.
    19. Galeazzo Impicciatore & Luca Panaccione & Francesco Ruscitti, 2012. "Walras’ theory of capital formation: an intertemporal equilibrium reformulation," Journal of Economics, Springer, vol. 106(2), pages 99-118, June.
    20. Herings, P. Jean-Jacques & Peeters, Ronald J. A. P., 2004. "Stationary equilibria in stochastic games: structure, selection, and computation," Journal of Economic Theory, Elsevier, vol. 118(1), pages 32-60, September.

    More about this item

    Keywords

    ;
    ;
    ;

    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:bie:wpaper:382. 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: Bettina Weingarten (email available below). General contact details of provider: https://edirc.repec.org/data/imbiede.html .

    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.