January  2016, 3(1): 101-120. doi: 10.3934/jdg.2016005

Finite composite games: Equilibria and dynamics

1. 

Sorbonne Universités, UPMC Univ Paris 06, Institut de Mathématiques de Jussieu-Paris Rive Gauche, UMR 7586, CNRS, Univ Paris Diderot, Sorbonne Paris Cité, F-75005, Paris

2. 

Department of Economics, University of Oxford, Nuffield College, New Road, Oxford, OX1 1NF, United Kingdom

Received  March 2015 Revised  February 2016 Published  March 2016

We study games with finitely many participants, each having finitely many choices. We consider the following categories of participants:
(I) populations: sets of nonatomic agents,
(II) atomic splittable players,
(III) atomic non splittable players.
We recall and compare the basic properties, expressed through variational inequalities, concerning equilibria, potential games and dissipative games, as well as evolutionary dynamics.
    Then we consider composite games where the three categories of participants are present, a typical example being congestion games, and extend the previous properties of equilibria and dynamics.
    Finally we describe an instance of composite potential game.
Citation: Sylvain Sorin, Cheng Wan. Finite composite games: Equilibria and dynamics. Journal of Dynamics & Games, 2016, 3 (1) : 101-120. doi: 10.3934/jdg.2016005
References:
[1]

T. Boulogne, E. Altman, O. Pourtallier and H. Kameda, Mixed equilibrium for multiclass routing game,, IEEE Trans. Automat. Control, 47 (2002), 903.  doi: 10.1109/TAC.2002.1008357.  Google Scholar

[2]

G. W. Brown and J. von Neumann, Solutions of games by differential equations,, in Contibutions to the Theory of Games, 24 (1950), 73.   Google Scholar

[3]

R. Cominetti, J. Correa and N. Stier-Moses, The impact of oligopolistic competition in networks,, Oper. Res., 57 (2009), 1421.  doi: 10.1287/opre.1080.0653.  Google Scholar

[4]

S. C. Dafermos, Traffic equilibrium and variational inequalities,, Transportation Sci., 14 (1980), 42.  doi: 10.1287/trsc.14.1.42.  Google Scholar

[5]

P. Dupuis and A. Nagurney, Dynamical systems and variational inequalities,, Ann. Oper. Res., 44 (1993), 9.  doi: 10.1007/BF02073589.  Google Scholar

[6]

T. L. Friesz, D. Bernstein, N. J. Mehta, R. L. Tobin and S. Ganjalizadeh, Day-to-day dynamic network disequilibria and idealized traveler information systems,, Oper. Res., 42 (1994), 1120.  doi: 10.1287/opre.42.6.1120.  Google Scholar

[7]

I. Gilboa and A. Matsui, Social stability and equilibrium,, Econometrica, 59 (1991), 859.  doi: 10.2307/2938230.  Google Scholar

[8]

P. T. Harker, Multiple equilibrium behaviors on networks,, Transportation Sci., 22 (1988), 39.  doi: 10.1287/trsc.22.1.39.  Google Scholar

[9]

S. Hart and A. Mas-Colell, Uncoupled dynamics do not lead to Nash equilibrium,, Am. Econ. Rev., 93 (2003), 1830.   Google Scholar

[10]

A. Haurie and P. Marcotte, On the relationship between Nash-Cournot and Wardrop equilibria,, Networks, 15 (1985), 295.  doi: 10.1002/net.3230150303.  Google Scholar

[11]

J. Hofbauer, From Nash and Brown to Maynard Smith: Equilibria, dynamics and ESS,, Selection, 1 (2000), 81.  doi: 10.1556/Select.1.2000.1-3.8.  Google Scholar

[12]

J. Hofbauer and W. H. Sandholm, Stable games and their dynamics,, J. Econom. Theory, 144 (2009), 1665.  doi: 10.1016/j.jet.2009.01.007.  Google Scholar

[13]

J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics,, Cambridge University Press, (1998).  doi: 10.1017/CBO9781139173179.  Google Scholar

[14]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications,, Academic Press, (1980).   Google Scholar

[15]

R. Lahkar and W. H. Sandholm, The projection dynamic and the geometry of population games,, Games Econom. Behav., 64 (2008), 565.  doi: 10.1016/j.geb.2008.02.002.  Google Scholar

[16]

D. Monderer and L. S. Shapley, Potential games,, Games Econom. Behav., 14 (1996), 124.  doi: 10.1006/game.1996.0044.  Google Scholar

[17]

J. J. Moreau, Proximité et dualité dans un espace hilbertien,, (French) [Proximity and duality in a Hilbert space] Bull. Soc. Math. France, 93 (1965), 273.   Google Scholar

