×

Improving the price of anarchy for selfish routing via coordination mechanisms. (English) Zbl 1291.91037

Summary: We reconsider the well-studied Selfish Routing game with affine latency functions. The Price of Anarchy for this class of games takes maximum value \(4/3\); this maximum is attained already for a simple network of two parallel links, known as Pigou’s network. We improve upon the value \(4/3\) by means of Coordination Mechanisms.
We increase the latency functions of the edges in the network, i.e., if \(\ell_e(x)\) is the latency function of an edge \(e\), we replace it by \(\hat\ell_e(x)\) with \(\ell_e(x)\leq\hat\ell_e(x)\) for all \(x\). Then an adversary fixes a demand rate as input. The engineered Price of Anarchy of the mechanism is defined as the worst-case ratio of the Nash social cost in the modified network over the optimal social cost in the original network. Formally, if \(\hat C_N(r)\) denotes the cost of the worst Nash flow in the modified network for rate \(r\) and \(C_{\mathrm{opt}}(r)\) denotes the cost of the optimal flow in the original network for the same rate then \[ e\mathrm{PoA} = \max\limits_{r\geq 0}\frac{\hat C_N(r)}{C_{\mathrm{opt}}(r)}. \] We first exhibit a simple coordination mechanism that achieves for any network of parallel links an engineered Price of Anarchy strictly less than \(4/3\). For the case of two parallel links our basic mechanism gives \(5/4=1.25\). Then, for the case of two parallel links, we describe an optimal mechanism; its engineered Price of Anarchy lies between \(1.191\) and \(1.192\).

MSC:

91A43 Games involving graphs
91A10 Noncooperative games
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angel, E., Bampis, E., Pascual, F.: Truthful algorithms for scheduling selfish tasks on parallel machines. Theor. Comput. Sci. 369(1-3), 157-168 (2006) · Zbl 1140.90025 · doi:10.1016/j.tcs.2006.07.057
[2] Angel, E., Bampis, E., Pascual, F., Tchetgnia, A.-A.: On truthfulness and approximation for scheduling selfish tasks. J. Sched. 12(5), 437-445 (2009) · Zbl 1177.90141 · doi:10.1007/s10951-009-0118-8
[3] Azar, Y.; Jain, K.; Mirrokni, V. S., (Almost) optimal coordination mechanisms for unrelated machine scheduling, 323-332 (2008) · Zbl 1192.90060
[4] Bernstein, D., Smith, T.E.: Equilibria for networks with lower semicontinuous costs: with an application to congestion pricing. Transp. Sci. 28(3), 221-235 (1994) · Zbl 0814.90022 · doi:10.1287/trsc.28.3.221
[5] Bonifaci, V.; Salek, M.; Schäfer, G., On the efficiency of restricted tolls in network routing games, 302-313 (2011) · Zbl 1233.90077
[6] Caragiannis, I., Efficient coordination mechanisms for unrelated machine scheduling, 815-824 (2009) · Zbl 1423.90082
[7] Christodoulou, G.; Gourvès, L.; Pascual, F., Scheduling selfish tasks: about the performance of truthful algorithms, 187-197 (2007) · Zbl 1206.90041
[8] Christodoulou, G., Koutsoupias, E., Nanavati, A.: Coordination mechanisms. Theor. Comput. Sci. 410(36), 3327-3336 (2009) · Zbl 1177.91016 · doi:10.1016/j.tcs.2009.01.005
[9] Christodoulou, G.; Mehlhorn, K.; Pyrga, E., Improving the price of anarchy for selfish routing via coordination mechanisms, 119-130 (2011) · Zbl 1346.91021
[10] Cole, R.; Dodis, Y.; Roughgarden, T., Pricing network edges for heterogeneous selfish users, 521-530 (2003) · Zbl 1192.68032
[11] Cole, R., Dodis, Y., Roughgarden, T.: How much can taxes help selfish routing? J. Comput. Syst. Sci. 72(3), 444-467 (2006) · Zbl 1103.68018 · doi:10.1016/j.jcss.2005.09.010
[12] Cole, R.; Correa, J. R.; Gkatzelis, V.; Mirrokni, V.; Olver, N., Inner product spaces for MinSum coordination mechanisms (2011) · Zbl 1288.90025
[13] Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: A geometric approach to the price of anarchy in nonatomic congestion games. Games Econ. Behav. 64, 457-469 (2008) · Zbl 1152.91321 · doi:10.1016/j.geb.2008.01.001
[14] Dafermos, S.: An extended traffic assignment model with applications to two-way traffic. Transp. Sci. 5, 366-389 (1971) · doi:10.1287/trsc.5.4.366
[15] Dafermos, S.C., Sparrow, F.T.: The traffic assignment problem for a general network. J. Res. Natl. Bur. Stand. B, Math. Sci. 73B(2), 91-118 (1969) · Zbl 0197.46003 · doi:10.6028/jres.073B.010
[16] de Palma, A., Nesterov, Y.: Optimization formulations and static equilibrium in congested transportation networks. CORE Discussion Paper 9861, Université Catholique de Louvain, Louvain-la-Neuve, 12-17, 1998 · Zbl 0197.46003
[17] Fleischer, L.: Linear tolls suffice: new bounds and algorithms for tolls in single source networks. Theor. Comput. Sci. 348(2-3), 217-225 (2005) · Zbl 1081.90009 · doi:10.1016/j.tcs.2005.09.014
[18] Fleischer, L.; Jain, K.; Mahdian, M., Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games, 277-285 (2004)
[19] Immorlica, N.; Li, L.; Mirrokni, V. S.; Schulz, A., Coordination mechanisms for selfish scheduling, 55-69 (2005) · Zbl 1172.90004
[20] Karakostas, G.; Kolliopoulos, S. G., Edge pricing of multicommodity networks for heterogeneous selfish users, 268-276 (2004)
[21] Karakostas, G.; Kolliopoulos, S. G., The efficiency of optimal taxes, 3-12 (2004)
[22] Kollias, K., Non-preemptive coordination mechanisms for identical machine scheduling games, 197-208 (2008) · Zbl 1143.68343
[23] Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. Comput. Sci. Rev. 3(2), 65-69 (2009) · Zbl 1303.91012 · doi:10.1016/j.cosrev.2009.04.003
[24] Marcotte, P.; Patriksson, M., Traffic equilibrium, No. 14, 623-713 (2007), Amsterdam · doi:10.1016/S0927-0507(06)14010-4
[25] Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007) · Zbl 1130.91005 · doi:10.1017/CBO9780511800481
[26] Patriksson, M.: The Traffic Assignment Problem: Models and Methods. V.S.P. Intl Science, Leiden (1994) · Zbl 0828.90127
[27] Roughgarden, T., Designing networks for selfish users is hard (2001)
[28] Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM 49, 236-259 (2002) · Zbl 1323.90011 · doi:10.1145/506147.506153
[29] Wardrop, J. G., Some theoretical aspects of road traffic research, No. 1, 325-378 (1952)
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.