Best response algorithms in ratio-bounded games: convergence of affine relaxations to Nash equilibria

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: In two-player non-cooperative games whose strategy sets are Hilbert spaces, in order to approach Nash equilibria we are interested in the affine relaxations of the best response algorithm (where a player's strategy is exactly a best response to the strategy of the other player that comes from the previous step, sometimes called as "fictitious play"). For this purpose we define a class of games, called ratio-bounded games, that relies on explicit assumptions on the data and that contains large classes of games already known in literature, both in finite and in infinite dimensional setting: extended quadratic games including potential and antipotential games, non-quadratic games with a bilinear interaction, and linear state differential games. We provide a classification of the ratio-bounded games in four subclasses such that, for each of them, the following issues are examined: the existence and uniqueness of Nash equilibria, the convergence of affine relaxations of the best response algorithm and the estimation of related errors. In particular, the results on convergence of convex relaxations of the best response algorithm include those obtained for zero-sum games in Morgan [Int. J. Comput. Math., 4 (1974), pp. 143-175], and the results on convergence of affine non-convex relaxations include those obtained for non-zero-sum games in Caruso, Ceparano, Morgan [SIAM J. Optim., 30 (2020), pp. 1638-1663].

Keywords: Two-player non-cooperative game; Nash equilibrium; existence and uniqueness; fixed point; contraction mapping; non-expansive mapping; super monotone operator; best response algorithm; convex relaxation; affine non-convex relaxation; convergence and error bound. (search for similar items in EconPapers)
Date: 2020-12-18
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.csef.it/WP/wp593.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:593

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 ().