Abstract
This chapter considers three fundamental problems in the general area of communication networks and their relationship to game theory. These problems are (i) allocation of shared bandwidth resources, (ii) routing across shared links, and (iii) scheduling across shared spectrum. Each problem inherently involves agents that experience negative externalities under which the presence of one degrades the utility perceived by others. Two approaches to solving such problems are (i) to find a globally optimal allocation and simply implement it in a fait accompli fashion, and (ii) request information from the competing agents (traffic flows) and construct a mechanism to allocate resources. Often, only the second option is viable, since a centralized solution using complete information might be impractical (or impossible) with many millions of competing flows, each one having private information about the application that it corresponds to. Hence, a game theoretical analysis of these problems is natural. In what follows, we will present results on each problem and characterize the efficiency loss that results from the mechanism employed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adlakha S, Johari R (2013) Mean field equilibrium in dynamic games with strategic complementarities. Oper Res 61(4):971–989
Benaïm M, Le Boudec J-Y (2008) A class of mean field interaction models for computer and communication systems. Perform Eval 65(11–12):823–838
Billingsley P (2009) Convergence of probability measures. Wiley-Interscience, Hoboken
Borkar V, Sundaresan R (2012) Asymptotics of the invariant measure in mean field models with jumps. Stoch Syst 2(2):322–380
Braess D (1968) Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung 12(1):258–268
Clarke EH (1971) Multipart pricing of public goods. Public Choice 11(1):17–33
Graham C, Méléard S (1994) Chaos hypothesis for a system interacting through shared resources. Probab Theory Relat Fields 100(2):157–174
Groves T (1973) Incentives in teams. Econometrica J Econom Soc 41(4):617–631
Hernández-Lerma O, de Ozak MM (1992) Discrete-time Markov control processes with discounted unbounded costs: optimality criteria. Kybernetika 28(3):191–212
Iyer K, Johari R, Sundararajan M (2014) Mean field equilibria of dynamic auctions with learning. Manag Sci 60(12):2949–2970
Johari R, Tsitsiklis JN (2004) Efficiency loss in a network resource allocation game. Math Oper Res 29(3):407–435
Johari R, Tsitsiklis JN (2005) Communication requirements of VCG-like mechanisms in convex environments. In: Proceedings of the Allerton Conference on Control, Communications and Computing, pp 1191–1196
Kelly FP (1997) Charging and rate control for elastic traffic. Eur Trans Telecommun 8:33–37
Li J, Xia B, Geng X, Ming H, Shakkottai S, Subramanian V, Xie L (2015) Energy coupon: a mean field game perspective on demand response in smart grids. ACM SIGMETRICS Perform Eval Rev 43(1):455–456
Li J, Bhattacharyya R, Paul S, Shakkottai S, Subramanian V (2017) Incentivizing sharing in realtime D2D streaming networks: a mean field game perspective. IEEE/ACM Trans Netw 25(1):3–17
Maheswaran RT, Basar T (2006) Efficient signal proportional allocation (ESPA) mechanisms: decentralized social welfare maximization for divisible resources. IEEE J Sel Areas Commun 24(5):1000–1009
Manjrekar M, Ramaswamy V, Shakkottai S (2014) A mean field game approach to scheduling in cellular systems. In: Proceedings IEEE INFOCOM, 2014, Toronto, pp 1554–1562
Meyn SP, Tweedie RL, Glynn PW (2009) Markov chains and stochastic stability, vol 2. Cambridge University Press, Cambridge
Pigou AC (1920) The economics of welfare. Palgrave Macmillan, New York
Roughgarden T (2015) Intrinsic robustness of the price of anarchy. J ACM 62(5):32
Roughgarden T (2016) Twenty lectures on algorithmic game theory. Cambridge University Press, Cambridge
Roughgarden T, Schoppmann F (2015) Local smoothness and the price of anarchy in splittable congestion games. J Econ Theory 156:317–342
Roughgarden T, Tardos E (2002) How bad is selfish routing? J ACM 49(2):236–259
Shakkottai S, Srikant R (2007) Network optimization and control. Found Tr Netw 2(3):271–379
Srikant R (2004) The mathematics of internet congestion control. Birkhauser, New York
Strauch RE (1966) Negative dynamic programming. Ann Math Stat 37(4):871–890
Tembine H, Le Boudec JY, El-Azouzi R, Altman E (2009) Mean field asymptotics of Markov decision evolutionary games and teams. In: International Conference on Game Theory for Networks (GameNets), pp 140–150
Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J Financ 16(1):8–37
Xu J, Hajek B (2012) The supermarket game. In: IEEE International Symposium on Information Theory (ISIT, 2012), Cambridge, pp 2511–2515
Yang S, Hajek B (2007) VCG-Kelly mechanisms for allocation of divisible goods: adapting VCG mechanisms to one-dimensional signals. IEEE J Sel Areas Commun 25(6):1237–1243
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this entry
Cite this entry
Shakkottai, S., Srikant, R. (2020). Communication Networks: Pricing, Congestion Control, Routing, and Scheduling. In: Basar, T., Zaccour, G. (eds) Handbook of Dynamic Game Theory. Springer, Cham. https://doi.org/10.1007/978-3-319-27335-8_29-2
Download citation
DOI: https://doi.org/10.1007/978-3-319-27335-8_29-2
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
Chapter history
-
Latest
Communication Networks: Pricing, Congestion Control, Routing, and Scheduling- Published:
- 02 December 2019
DOI: https://doi.org/10.1007/978-3-319-27335-8_29-2
-
Original
Communication Networks: Pricing, Congestion Control, Routing, and Scheduling- Published:
- 02 May 2017
DOI: https://doi.org/10.1007/978-3-319-27335-8_29-1