Abstract
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 (\(\mathrm {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 \(\mathrm {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 \(\mathrm {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 \(\mathrm {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 \(\mathrm {PoA}\), and (ii) considering more flexible modifications does not lead to any further improvement.
This research was supported by the project Algorithmic Game Theory, co-financed by the European Union (European Social Fund) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework - Research Funding Program: THALES, investing in knowledge society through the European Social Fund, and by grant NSF CCF 1216103.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
- 1.
To simplify the model and make it easily applicable to general networks, we assume that the perceived cost of the players under latency modifications is separable. This is a reasonable simplifying assumption on the structure of risk-averse costs (see also [13, 15]) and only affects the extension of our results to series-parallel networks.
- 2.
Property (d) requires that \(\mathcal {D}\) should be closed under addition of constants, as long as the resulting function remains nonnegative.
References
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)
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)
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004)
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)
Fleischer, L.: Linear tolls suffice: new bounds and algorithms for tolls in single source networks. Theoret. Comput. Sci. 348, 217–225 (2005)
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)
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)
Hall, M.A.: Properties of the equilibrium state in transportation networks. Transp. Sci. 12(3), 208–216 (1978)
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)
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)
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)
Nikolova, E., Stier-Moses, N.E.: Stochastic selfish routing. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 314–325. Springer, Heidelberg (2011)
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)
Ordóñez, F., Stier-Moses, N.: Wardrop equilibria with risk-averse users. Transp. Sci. 44(1), 63–86 (2010)
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)
Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33(2), 332–350 (2004)
Roughgarden, T.: Selfish Routing and The Price of Anarchy. MIT press, Cambridge (2005)
Tversky, A., Kahneman, D.: Prospect theory: an analysis of decision under risk. Econometrica 47(2), 263–291 (1979)
Valdez, J., Tarjan, R.E., Lawler, E.L.: The recognition of series-parallel digraphs. SIAM J. Comput. 11(2), 298–313 (1982)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fotakis, D., Kalimeris, D., Lianeas, T. (2015). Improving Selfish Routing for Risk-Averse Players. In: Markakis, E., Schäfer, G. (eds) Web and Internet Economics. WINE 2015. Lecture Notes in Computer Science(), vol 9470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48995-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-662-48995-6_24
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48994-9
Online ISBN: 978-3-662-48995-6
eBook Packages: Computer ScienceComputer Science (R0)