Abstract
It is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal centralized solution may be unbounded even if the system consists of only two parallel links. This ratio is called the price of anarchy (PoA). In this article, we investigate ways by which one can reduce the performance degradation due to selfish behavior. We investigate two primary methods (a) Stackelberg routing strategies, where a central authority, for example, network manager, controls a fixed fraction of the flow, and can route this flow in any desired way so as to influence the flow of selfish users; and (b) network tolls, where tolls are imposed on the edges to modify the latencies of the edges, and thereby influence the induced Nash equilibrium. We obtain results demonstrating the effectiveness of both Stackelberg strategies and tolls in controlling the price of anarchy.
For Stackelberg strategies, we obtain the first results for nonatomic routing in graphs more general than parallel-link graphs, and strengthen existing results for parallel-link graphs. (i) In series-parallel graphs, we show that Stackelberg routing reduces the PoA to a constant (depending on the fraction of flow controlled). (ii) For general graphs, we obtain latency-class specific bounds on the PoA with Stackelberg routing, which give a continuous trade-off between the fraction of flow controlled and the price of anarchy. (iii) In parallel-link graphs, we show that for any given class L of latency functions, Stackelberg routing reduces the PoA to at most α + (1-α)ċρ(L), where α is the fraction of flow controlled and ρ(L) is the PoA of class L (when α = 0).
For network tolls, motivated by the known strong results for nonatomic games, we consider the more general setting of atomic splittable routing games. We show that tolls inducing an optimal flow always exist, even for general asymmetric games with heterogeneous users, and can be computed efficiently by solving a convex program. This resolves a basic open question about the effectiveness of tolls for atomic splittable games. Furthermore, we give a complete characterization of flows that can be induced via tolls.
- Awerbuch, B., Azar, Y., and Epstein, A. 2005. The price of routing unsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 57--66. Google ScholarDigital Library
- Beckman, M., McGuire, C. B., and Winsten, C. B. 1956. Studies in the Economics of Transportation. Yale University Press.Google Scholar
- Bhaskar, U., Fleischer, L., Hoy, D., and Huang, C. 2009. Equilibria of atomic flow games are not unique. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. 748--757. Google ScholarDigital Library
- Bhaskar, U., Fleischer, L., and Huang, C. 2010. The price of collusion in series-parallel networks. In Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization. 313--326. Google ScholarDigital Library
- Bonifaci, V., Harks, T., and Schäfer, G. 2010. Stackelberg routing in arbitrary networks. Math. Oper Res. 35, 2, 330--346. Google ScholarDigital Library
- Caragiannis, I., Kaklamanis, C., and Kanellopoulos, P. 2006. Taxes for linear atomic congestion games. In Proceedings of the 14th Annual European Symposium on Algorithms. 184--195. Google ScholarDigital Library
- Christodoulou, G. and Koutsoupias, E. 2005. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 67--73. Google ScholarDigital Library
- Cole, R., Dodis, Y., and Roughgarden, T. 2003. Pricing network edges for heterogeneous selfish users. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. 521--530. Google ScholarDigital Library
- Cole, R., Dodis, Y., and Roughgarden, T. 2006. How much can taxes help selfish routing? Journal of Comput. Syst. Sci. 72, 444--467. Google ScholarDigital Library
- Cominetti, R., Correa, J. R., and Stier-Moses, N. 2009. The impact of oligopolistic competition in networks. Oper. Res. 57, 6, 1421--1437. Google ScholarDigital Library
- Correa, J. and Stier-Moses, N. 2006. A note on Stackelberg routing. Unpublished manuscript.Google Scholar
- Correa, J. R., Schulz, A. S., and Stier-Moses, N. 2007. Fast, fair, and efficient flows in networks. Oper. Res. 55, 2, 215--225. Google ScholarDigital Library
- Dial, R. B. 1999. Network-optimized road pricing: Part I: A parable and a model. Oper. Res. 47, 1, 54--64. Google ScholarDigital Library
- Fleischer, L. 2005. Linear tolls suffice: New bounds and algorithms for tolls in single source networks. Theoret. Comput. Sci. 348, 217--225. Google ScholarDigital Library
- Fleischer, L., Jain, K., and Mahdian, M. 2004. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 277--285. Google ScholarDigital Library
- Fotakis, D. 2010. Stackelberg strategies for atomic congestion games. Theory Comput. Syst. 47, 1, 218--249. Google ScholarDigital Library
- Harks, T. 2011. Stackelberg strategies and collusion in network games with splittable flow. Theory Comput. Syst. 48, 4, 781--802. Google ScholarDigital Library
- Hayrapetyan, A., Tardos, É., and Wexler, T. 2006. The effect of collusion in congestion games. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. 89--98. Google ScholarDigital Library
- Kaporis, A. and Spirakis, P. 2009. The price of optimum in Stackelberg games on arbitrary single commodity networks and latency functions. Theoretical Computer Science 410, 745--755. Google ScholarDigital Library
- Karakostas, G. and Kolliopoulos, S. 2004. Edge pricing of multicommodity networks for heterogeneous users. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 268--276. Google ScholarDigital Library
- Karakostas, G. and Kolliopoulos, S. 2009. Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica 53, 1, 132--153. Google ScholarDigital Library
- Korilis, Y. A., Lazar, A. A., and Orda, A. 1997. Achieving network optima using Stackelberg routing strategies. IEEE/ACM Transactions on Networking 5, 1, 161--173. Google ScholarDigital Library
- Koutsoupias, E. and Papadimitriou, C. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science. 404--413. Google ScholarDigital Library
- Kumar, V. S. A. and Marathe, A. 2002. Improved results for Stackelberg scheduling strategies. In Proceedings of the 29th International Colloquium on Automata, Languages, and Programming. 776--787. Google ScholarDigital Library
- Orda, A., Rom, R., and Shimkin, N. 1993. Competitive routing in multiuser communication networks. IEEE/ACM Trans. Netw. 1, 510--521. Google ScholarDigital Library
- Papadimitriou, C. H. 2001. Algorithms, games, and the Internet. In Proceedings of the 28th International Colloquium on Automata, Languages, and Programming. 1--3. Google ScholarDigital Library
- Pigou, A. C. 1920. The Economics of Welfare. Macmillan.Google Scholar
- Roughgarden, T. 2003. The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67, 2, 341--364. Google ScholarDigital Library
- Roughgarden, T. 2004. Stackelberg scheduling strategies. SIAM J. Comput. 33, 2, 332--350. Google ScholarDigital Library
- Roughgarden, T. 2005. Selfish Routing and the Price of Anarchy. MIT Press. Google ScholarDigital Library
- Roughgarden, T. and Tardos, É. 2002. How bad is selfish routing? J.ACM 49, 236--259. Google ScholarDigital Library
- Sharma, Y. and Williamson, D. P. 2007. Stackelberg thresholds in network routing games or the value of altruism. In Proceedings of the 8th Annual ACM Conference on Electronic Commerce. 93--102. Google ScholarDigital Library
- Swamy, C. 2007. The effectiveness of Stackelberg strategies and tolls for network congestion games. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1133--1142. Google ScholarDigital Library
- Wardrop, J. G. 1952. Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers, Part II, volume 1. 325--378.Google Scholar
- Yang, H. and Huang, H. J. 2004. The multi-class, multi-criteria traffic network equilibria and system optimum problem. Transport. Res. B 28, 1--15.Google Scholar
- Yang, H. and Zhang, X. 2008. Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors. Transport. Res. B 42, 99--112.Google ScholarCross Ref
Index Terms
- The effectiveness of stackelberg strategies and tolls for network congestion games
Recommendations
Stackelberg Strategies for Atomic Congestion Games
Special Section: Algorithmic Game Theory; Guest Editors: Burkhard Monien and Ulf-Peter SchroederWe investigate the effectiveness of Stackelberg strategies for atomic congestion games with unsplittable demands. In our setting, only a fraction of the players are selfish, while the rest are willing to follow a predetermined strategy. A Stackelberg ...
The effectiveness of Stackelberg strategies and tolls for network congestion games
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithmsIt is well known that in a network with arbitrary (convex) latency functions that are a function of edge traffic, the worst-case ratio, over all inputs, of the system delay caused due to selfish behavior versus the system delay of the optimal ...
On Stackelberg Strategies in Affine Congestion Games
We investigate the efficiency of some Stackelberg strategies in congestion games with affine latency functions. A Stackelberg strategy is an algorithm that chooses a subset of players and assigns them a prescribed strategy with the purpose of mitigating ...
Comments