Skip to main content
SpringerLink
Log in

Network Games

  • Living reference work entry
  • First Online:
Handbook of Dynamic Game Theory

Abstract

This chapter provides a general overview of the topic of network games, its application in a number of areas, and recent advances, by focusing on four major types of games, namely, congestion games, resource allocation games, diffusion games, and network formation games. Several algorithmic aspects and methodologies for analyzing such games are discussed, and connections between network games and other relevant topical areas are identified.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Throughout this chapter, we refer to players as “he,” “she,” or “it” (“his,” “her,” or “its”) interchangeably, somewhat context dependent.

  2. 2.

    Another example arises in the transmission of pockets in communication networks, where because of fixed bandwidth, an increase in the rate leads to increase in transmission time (i.e., delay) and thus increase in cost.

  3. 3.

    A pure-strategy Nash equilibrium is an action profile from which no player has a unilateral incentive to change his strategy.

  4. 4.

    Polynomial local search (PLS) is a complexity class that models the difficulty of finding a locally optimal solution to an optimization problem. A PLS-complete problem refers to a “hardest” problem in this complexity class.

  5. 5.

    If instead of utility functions we were working with cost functions c i (⋅ ), i ∈ [n], then the definition of PoA will change to \(PoA = \frac{\max _{\boldsymbol{a}^{{\ast}}\in NE}\ c(\boldsymbol{a}^{{\ast}})} {\min _{\boldsymbol{a}\in \mathcal{A}}\ c(\boldsymbol{a})}\), where \(c: \mathcal{A}\rightarrow \mathbb{R}\) denotes the social cost function defined by \(c(\boldsymbol{a}) =\sum _{ i=1}^{n}c_{i}(\boldsymbol{a})\).

  6. 6.

    For a finite set \(\mathcal{S}\), a set function \(f(\cdot ): 2^{\mathcal{S}}\rightarrow \mathbb{R}\) is called sub-modular if \(f(\mathcal{X}\cup \{ s\}) - f(\mathcal{X}) \geq f(\mathcal{Y}\cup \{ s\}) - f(\mathcal{Y})\) for any \(\mathcal{X} \subseteq \mathcal{Y}\subseteq \mathcal{S}\), \(s \in \mathcal{S}\).

  7. 7.

    A dominating set of a graph is a subset of its vertices such that each edge has at least one end point in that set.

