Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Dynamic Games and Applications
Erschienen in: Dynamic Games and Applications 2/2022

11.11.2021

Newton’s Method, Bellman Recursion and Differential Dynamic Programming for Unconstrained Nonlinear Dynamic Games

verfasst von: Bolei Di, Andrew Lamperski

Erschienen in: Dynamic Games and Applications | Ausgabe 2/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Dynamic games arise when multiple agents with differing objectives control a dynamic system. They model a wide variety of applications in economics, defense, energy systems and etc. However, compared to single-agent control problems, the computational methods for dynamic games are relatively limited. As in the single-agent case, only specific dynamic games can be solved exactly, so approximation algorithms are required. In this paper, we show how to extend the Newton step algorithm, the Bellman recursion and the popular differential dynamic programming (DDP) for single-agent optimal control to the case of full-information nonzero sum dynamic games. We show that the Newton’s step can be solved in a computationally efficient manner and inherits its original quadratic convergence rate to open-loop Nash equilibria, and that the approximated Bellman recursion and DDP methods are very similar and can be used to find local feedback \(O(\varepsilon ^2)\)-Nash equilibria. Numerical examples are provided.
Vorheriger Artikel Markov Perfect Equilibria in Multi-Mode Differential Games with Endogenous Timing of Mode Transitions
Nächster Artikel Dynamic Information Design: A Simple Problem on Optimal Sequential Information Disclosure

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Abadi M, Agarwal A, Barham P, Brevdo E, Chen Z, Citro C, Corrado GS, Davis A, Dean J, Devin M, Ghemawat S, Goodfellow I, Harp A, Irving G, Isard M, Jia Y, Jozefowicz R, Kaiser L, Kudlur M, Levenberg J, Mané D, Monga R, Moore S, Murray D, Olah C, Schuster M, Shlens J, Steiner B, Sutskever I, Talwar K, Tucker P, Vanhoucke V, Vasudevan V, Viégas F, Vinyals O, Warden P, Wattenberg M, Wicke M, Yu Y, Zheng X (2015) TensorFlow: large-scale machine learning on heterogeneous systems. https://​www.​tensorflow.​org/​
2.
Andersson JAE, Gillis J, Horn G, Rawlings JB, Diehl M (2018) CasADi—a software framework for nonlinear optimization and optimal control. Math Program Comput (in press)
3.
Basar T (1976) On the uniqueness of the Nash solution in linear-quadratic differential games. Int J Game Theory 5(2–3):65–90MathSciNetMATHCrossRef
4.
Basar T, Haurie A, Zaccour G (2018) Nonzero-sum differential games. In Basar T, Zaccour G (eds) Handbook of dynamic game theory. Springer, pp 61–110
5.
Basar T, Olsder GJ (1999) Dynamic noncooperative game theory, vol 3. SIAM, PhiladelphiaMATH
6.
Basar T, Zaccour G (2018) Handbook of Dynamic Game Theory. Springer
7.
8.
Berridge S, Krawczyk JB (1997) Relaxation algorithms in finding Nash equilibria. Available at SSRN 66448
9.
10.
11.
Bressan A, Nguyen KT (2018) Stability of feedback solutions for infinite horizon noncooperative differential games. Dyn Games Appl 8(1):42–78MathSciNetMATHCrossRef
12.
Buckdahn R, Cardaliaguet P, Quincampoix M (2011) Some recent aspects of differential game theory. Dyn Games Appl 1(1):74–114MathSciNetMATHCrossRef
13.
Cacace S, Cristiani E, Falcone M (2011) Numerical approximation of Nash equilibria for a class of non-cooperative differential games. arXiv preprint arXiv:​1109.​3569
14.
Carlson D, Haurie A, Zaccour G (2016) Infinite horizon concave games with coupled constraints. In: Handbook of dynamic game theory, pp 1–44
15.
Contreras J, Klusch M, Krawczyk JB (2004) Numerical solutions to Nash–Cournot equilibria in coupled constraint electricity markets. IEEE Trans Power Syst 19(1):195–206CrossRef
16.
Darbon J, Langlois GP, Meng T (2020) Overcoming the curse of dimensionality for some Hamilton–Jacobi partial differential equations via neural network architectures. Res Math Sci 7(3):1–50MathSciNetMATHCrossRef
17.
Darbon J, Meng T (2021) On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton–Jacobi partial differential equations. J Comput Phys 425:109907MathSciNetCrossRef
18.
Dechert WD (1997) Non cooperative dynamic games: a control theoretic approach. Unpublished, available on request to the author
19.
Diehl M, Bjornberg J (2004) Robust dynamic programming for min-max model predictive control of constrained uncertain systems. IEEE Trans Autom Control 49(12):2253–2257MathSciNetMATHCrossRef
20.
Duncan TE, Pasik-Duncan B (2015) Some stochastic differential games with state dependent noise. In: 2015 54th IEEE Conference on Decision and Control (CDC). IEEE, pp 3773–3777
21.
Dunn JC, Bertsekas DP (1989) Efficient dynamic programming implementations of Newton’s method for unconstrained optimal control problems. J Optim Theory Appl 63(1):23–38
22.
23.
24.
Engwerda J (2017) A numerical algorithm to calculate the unique feedback Nash equilibrium in a large scalar LQ differential game. Dyn Games Appl 7(4):635–656MathSciNetMATHCrossRef
25.
Engwerda J et al (2012) Feedback Nash equilibria for linear quadratic descriptor differential games. Automatica 48(4):625–631MathSciNetMATHCrossRef
26.
Evans LC, Souganidis PE (1984) Differential games and representation formulas for solutions of Hamilton–Jacobi–Isaacs equations. Indiana Univ Math J 33(5):773–797MathSciNetMATHCrossRef
27.
Exarchos I, Theodorou E, Tsiotras P (2018) Stochastic differential games: a sampling approach via fbsdes. Dyn Games Appl 9:486–505MathSciNetMATHCrossRef
28.
Facchinei F, Fischer A, Piccialli V (2007) On generalized Nash games and variational inequalities. Oper Res Lett 35(2):159–164MathSciNetMATHCrossRef
29.
Facchinei F, Fischer A, Piccialli V (2009) Generalized Nash equilibrium problems and Newton methods. Math Program 117(1–2):163–194MathSciNetMATHCrossRef
30.
31.
Facchinei F, Pang JS (2007) Finite-dimensional variational inequalities and complementarity problems. Springer, BerlinMATH
32.
Frihauf P, Krstic M, Basar T (2012) Nash equilibrium seeking in noncooperative games. IEEE Trans Autom Control 57(5):1192–1207MathSciNetMATHCrossRef
33.
Frihauf P, Krstic M, Başar T (2013) Finite-horizon LQ control for unknown discrete-time linear systems via extremum seeking. Eur J Control 19(5):399–407MathSciNetMATHCrossRef
34.
Frihauf P, Krstic M, Başar T (2013) Nash equilibrium seeking for dynamic systems with non-quadratic payoffs. In: Advances in dynamic games. Springer, pp 179–198
35.
González-Sánchez D, Hernández-Lerma O (2013) Discrete-time stochastic control and dynamic potential games: the Euler-equation approach. Springer, BerlinMATHCrossRef
36.
González-Sánchez D, Hernández-Lerma O (2014) Dynamic potential games: the discrete-time stochastic case. Dyn Games Appl 4(3):309–328MathSciNetMATHCrossRef
37.
González-Sánchez D, Hernández-Lerma O (2016) A survey of static and dynamic potential games. Sci China Math 59(11):2075–2102MathSciNetMATHCrossRef
38.
Haurie A, Krawczyk JB, Zaccour G (2012) Games and dynamic games, vol 1. World Scientific Publishing Company, SingaporeMATHCrossRef
39.
Isaacs R (1999) Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Courier Corporation, ChelmsfordMATH
40.
Kebriaei H, Iannelli L (2018) Discrete-time robust hierarchical linear-quadratic dynamic games. IEEE Trans Autom Control 63(3):902–909MathSciNetMATHCrossRef
41.
42.
Krawczyk JB (2005) Coupled constraint Nash equilibria in environmental games. Resour Energy Econ 27(2):157–181CrossRef
43.
Krawczyk JB, Petkov V (2018) Multistage games. In: Handbook of dynamic game theory, pp 157–213
44.
Krawczyk JB, Uryasev S (2000) Relaxation algorithms to find Nash equilibria with economic applications. Environ Model Assess 5(1):63–73CrossRef
45.
Krikelis N, Rekasius Z (1971) On the solution of the optimal linear control problems under conflict of interest. IEEE Trans Autom Control 16(2):140–147MathSciNetCrossRef
46.
47.
Liao LZ, Shoemaker CA (1991) Convergence in unconstrained discrete-time differential dynamic programming. IEEE Trans Autom Control 36(6):692–706MathSciNetMATHCrossRef
48.
Lin W (2013) Differential games for multi-agent systems under distributed information. Ph.D. thesis, University of Central Florida information
49.
Mazalov VV, Rettieva AN, Avrachenkov KE (2017) Linear-quadratic discrete-time dynamic potential games. Autom Remote Control 78(8):1537–1544MathSciNetMATHCrossRef
50.
Murray D, Yakowitz S (1984) Differential dynamic programming and Newton’s method for discrete optimal control problems. J Optim Theory Appl 43(3):395–414
51.
Nakamura-Zimmerer T, Gong Q, Kang W (2021) Adaptive deep learning for high-dimensional Hamilton–Jacobi–Bellman equations. SIAM J Sci Comput 43(2):A1221–A1247MathSciNetMATHCrossRef
52.
Nocedal J, Wright SJ (2006) Numerical optimization, 2nd edn. Springer, BerlinMATH
53.
O’Donoghue B, Stathopoulos G, Boyd S (2013) A splitting method for optimal control. IEEE Trans Control Syst Technol 21(6):2432–2442
54.
Pan Y, Ozguner U (2004) Sliding mode extremum seeking control for linear quadratic dynamic game. In: Proceedings of the 2004 American Control Conference, vol 1. IEEE, pp 614–619
55.
Paszke A, Gross S, Chintala S, Chanan G, Yang E, DeVito Z, Lin Z, Desmaison A, Antiga L, Lerer A (2017) Automatic differentiation in pytorch. In: NIPS-W
56.
Plaksin A (2020) Viscosity solutions of Hamilton–Jacobi–Bellman–Isaacs equations for time-delay systems. arXiv e-prints arXiv:​2001.​07905
57.
Sethi SP (2019) Differential games. In: Optimal control theory. Springer, pp 385–407
58.
Sun W, Theodorou EA, Tsiotras P (2015) Game theoretic continuous time differential dynamic programming. In: American Control Conference (ACC), 2015. IEEE, pp 5593–5598
59.
Sun W, Theodorou EA, Tsiotras P (2016) Stochastic game theoretic trajectory optimization in continuous time. In: 2016 IEEE 55th Conference on Decision and Control (CDC). IEEE, pp 6167–6172
60.
Tassa Y (2011) Theory and implementation of biomimetic motor controllers. Hebrew University of Jerusalem
61.
Zazo S, Macua SV, Sánchez-Fernández M, Zazo J (2015) Dynamic potential games in communications: fundamentals and applications. arXiv preprint arXiv:​1509.​01313
62.
Zazo S, Macua SV, Sánchez-Fernández M, Zazo J (2016) Dynamic potential games with constraints: fundamentals and applications in communications. IEEE Trans Signal Process 64(14):3806–3821MathSciNetMATHCrossRef
63.
Zazo S, Valcarcel S, Matilde S, Zazo J et al (2015) A new framework for solving dynamic scheduling games. In: 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, pp 2071–2075
Metadaten
Titel
Newton’s Method, Bellman Recursion and Differential Dynamic Programming for Unconstrained Nonlinear Dynamic Games
verfasst von
Bolei Di
Andrew Lamperski
Publikationsdatum
11.11.2021
Verlag
Springer US
Erschienen in
Dynamic Games and Applications / Ausgabe 2/2022
Print ISSN: 2153-0785
Elektronische ISSN: 2153-0793
DOI
https://doi.org/10.1007/s13235-021-00399-8

Weitere Artikel der Ausgabe 2/2022

Dynamic Games and Applications 2/2022 Zur Ausgabe

OriginalPaper

The Frequency of Convergent Games under Best-Response Dynamics

OriginalPaper

An Evolutionary Game Model Between Governments and Manufacturers Considering Carbon Taxes, Subsidies, and Consumers’ Low-Carbon Preference

OriginalPaper

Markov Perfect Equilibria in Multi-Mode Differential Games with Endogenous Timing of Mode Transitions

OriginalPaper

Continuous-Time Zero-Sum Games for Markov Decision Processes with Discounted Risk-Sensitive Cost Criterion

OriginalPaper

Maximum Principle for General Partial Information Nonzero Sum Stochastic Differential Games and Applications

OriginalPaper

Dynamic Quantum Games

Premium Partner

    Bildnachweise