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. 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.
    3. 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.
    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. 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.
    7. van der Laan, G. & Talman, D., 1993. "Intersection Theorems on the Simplotope," Papers 9370, Tilburg - Center for Economic Research.
    8. 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.
    9. 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.
    10. 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.
    11. Liang Liang & Jie Wu & Wade D. Cook & Joe Zhu, 2008. "The DEA Game Cross-Efficiency Model and Its Nash Equilibrium," Operations Research, INFORMS, vol. 56(5), pages 1278-1288, October.
    12. 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.
    13. Wheatley, W. Parker, 2003. "Survival And Ownership Of Internet Marketplaces For Agriculture," 2003 Annual meeting, July 27-30, Montreal, Canada 22214, American Agricultural Economics Association (New Name 2008: Agricultural and Applied Economics Association).
    14. Stauber, Ronald, 2011. "Knightian games and robustness to ambiguity," Journal of Economic Theory, Elsevier, vol. 146(1), pages 248-274, January.
    15. Tim Roughgarden, 2018. "Complexity Theory, Game Theory, and Economics: The Barbados Lectures," Papers 1801.00734, arXiv.org, revised Feb 2020.
    16. Roy Allen & John Rehbeck, 2021. "A Generalization of Quantal Response Equilibrium via Perturbed Utility," Games, MDPI, vol. 12(1), pages 1-16, March.
    17. Keyzer, Michiel & van Wesenbeeck, Lia, 2005. "Equilibrium selection in games: the mollifier method," Journal of Mathematical Economics, Elsevier, vol. 41(3), pages 285-301, April.
    18. 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.
    19. 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.
    20. P. Baecker & G. Grass & U. Hommel, 2010. "Business value and risk in the presence of price controls: an option-based analysis of margin squeeze rules in the telecommunications industry," Annals of Operations Research, Springer, vol. 176(1), pages 311-332, April.

    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.