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

Francesco Caruso (), Maria Carmela Ceparano and Jacqueline Morgan
Additional contact information
Francesco Caruso: Università di Napoli Federico II

CSEF Working Papers from Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy

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.

Keywords: zero-sum game; saddle point; non-cooperative non zero-sum game; Nash equilibrium; uniqueness; theoretical and numerical approximation; fixed point; super monotone operator; best response algorithm; convex and non-convex relaxation; local variation method; error bound. (search for similar items in EconPapers)
Date: 2018-06-25, Revised 2020-03-23
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.csef.it/WP/wp502.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sef:csefwp:502

Access Statistics for this paper

More papers in CSEF Working Papers from Centre for Studies in Economics and Finance (CSEF), University of Naples, Italy Contact information at EDIRC.
Bibliographic data for series maintained by Dr. Maria Carannante ().