Nash equilibrium seeking for dynamic systems with non-quadratic payoffs

Paul Frihauf, Miroslav Krstic, M Tamer Basar

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We consider general, stable nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. To achieve locally stable convergence to the resulting steady-state Nash equilibria, we introduce a non-model-based approach, where the players determine their actions based only on their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. Since non-quadratic payoffs create the possibility of multiple, isolated Nash equilibria, our convergence results are local. Specifically, the attainment of any particular Nash equilibrium is not assured for all initial conditions, but only for initial conditions in a set around that specific stable Nash equilibrium. For non-quadratic costs, the convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases.

Original languageEnglish (US)
Title of host publicationAnnals of the International Society of Dynamic Games
PublisherBirkhauser
Pages179-198
Number of pages20
DOIs
StatePublished - Jan 1 2013

Publication series

NameAnnals of the International Society of Dynamic Games
Volume12
ISSN (Print)2474-0179
ISSN (Electronic)2474-0187

Fingerprint

Nash Equilibrium
Dynamic Systems
Dynamical systems
Differential equations
Derivatives
Initial conditions
Stable Convergence
Perturbation
Non-cooperative Game
Output
Costs
Extremum
Convergence Results
Nonlinear Differential Equations
Biased
Quantify
Proportion
Dynamic systems
Nash equilibrium
Gradient

Keywords

  • Extremum seeking
  • Learning
  • Nash equilibria
  • Noncooperative games

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics

Cite this

Frihauf, P., Krstic, M., & Basar, M. T. (2013). Nash equilibrium seeking for dynamic systems with non-quadratic payoffs. In Annals of the International Society of Dynamic Games (pp. 179-198). (Annals of the International Society of Dynamic Games; Vol. 12). Birkhauser. https://doi.org/10.1007/978-0-8176-8355-9_9

Nash equilibrium seeking for dynamic systems with non-quadratic payoffs. / Frihauf, Paul; Krstic, Miroslav; Basar, M Tamer.

Annals of the International Society of Dynamic Games. Birkhauser, 2013. p. 179-198 (Annals of the International Society of Dynamic Games; Vol. 12).

Research output: Chapter in Book/Report/Conference proceedingChapter

Frihauf, P, Krstic, M & Basar, MT 2013, Nash equilibrium seeking for dynamic systems with non-quadratic payoffs. in Annals of the International Society of Dynamic Games. Annals of the International Society of Dynamic Games, vol. 12, Birkhauser, pp. 179-198. https://doi.org/10.1007/978-0-8176-8355-9_9
Frihauf P, Krstic M, Basar MT. Nash equilibrium seeking for dynamic systems with non-quadratic payoffs. In Annals of the International Society of Dynamic Games. Birkhauser. 2013. p. 179-198. (Annals of the International Society of Dynamic Games). https://doi.org/10.1007/978-0-8176-8355-9_9
Frihauf, Paul ; Krstic, Miroslav ; Basar, M Tamer. / Nash equilibrium seeking for dynamic systems with non-quadratic payoffs. Annals of the International Society of Dynamic Games. Birkhauser, 2013. pp. 179-198 (Annals of the International Society of Dynamic Games).
@inbook{49d11a23f413447b85c29952e1ed0d88,
title = "Nash equilibrium seeking for dynamic systems with non-quadratic payoffs",
abstract = "We consider general, stable nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. To achieve locally stable convergence to the resulting steady-state Nash equilibria, we introduce a non-model-based approach, where the players determine their actions based only on their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. Since non-quadratic payoffs create the possibility of multiple, isolated Nash equilibria, our convergence results are local. Specifically, the attainment of any particular Nash equilibrium is not assured for all initial conditions, but only for initial conditions in a set around that specific stable Nash equilibrium. For non-quadratic costs, the convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases.",
keywords = "Extremum seeking, Learning, Nash equilibria, Noncooperative games",
author = "Paul Frihauf and Miroslav Krstic and Basar, {M Tamer}",
year = "2013",
month = "1",
day = "1",
doi = "10.1007/978-0-8176-8355-9_9",
language = "English (US)",
series = "Annals of the International Society of Dynamic Games",
publisher = "Birkhauser",
pages = "179--198",
booktitle = "Annals of the International Society of Dynamic Games",

}

TY - CHAP

T1 - Nash equilibrium seeking for dynamic systems with non-quadratic payoffs

AU - Frihauf, Paul

AU - Krstic, Miroslav

AU - Basar, M Tamer

PY - 2013/1/1

Y1 - 2013/1/1

N2 - We consider general, stable nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. To achieve locally stable convergence to the resulting steady-state Nash equilibria, we introduce a non-model-based approach, where the players determine their actions based only on their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. Since non-quadratic payoffs create the possibility of multiple, isolated Nash equilibria, our convergence results are local. Specifically, the attainment of any particular Nash equilibrium is not assured for all initial conditions, but only for initial conditions in a set around that specific stable Nash equilibrium. For non-quadratic costs, the convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases.

AB - We consider general, stable nonlinear differential equations with N inputs and N outputs, where in the steady state, the output signals represent the payoff functions of a noncooperative game played by the steady-state values of the input signals. To achieve locally stable convergence to the resulting steady-state Nash equilibria, we introduce a non-model-based approach, where the players determine their actions based only on their own payoff values. This strategy is based on the extremum seeking approach, which has previously been developed for standard optimization problems and employs sinusoidal perturbations to estimate the gradient. Since non-quadratic payoffs create the possibility of multiple, isolated Nash equilibria, our convergence results are local. Specifically, the attainment of any particular Nash equilibrium is not assured for all initial conditions, but only for initial conditions in a set around that specific stable Nash equilibrium. For non-quadratic costs, the convergence to a Nash equilibrium is not perfect, but is biased in proportion to the perturbation amplitudes and the higher derivatives of the payoff functions. We quantify the size of these residual biases.

KW - Extremum seeking

KW - Learning

KW - Nash equilibria

KW - Noncooperative games

UR - http://www.scopus.com/inward/record.url?scp=85055051229&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85055051229&partnerID=8YFLogxK

U2 - 10.1007/978-0-8176-8355-9_9

DO - 10.1007/978-0-8176-8355-9_9

M3 - Chapter

AN - SCOPUS:85055051229

T3 - Annals of the International Society of Dynamic Games

SP - 179

EP - 198

BT - Annals of the International Society of Dynamic Games

PB - Birkhauser

ER -