[18]

A. Nagurney and D. Zhang, Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria,, Transportation Sci., 31 (1997), 147.  doi: 10.1287/trsc.31.2.147.  Google Scholar

[19]

M. Pappalardo and M. Passacantando, Stability for equilibrium problems: From variational inequalities to dynamical systems,, J. Optim. Theory Appl., 113 (2002), 567.  doi: 10.1023/A:1015312921888.  Google Scholar

[20]

M. Pappalardo and M. Passacantando, Gap functions and Lyapunov functions,, J. Global Optim., 28 (2004), 379.  doi: 10.1023/B:JOGO.0000026455.72523.ed.  Google Scholar

[21]

W. H. Sandholm, Potential games with continuous player sets,, J. Econom. Theory, 97 (2001), 81.  doi: 10.1006/jeth.2000.2696.  Google Scholar

[22]

W. H. Sandholm, Excess payoff dynamics and other well-behaved evolutionary dynamics,, J. Econom. Theory, 124 (2005), 149.  doi: 10.1016/j.jet.2005.02.003.  Google Scholar

[23]

W. H. Sandholm, Pairwise comparison dynamics and evolutionary foundations for Nash equilibrium,, Games, 1 (2010), 3.  doi: 10.3390/g1010003.  Google Scholar

[24]

W. H. Sandholm, Population Games and Evolutionary Dynamics,, MIT Press, (2011).   Google Scholar

[25]

R. Selten, Preispolitik der Mehrproduktenunternehmung in der Statischen Theorie,, Springer-Verlag, (1970).  doi: 10.1007/978-3-642-48888-7.  Google Scholar

[26]

M. J. Smith, The existence, uniqueness and stability of traffic equilibria,, Transportation Res. Part B, 13 (1979), 295.  doi: 10.1016/0191-2615(79)90022-5.  Google Scholar

[27]

M. J. Smith, An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow function,, Transportation Res. Part B, 17 (1983), 365.  doi: 10.1016/0191-2615(83)90003-6.  Google Scholar

[28]

M. J. Smith, The stability of a dynamic model of traffic assignment - an application of a method of Lyapunov,, Transportation Sci., 18 (1984), 245.  doi: 10.1287/trsc.18.3.245.  Google Scholar

[29]

M. J. Smith, A descent algorithm for solving monotone variational inequalities and monotone complementarity problems,, J. Optim. Theory Appl., 44 (1984), 485.  doi: 10.1007/BF00935463.  Google Scholar

[30]

J. M. Swinkels, Adjustment dynamics and rational play in games,, Games Econom. Behav., 5 (1993), 455.  doi: 10.1006/game.1993.1025.  Google Scholar

[31]

P. D. Taylor and L. B. Jonker, Evolutionary stable strategies and game dynamics,, Math. Biosci., 40 (1978), 145.  doi: 10.1016/0025-5564(78)90077-9.  Google Scholar

[32]

E. Tsakas and M. Voorneveld, The target projection dynamic,, Games Econom. Behav., 67 (2009), 708.  doi: 10.1016/j.geb.2009.01.003.  Google Scholar

[33]

C. Wan, Coalitions in network congestion games,, Math. Oper. Res., 37 (2012), 654.  doi: 10.1287/moor.1120.0552.  Google Scholar

[34]

C. Wan, Jeux de congestion dans les réseaux Partie I. Modèles et équilibres,, (French) [Network congstion games Part I. Models and equilibria] Tech. Sci. Inform., 32 (2013), 951.   Google Scholar

[35]

G. Wardrop, Some theoretical aspects of road traffic research communication networks,, Proc. Inst. Civ. Eng., 1 (1952), 325.   Google Scholar

[36]

H. Yang and X. Zhang, Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors,, Transportation Res. Part B, 42 (2008), 99.  doi: 10.1016/j.trb.2007.07.001.  Google Scholar

[37]

D. Zhang and A. Nagurney, Formulation, stability, and computation of traffic network equilibria as projected dynamical systems,, J. Optim. Theory Appl., 93 (1997), 417.  doi: 10.1023/A:1022610325133.  Google Scholar

show all references

References:
[1]

T. Boulogne, E. Altman, O. Pourtallier and H. Kameda, Mixed equilibrium for multiclass routing game,, IEEE Trans. Automat. Control, 47 (2002), 903.  doi: 10.1109/TAC.2002.1008357.  Google Scholar

[2]

G. W. Brown and J. von Neumann, Solutions of games by differential equations,, in Contibutions to the Theory of Games, 24 (1950), 73.   Google Scholar

[3]

