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]

Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics & Games, 2014, 1 (3) : 537-553. doi: 10.3934/jdg.2014.1.537

[2]

William H. Sandholm. Local stability of strict equilibria under evolutionary game dynamics. Journal of Dynamics & Games, 2014, 1 (3) : 485-495. doi: 10.3934/jdg.2014.1.485

[3]

Astridh Boccabella, Roberto Natalini, Lorenzo Pareschi. On a continuous mixed strategies model for evolutionary game theory. Kinetic & Related Models, 2011, 4 (1) : 187-213. doi: 10.3934/krm.2011.4.187

[4]

Anna Lisa Amadori, Astridh Boccabella, Roberto Natalini. A hyperbolic model of spatial evolutionary game theory. Communications on Pure & Applied Analysis, 2012, 11 (3) : 981-1002. doi: 10.3934/cpaa.2012.11.981

[5]

Georgios Konstantinidis. A game theoretic analysis of the cops and robber game. Journal of Dynamics & Games, 2014, 1 (4) : 599-619. doi: 10.3934/jdg.2014.1.599

[6]

Scott G. McCalla. Paladins as predators: Invasive waves in a spatial evolutionary adversarial game. Discrete & Continuous Dynamical Systems - B, 2014, 19 (5) : 1437-1457. doi: 10.3934/dcdsb.2014.19.1437

[7]

John Cleveland. Basic stage structure measure valued evolutionary game model. Mathematical Biosciences & Engineering, 2015, 12 (2) : 291-310. doi: 10.3934/mbe.2015.12.291

[8]

Jiahua Zhang, Shu-Cherng Fang, Yifan Xu, Ziteng Wang. A cooperative game with envy. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2049-2066. doi: 10.3934/jimo.2017031

[9]

Ying Ji, Shaojian Qu, Fuxing Chen. Environmental game modeling with uncertainties. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 989-1003. doi: 10.3934/dcdss.2019067

[10]

David Cantala, Juan Sebastián Pereyra. Endogenous budget constraints in the assignment game. Journal of Dynamics & Games, 2015, 2 (3&4) : 207-225. doi: 10.3934/jdg.2015002

[11]

Tao Li, Suresh P. Sethi. A review of dynamic Stackelberg game models. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 125-159. doi: 10.3934/dcdsb.2017007

[12]

Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Two-person knapsack game. Journal of Industrial & Management Optimization, 2010, 6 (4) : 847-860. doi: 10.3934/jimo.2010.6.847

[13]

Hyeng Keun Koo, Shanjian Tang, Zhou Yang. A Dynkin game under Knightian uncertainty. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5467-5498. doi: 10.3934/dcds.2015.35.5467

[14]

Peter Bednarik, Josef Hofbauer. Discretized best-response dynamics for the Rock-Paper-Scissors game. Journal of Dynamics & Games, 2017, 4 (1) : 75-86. doi: 10.3934/jdg.2017005

[15]

King-Yeung Lam. Dirac-concentrations in an integro-pde model from evolutionary game theory. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 737-754. doi: 10.3934/dcdsb.2018205

[16]

Pierre Cardaliaguet, Chloé Jimenez, Marc Quincampoix. Pure and Random strategies in differential game with incomplete informations. Journal of Dynamics & Games, 2014, 1 (3) : 363-375. doi: 10.3934/jdg.2014.1.363

[17]

Sourabh Bhattacharya, Abhishek Gupta, Tamer Başar. Jamming in mobile networks: A game-theoretic approach. Numerical Algebra, Control & Optimization, 2013, 3 (1) : 1-30. doi: 10.3934/naco.2013.3.1

[18]

Ido Polak, Nicolas Privault. A stochastic newsvendor game with dynamic retail prices. Journal of Industrial & Management Optimization, 2018, 14 (2) : 731-742. doi: 10.3934/jimo.2017072

[19]

Eduardo Espinosa-Avila, Pablo Padilla Longoria, Francisco Hernández-Quiroz. Game theory and dynamic programming in alternate games. Journal of Dynamics & Games, 2017, 4 (3) : 205-216. doi: 10.3934/jdg.2017013

[20]

Lianju Sun, Ziyou Gao, Yiju Wang. A Stackelberg game management model of the urban public transport. Journal of Industrial & Management Optimization, 2012, 8 (2) : 507-520. doi: 10.3934/jimo.2012.8.507

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]