On the impact of singleton strategies in congestion games (extended abstract)

Abstract

To what extent the structure of the players' strategic space in uences the e ciency of decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games in which players can only choose among single resources. We consider three di erent solutions concepts, namely, approximate pure Nash equilibria, approximate one-round walks generated by sel sh players aiming at minimizing their personal cost and approximate one-round walks generated by cooperative players aiming at minimizing the marginal increase in the sum of the players' personal costs. The last two concepts can also be interpreted as solutions of simple greedy online algorithms for the related resource selection problem. Under fairly general latency functions on the resources, we show that, for all three types of solutions, better bounds cannot be achieved if players are either weighted or asymmetric. On the positive side, we prove that, under mild assumptions on the latency functions, improvements on the performance of approximate pure Nash equilibria are possible for load balancing games with weighted and symmetric players in the case of identical resources. We also design lower bounds on the performance of one-round walks in load balancing games with unweighted players and identical resources (in this case, solutions generated by sel sh and cooperative players coincide).

-

Congestion games [ 17 ] are non-cooperative games in which there is a set of selfish players competing for a set of resources, and each resource incurs a certain latency, expressed by a congestion-dependent function, to the players using it. Each player has a certain weight and an available set of strategies, where each strategy is a non-empty subset of resources, and aims at choosing a strategy minimizing her personal cost which is de ned as the sum of the latencies experienced on all the selected resources. We speak of weighted games/players when players have arbitrarily non-negative weights and of unweighted games/players when all players have unitary weight.

Stable outcomes in this setting are the pure Nash equilibria [ 16 ]: strategy pro les in which no player can lower her cost by unilaterally deviating to another strategy. However, they are compelling solution concepts, as they might not always exist in weighted games [ 11 ] and, even when their existence is guaranteed, as, for instance, in unweighted games [ 17 ] and in weighted games with a ne latency functions [ 11, 13 ], their computation might be an intractable problem [ 1, 9 ]. For such a reason, more relaxed solution concepts are usually considered in the literature, as -approximate pure Nash equilibria or -approximate one-round walks.

An -approximate pure Nash equilibrium is the relaxation of the concept of pure Nash equilibrium in which no player can lower her cost of a factor more than 1 + by unilaterally deviating to another strategy, while an -approximate one-round walk is de ned as a myopic process in which players arrive in an arbitrary order and, upon arrival, each of them has to make an irrevocably strategic choice aiming at approximatively minimizing a certain cost function. In this work, we shall consider two variants of this process: in the rst, players choose a strategy approximatively minimizing, up to a factor of 1 + , their personal cost (sel sh players), while, in the second, players choose the strategy approximatively minimizing, up to a factor of 1 + , the marginal increase in the social cost (cooperative players) which is de ned as the sum of the players' personal costs (for the case of = 0, we use the term exact one-round walk). In particular, approximate one-round walks can be interpreted as simple greedy online algorithms for the equivalent resource selection problem associated with a given congestion game. The worst-case e ciency of these solution concepts with respect to the optimal social cost is termed as the -approximate price of anarchy (for the case of pure Nash equilibria, the term price of anarchy [ 14 ] is adopted) and as the competitive ratio of -approximate one-round walks, respectively.

Interesting special cases of congestion games are obtained by restricting the combinatorics of the players' strategic space. In symmetric congestion games, all players share the same set of strategies; in network congestion games the players' strategies are de ned as paths in a given network; in matroid congestion games [ 1, 2 ], the strategy set of every player is given by a subset of the set of bases of a matroid de ned over the set of available resources, so that all players require the same number of resources; in k-uniform matroid congestion games [ 8 ], each player can select any subset of cardinality k from a prescribed player-speci c set of resources; nally, in load balancing games, players can only choose single resources.

