×

zbMATH — the first resource for mathematics

Bottleneck routing with elastic demands. (English) Zbl 1404.91056
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 384-397 (2015).
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 their fixed demand. The disutility of a used 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.
For the entire collection see [Zbl 1326.68026].

MSC:
91A43 Games involving graphs
90B18 Communication networks in operations research
91-04 Software, source code, etc. for problems pertaining to game theory, economics, and finance
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Banner, R., Orda, A.: Bottleneck routing games in communication networks. IEEE J. Sel. Area Commun. 25(6), 1173–1179 (2007) · doi:10.1109/JSAC.2007.070811
[2] Busch, C., Kannan, R., Samman, A.: Bottleneck routing games on grids. In: Proceedings 2nd International ICST Conference on Game Theory for Networks, pp. 294–307 (2011)
[3] Busch, C., Magdon-Ismail, M.: Atomic routing games on maximum congestion. Theor. Comput. Sci. 410(36), 3337–3347 (2009) · Zbl 1168.91328 · doi:10.1016/j.tcs.2009.04.015
[4] Caragiannis, I., Galdi, C., Kaklamanis, C.: Network load games. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 809–818. Springer, Heidelberg (2005) · Zbl 1175.68027 · doi:10.1007/11602613_81
[5] Cole, R., Dodis, Y., Roughgarden, T.: Bottleneck links, variable demand, and the tragedy of the commons. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 668–677 (2006) · Zbl 1192.91040 · doi:10.1145/1109557.1109630
[6] Cominetti, R., Guzman, C.: Network congestion control with markovian multipath routing. Math. Program. Ser. A 147(1–2), 231–251 (2014) · Zbl 1297.90013 · doi:10.1007/s10107-013-0719-z
[7] de Keijzer, B., Schäfer, G., Telelis, O.A.: On the inefficiency of equilibria in linear bottleneck congestion games. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 335–346. Springer, Heidelberg (2010) · Zbl 1310.91020 · doi:10.1007/978-3-642-16170-4_29
[8] Gai, Y., Liu, H., Krishnamachari, B.: A packet dropping mechanism for efficient operation of \[ M/M/1 \]
queues with selfish users. In: Proceedings of the 30th IEEE International Conference on Computer Communications, pp. 2687–2695 (2011)
[9] 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) · doi:10.1109/TNET.2006.886738
[10] Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure nash and strong equilibria in bottleneck congestion games. Math. Program. Ser. A 141, 193–215 (2013) · Zbl 1288.91010 · doi:10.1007/s10107-012-0521-3
[11] Harks, T., Hoefer, M., Schewior, K., Skopalik, A.: Routing games with progressive filling. In: Proceedings of the 33rd IEEE International Conference on Computer Communications, pp. 352–360 (2014) · doi:10.1109/INFOCOM.2014.6847957
[12] Harks, T., Klimm, M.: Congestion games with variable demands. In: Apt, K. (ed.) Proceedings of the 13th Conference Theoretical Aspects of Rationality and Knowledge, pp. 111–120 (2011) · Zbl 1347.91014 · doi:10.1145/2000378.2000391
[13] Harks, T., Klimm, M.: Equilibria in a class of aggregative location games. J. Math. Econom. (2015) forthcoming · Zbl 1368.91007 · doi:10.1016/j.jmateco.2015.09.006
[14] 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 · doi:10.1007/s00182-012-0322-1
[15] Kakutani, S.: A generalization of Brouwer’s fixed point theorem. Duke Math. J. 8(3), 457–458 (1941) · JFM 67.0742.03 · doi:10.1215/S0012-7094-41-00838-4
[16] Kannan, R., Busch, C.: Bottleneck congestion games with logarithmic price of anarchy. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 222–233. Springer, Heidelberg (2010) · Zbl 1310.91015 · doi:10.1007/978-3-642-16170-4_20
[17] Kannan, R., Busch, C., Vasilakos, A.V.: Optimal price of anarchy of polynomial and super-polynomial bottleneck congestion games. In: Jain, R., Kannan, R. (eds.) GAMENETS 2011. LNICST, vol. 75, pp. 308–320. Springer, Heidelberg (2012) · doi:10.1007/978-3-642-30373-9_22
[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 · doi:10.1057/palgrave.jors.2600523
[19] Keshav, S.: An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network. Addison-Wesley, Boston (1997)
[20] Key, P.B., Massoulié, L., Towsley, D.F.: Path selection and multipath congestion control. Commun. ACM 54(1), 109–116 (2011) · Zbl 05892575 · doi:10.1145/1866739.1866762
[21] Key, P.B., Proutiere, A.: Routing games with elastic traffic. SIGMETRICS Perform. Eval. Rev. 37(2), 63–64 (2009) · doi:10.1145/1639562.1639587
[22] Korilis, Y., Lazar, A.: On the existence of equilibria in noncooperative optimal flow control. J. ACM 42(3), 584–613 (1995) · Zbl 0885.68015 · doi:10.1145/210346.210415
[23] Kukushkin, N.: Acyclicity of improvements in games with common intermediate objectives. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow (2004)
[24] Kukushkin, N.: Congestion games revisited. Internat. J. Game Theory 36, 57–83 (2007) · Zbl 1134.91007 · doi:10.1007/s00182-007-0090-5
[25] Miller, K., Harks, T.: Utility max-min fair congestion control with time-varying delays. In: Proceedings of the 27th IEEE International Conference on Computer Communicatins, pp. 331–335 (2008) · doi:10.1109/INFOCOM.2008.75
[26] Paganini, F., Mallada, E.: A unified approach to congestion control and node-based multipath routing. IEEE/ACM Trans. Netw. 17(5), 1413–1426 (2009) · doi:10.1109/TNET.2008.2011902
[27] Qiu, L., Yang, Y., Zhang, Y., Shenker, S.: On selfish routing in Internet-like environments. IEEE/ACM Trans. Netw. 14(4), 725–738 (2006) · doi:10.1109/TNET.2006.880179
[28] Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1), 65–67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[29] Sheffi, Y.: Urban Transp. Netw. Prentice-Hall, Upper Saddle River (1985)
[30] Shenker, S.: Fundamental design issues for the future Internet. IEEE J. Sel. Area Commun. 13, 1176–1188 (1995) · doi:10.1109/49.414637
[31] Srikant, R.: The Mathematics of Internet Congestion Control. Birkhäuser, Basel (2003) · Zbl 1086.68018
[32] Voice, T.: Stability of multi-path dual congestion control algorithms. IEEE/ACM Trans. Netw. 15(6), 1231–1239 (2007) · doi:10.1109/TNET.2007.899011
[33] Wardrop, J.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers (Part II), vol. 1, pp. 325–378 (1952) · doi:10.1680/ipeds.1952.11362
[34] Wydrowski, B., Andrew, L.L.H., Zukerman, M.: Maxnet: a congestion control architecture for scalable networks. IEEE Commun. Lett. 7, 511–513 (2003) · doi:10.1109/LCOMM.2003.818888
[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) · doi:10.1109/TNET.2013.2247416
[36] Zhang, Y., Kang, S., Loguinov, D.: Delay-independent stability and performance of distributed congestion control. IEEE/ACM Trans. Netw. 15(4), 838–851 (2007) · doi:10.1109/TNET.2007.896169
[37] Zhang, Y., Leonard, D., Loguinov, D.: Jetmax: scalable max-min congestion control for high-speed heterogeneous networks. Comput. Netw. 52(6), 1193–1219 (2008) · Zbl 1135.68336 · doi:10.1016/j.comnet.2007.11.021
[38] Zhang, Y., Loguinov, D.: On delay-independent diagonal stability of max-min congestion control. IEEE Trans. Autom. Control 54(5), 1111–1116 (2009) · Zbl 1367.93550 · doi:10.1109/TAC.2009.2013005
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.