IDEAS home Printed from https://ideas.repec.org/p/sef/csefwp/502.html
   My bibliography  Save this paper

An Adjustment Process-based Algorithm with Error Bounds for Approximating a Nash Equilibrium

Author

Listed:

Abstract

Regarding the approximation of Nash equilibria in games where the players have a continuum of strategies, there exist various algorithms based on best response dynamics and on its relaxed variants: from one step to the next, a player's strategy is updated by using explicitly a best response to the strategies of the other players that come from the previous steps. These iterative schemes generate sequences of strategy profiles which are constructed by using continuous optimization techniques and they have been shown to converge in the following situations: in zero-sum games or, in non zero-sum ones, under contraction assumptions or under linearity of best response functions. In this paper, we propose an algorithm which guarantees the convergence to a Nash equilibrium in two-player non zero-sum games when the best response functions are not necessarily linear, both their compositions are not contractions and the strategy sets are Hilbert spaces. Firstly, we address the issue of uniqueness of the Nash equilibrium extending to a more general class the result obtained by Caruso, Ceparano, and Morgan [J. Math. Anal. Appl., 459 (2018), pp. 1208-1221] for weighted potential games. Then, we describe a theoretical approximation scheme based on a non-standard (non-convex) relaxation of best response iterations which converges to the unique Nash equilibrium of the game. Finally, we define a numerical approximation scheme relying on a derivative-free continuous optimization technique applied in a finite dimensional setting and we provide convergence results and error bounds.

Suggested Citation

  • Francesco Caruso & Maria Carmela Ceparano & Jacqueline Morgan, 2018. "An Adjustment Process-based Algorithm with Error Bounds for Approximating a Nash Equilibrium," CSEF Working Papers 502, Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy, revised 23 Mar 2020.
  • Handle: RePEc:sef:csefwp:502
    as

    Download full text from publisher

    File URL: http://www.csef.it/WP/wp502.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Simone Sagratella, 2017. "Algorithms for generalized potential games with mixed-integer variables," Computational Optimization and Applications, Springer, vol. 68(3), pages 689-717, December.
    2. Branzei, Rodica & Mallozzi, Lina & Tijs, Stef, 2003. "Supermodular games and potential games," Journal of Mathematical Economics, Elsevier, vol. 39(1-2), pages 39-49, February.
    3. Francesco Caruso & Maria Carmela Ceparano & Jacqueline Morgan, 2017. "Uniqueness of Nash Equilibrium in Continuous Weighted Potential Games," CSEF Working Papers 471, Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy, revised 18 Jun 2017.
    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. Christian Ewerhart, 2020. "Ordinal potentials in smooth games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(4), pages 1069-1100, November.
    2. Duersch, Peter & Oechssler, Jörg & Schipper, Burkhard C., 2012. "Unbeatable imitation," Games and Economic Behavior, Elsevier, vol. 76(1), pages 88-96.
    3. Peter Duersch & Jörg Oechssler & Burkhard Schipper, 2014. "When is tit-for-tat unbeatable?," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(1), pages 25-36, February.
    4. Francesco Caruso & Maria Carmela Ceparano & Jacqueline Morgan, 2019. "Subgame Perfect Nash Equilibrium: A Learning Approach via Costs to Move," Dynamic Games and Applications, Springer, vol. 9(2), pages 416-432, June.
    5. Stein, Oliver & Sudermann-Merx, Nathan, 2018. "The noncooperative transportation problem and linear generalized Nash games," European Journal of Operational Research, Elsevier, vol. 266(2), pages 543-553.
    6. Francesco Cesarone & Lorenzo Lampariello & Davide Merolla & Jacopo Maria Ricci & Simone Sagratella & Valerio Giuseppe Sasso, 2023. "A bilevel approach to ESG multi-portfolio selection," Computational Management Science, Springer, vol. 20(1), pages 1-23, December.
    7. 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.
    8. Rahman Khorramfar & Osman Ozaltin & Reha Uzsoy & Karl Kempf, 2024. "Coordinating Resource Allocation during Product Transitions Using a Multifollower Bilevel Programming Model," Papers 2401.17402, arXiv.org.
    9. Giancarlo Bigi & Lorenzo Lampariello & Simone Sagratella & Valerio Giuseppe Sasso, 2023. "Approximate variational inequalities and equilibria," Computational Management Science, Springer, vol. 20(1), pages 1-16, December.
    10. Peter Duersch & Jörg Oechssler & Burkhard Schipper, 2012. "Pure strategy equilibria in symmetric two-player zero-sum games," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(3), pages 553-564, August.
    11. Peter Duersch & Jörg Oechssler & Burkhard Schipper, 2014. "When is tit-for-tat unbeatable?," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(1), pages 25-36, February.
    12. Francesco Caruso & Maria Carmela Ceparano & Jacqueline Morgan, 2021. "A Local Variation Method for Bilevel Nash Equilibrium Problems," CSEF Working Papers 620, Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy.
    13. Lorenzo Lampariello & Christoph Neumann & Jacopo M. Ricci & Simone Sagratella & Oliver Stein, 2020. "An explicit Tikhonov algorithm for nested variational inequalities," Computational Optimization and Applications, Springer, vol. 77(2), pages 335-350, November.
    14. Lampariello, Lorenzo & Neumann, Christoph & Ricci, Jacopo M. & Sagratella, Simone & Stein, Oliver, 2021. "Equilibrium selection for multi-portfolio optimization," European Journal of Operational Research, Elsevier, vol. 295(1), pages 363-373.
    15. Francesco Caruso & Maria Carmela Ceparano & Jacqueline Morgan, 2020. "Best response algorithms in ratio-bounded games: convergence of affine relaxations to Nash equilibria," CSEF Working Papers 593, Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy.
    16. Burkhard Schipper & Peter Duersch & Joerg Oechssler, 2011. "Once Beaten, Never Again: Imitation in Two-Player Potential Games," Working Papers 26, University of California, Davis, Department of Economics.
    17. Lina Mallozzi, 2013. "An application of optimization theory to the study of equilibria for games: a survey," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(3), pages 523-539, September.
    18. Burkhard C. Schipper & Peter Duersch & Joerg Oechssler, 2010. "Pure Saddle Points and Symmetric Relative Payoff Games," Working Papers 301, University of California, Davis, Department of Economics.
    19. Ewerhart, Christian, 2017. "The lottery contest is a best-response potential game," Economics Letters, Elsevier, vol. 155(C), pages 168-171.
    20. Burkhard Schipper & Peter Duersch & Joerg Oechssler, 2011. "Once Beaten, Never Again: Imitation in Two-Player Potential Games," Working Papers 1112, University of California, Davis, Department of Economics.

    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:sef:csefwp:502. 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: Dr. Maria Carannante (email available below). General contact details of provider: https://edirc.repec.org/data/cssalit.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.