zbMATH — the first resource for mathematics

Improving selfish routing for risk-averse players. (English) Zbl 1404.91050
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, 328-342 (2015).
Summary: We investigate how and to which extent one can exploit risk aversion and modify the perceived cost of the players in selfish routing so that the price of anarchy (PoA) is improved. We introduce small random perturbations to the edge latencies so that the expected latency does not change, but the perceived cost of the players increases due to risk-aversion. We adopt the model of $$\gamma$$-modifiable routing games, a variant of routing games with restricted tolls. We prove that computing the best $$\gamma$$-enforceable flow is NP-hard for parallel-link networks with affine latencies and two classes of heterogeneous risk-averse players. On the positive side, we show that for parallel-link networks with heterogeneous players and for series-parallel networks with homogeneous players, there exists a nicely structured $$\gamma$$-enforceable flow whose PoA improves fast as $$\gamma$$ increases. We show that the complexity of computing such a $$\gamma$$-enforceable flow is determined by the complexity of computing a Nash flow of the original game. Moreover, we prove that the PoA of this flow is best possible in the worst-case, in the sense that there are instances where (i) the best $$\gamma$$-enforceable flow has the same PoA, and (ii) considering more flexible modifications does not lead to any further improvement.
For the entire collection see [Zbl 1326.68026].

MSC:
 91A43 Games involving graphs 91B16 Utility theory
Full Text:
References:
 [1] Angelidakis, H., Fotakis, D., Lianeas, T.: Stochastic congestion games with risk-averse players. In: Vöcking, B. (ed.) SAGT 2013. LNCS, vol. 8146, pp. 86–97. Springer, Heidelberg (2013) · Zbl 1319.91046 · doi:10.1007/978-3-642-41392-6_8 [2] Bonifaci, V., Salek, M., Schäfer, G.: Efficiency of restricted tolls in non-atomic network routing games. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 302–313. Springer, Heidelberg (2011) · Zbl 1233.90077 · doi:10.1007/978-3-642-24829-0_27 [3] Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004) · Zbl 1082.90009 · doi:10.1287/moor.1040.0098 [4] Fiat, A., Papadimitriou, C.: When the players are not expectation maximizers. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 1–14. Springer, Heidelberg (2010) · Zbl 1253.91009 · doi:10.1007/978-3-642-16170-4_1 [5] Fleischer, L.: Linear tolls suffice: new bounds and algorithms for tolls in single source networks. Theoret. Comput. Sci. 348, 217–225 (2005) · Zbl 1081.90009 · doi:10.1016/j.tcs.2005.09.014 [6] Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 277–285 (2004) · doi:10.1109/FOCS.2004.69 [7] Fotakis, D.A., Spirakis, P.G.: Cost-balancing tolls for atomic network congestion games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol. 4858, pp. 179–190. Springer, Heidelberg (2007) · Zbl 05264308 · doi:10.1007/978-3-540-77105-0_19 [8] Hall, M.A.: Properties of the equilibrium state in transportation networks. Transp. Sci. 12(3), 208–216 (1978) · doi:10.1287/trsc.12.3.208 [9] Hoefer, M., Olbrich, L., Skopalik, A.: Taxing subnetworks. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 286–294. Springer, Heidelberg (2008) · Zbl 05496542 · doi:10.1007/978-3-540-92185-1_35 [10] Jelinek, T., Klaas, M., Schäfer, G.: Computing optimal tolls with arc restrictions and heterogeneous players. In: Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014), LIPIcs 25, pp. 433–444 (2014) · Zbl 1360.91046 [11] Karakostas, G., Kolliopoulos, S.: Edge pricing of multicommodity networks for heterogeneous users. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 268–276 (2004) · doi:10.1109/FOCS.2004.26 [12] Nikolova, E., Stier-Moses, N.E.: Stochastic selfish routing. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 314–325. Springer, Heidelberg (2011) · Zbl 1233.90087 · doi:10.1007/978-3-642-24829-0_28 [13] Nikolova, E., Stier-Moses, N.: The burden of risk aversion in mean-risk selfish routing. In: Proceedings of the 16th ACM Conference on Electronic Commerce (EC 2015), pp. 489–506 (2015) · doi:10.1145/2764468.2764485 [14] Ordóñez, F., Stier-Moses, N.: Wardrop equilibria with risk-averse users. Transp. Sci. 44(1), 63–86 (2010) · doi:10.1287/trsc.1090.0292 [15] Piliouras, G., Nikolova, E., Shamma, J.S.: Risk Sensitivity of price of anarchy under uncertainty. In: Proceedings of the 14th ACM Conference on Electronic Commerce (EC 2013), pp. 715–732 (2013) · doi:10.1145/2492002.2482578 [16] Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33(2), 332–350 (2004) · Zbl 1080.90046 · doi:10.1137/S0097539701397059 [17] Roughgarden, T.: Selfish Routing and The Price of Anarchy. MIT press, Cambridge (2005) · Zbl 1318.68065 [18] Tversky, A., Kahneman, D.: Prospect theory: an analysis of decision under risk. Econometrica 47(2), 263–291 (1979) · Zbl 0411.90012 · doi:10.2307/1914185 [19] Valdez, J., Tarjan, R.E., Lawler, E.L.: The recognition of series-parallel digraphs. SIAM J. Comput. 11(2), 298–313 (1982) · Zbl 0478.68065 · doi:10.1137/0211023
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.