Affine Relaxations of the Best Response Algorithm: Global Convergence in Ratio-Bounded Games

DOI10.1137/21M140612XOpenAlexW4385497031MaRDI QIDQ6116265

Jacqueline Morgan, Francesco Caruso, Maria Carmela Ceparano

Publication date: 11 August 2023

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/21m140612x

zbMATH Keywords

global convergence fixed point nonexpansive mapping Nash equilibrium error bound existence and uniqueness zero-sum game convex relaxation contraction mapping potential game speed of convergence two-player noncooperative game best response algorithm super monotone operator nonconvex affine relaxation

Mathematics Subject Classification ID

Noncooperative games (91A10) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Algorithmic game theory and complexity (91A68)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Perturbations of set-valued dynamical systems, with applications to game theory
Approximating saddle points as equilibria of differential inclusions
Lectures on convex optimization
Méthodes pour la recherche de points de selle
Iterative approximation of fixed points
Nash equilibrium with strategic complementarities
Distributed algorithms for the computation of noncooperative equilibria
Relaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria
Averaged predictions and the learning of equilibrium play
Fictitious play applied to sequences of games and discounted stochastic games
Correlated equilibrium and potential games
Congestion models and weighted Bayesian potential games
On the rate of convergence of continuous-time fictitious play
Supermodular games and potential games.
Uniqueness of Nash equilibrium in continuous two-player weighted potential games
Stochastic learning in multi-agent optimization: communication and payoff-based approaches
Learning in games with continuous action sets and unknown payoff functions
Fictitious play in \(2\times n\) games
Potential games
Fictitious play property for games with identical interests
Best-response dynamics in zero-sum stochastic games
Subgame perfect Nash equilibrium: a learning approach via costs to move
Interactive decisions and potential games
Best response dynamics for continuous zero-sum games
Construction of fixed points of nonlinear mappings in Hilbert space
An iterative method of solving a game
On the computation of equilibria in monotone and potential stochastic hierarchical games
Complexity and Optimality of the Best Response Algorithm in Random Potential Games
On Best-Response Dynamics in Potential Games
Convergence results of an approximation method for constrained saddle point problems
Social Stability and Equilibrium
On approximate mixed Nash equilibria and average marginal functions for two-stage three-players games
A New Class of Alternating Proximal Minimization Algorithms with Costs-to-Move
An algorithm for a constrained saddle point problem via an exact penalty method
Equilibrium Points in Nonzero-Sum n-Person Submodular Games
Methode directe de recherche du point de selle d'une fonctlonnelle convexe-concave et application aux problémes variationnels elliptiques avec deux controles antagonistes
Evolutionary Games and Population Dynamics
Refined best reply correspondence and dynamics
Learning with minimal information in continuous games
Fictitious Play in Zero-Sum Stochastic Games
On Synchronous, Asynchronous, and Randomized Best-Response Schemes for Stochastic Nash Games
An Inverse-Adjusted Best Response Algorithm for Nash Equilibria
Stochastic Approximations and Differential Inclusions
Equilibrium points in n -person games
Mean Value Methods in Iteration

This page was built for publication: Affine Relaxations of the Best Response Algorithm: Global Convergence in Ratio-Bounded Games