nach oben

Dynamic Games and Applications

Erschienen in:

31.01.2022

Continuous Time Learning Algorithms in Optimization and Game Theory

verfasst von: Sylvain Sorin

Erschienen in: Dynamic Games and Applications | Ausgabe 1/2023

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The purpose of this work is the comparison of learning algorithms in continuous time used in optimization and game theory. The first three are issued from no-regret dynamics and cover in particular “Replicator dynamics” and “Local projection dynamics”. Then we study “Conditional gradient” versus “Global projection” dynamics and finally “Frank-Wolfe” versus “Best reply” dynamics. Important similarities occur when considering potential or dissipative games.

Vorheriger Artikel Special Issue : Multi-Agent Dynamic Decision Making and Learning

Nächster Artikel Multi-Agent Natural Actor-Critic Reinforcement Learning Algorithms

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

Nur mit Berechtigung zugänglich

Akin E (1979) The geometry of population genetics. Lecture notes in biomathematics, vol 31. Springer, BerlinCrossRef

Alvarez F, Bolte J, Brahic O (2004) Hessian Riemannian gradient flows in convex programming. SIAM J Control Optim 43:477–501MathSciNetMATHCrossRef

Antipin AS (1994) Minimization of convex functions on convex sets by means of differential equations. Differ Equ 30:1365–1375MathSciNetMATH

Attouch H, Teboulle M (2004) Regularized Lotka-Volterra dynamical system as continuous proximal-like method in optimization. J Optim Theory Appl 121:541–570MathSciNetMATHCrossRef

Avrachenkov K, Borkar VS (2019) Metastability in stochastic replicator dynamics. Dyn Games Appl 9:366–390MathSciNetMATHCrossRef

Barron EN, Goebel R, Jensen RR (2010) Best response dynamics for continuous games. Proc AMS 138:1069–1083MathSciNetMATHCrossRef

Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper Res Lett 31:167–175MathSciNetMATHCrossRef

Benaim M, Hofbauer J, Sorin S (2005) Stochastic approximations and differential inclusions. SIAM J Control Optim 44:328–348MathSciNetMATHCrossRef

Benaim M, Hofbauer J, Sorin S (2006) Stochastic approximations and differential inclusions. Part II: applications. Math Oper Res 31:673–695MathSciNetMATHCrossRef

10.

Benaim M, Hofbauer J, Sorin S (2012) Perturbations of set-valued dynamical systems, with applications to game theory. Dyn Games Appl 2:195–205MathSciNetMATHCrossRef

11.

Bolte J (2003) Continuous gradient projection method in Hilbert spaces. J Optim Theory Appl 119:235–259MathSciNetMATHCrossRef

12.

Bolte J, Teboulle M (2003) Barrier operators and associated gradient-like dynamical systems for constrained minimization problems. SIAM J Control Optim 42:1266–1292MathSciNetMATHCrossRef

13.

Brézis H (1973) Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. North Holland, AmsterdamMATH

14.

Brown GW (1951) Iterative solutions of games by fictitious play. In: Koopmans TC (ed) Activity analysis of production and allocation. Wiley, Hoboken, pp 374–376

15.

Brown GW, von Neumann J (1950) Solutions of games by differential equations. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games, I. Annals of mathematical studies, vol 24. Princeton University Press, Princeton, pp 73–79

16.

Bruck RE (1975) Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. J Funct Anal 18:15–26MathSciNetMATHCrossRef

17.

Dafermos SC (1980) Traffic equilibrium and variational inequalities. Transp Sci 14:42–54MathSciNetCrossRef

18.

Dupuis P, Nagurney A (1993) Dynamical systems and variational inequalities. Ann Oper Res 44:9–42MathSciNetMATHCrossRef

19.

Facchinei F, Pang J (2007) Finite-dimensional variational inequalities and complementarity problems. Springer, BerlinMATH

20.

Foster D, Young HP (1990) Stochastic evolutionary game dynamics. Theor Popul Biol 38:219–232MathSciNetMATHCrossRef

21.

Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res Logist Q 3:95–110MathSciNetCrossRef