R. Cominetti, J. Correa and N. Stier-Moses, The impact of oligopolistic competition in networks,, Oper. Res., 57 (2009), 1421.  doi: 10.1287/opre.1080.0653.  Google Scholar

[4]

S. C. Dafermos, Traffic equilibrium and variational inequalities,, Transportation Sci., 14 (1980), 42.  doi: 10.1287/trsc.14.1.42.  Google Scholar

[5]

P. Dupuis and A. Nagurney, Dynamical systems and variational inequalities,, Ann. Oper. Res., 44 (1993), 9.  doi: 10.1007/BF02073589.  Google Scholar

[6]

T. L. Friesz, D. Bernstein, N. J. Mehta, R. L. Tobin and S. Ganjalizadeh, Day-to-day dynamic network disequilibria and idealized traveler information systems,, Oper. Res., 42 (1994), 1120.  doi: 10.1287/opre.42.6.1120.  Google Scholar

[7]

I. Gilboa and A. Matsui, Social stability and equilibrium,, Econometrica, 59 (1991), 859.  doi: 10.2307/2938230.  Google Scholar

[8]

P. T. Harker, Multiple equilibrium behaviors on networks,, Transportation Sci., 22 (1988), 39.  doi: 10.1287/trsc.22.1.39.  Google Scholar

[9]

S. Hart and A. Mas-Colell, Uncoupled dynamics do not lead to Nash equilibrium,, Am. Econ. Rev., 93 (2003), 1830.   Google Scholar

[10]

A. Haurie and P. Marcotte, On the relationship between Nash-Cournot and Wardrop equilibria,, Networks, 15 (1985), 295.  doi: 10.1002/net.3230150303.  Google Scholar

[11]

J. Hofbauer, From Nash and Brown to Maynard Smith: Equilibria, dynamics and ESS,, Selection, 1 (2000), 81.  doi: 10.1556/Select.1.2000.1-3.8.  Google Scholar

[12]

J. Hofbauer and W. H. Sandholm, Stable games and their dynamics,, J. Econom. Theory, 144 (2009), 1665.  doi: 10.1016/j.jet.2009.01.007.  Google Scholar

[13]

J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics,, Cambridge University Press, (1998).  doi: 10.1017/CBO9781139173179.  Google Scholar

[14]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications,, Academic Press, (1980).   Google Scholar

[15]

R. Lahkar and W. H. Sandholm, The projection dynamic and the geometry of population games,, Games Econom. Behav., 64 (2008), 565.  doi: 10.1016/j.geb.2008.02.002.  Google Scholar

[16]

D. Monderer and L. S. Shapley, Potential games,, Games Econom. Behav., 14 (1996), 124.  doi: 10.1006/game.1996.0044.  Google Scholar

[17]

J. J. Moreau, Proximité et dualité dans un espace hilbertien,, (French) [Proximity and duality in a Hilbert space] Bull. Soc. Math. France, 93 (1965), 273.   Google Scholar

[18]

A. Nagurney and D. Zhang, Projected dynamical systems in the formulation, stability analysis, and computation of fixed demand traffic network equilibria,, Transportation Sci., 31 (1997), 147.  doi: 10.1287/trsc.31.2.147.  Google Scholar

[19]

M. Pappalardo and M. Passacantando, Stability for equilibrium problems: From variational inequalities to dynamical systems,, J. Optim. Theory Appl., 113 (2002), 567.  doi: 10.1023/A:1015312921888.  Google Scholar

[20]

M. Pappalardo and M. Passacantando, Gap functions and Lyapunov functions,, J. Global Optim., 28 (2004), 379.  doi: 10.1023/B:JOGO.0000026455.72523.ed.  Google Scholar

[21]

W. H. Sandholm, Potential games with continuous player sets,, J. Econom. Theory, 97 (2001), 81.  doi: 10.1006/jeth.2000.2696.  Google Scholar

[22]

W. H. Sandholm, Excess payoff dynamics and other well-behaved evolutionary dynamics,, J. Econom. Theory, 124 (2005), 149.  doi: 10.1016/j.jet.2005.02.003.  Google Scholar

[23]

W. H. Sandholm, Pairwise comparison dynamics and evolutionary foundations for Nash equilibrium,, Games, 1 (2010), 3.  doi: 10.3390/g1010003.  Google Scholar

[24]

W. H. Sandholm, Population Games and Evolutionary Dynamics,, MIT Press, (2011).   Google Scholar

[25]

R. Selten, Preispolitik der Mehrproduktenunternehmung in der Statischen Theorie,, Springer-Verlag, (1970).  doi: 10.1007/978-3-642-48888-7.  Google Scholar

[26]

