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 and 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-916. doi: 10.1109/TAC.2002.1008357.

[2]

G. W. Brown and J. von Neumann, Solutions of games by differential equations, in Contibutions to the Theory of Games, I (ed. H.W. Kuhn and A.W. Tucker), Ann. Math. Studies, 24 (1950), 73-79.

[3]

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

[4]

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

[5]

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

[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-1136. doi: 10.1287/opre.42.6.1120.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980.

[15]

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

[16]

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

[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-299.

[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-158. doi: 10.1287/trsc.31.2.147.

[19]

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

[20]

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

[21]

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

[22]

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

[23]

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

[24]

W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, Cambridge, MA, 2011.

[25]

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

[26]

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

[27]

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

[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-252. doi: 10.1287/trsc.18.3.245.

[29]

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

[30]

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

[31]

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

[32]

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

[33]

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

[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-980.

[35]

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

[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-112. doi: 10.1016/j.trb.2007.07.001.

[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-444. doi: 10.1023/A:1022610325133.

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-916. doi: 10.1109/TAC.2002.1008357.

[2]

G. W. Brown and J. von Neumann, Solutions of games by differential equations, in Contibutions to the Theory of Games, I (ed. H.W. Kuhn and A.W. Tucker), Ann. Math. Studies, 24 (1950), 73-79.

[3]

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

[4]

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

[5]

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

[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-1136. doi: 10.1287/opre.42.6.1120.

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980.

[15]

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

[16]

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

[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-299.

[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-158. doi: 10.1287/trsc.31.2.147.

[19]

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

[20]

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

[21]

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

[22]

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

[23]

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

[24]

W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, Cambridge, MA, 2011.

[25]

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

[26]

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

[27]

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

[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-252. doi: 10.1287/trsc.18.3.245.

[29]

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

[30]

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

[31]

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

[32]

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

[33]

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

[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-980.

[35]

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

[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-112. doi: 10.1016/j.trb.2007.07.001.

[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-444. doi: 10.1023/A:1022610325133.

[1]

Yannick Viossat. Game dynamics and Nash equilibria. Journal of Dynamics and 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 and 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 and 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 and 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 and 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 and 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]

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

[9]

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

[10]

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

[11]

Jewaidu Rilwan, Poom Kumam, Onésimo Hernández-Lerma. Stability of international pollution control games: A potential game approach. Journal of Dynamics and Games, 2022, 9 (2) : 191-202. doi: 10.3934/jdg.2022003

[12]

René Aïd, Roxana Dumitrescu, Peter Tankov. The entry and exit game in the electricity markets: A mean-field game approach. Journal of Dynamics and Games, 2021, 8 (4) : 331-358. doi: 10.3934/jdg.2021012

[13]

Abbas Ja'afaru Badakaya, Aminu Sulaiman Halliru, Jamilu Adamu. Game value for a pursuit-evasion differential game problem in a Hilbert space. Journal of Dynamics and Games, 2022, 9 (1) : 1-12. doi: 10.3934/jdg.2021019

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Stamatios Katsikas, Vassilli Kolokoltsov. Evolutionary, mean-field and pressure-resistance game modelling of networks security. Journal of Dynamics and Games, 2019, 6 (4) : 315-335. doi: 10.3934/jdg.2019021

[20]

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

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]