22.

Friesz TL, Bernstein D, Mehta NJ, Tobin RL, Ganjalizadeh S (1994) Day-to-day dynamic network disequilibria and idealized traveler information systems. Oper Res 42:1120–1136MathSciNetMATHCrossRef

23.

Gilboa I, Matsui A (1991) Social stability and equilibrium. Econometrica 59:859–867MathSciNetMATHCrossRef

24.

Hart S, Mas-Colell A (2003) Uncoupled dynamics do not lead to Nash equilibrium. Am Econ Rev 93:1830–1836CrossRef

25.

Hofbauer J, Sandholm WH (2009) Stable games and their dynamics. J Econ Theory 144:1665–1693MathSciNetMATHCrossRef

26.

Hofbauer J, Sigmund K (1998) Evolutionary games and population dynamics. Cambridge University Press, CambridgeMATHCrossRef

27.

Hofbauer J, Sorin S (2006) Best response dynamics for continuous zero-sum games. Discrete Contin Dyn Syst Ser B 6:215–224MathSciNetMATH

28.

Hofbauer J, Sorin S, Viossat Y (2009) Time average replicator and best reply dynamics. Math Oper Res 34:263–269MathSciNetMATHCrossRef

29.

Kinderlehrer D, Stampacchia G (1980) An introduction to variational inequalities and their applications. Academic Press, LondonMATH

30.

Kwon J, Mertikopoulos P (2017) A continuous time approach to on-line optimization. J Dyn Games 4:125–148MathSciNetMATHCrossRef

31.

Lahkar R, Sandholm WH (2008) The projection dynamic and the geometry of population games. Games Econ Behav 64:565–590MathSciNetMATHCrossRef

32.

Maynard Smith J (1982) Evolution and the theory of games. Cambridge U.P., CambridgeMATHCrossRef

33.

Mazumdar E, Ratliff LJ, Sastry SS (2020) On gradient-based learning in continuous games. SIAM J Math Data Sci 2:103–131MathSciNetMATHCrossRef

34.

Mertikopoulos P, Sandholm WH (2016) Learning in games via reinforcement and regularization. Math Oper Res 41:1297–1324MathSciNetMATHCrossRef

35.

Mertikopoulos P, Sandholm WH (2018) Riemannian game dynamics. J Econ Theory 177:315–364MathSciNetMATHCrossRef

36.

Mertikopoulos P, Zhou Z (2019) Learning in games with continuous action sets and unknown payoff functions. Math Program 173:465–507MathSciNetMATHCrossRef

37.

Minty GJ (1967) On the generalization of a direct method of the calculus of variations. Bull AMS 73:315–321MathSciNetMATHCrossRef

38.

Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14:124–143MathSciNetMATHCrossRef

39.

Monderer D, Shapley LS (1996) Fictitious Play property for games with identical interests. J Econ Theory 68:258–265MathSciNetMATHCrossRef

40.

Moreau JJ (1965) Proximité et dualité dans un espace hilbertien. Bull Soc Math Fr 93:273–299MATHCrossRef

41.

Nash J (1950) Equilibrium points in \(n\)-person games. Proc Natl Acad Sci 36:48–49MathSciNetMATHCrossRef

42.

Nash J (1951) Non-cooperative games. Ann Math 54:286–295MathSciNetMATHCrossRef

43.

Nemirovski A, Yudin D (1983) Problem complexity and method efficiency in optimization. Wiley, Hoboken

44.

Nesterov Y (2009) Primal-dual subgradient methods for convex problems. Math Program 120:221–259MathSciNetMATHCrossRef

45.

Nikaido H, Isoda K (1955) Note on non cooperative convex games. Pac J Math 5:807–815MathSciNetMATHCrossRef

46.

Opial Z (1967) Weak Convergence of the sequence of successive approximations for nonexpansive mappings. Bull Am Math Soc 73:591–597MathSciNetMATHCrossRef

47.

Pappalardo M, Passacantando M (2004) Gap functions and Lyapunov functions. J Glob Optim 28:379–385MathSciNetMATHCrossRef