M. J. Smith, The existence, uniqueness and stability of traffic equilibria,, Transportation Res. Part B, 13 (1979), 295.  doi: 10.1016/0191-2615(79)90022-5.  Google Scholar

[27]

M. J. Smith, An algorithm for solving asymmetric equilibrium problems with a continuous cost-flow function,, Transportation Res. Part B, 17 (1983), 365.  doi: 10.1016/0191-2615(83)90003-6.  Google Scholar

[28]

M. J. Smith, The stability of a dynamic model of traffic assignment - an application of a method of Lyapunov,, Transportation Sci., 18 (1984), 245.  doi: 10.1287/trsc.18.3.245.  Google Scholar

[29]

M. J. Smith, A descent algorithm for solving monotone variational inequalities and monotone complementarity problems,, J. Optim. Theory Appl., 44 (1984), 485.  doi: 10.1007/BF00935463.  Google Scholar

[30]

J. M. Swinkels, Adjustment dynamics and rational play in games,, Games Econom. Behav., 5 (1993), 455.  doi: 10.1006/game.1993.1025.  Google Scholar

[31]

P. D. Taylor and L. B. Jonker, Evolutionary stable strategies and game dynamics,, Math. Biosci., 40 (1978), 145.  doi: 10.1016/0025-5564(78)90077-9.  Google Scholar

[32]

E. Tsakas and M. Voorneveld, The target projection dynamic,, Games Econom. Behav., 67 (2009), 708.  doi: 10.1016/j.geb.2009.01.003.  Google Scholar

[33]

C. Wan, Coalitions in network congestion games,, Math. Oper. Res., 37 (2012), 654.  doi: 10.1287/moor.1120.0552.  Google Scholar

[34]

C. Wan, Jeux de congestion dans les réseaux Partie I. Modèles et équilibres,, (French) [Network congstion games Part I. Models and equilibria] Tech. Sci. Inform., 32 (2013), 951.   Google Scholar

[35]

G. Wardrop, Some theoretical aspects of road traffic research communication networks,, Proc. Inst. Civ. Eng., 1 (1952), 325.   Google Scholar

[36]

H. Yang and X. Zhang, Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors,, Transportation Res. Part B, 42 (2008), 99.  doi: 10.1016/j.trb.2007.07.001.  Google Scholar

[37]

D. Zhang and A. Nagurney, Formulation, stability, and computation of traffic network equilibria as projected dynamical systems,, J. Optim. Theory Appl., 93 (1997), 417.  doi: 10.1023/A:1022610325133.  Google Scholar

[1]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[2]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047

[3]

David W. K. Yeung, Yingxuan Zhang, Hongtao Bai, Sardar M. N. Islam. Collaborative environmental management for transboundary air pollution problems: A differential levies game. Journal of Industrial & Management Optimization, 2021, 17 (2) : 517-531. doi: 10.3934/jimo.2019121

[4]

Youming Guo, Tingting Li. Optimal control strategies for an online game addiction model with low and high risk exposure. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020347

[5]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[6]

Qingfeng Zhu, Yufeng Shi. Nonzero-sum differential game of backward doubly stochastic systems with delay and applications. Mathematical Control & Related Fields, 2021, 11 (1) : 73-94. doi: 10.3934/mcrf.2020028

[7]

Zhongbao Zhou, Yanfei Bai, Helu Xiao, Xu Chen. A non-zero-sum reinsurance-investment game with delay and asymmetric information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 909-936. doi: 10.3934/jimo.2020004

[8]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[9]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[10]

Ebraheem O. Alzahrani, Muhammad Altaf Khan. Androgen driven evolutionary population dynamics in prostate cancer growth. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020426

[11]

Wenrui Hao, King-Yeung Lam, Yuan Lou. Ecological and evolutionary dynamics in advective environments: Critical domain size and boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 367-400. doi: 10.3934/dcdsb.2020283

[12]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[13]

José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020376

[14]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006

[15]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378

[16]

Andrew D. Lewis. Erratum for "nonholonomic and constrained variational mechanics". Journal of Geometric Mechanics, 2020, 12 (4) : 671-675. doi: 10.3934/jgm.2020033

[17]

Xiaoming Wang. Upper semi-continuity of stationary statistical properties of dissipative systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 521-540. doi: 10.3934/dcds.2009.23.521

[18]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331

[19]

Xing-Bin Pan. Variational and operator methods for Maxwell-Stokes system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3909-3955. doi: 10.3934/dcds.2020036

[20]

Constantine M. Dafermos. A variational approach to the Riemann problem for hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 185-195. doi: 10.3934/dcds.2009.23.185

 Impact Factor: 

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]