Characterization and computation of local Nash equilibria in continuous games
Published 1 October 2013
Lillian J. Ratliff, Samuel A. Burden, S. Shankar Sastry
Citations214
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Drawing on this analogy, an iterative steepest descent algorithm is proposed for numerical approximation of local Nash equilibria and a sufficient condition ensuring local convergence of the algorithm is provided.
Abstract
We present derivative-based necessary and sufficient conditions ensuring player strategies constitute local Nash equilibria in non-cooperative continuous games. Our results can be interpreted as generalizations of analogous second-order conditions for local optimality from nonlinear programming and optimal control theory. Drawing on this analogy, we propose an iterative steepest descent algorithm for numerical approximation of local Nash equilibria and provide a sufficient condition ensuring local convergence of the algorithm. We demonstrate our analytical and computational techniques by computing local Nash equilibria in games played on a finite-dimensional differentiable manifold or an infinite-dimensional Hilbert space.
Keywords
Computer ScienceDecision SciencesMathematics
American Mathematical Society eBooksTheory of games and economic behavior
16,943 Citations2019Stephan Ramon Garcia, Steven J. Miller
EconometricaExistence and Uniqueness of Equilibrium Points for Concave N-Person Games
2,700 Citations1965Judah B Rosen
Optimization: Algorithms and Consistent Approximations
926 Citations1997E. Polak
This paper presents a meta-anatomy of semi-Infinite Optimization, a branch of optimization that combines the efforts of biologists and mathematicians to study the response of the immune system to injury.
IEEE Transactions on Power SystemsNumerical Solutions to Nash–Cournot Equilibria in Coupled Constraint Electricity Markets
285 Citations2004Javier Contreras, Matthias Klusch +1 more
AutomaticaDistributed algorithms for the computation of noncooperative equilibria
191 Citations1987Shu Li, Tamer Başar
It is shown in the context of a fish war example that the algorithm given is in some aspects superior to various algorithms found in the literature, and is furthermore more meaningful for real world implementation.
IEEE Transactions on Automatic ControlOn relaxation algorithms in computation of noncooperative equilibria
146 Citations1994Stan Uryasev, R.Y. Rubinstein
This approach can be generalized for the stochastic Nash equilibrium problems with uncertainties in parameters, and the convergence theorem is proved for nonsmooth weakly convex-concave Nikaido-Isoda functions.
Journal of Economic Dynamics and ControlRelaxation techniques and asynchronous algorithms for on-line computation of non-cooperative equilibria
77 Citations1987Tamer Başar
A relaxation technique is introduced which leads to on-line implementable algorithms thai converge to equilibria, be they stable or unstable, and in some cases in a finite number of steps.
Designing games for distributed optimization
61 Citations2011Na Li, Jason R. Marden
A systematic methodology for meeting agent objective functions to meet objectives such as locality of information and efficiency of resulting equilibria within the framework of potential games is developed using a broader framework of games termed state based potential games.
The International Journal of Robotics ResearchPhase Regulation of Decentralized Cyclic Robotic Systems
55 Citations2002Eric Klavins, Daniel E. Koditschek
A class of dynamical systems defined over n-dimensional tori (the cross product of n oscillator phases) that serve as reference fields for the specified task that represent the ideal flow and phase couplings of the various cyclic tasks to be coordinated are introduced.
Journal of Optimization Theory and ApplicationsNonexistence and nonuniqueness of open-loop equilibria in linear-quadratic differential games
43 Citations1982Th. Eisele
Pricing in linear-quadratic dynamic games
18 Citations2012Lillian J. Ratliff, Samuel Coogan +2 more
Methods for ensuring that the total cost incurred due to the leader's pricing is as close as possible to a specified nominal cost are discussed, as well as methods for minimizing the explicit dependence of a player's cost on other players' control inputs.
Genericity and structural stability of non-degenerate differential Nash equilibria
15 Citations2014Lillian J. Ratliff, Samuel A. Burden +1 more
It is demonstrated that equilibria that are computable using decoupled myopic approximate best-response persist under perturbations to the cost functions of individual players, implying that second-order conditions suffice to characterize local NashEquilibria in an open-dense set of games where player costs are smooth functions.
Lecture notes in control and information sciencesDecentralized Coordination with Local Interactions: Some New Directions
13 Citations2004Abubakr Muhammad, Magnus Egerstedt
It is given sufficient conditions for a graph to be a connectivity graph in the sense that it can be realized as a formation in the configuration space, and the topological shape of a given connectivity graph is captured using triangulation techniques.
Annals of Operations ResearchRestricted attention, myopic play, and thelearning of equilibrium
10 Citations1998Sjur Didrik Flåm
This work considers repeated play of noncooperative games in which agents have more decision to consider at every stage than their attention allows, and concludes that myopic steps lead to Nash equilibrium in the long run.