Abstract
Congestion games ignore the stochastic nature of resource delays and the risk-averse attitude of the players to uncertainty. To take these aspects into account, we introduce two variants of atomic congestion games, one with stochastic players, where each player assigns load to her strategy independently with a given probability, and another with stochastic edges, where the latency functions are random. In both variants, the players are risk-averse, and their individual cost is a player-specific quantile of their delay distribution. We focus on parallel-link networks and investigate how the main properties of such games depend on the risk attitude and on the participation probabilities of the players. In a nutshell, we prove that stochastic congestion games on parallel-links admit an efficiently computable pure Nash equilibrium if the players have either the same risk attitude or the same participation probabilities, and also admit a potential function if the players have the same risk attitude. On the negative side, we present examples of stochastic games with players of different risk attitudes that do not admit a potential function. As for the inefficiency of equilibria, for parallel-link networks with linear delays, we prove that the Price of Anarchy is Θ(n), where n is the number of stochastic players, and may be unbounded, in case of stochastic edges.
This research was supported by the project Algorithmic Game Theory, co-financed by the European Union (European Social Fund - ESF) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES, investing in knowledge society through the European Social Fund.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ackermann, H., Röglin, H., Vöcking, B.: On the Impact of Combinatorial Structre on Congestion Games. Journal of the Association for Computing Machinery 55(6), 25 (2008)
Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact Price of Anarchy for Polynomial Congestion Games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 218–229. Springer, Heidelberg (2006)
Ashlagi, I., Monderer, D., Tennenholtz, M.: Resource selection games with unknown number of players. In: Proc. of the 5th Conference on Autonomous Agents and Multiagent Systems (AAMAS 2006), pp. 819–825 (2006)
Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In: Proc. of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 57–66 (2005)
Caragiannis, I., Fanelli, A., Gravin, N., Skopalik, A.: Efficient computation of approximate pure Nash equilibria in congestion games. In: Proc. of the 52nd IEEE Symposium on Foundations of Computer Science (FOCS 2011), pp. 532–541 (2011)
Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.: Tight Bounds for Selfish and Greedy Load Balancing. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 311–322. Springer, Heidelberg (2006)
Chien, S., Sinclair, A.: Convergece to Approximate Nash Equilibria in Congestion Games. In: Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 169–178 (2007)
Christodoulou, G., Koutsoupias, E.: The Price of Anarchy of Finite Congestion Games. In: Proc. of the 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 67–73 (2005)
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)
Fotakis, D.: Congestion games with linearly independent paths: Convergence time and price of anarchy. Theory of Computing Systems 47(1), 113–136 (2010)
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish Unsplittable Flows. Theoretical Computer Science 348, 226–239 (2005)
Harks, T., Klimm, M.: On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research 37(3), 419–436 (2012)
Milchtaich, I.: Congestion Games with Player-Specific Payoff Functions. Games and Economic Behavior 13, 111–124 (1996)
Nikolova, E., Stier-Moses, N.E.: Stochastic selfish routing. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol. 6982, pp. 314–325. Springer, Heidelberg (2011)
Ordóñez, F., Stier-Moses, N.: Wardrop equilibria with risk-averse users. Transportation Science 44(1), 63–86 (2010)
Piliouras, G., Nikolova, E., Shamma, J.S.: Risk sensitivity of price of anarchy under uncertainty. In: Proc. of the 14th ACM Conference on Electronic Commerce (EC 2013), pp. 715–732 (2013)
Rockafellar, R.T.: Coherent Approaches to Risk in Optimization Under Uncertainty. In: Tutorials in Operations Research, pp. 38–61 (2007)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)
Tversky, A., Kahneman, D.: Prospect Theory: An analysis of decision under risk. Econometrica 47(2), 263–291 (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Angelidakis, H., Fotakis, D., Lianeas, T. (2013). Stochastic Congestion Games with Risk-Averse Players. In: Vöcking, B. (eds) Algorithmic Game Theory. SAGT 2013. Lecture Notes in Computer Science, vol 8146. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41392-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-41392-6_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41391-9
Online ISBN: 978-3-642-41392-6
eBook Packages: Computer ScienceComputer Science (R0)