References

  • Ackermann H, Röglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J ACM (JACM) 55(6):25

    Article  MATH  MathSciNet  Google Scholar 

  • Alon N, Feldman M, Procaccia AD, Tennenholtz M (2010) A note on competitive diffusion through social networks. Inf Process Lett 110(6):221–225

    Article  MATH  MathSciNet  Google Scholar 

  • Alon N, Demaine ED, Hajiaghayi MT, Leighton T (2013) Basic network creation games. SIAM J Discret Math 27(2):656–668

    Article  MATH  MathSciNet  Google Scholar 

  • Alpcan T, Başar T (2010) Network security: a decision and game-theoretic approach. Cambridge University Press, Leiden

    Book  MATH  Google Scholar 

  • Altman E (2014) Bio-inspired paradigms in network engineering games. J Dyn Games (JDG) 1(1):1–15

    MATH  MathSciNet  Google Scholar 

  • Altman E, Boulogne T, El-Azouzi R, Jiménez T, Wynter L (2006) A survey on networking games in telecommunications. Comput Oper Res 33(2):286–311

    Article  MATH  MathSciNet  Google Scholar 

  • Anantharam V (2004) On the Nash dynamics of congestion games with player-specific utility. In: IEEE conference on decision and control, vol 5. IEEE, pp 4673–4678

    Google Scholar 

  • Awerbuch B, Azar Y, Epstein A, Mirrokni VS, Skopalik A (2008) Fast convergence to nearly optimal solutions in potential games. In: Proceedings of the 9th ACM conference on electronic commerce. ACM, pp 264–273

    Google Scholar 

  • Başar T (2007) Control and game-theoretic tools for communication networks. Appl Comput Math 6(2):104–125

    MATH  MathSciNet  Google Scholar 

  • Başar T, Olsder GJ (1998) Dynamic noncooperative game theory. SIAM, Philadelphia

    MATH  Google Scholar 

  • Blum A, Even-Dar E, Ligett K (2006) Routing without regret: on convergence to Nash equilibria of regret-minimizing algorithms in routing games. In: Proceedings of the twenty-fifth annual ACM symposium on principles of distributed computing. ACM, pp 45–52

    MATH  Google Scholar 

  • Bramoullé Y, Kranton R, D’amours M (2014) Strategic interaction and networks. Am Econ Rev 104(3):898–930

    Article  Google Scholar 

  • Bolouki S, Nedić A, Başar T (2017) Social networks. In: Başar T, Zaccour G (eds) Handbook of dynamic game theory. Springer International Publishing, Cham

    Google Scholar 

  • Caines PE, Huang M, Malhamé RP (2017) Mean field games. In: Başar T, Zaccour G (eds) Handbook of dynamic game theory. Springer International Publishing, Cham

    Google Scholar 

  • Chun B-G, Chaudhuri K, Wee H, Barreno M, Papadimitriou CH, Kubiatowicz J (2004) Selfish caching in distributed systems: a game-theoretic analysis. In: Proceedings of the twenty-third annual ACM symposium on principles of distributed computing. ACM, pp 21–30

    MATH  Google Scholar 

  • Correa JR, Schulz AS, Stier-Moses NE (2004) Selfish routing in capacitated networks. Math Oper Res 29(4):961–976

    Article  MATH  MathSciNet  Google Scholar 

  • Daskalakis C, Papadimitriou CH (2006) Computing pure Nash equilibria in graphical games via Markov random fields. In: Proceedings of the 7th ACM conference on electronic commerce. ACM, pp 91–99

    Google Scholar 

  • Demaine ED, Hajiaghayi MT, Mahini H, Zadimoghaddam M (2007) The price of anarchy in network creation games. In: Proceedings of the twenty-sixth annual ACM symposium on principles of distributed computing. ACM, pp 292–298

    MATH  Google Scholar 

  • Dürr C, Thang N (2007) Nash equilibria in Voronoi games on graphs. In: Algorithms-ESA, pp 17–28

    MATH  Google Scholar 

  • Eksin C, Molavi P, Ribeiro A, Jadbabaie A (2013) Learning in network games with incomplete information: asymptotic analysis and tractable implementation of rational behavior. IEEE Signal Process Mag 30(3):30–42

    Article  Google Scholar 

  • Etesami SR, Başar T (2015) Game-theoretic analysis of the Hegselmann-Krause model for opinion dynamics in finite dimensions. IEEE Trans Autom Control 60(7):1886–1897

    Article  MATH  MathSciNet  Google Scholar 

  • Etesami SR, Başar T (2016) Complexity of equilibrium in competitive diffusion games on social networks. Automatica 68:100–110

    Article  MATH  MathSciNet  Google Scholar 

  • Etesami SR, Başar T (2017a) Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game. Automatica 76:153–163

    Article  MATH  MathSciNet  Google Scholar 

  • Etesami SR, Başar T (2017b) Pure Nash equilibrium in a binary capacitated resource allocation game. IEEE Trans Control Netw Syst. doi:10.1109/TCNS.2016.2631440, http://ieeexplore.ieee.org/abstract/document/7752896/. Published online: 22 Nov 2016

  • Etesami SR, Saad W, Mandayam N, Poor HV (2017, to appear) Smart routing in smart grids. In: Proceedings of the 56th IEEE conference on decision and control, Melbourne, 12–15 Dec. https://arxiv.org/abs/1705.03805

  • Fabrikant A, Luthra A, Maneva E, Papadimitriou CH, Shenker S (2003) On a network creation game. In: Proceedings of the twenty-second annual symposium on principles of distributed computing. ACM, pp 347–351

    MATH  Google Scholar 

  • Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. In: Proceedings of the thirty-sixth annual ACM symposium on theory of computing. ACM, pp 604–612

    MATH  Google Scholar 

  • Galeotti A, Goyal S, Jackson MO, Vega-Redondo F, Yariv L (2010) Network games. Rev Econ Stud 77(1):218–244

    Article  MATH  MathSciNet  Google Scholar 

  • Gionis A, Terzi E, Tsaparas P (2013) Opinion maximization in social networks. In: Proceedings of the 2013 SIAM international conference on data mining. SIAM, pp 387–395

    Google Scholar 

  • Goemans MX, Li L, Mirrokni VS, Thottan M (2006) Market sharing games applied to content distribution in ad hoc networks. IEEE J Sel Areas Commun 24(5):1020–1033

    Article  Google Scholar 

  • Gopalakrishnan R, Kanoulas D, Karuturi NN, Rangan CP, Rajaraman R, Sundaram R (2012) Cache me if you can: capacitated selfish replication games. In: LATIN. Springer, pp 420–432

    MATH  Google Scholar 

  • Goyal S, Vega-Redondo F (2000) Learning, network formation and coordination. Technical report, Tinbergen Institute Discussion Paper

    MATH  Google Scholar 

  • Goyal S, Heidari H, Kearns M (2014) Competitive contagion in networks. Games Econ Behav. doi:10.1016/j.geb.2014.09.002, http://www.sciencedirect.com/science/article/pii/S0899825614001365?via\%3Dihub

  • Grossklags J, Christin N, Chuang J (2008) Secure or insure? A game-theoretic analysis of information security games. In: Proceedings of the 17th international conference on world wide web. ACM, pp 209–218

    Google Scholar 

  • Jackson MO (2005) A survey of network formation models: stability and efficiency. In: Group formation in economics: networks, clubs, and coalitions. Cambridge University Press, Cambridge, pp 11–49

    Chapter  Google Scholar 

  • Jackson MO (2010) Social and economic networks. Princeton University Press, Princeton

    MATH  Google Scholar 

  • Jackson MO, Watts A (2002) On the formation of interaction networks in social coordination games. Games Econ Behav, 41(2):265–291

    Article  MATH  MathSciNet  Google Scholar 

  • Jackson MO, Wolinsky A (1996) A strategic model of social and economic networks. J Econ Theory 71(1):44–74

    Article  MATH  MathSciNet  Google Scholar 

  • Jackson MO, Yariv L (2007) Diffusion of behavior and equilibrium properties in network games. Am Econ Rev 97(2):92–98

    Article  Google Scholar 

  • Jensen MK (2010) Aggregative games and best-reply potentials. Econ Theory 43(1):45–66

    Article  MATH  MathSciNet  Google Scholar 

  • Kawald B, Lenzner P (2013) On dynamics in selfish network creation. In: Proceedings of the twenty-fifth annual ACM symposium on parallelism in algorithms and architectures. ACM, pp 83–92

    Google Scholar 

  • Kearns M, Littman ML, Singh S (2001) Graphical models for game theory. In: Proceedings of the seventeenth conference on uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc., pp 253–260

    Google Scholar 

  • Krichene W, Reilly JD, Amin S, Bayen AM (2017) Stackelberg routing on parallel transportation networks. In: Başar T, Zaccour G (eds) Handbook of dynamic game theory. Springer International Publishing, Cham

    Google Scholar 

  • Koshal J, Nedić A, Shanbhag UV (2016) Distributed algorithms for aggregative games on graphs. Oper Res 64(3):680–704

    Article  MATH  MathSciNet  Google Scholar 

  • Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In: STACS

    Book  MATH  Google Scholar 

  • Laoutaris N, Telelis O, Zissimopoulos V, Stavrakakis I (2006) Distributed selfish replication. IEEE Trans Parallel Distrib Syst 17(12):1401–1413

    Article  Google Scholar 

  • Lenzner P (2011) On dynamics in basic network creation games. In: Algorithmic game theory. Springer, Berlin/London, pp 254–265

    Chapter  Google Scholar 

  • Li N, Marden JR (2013) Designing games for distributed optimization. IEEE J Sel Top Sign Proces 7(2):230–242

    Article  Google Scholar 

  • Liang X, Xiao Y (2012) Game theory for network security. IEEE Commun Surv Tutor 15(1):472–486

    Article  MathSciNet  Google Scholar 

  • Maheswaran RT, Başar T (2001) Decentralized network resource allocation as a repeated noncooperative market game. In: Proceedings of the 40th IEEE conference on decision and control, vol 5. IEEE, pp 4565–4570

    Google Scholar 

  • Marden JR, Roughgarden T (2014) Generalized efficiency bounds in distributed resource allocation. IEEE Trans Autom Control 59(3):571–584

    Article  MATH  MathSciNet  Google Scholar 

  • Marden JR, Arslan G, Shamma JS (2007) Regret based dynamics: convergence in weakly acyclic games. In: Proceedings of the 6th international joint conference on autonomous agents and multiagent systems. ACM, p 42

    Google Scholar 

  • Menache I, Ozdaglar A (2011) Network games: theory, models, and dynamics. Synth Lect Commun Netw 4(1):1–159

    Article  MATH  Google Scholar 

  • Milchtaich I (1996) Congestion games with player-specific payoff functions. Games Econ Behav 13(1):111–124

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  • Montanari A, Saberi A (2010) The spread of innovations in social networks. Proc Natl Acad Sci 107(47):20196–20201

    Article  Google Scholar 

  • Murray C (2012) Markets in political influence: rent-seeking, networks and groups. Technical report, University Library of Munich

    Google Scholar 

  • Nisan N, Roughgarden T, Tardos E, Vazirani VV (2007) Algorithmic game theory, vol 1. Cambridge University Press, Cambridge/New York

    Book  MATH  Google Scholar 

  • Pacifici V, Dan G (2012) Convergence in player-specific graphical resource allocation games. IEEE J Sel Areas Commun 30(11):2190–2199

    Article  Google Scholar 

  • Panagopoulou P, Spirakis P (2008) A game theoretic approach for efficient graph coloring. In: Algorithms and computation, pp 183–195

    MATH  Google Scholar 

  • Parise F, Gentile B, Grammatico S, Lygeros J (2015) Network aggregative games: distributed convergence to Nash equilibria. In: 54th annual conference on decision and control (CDC). IEEE, pp 2295–2300

    Google Scholar 

  • Pollatos GG, Telelis OA, Zissimopoulos V (2008) On the social cost of distributed selfish content replication. In: International conference on research in networking. Springer, pp 195–206

    Google Scholar 

  • Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2(1):65–67

    Article  MATH  MathSciNet  Google Scholar 

  • Roughgarden T (2002) Selfish routing. Technical report, Ph.D. Dissertation, Cornell University, Ithaca

    Google Scholar 

  • Roughgarden T, Schrijvers O (2016) Network cost-sharing without anonymity. ACM Trans Econ Comput 4(2):8

    Article  MATH  MathSciNet  Google Scholar 

  • Saad W, Han Z, Başar T, Debbah M, Hjorungnes A (2011) Network formation games among relay stations in next generation wireless networks. IEEE Trans Commun 59(9):2528–2542

    Article  Google Scholar 

  • Saad W, Zhou X, Maham B, Başar T, Poor HV (2012) Tree formation with physical layer security considerations in wireless multi-hop networks. IEEE Trans Wirel Commun 11(11):3980–3991

    Article  Google Scholar 

  • Shakkottai S, Srikant R (2017) Communication networks: pricing, congestion control, routing and scheduling. In: Başar T, Zaccour G (eds) Handbook of dynamic game theory. Springer International Publishing, Cham

    Google Scholar 

  • Singer Y (2012) How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In: Proceedings of the fifth ACM international conference on web search and data mining. ACM, pp 733–742

    Google Scholar 

  • Small L, Mason O (2013) Information diffusion on the iterated local transitivity model of online social networks. Discret Appl Math 161(10):1338–1344

    Article  MATH  MathSciNet  Google Scholar 

  • Tekin C, Liu M, Southwell R, Huang J, Ahmad SHA (2012) Atomic congestion games on graphs and their applications in networking. IEEE/ACM Trans Netw (TON) 20(5):1541–1552

    Article  Google Scholar 

  • Tzoumas V, Amanatidis C, Markakis E (2012) A game-theoretic analysis of a competitive diffusion process over social networks. In: Proceedings of the 8th international conference on internet and network economics. Springer, pp 1–14

    Google Scholar 

  • Vetta A (2002) Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: Proceedings of the 43rd annual IEEE symposium on foundations of computer science, 2002. IEEE, pp 416–425

    Google Scholar 

  • Young HP (2006) The diffusion of innovations in social networks. In: The economy as an evolving complex system III: current perspectives and future directions, vol 267. Oxford University Press, Oxford/New York

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, University of Illinois at Urbana-Champaign, 1308 W Main St, 61801, Urbana, IL, USA

    S. Rasoul Etesami

  2. Coordinated Science Laboratory and Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, 1308 West Main, 61801, Urbana, IL, USA

    Tamer Başar

Authors
  1. S. Rasoul Etesami
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tamer Başar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Rasoul Etesami .

Editor information

Editors and Affiliations

  1. Center for Advanced Study, University of Illinois Urbana-Champaign, Urbana, Illinois, USA

    Tamer Basar

  2. GERAD, HEC Montréal, Montreal, Québec, Canada

    Georges Zaccour

Section Editor information

  1. Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1308 West Main, 61801, Urbana, IL, USA

    Tamer Başar

  2. Département de sciences de la décision, GERAD, HEC Montréal, Montreal, QC, Canada

    Georges Zaccour

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this entry

Cite this entry

Etesami, S.R., Başar, T. (2017). Network Games. In: Basar, T., Zaccour, G. (eds) Handbook of Dynamic Game Theory. Springer, Cham. https://doi.org/10.1007/978-3-319-27335-8_10-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-27335-8_10-1

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-27335-8

  • Online ISBN: 978-3-319-27335-8

  • eBook Packages: Springer Reference Religion and PhilosophyReference Module Humanities and Social SciencesReference Module Humanities

Publish with us

Policies and ethics

Search

Navigation