48.

Polyak B (1987) Introduction to optimization. In: Optimization software

49.

Rockafellar RT (1970) Convex analysis. Princeton University Press, PrincetonMATHCrossRef

50.

Rockafellar RT (1970) Monotone operators associated with saddle-functions and minmax problems. In: Browder F (ed) Nonlinear functional analysis. Proceedings of symposia in pure math, vol 18. AMS, pp 241–250

51.

Rosen JB (1965) Existence and uniqueness of equilibrium points for concave N-person games. Econometrica 33:520–534MathSciNetMATHCrossRef

52.

Rustichini A (1999) Optimal properties of stimulus-response learning models. Games Econ Behav 29:230–244MathSciNetMATHCrossRef

53.

Sandholm WH (2001) Potential games with continuous player sets. J Econ Theory 97:81–108MathSciNetMATHCrossRef

54.

Sandholm WH (2011) Population games and evolutionary dynamics. MIT Press, CambridgeMATH

55.

Sandholm WH (2015) Population games and deterministic evolutionary dynamics. In: Young HP, Zamir S (eds) Handbook of game theory IV. Elsevier, Amsterdam, pp 703–778

56.

Sandholm WH, Dokumaci E, Lahkar R (2008) The projection dynamic and the replicator dynamic. Games Econ Behav 64:666–683MathSciNetMATHCrossRef

57.

Shahshahani S (1979) A new mathematical framework for the study of linkage and selection. In: Memoirs of the American Mathematical Society, vol 211

58.

Smith MJ (1979) The existence, uniqueness and stability of traffic equilibria. Transp Res Part B 13:295–304MathSciNetCrossRef

59.

Sorin S (2009) Exponential weight algorithm in continuous time. Math Program Ser B 116:513–528MathSciNetMATHCrossRef

60.

Sorin S (2011) On some global and unilateral adaptive dynamics. In: Sigmund K (ed) Evolutionary game dynamics. Proceedings of symposia in applied mathematics, vol 69. A.M.S., pp 81–109

61.

Sorin S (2020) Replicator dynamics: old and new. J Dyn Games 7:365–385MathSciNetMATHCrossRef

62.

Sorin S (2021) No-regret algorithms in on-line learning, games and convex optimization. In: Mathematical programming (to appear)

63.

Sorin S, Wang C (2016) Finite composite games: equilibria and dynamics. J Dyn Games 3:101–120MathSciNetMATHCrossRef

64.

Swinkels JM (1993) Adjustment dynamics and rational play in games. Games Econ Behav 5:455–484MathSciNetMATHCrossRef

65.

Taylor PB, Jonker LB (1978) Evolutionary stable strategies and game dynamics. Math Biosci 40:145–156MathSciNetMATHCrossRef

66.

Tsakas E, Voorneveld M (2009) The target projection dynamic. Games Econ Behav 67:708–719MathSciNetMATHCrossRef

67.

Viossat Y (2014) Game dynamics and Nash equilibria. J Dyn Games 1:537–553MathSciNetMATHCrossRef

68.

Wardrop G (1952) Some theoretical aspects of road traffic research communication networks. Proc Inst Civ Eng Part 2 1:325–378

Titel: Continuous Time Learning Algorithms in Optimization and Game Theory
verfasst von: Sylvain Sorin
Publikationsdatum: 31.01.2022
Verlag: Springer US
Erschienen in: Dynamic Games and Applications / Ausgabe 1/2023
Print ISSN: 2153-0785
Elektronische ISSN: 2153-0793
DOI: https://doi.org/10.1007/s13235-021-00423-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2023

Robust Utility Design in Distributed Resource Allocation Problems with Defective Agents

Opinion Dynamics Control in a Social Network with a Communication Structure

Dynamic Games Among Teams with Delayed Intra-Team Information Sharing

Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games

Reinforcement Learning for Non-stationary Discrete-Time Linear–Quadratic Mean-Field Games in Multiple Populations

Special Issue : Multi-Agent Dynamic Decision Making and Learning

Premium Partner