To what extent the structure of the players' strategic space in uences the efciency of decentralized solutions in congestion games? In this work, we investigate whether better performance are possible when restricting to load balancing games. Previous work established that the price of anarchy does not improve when restricting to unweighted load balancing games with polynomial latency functions [ 7, 12 ], while better bounds are possible in unweighted symmetric load balancing games with fairly general latency functions [ 10 ]. Under the assumption of identical resources with a ne latency functions, improvements are also possible when restricting to both unweighted load balancing games [ 7, 18 ] and weighted symmetric load balancing games [ 15 ]. Finally, [ 4 ] proves that the price of anarchy does not improve when restricting to weighted symmetric load balancing games under polynomial latency functions. For the competitive ratio of exact one-round walks generated by cooperative players, no improvements are possible in unweighted load balancing games with a ne latency functions [ 7, 18 ], while improved performance can be obtained under the additional assumption of identical resources [ 7 ] (we observe that, in this case, solutions generated by both types of players coincide); however, for weighted players, no improvements are possible even under the assumption of identical resources [ 3, 6, 7 ]. For oneround walks generated by sel sh players, instead, no specialized limitations are currently known. 2

Our contribution We obtain an almost precise picture of the cases in which improved performance can be obtained in load balancing congestion games. This is done by either solving open problems or extending previously known results to both approximate solution concepts and more general latency functions. Speci cally, we provide the following characterizations.

Let C be a class of non-negative and non-decreasing functions such that, for each f 2 C and 2 R 0, the function g such that g(x) = f (x) belongs to C and let C0 C be the subclass of C such that, for each f 2 C0 and 2 R 0, the function h such that h(x) = f ( x) belongs to C0. A function f is semi-convex if xf (x) is convex, it is unbounded if limx!1 f (x) = 1. We prove that: for weighted players: under unbounded latency functions drawn from C0, the approximate price of anarchy does not improve when restricting to symmetric load balancing games (this solves an open problem raised in [ 4 ], where a similar limitation was shown only with respect to pure Nash equilibria and polynomial latency functions). Under latency functions drawn from C0, the competitive ratio of approximate one-round walks generated by sel sh players does not improve when restricting to load balancing games (this solves an open problem raised in [ 5 ]). If all functions in C0 are semi-convex, then the same limitation applies to the competitive ratio of approximate one-round walks generated by cooperative players (this generalizes results in [ 3, 6, 7 ] which hold only with respect to exact one-round walks for games with polynomial latency functions). We also provide a parametric formula for the relative bounds which we use to obtain the exact values for polynomial latency functions as reported in the following table. d Sel sh Players Coord. Players d

Sel sh Players

Coord. Players 1 2 3 4 1,521 for unweighted players: under latency functions drawn from C, either the approximate price of anarchy and the competitive ratio of approximate one-round walks generated by both sel sh and cooperative players do not improve when restricting to load balancing games (these generalize a result in [ 7, 12 ] which holds only with respect to pure Nash equilibria and polynomial latency functions, a result in [ 7, 18 ] which holds only with respect to exact one-round walks generated by cooperative players in games with a ne latency functions, and solve an open problem raised in [ 5 ] for (approximate) one-round walks generated by sel sh players). Also in this case we provide a parametric formula for the relative bounds which we use to obtain the exact bounds for polynomial latency functions as reported in the following table.

d Competitive Ratio d Competitive Ratio d Competitive Ratio

These negative results, together with the positive ones achieved by [ 7, 10 ], imply that better bounds on the approximate price of anarchy are possible only when dealing with unweighted symmetric load balancing games. However, under the additional hypothesis of identical resources, better performance are still possible. Let f be an increasing, continuous and semi-convex function. We prove that the approximate price of anarchy of weighted symmetric load balancing games with identical resources whose latency functions coincide with f is equal to supx2R>0 sup 2(0;1) xf (x) + (1 )inv(x)f (inv(x)) opt(x)f (opt(x)) ; where inv(x) := infft 0 : f (x) (1 + )f (x=2 + t)g and opt(x) := x + (1 )inv(x). This generalizes a result by [ 15 ] which holds only with respect to the price of anarchy under a ne latency functions. Furthermore, by using the previous formula, we compute the exact price of anarchy of weighted symmetric load balancing games with identical resources and polynomial latency functions as reported in the following table.

