Bottleneck routing with elastic demands. (English) Zbl 1525.91067
Summary: Bottleneck routing games are a well-studied model to investigate the impact of selfish behavior in communication networks. In this model, each user selects a path in a network for routing her fixed demand. The disutility of a user only depends on the most congested link visited. We extend this model by allowing users to continuously vary the demand rate at which data is sent along the chosen path. As our main result we establish tight conditions for the existence of pure strategy Nash equilibria.
MSC:
| 91A80 | Applications of game theory |
| 91A43 | Games involving graphs |
| 91B42 | Consumer behavior, demand theory |
References:
| [1] | Banner, R.; Orda, A., Bottleneck routing games in communication networks, IEEE J. Sel. Areas Commun., 25, 6, 1173-1179 (2007) |
| [2] | C. Busch, R. Kannan, A. Samman, Bottleneck routing games on grids, in: Proc. 2nd International ICST Conf. on Game Theory for Networks, 2011, pp. 294-307.; C. Busch, R. Kannan, A. Samman, Bottleneck routing games on grids, in: Proc. 2nd International ICST Conf. on Game Theory for Networks, 2011, pp. 294-307. |
| [3] | Busch, C.; Magdon-Ismail, M., Atomic routing games on maximum congestion, Theoret. Comput. Sci., 410, 36, 3337-3347 (2009) · Zbl 1168.91328 |
| [4] | I. Caragiannis, C. Galdi, C. Kaklamanis, Network load games, in: Proc. 16th International Symposium on Algorithms and Computation, 2005, pp. 809-818.; I. Caragiannis, C. Galdi, C. Kaklamanis, Network load games, in: Proc. 16th International Symposium on Algorithms and Computation, 2005, pp. 809-818. · Zbl 1175.68027 |
| [5] | R. Cole, Y. Dodis, T. Roughgarden, Bottleneck links, variable demand, and the tragedy of the commons, in: Proc. 17th Annual ACM-SIAM Sympos. on Discrete Algorithms, 2006, pp. 668-677.; R. Cole, Y. Dodis, T. Roughgarden, Bottleneck links, variable demand, and the tragedy of the commons, in: Proc. 17th Annual ACM-SIAM Sympos. on Discrete Algorithms, 2006, pp. 668-677. · Zbl 1192.91040 |
| [6] | Cominetti, R.; Guzman, C., Network congestion control with Markovian multipath routing, Math. Program. A, 147, 1-2, 231-251 (2014) · Zbl 1297.90013 |
| [7] | de Keijzer, B.; Schäfer, G.; Telelis, O., On the inefficiency of equilibria in linear bottleneck congestion games, (Kontogiannis, S.; Koutsoupias, E.; Spirakis, P., Proc. 3rd Internat. Sympos. Algorithmic Game Theory. Proc. 3rd Internat. Sympos. Algorithmic Game Theory, LNCS, vol. 6386 (2010)), 335-346 · Zbl 1310.91020 |
| [8] | Han, H.; Shakkottai, S.; Hollot, C. V.; Srikant, R.; Towsley, D. F., Multi-path TCP: a joint congestion control and routing scheme to exploit path diversity in the Internet, IEEE/ACM Trans. Netw., 16, 6, 1260-1271 (2006) |
| [9] | Harks, T.; Hoefer, M.; Klimm, M.; Skopalik, A., Computing pure Nash and strong equilibria in bottleneck congestion games, Math. Program. A, 141, 193-215 (2013) · Zbl 1288.91010 |
| [10] | Harks, T.; Hoefer, M.; Schewior, K.; Skopalik, A., Routing games with progressive filling, IEEE/ACM Trans. Netw., 24, 4, 2553-2562 (2016) |
| [11] | Harks, T.; Klimm, M., Equilibria in a class of aggregative location games, J. Math. Econom., 61, 211-220 (2015) · Zbl 1368.91007 |
| [12] | Harks, T.; Klimm, M., Congestion games with variable demands, Math. Oper. Res., 41, 1, 255-277 (2016) · Zbl 1347.91014 |
| [13] | Harks, T.; Klimm, M.; Möhring, R., Strong equilibria in games with the lexicographical improvement property, Internat. J. Game Theory, 42, 2, 461-482 (2012) · Zbl 1269.91023 |
| [14] | T. Harks, M. Klimm, M. Schneider, Bottleneck routing with elastic demands, in: Proc. 11th Internat. Conference on Web and Internet Econom., 2015, pp. 384-397.; T. Harks, M. Klimm, M. Schneider, Bottleneck routing with elastic demands, in: Proc. 11th Internat. Conference on Web and Internet Econom., 2015, pp. 384-397. · Zbl 1404.91056 |
| [15] | Kakutani, S., A generalization of Brouwer’s fixed point theorem, Duke Math. J., 8, 3, 457-458 (1941) · JFM 67.0742.03 |
| [16] | R. Kannan, C. Busch, Bottleneck congestion games with logarithmic price of anarchy, in: S. Kontogiannis, E. Koutsoupias, and P. Spirakis, editors, Proc. 3rd Internat. Sympos. Algorithmic Game Theory, Vol. 6386, 2010, pp. 222-233.; R. Kannan, C. Busch, Bottleneck congestion games with logarithmic price of anarchy, in: S. Kontogiannis, E. Koutsoupias, and P. Spirakis, editors, Proc. 3rd Internat. Sympos. Algorithmic Game Theory, Vol. 6386, 2010, pp. 222-233. · Zbl 1310.91015 |
| [17] | R. Kannan, C. Busch, A.V. Vasilakos, Optimal price of anarchy of polynomial and super-polynomial bottleneck congestion games, in: Proc. 2nd International ICST Conf. on Game Theory for Networks, 2011, pp. 308-320.; R. Kannan, C. Busch, A.V. Vasilakos, Optimal price of anarchy of polynomial and super-polynomial bottleneck congestion games, in: Proc. 2nd International ICST Conf. on Game Theory for Networks, 2011, pp. 308-320. |
| [18] | Kelly, F.; Maulloo, A.; Tan, D., Rate control in communication networks: Shadow prices, proportional fairness, and stability, J. Oper. Res. Soc., 49, 237-252 (1998) · Zbl 1111.90313 |
| [19] | Key, P. B.; Massoulié, L.; Towsley, D. F., Path selection and multipath congestion control, Commun. ACM, 54, 1, 109-116 (2011) |
| [20] | Key, P. B.; Proutiere, A., Routing games with elastic traffic, SIGMETRICS Perform. Eval. Rev., 37, 2, 63-64 (2009) |
| [21] | Khanna, A.; Zinky, J., The revised ARPANET routing metric, SIGCOMM Comput. Commun. Rev., 19, 4, 45-56 (1989) |
| [22] | Kolstad, C. D.; Mathiesen, L., Computing Cournot-Nash equilibria, Oper. Res., 39, 5, 739-748 (1991) · Zbl 0744.90006 |
| [23] | Korilis, Y.; Lazar, A., On the existence of equilibria in noncooperative optimal flow control, J. ACM, 42, 3, 584-613 (1995) · Zbl 0885.68015 |
| [24] | N. Kukushkin, Acyclicity of improvements in games with common intermediate objectives. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow, 2004.; N. Kukushkin, Acyclicity of improvements in games with common intermediate objectives. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow, 2004. |
| [25] | Kukushkin, N., Congestion games revisited, Internat. J. Game Theory, 36, 57-83 (2007) · Zbl 1134.91007 |
| [26] | K. Miller, T. Harks, Utility max-min fair congestion control with time-varying delays, in: Proc. 27th IEEE Internat. Conf. on Computer Comm., 2008, pp. 331-335.; K. Miller, T. Harks, Utility max-min fair congestion control with time-varying delays, in: Proc. 27th IEEE Internat. Conf. on Computer Comm., 2008, pp. 331-335. |
| [27] | Paganini, F.; Mallada, E., A unified approach to congestion control and node-based multipath routing, IEEE/ACM Trans. Netw., 17, 5, 1413-1426 (2009) |
| [28] | Qiu, L.; Yang, Y.; Zhang, Y.; Shenker, S., On selfish routing in Internet-like environments, IEEE/ACM Trans. Netw., 14, 4, 725-738 (2006) |
| [29] | Rosenthal, R., A class of games possessing pure-strategy Nash equilibria, Internat. J. Game Theory, 2, 1, 65-67 (1973) · Zbl 0259.90059 |
| [30] | Sheffi, Y., Urban Transportation Networks (1985), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ, USA |
| [31] | Shenker, S., Fundamental design issues for the future Internet, IEEE J. Sel. Areas Commun., 13, 1176-1188 (1995) |
| [32] | Srikant, R., The Mathematics of Internet Congestion Control (2003), Birkhäuser: Birkhäuser Basel, Switzerland · Zbl 1086.68018 |
| [33] | Voice, T., Stability of multi-path dual congestion control algorithms, IEEE/ACM Trans. Netw., 15, 6, 1231-1239 (2007) |
| [34] | Wardrop, J., Some theoretical aspects of road traffic research, Proc. Inst. Civ. Eng., 1, Part II, 325-378 (1952) |
| [35] | Yang, D.; Xue, G.; Fang, X.; Misra, S.; Zhang, J., A game-theoretic approach to stable routing in max-min fair networks, IEEE/ACM Trans. Netw., 21, 6, 1947-1959 (2013) |
| [36] | Zhang, Y.; Loguinov, D., On delay-independent diagonal stability of max-min congestion control, IEEE Trans. Automat. Control, 54, 5, 1111-1116 (2009) · Zbl 1367.93550 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
