×

Efficiency of atomic splittable selfish routing with polynomial cost functions. (English) Zbl 1162.90360

Summary: Previous works on the inefficiency of selfish routing have focused on the Wardropian traffic equilibria with an infinite number of infinitesimal players, each controlling a negligible fraction of the overall traffic, but only very limited pseudo-approximation results have been obtained for the atomic selfish routing game with a finite number of players. In this note we examine the price of anarchy of selfish routing with atomic Cournot-Nash players, each controlling a strictly positive splittable amount of flow. We obtain an upper bound of the inefficiency of equilibria with polynomial cost functions, and show that the bound is 1 or there is no efficiency loss when there is only one player, and the bound reduces to the result established in the literature when there are an infinite number of infinitesimal players.

MSC:

90B10 Deterministic network models in operations research
91B50 General equilibrium theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altman E, Basar T, Jimenez T, Shimkin N (2002) Competitive routing in networks with polynomial costs. IEEE Trans Automat Contr 47:92–96 · Zbl 1364.90077 · doi:10.1109/9.981725
[2] Awerbuch B, Azar Y, Epstein A (2005) The price of routing unsplittable flow. In: Proceedings of the 37th ACM Symposium on the theory of computing (to appear) · Zbl 1192.90099
[3] Chau CK, Sim KM (2003) The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Oper Res Lett 31:327–334 · Zbl 1052.91009 · doi:10.1016/S0167-6377(03)00030-0
[4] Correa JR, Schulz AS, Stier-Moses NE (2004) Selfish routing in capacitated networks. Math Oper Res 29:961–976 · Zbl 1082.90009 · doi:10.1287/moor.1040.0098
[5] Correa JR, Schulz AS, Stier Moses NE (2005) On the inefficiency of equilibria in congestion games. In: Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO 2005) (to appear) · Zbl 1119.91302
[6] Harker PT (1988) Multiple equilibrium behaviors on networks. Transp Sci 22:39–46 · Zbl 0638.90040 · doi:10.1287/trsc.22.1.39
[7] Haurie A, Marcotte P (1985) On the relationship between Nash–Cournot and Wardrop equilibria. Networks 15:295–308 · Zbl 0579.90030 · doi:10.1002/net.3230150303
[8] Papadimitriou CH (2001) Algorithms, games, and the internet. In: Proceedings of the 33rd Annual ACM Symposium on the theory of computing, pp 749–753 · Zbl 1323.68022
[9] Perakis G (2004) The price of anarchy when costs are nonlinear and asymmetric. Lect Notes Comput Sci 3064:46–58. Springer · Zbl 1092.90012 · doi:10.1007/978-3-540-25960-2_4
[10] Roughgarden T (2003) The price of anarchy is independent of the network topology. J Comput Syst Sci 67:341–364 · Zbl 1072.68025 · doi:10.1016/S0022-0000(03)00044-8
[11] Roughgarden T (2005a) Selfish routing and the price of anarchy. The MIT Press, Cambridge · Zbl 1318.68065
[12] Roughgarden T (2005b) Selfish routing with atomic players. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA05), pp 1184–1185 · Zbl 1297.91037
[13] Roughgarden T, Tardos E (2002) How bad is selfish routing? J ACM 49:236–259 · Zbl 1323.90011 · doi:10.1145/506147.506153
[14] Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in non-atomic congestion games. Games Econom Behav 47:389–403 · Zbl 1068.91002 · doi:10.1016/j.geb.2003.06.004
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.