d Identical Res. General Res. d Identical Res.

General Res.

Finally, still for the case of identical resources, we design lower bounds on the performance of exact one-round walks in load balancing games with unweighted players (this improves and generalizes a result in [ 7 ] which holds only for a ne latency functions).

References

1. H. Ackermann , H. Roglin, and B. Vo cking. On the impact of combinatorial structure on congestion games . Journal of ACM , 55 ( 6 ), 2008 .

2. H. Ackermann , H. Roglin, and B. Vo cking. Pure Nash equilibria in player-speci c and weighted congestion games . Theoretical Computer Science , 410 ( 17 ): 1552 { 1563 , 2009 .

3. B. Awerbuch , Y. Azar , E. F. Grove , M.- Y. Kao , P. Krishnan , and J. S. Vitter . Load balancing in the Lp norm . In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS) , IEEE Computer Society , pp. 383 { 391 , 1995 .

4. K. Bhawalkar , M. Gairing , and T. Roughgarden . Weighted congestion games: price of anarchy, universal worst-case examples, and tightness . ACM Transactions on Economics and Computation 2 ( 4 ): 1{ 23 , 2014 .

5. V. Bilo , A. Fanelli , M. Flammini , and L. Moscardelli . Performances of one-round walks in linear congestion games . Theory of Computing Systems , 49 ( 1 ): 24 { 45 , 2011 .

6. I. Caragiannis . E cient coordination mechanisms for unrelated machine scheduling . Algorithmica , 66 ( 3 ): 512 { 540 , 2013 .

7. I. Caragiannis , M. Flammini , C. Kaklamanis , P. Kanellopoulos , and L. Moscardelli . Tight bounds for sel sh and greedy load balancing . Algorithmica , 61 ( 3 ): 606 { 637 , 2011 .

8. J. de Jong, M. Klimm, and M. Uetz . E ciency of equilibria in uniform matroid congestion games . In Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT) , LNCS 9928 , Springer, pp. 105 { 116 , 2016 .

9. A. Fabrikant , C. H. Papadimitriou , and K. Talwar . The complexity of pure Nash equilibria . In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC) , ACM Press, pp. 604 { 612 , 2004 .

10. D. Fotakis . Stackelberg strategies for atomic congestion games . Theory of Computing Systems , 47 ( 1 ): 218 { 249 , 2010 .

11. D. Fotakis , S. Kontogiannis , and P. Spirakis . Sel sh unsplittable ows . Theoretical Computer Science , 348 : 226 { 239 , 2005 .

12. M. Gairing and F. Schoppmann . Total latency in singleton congestion games . In Proceedings of the Third International Workshop on Internet and Network Economics (WINE) , LNCS 4858 , Springer, pp. 381 { 387 , 2007 .

13. T. Harks and M. Klimm . On the existence of pure Nash equilibria in weighted congestion games . Mathematics of Operations Research , 37 ( 3 ): 419 { 436 , 2012 .

14. E. Koutsoupias and C. Papadimitriou . Worst-case equilibria . In Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS) , LNCS 1653 , Springer, pp. 404 { 413 , 1999 .

15. T. Lucking, M. Mavronicolas , B. Monien , and M. Rode . A new model for sel sh routing . Theoretical Computer Science , 406 ( 3 ): 187{ 2006 , 2008 .

16. J. F. Nash . Equilibrium points in n-person games . Proceedings of the National Academy of Science , 36 ( 1 ): 48 { 49 , 1950 .

17. R. W. Rosenthal . A class of games possessing pure-strategy Nash equilibria . International Journal of Game Theory , 2 ( 1 ): 65 { 67 , 1973 .

18. S. Suri , C. Toth , and Y. Zhou . Sel sh load balancing and atomic congestion games . Algorithmica , 47 ( 1 ): 79 { 96 , 2007 .