The Price of Anarchy of Affine Congestion Games with Similar Strategies Vittorio Bilò1 and Cosimo Vinci2 1 Department of Mathematics and Physics “Ennio De Giorgi”, University of Salento Provinciale Lecce-Arnesano, P.O. Box 193, 73100 Lecce - Italy vittorio.bilo@unisalento.it 2 Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila Via Vetoio, Loc. Coppito, 67100 L’Aquila - Italy cosimo.vinci@univaq.it Abstract. Affine congestion games are a well-studied model for selfish behavior in distributed systems, such as transportation and communica- tion networks. Seminal influential papers in Algorithmic Game Theory have bounded the worst-case inefficiency of Nash equilibria, termed as price of anarchy, in several variants of these games. In this work, we in- vestigate to what extent these bounds depend on the similarities among the players’ strategies. Our notion of similarity is modeled by assuming that, given a parameter θ ≥ 1, the costs of any two strategies available to a same player, when evaluated in absence of congestion, are within a factor θ one from the other. It turns out that, for the non-atomic case, better bounds can always be obtained for any finite value of θ. For the atomic case, instead, θ < 3/2 and θ < 2 are necessary and sufficient conditions to obtain better bounds in games played on general graph topologies and on parallel link graphs, respectively. It is worth notic- ing that small values of θ model the behavioral attitude of players who are partially oblivious to congestion and are not willing to significantly deviate from what is their best strategy in absence of congestion. 1 Introduction What route should I choose to go to work? This is a fundamental question that millions of people ask themselves daily, especially in metropolitan areas where the set of possible alternatives may be considerably diversified. In an ideal situation in which travel time is not affected by traffic, everyone would select the fastest path. However, when some roads become heavily congested, the ideal travel time may tremendously increase and some people may prefer taking longer detours to avoid traffic delay. As every worker can be seen as a selfish and rational agent who is only interested in minimizing its travel time, this type of problems gets suitably modeled as non-cooperative strategic games, usually called routing games [46]. There is a vast scientific literature on routing games, started from the be- ginning of the last century with the early works on transportation networks by 2 V. Bilò and C. Vinci Pigou [39], and developed and flourished later on, thanks to the advent of dis- tributed networks, such as the Internet. One of the most successful and studied models in this area is that of congestion games [41] introduced by Rosenthal in 1973. In a congestion game, there is a finite set of players competing for a finite set of resources (i.e., roads in a network). Each player can choose an al- ternative from a set of available strategies, where each strategy is a subset of resources (i.e., one of the possible paths to go to work), and each resource has an associated latency function expressing the cost that a player incurs for using it; such a function only depends on the number of users (i.e., the travel time of a congested road as a function of the traffic). The cost of a player is defined as the sum of the latencies of the resources she chooses, and each player aims at minimizing it. A particularly well-studied case concerns affine congestion games, where the resource latency functions are affine (i.e., the travel time of a road increases linearly with its congestion). Two versions of congestion games are usually considered in the literature depending on the amount of traffic controlled by the players: the atomic case and the non-atomic one. In the atomic case [41], every player controls a non- negligible amount of traffic (i.e., traffic is discrete and every player contributes for a congestion of one), while, in the non-atomic case [4, 39], every player con- trols a negligible amount of traffic (i.e., traffic is a continuous flow and every player infinitesimally contributes to the congestion). A nice property possessed by congestion games is that they always admit pure Nash equilibria [38]: an outcome in which no player has an incentive to deviate to a different strategy. The study of routing games (and so that of congestion games) has known a booming growth in the last twenty years thanks to the seminal papers by Koutsoupias and Papadimitriou [36] and Roughgarden and Tardos [47], which initiated the investigation of the inefficiency of pure Nash equilibria in non- cooperative networks. The notion of price of anarchy [36], defined as the worst- case ratio of the social welfare of a pure Nash equilibrium to the social optimum, has been introduced to assess this phenomenon. Thanks to the effort of many researchers worldwide, we have a deep and almost complete understanding of the price of anarchy in (several variants of) congestion games [1, 3, 5, 6, 15, 16, 20, 26– 30, 32, 42, 44, 45, 47, 48]. In particular, the following results have been obtained with respect to affine congestion games. For the non-atomic case, Roughgarden and Tardos [47] showed that the price of anarchy is 4/3 and Roughgarden [42] complemented this result by proving that this value is independent of the net- work topology. For the atomic case, Awerbuch et al. [3] and Christodoulou and Koutsoupias [20] independently proved that the price of anarchy rises to 5/2, while Lücking et al. [37] showed, that for games played on parallel link graphs, i.e., for the case in which all players have the same strategic space and each strategy is a singleton set, the price of anarchy drops again to 4/3. 1.1 Our Contribution In this work, we investigate to what extent the price of anarchy of affine con- gestion games is affected by the similarities among the players’ strategies. Our The Price of Anarchy of Affine Congestion Games with Similar Strategies 3 notion of similarity is modeled by assuming that, given a parameter θ ≥ 1, the costs of any two strategies available to a same player, when evaluated in absence of congestion, are within a factor θ one from the other. √ For the non-atomic 2 case, we show that the price of anarchy is exactly θ(θ−1)+θ−2  for any θ ∈ R≥1 \ 4 and 9 for θ = 4 . Hence, improvements   √ (3θ−4) 2 θ(θ−1)−θ 3 8 3 on the 34 -bound shown by Roughgarden and Tardos [47] can be obtained for any 4θ finite value of θ. We also provide a lower bound of 3θ+1 which holds for games played on parallel link ngraphs.√For the atomic case, o we show that the price of (4θ−6) θ 2 −θ+3+4θ 2 +θ−8 5 anarchy is exactly min 8θ−11 , 2 for θ ∈ R≥1 \ 11 8 289 and 120 for θ = 11 8 , for games played on generic network topologies. Forngames played o on parallel link graphs, instead, we show an upper bound of min 3θ−2 4 2θ−1 , 3 and n o 2θ 4 a lower bound of max θ+1 , 3 , which are almost tight, since their difference is at most 0.0572. It turns out that θ < 3/2 and θ < 2 are necessary and sufficient conditions to obtain improved bounds in general games and in games played on parallel link networks, respectively. To this aim, we observe that small values of θ model the behavioral attitude of players who are partially oblivious to conges- tion and are not willing to significantly deviate from what is their best strategy in absence of congestion. 1.2 Related Work The price of anarchy of non-atomic congestion games has been first considered in the seminal papers by Roughgarden and Tardos [47] and Roughgarden [42], and later on investigated in a number of follow-up papers [26–28]. The inefficiency of Nash equilibria in atomic congestion games has been first considered by Awer- buch et al. [3] and Christodoulou and Koutsoupias [20] who characterized the price of anarchy in games with affine latency functions. Caragiannis et al. [16] extended their bounds to singleton congestion games, where each strategy is a singleton set, while Lücking et al. [37] gave better bounds for games played on parallel link graphs. The price of anarchy has been largely studied for other classes of atomic congestion games (e.g. games with polynomial latencies [1, 23], or with general latency functions [5, 15, 32, 45], games with altruistic players [7, 9, 18, 19, 31, 40]). Furthermore, other quality metrics to measure the performance of atomic congestion games (e.g. the approximate price of anarchy [8, 23], the price of stability [2, 11, 21, 23], the approximation ratio of some special types of best-response dynamics [10, 15, 24, 50]) have been introduced and analyzed. Fi- nally, mechanisms to improve the price of anarchy have been proposed in [13, 14, 17, 22, 25, 35, 32–34, 43, 49]. 2 Model and Definitions For an integer i, set [i] := {1, 2, . . . , i}. An atomic congestion  game, or simply congestion game, is a tuple CG = [n], E, (`e )e∈E , (Σi )i∈[n] , where [n] is a set of 4 V. Bilò and C. Vinci n ≥ 2 players, E is a set of resources, `e : R≥0 → R≥0 is the latency function of resource e ∈ R, and, for each player i ∈ [n], Σi ⊆ 2R \ ∅ is her set of strategies (i.e. a strategy is a non-empty subset of resources). A congestion game is affine when, for each e ∈ E, `e (x) = αe x + βe , with αe , βe ≥ 0. If βe = 0 for any e ∈ E we speak of linear congestion games. A singleton congestion game is a congestion game in which, for each i ∈ [n] and S ∈ Σi , |S| = 1, i.e., each player can only select single resources, and a symmetric congestion game is one in which Σi = Σ for each i ∈ [n], i.e., all players share the same strategy space. Congestion games which are both symmetric and singleton are equivalently denoted as games played on parallel link graphs (in particular, when considering network games). A strategy profile is an n-tuple of strategies σ = (σ1 , . . . , σn ), that is, a state of the game in which each player i ∈ [n] is adopting strategy σi ∈ Σi , so that ×i∈[n] Σi denotes the set of strategy profiles which can be realized in CG. For a strategy profile σ, the congestion of resource e ∈ E in σ, denoted as ke (σ) := |{i ∈ [n] : e ∈ σi }|, is the number of players using P resource e in σ. The cost of player i in σ is defined as ci (σ) := e∈σi `e (ke (σ)) and each player aims at minimizing it. For the sake of conciseness, when the strategy profile σ is clear from the context, we write ke in place of ke (σ). Congestion Games with Similar Strategies Given θ ≥ 1, a congestion game with θ-similar strategies is a congestion game CG(θ) equal to a given congestion game CG, but where each player P i ∈ [n] has aP strategy set Σi (θ) ⊆ Σi defined as follows: Σi (θ) := S ∈ Σi : e∈S `e (1) ≤ θ e∈S 0 `e (1) ∀S 0 ∈ Σi , i.e. the costs of any two strategies available to a same player, when evaluated in absence of congestion (except for the unitary congestion due to herself), are within a factor θ one from the other. Observe that for θ = ∞, CG(θ) coincides with CG. Pure Nash Equilibria Fix a strategy profile σ and a player i ∈ [n]. We denote with σ−i the restriction of σ to all the players other than i; moreover, for a strategy S ∈ Σi , we denote with (σ−i , S) the strategy profile obtained from σ when player i changes her strategy from σi to S, while the strategies of all the other players are kept fixed. A pure Nash equilibrium [38] is a strategy profile σ such that, for any player i ∈ [n] and strategy S ∈ Σi , ci (σ) ≤ ci (σ−i , S), that is, an outcome of the game in which no player can improve her situation by unilaterally deviating to another strategy. Quality of Equilibria A social function that is usually used as a measure of the quality of a P strategy profilePin congestion games is the total latency, defined as SUM(σ) := i∈[n] ci (σ) = e∈E ke (σ)`e (ke (σ)). A social optimum is a strategy profile σ ∗ minimizing SUM. Again, for the sake of conciseness, once a particular social optimum has been fixed, we write oe to denote the value ke (σ ∗ ). The price of anarchy of a congestion game CG (with respect to the social func- tion SUM), denoted as PoA(CG), is the maximum of the ratio SUM(σ)/SUM(σ ∗ ), where σ is a pure Nash equilibrium for CG and σ ∗ is a social optimum for CG. The Price of Anarchy of Affine Congestion Games with Similar Strategies 5 Relatively to congestion games with θ-similar strategies, observe that the price of anarchy is a non decreasing function with respect to θ. Remark 1. As shown in [6] for classic affine congestion games, given an affine congestion game with θ-similar strategies CG(θ), we have that there exists a linear congestion game with θ-similar strategies CG∗ (θ) having the same price of anarchy of CG(θ) (a proof of this fact is deferred to the full version of this paper). Non-atomic Congestion Games Non-atomic congestion games [39, 51, 4] are an important variant of atomic congestion games, obtained when the social im- pact of each player is infinitesimally small, and there are infinitely many players . A non-atomic congestion game, is a tuple NCG = (fi )i∈[n] , E, (`e )e∈E , (Σi )i∈[n] where fi ∈ R≥0 is the amount of players of type i for any i ∈ [n], Σi ⊆ 2R \ ∅ is the set of strategies for players of type i for any i ∈ [n], and the other quantities are defined analogously to atomic congestion games. The concepts defined for atomic congestion games can be adapted to the non- atomic case. A strategy profile is a tuple σ := (σi,S )i∈[n],S∈Σi , that is a state of the game where σi,S ≥ 0 is the total amount of players of type i selecting strategy S, for any i ∈ [n] and S ∈ Σi . Given a strategy profile σ, ke (σ) := P i∈[n],S∈Σi :e∈S σi,S isP the total amount of players selecting e in σ, and given a strategy S, cS (σ) := e∈S `e (ke (σ)) is the cost of players selecting S in σ. A pure Nash equilibrium (often called Wardrop equilibrium [51] when refer- ring to non-atomic games), is a strategy profile σ such that, for any i ∈ [n] and S ∈ Σi such that σi,S > 0, cS (σ) ≤ cS 0 (σ) holds P for any S 0 ∈ Σi . The total latency function is defined as SUM(σ) := i∈[n],S∈Σi σi,S cS (σ) = P e∈E k e (σ)`e (k e (σ)). Finally, the concepts of singleton games, symmetric games, social optima, and price of anarchy are defined as in atomic congestion games. Given θ ≥ 1, a non-atomic congestion game with θ-similar strategy NCG(θ) is equal to a given non-atomic congestion Pgame NCG, but where the set of strategy is Σi (θ) := S ∈ Σi : e∈S `e (0) ≤ θ e∈S 0 `e (0) ∀S 0 ∈ Σi 3 .  P 3 Affine Congestion Games with Similar Strategies In the following theorem we compute an upper bound on the price of anarchy of affine congestion games with θ-similar strategies for any θ ≥ 1, when there is no restrictions on the players’ strategic space. 3 To define Σi (θ) for the non-atomic case, we consider `e (0) instead of `e (1) since, for non-atomic games, the contribution of each player to the congestion of each resource is null, differently from atomic games in which the contribution to the congestion is unitary. 6 V. Bilò and C. Vinci Theorem 1 (Upper Bound). Let CG(θ) be an arbitrary affine congestion game with θ-similar strategies. Then4 :  √ (4θ−6) θ 2 −θ+3+4θ 2 +θ−8    8θ−11 if 1 ≤ θ < 11 8 or 11 8 < θ < 32 PoA(CG(θ)) ≤ 289 if θ = 811  120 5  if θ ≥ 23 2 Proof. If θ ≥ 32 the upper bound of 52 trivially holds since 52 is the price of anarchy of general affine congestion games [20, 3], i.e. for θ → ∞. Assume that 1 ≤ θ < 11 11 3 8 or 8 < θ < 2 . Because of Remark 1, assume without loss of generality that CG(θ) is a linear congestion game. Let σ = (σ1 , σ2 , . . . , σn ) and σ ∗ = (σ1∗ , σ2∗ , . . . , σn∗ ) be a pure Nash equilibrium and a social optimum of CG(θ), respectively. By applying the primal-dual method (a powerful technique introduced by Bilò [6] to determine good bounds on the performance of congestion games), we get the following linear program (recall that we write ke and oe in place of ke (σ) and ke (σ ∗ ), respectively): X LP : max αe ke2 (1) e∈E X X s.t. αe ke2 ≤ αe oe (ke + 1) (2) e∈E e∈E X X αe ke ≤ θ αe oe (3) e∈E e∈E X αe o2e = 1 (4) e∈E αe ≥ 0, ∀e ∈ E where: • the objective function (1) is the total latency of σ; • (2) has been obtained by relaxing inequality ci (σ) ≤ ci (σ−i , σi∗ ) (that holds because P of the pure Nash P equilibrium condition) to obtain inequalities of the form e∈σi αe ke ≤ e∈σ∗ αe (ke + 1), and by summing them for any i ∈ [n]; i P • (3) P has been obtained by summing all the inequalities e∈σi αe ≤ θ e∈σ∗ αe for each i ∈ [n] (holding since strategies are θ-similar); i • the linear coefficients αe ’s are the variables of the linear program, and the other quantities are fixed parameters; • (4) normalizes the optimal social function, so that the maximum value of the objective function is an upper bound on the price of anarchy. By taking the dual of LP, in which we associate the dual variable x(θ) to the primal constraint (2), the dual variable y(θ) to the primal constraint (3), and 4 We consider separately the case θ = 11 8 since the function determining the price of anarchy for the cases 1 ≤ θ < 11 8 or 11 8 < θ < 32 (so as other functions considered in the proof) is not defined for θ = 11 8 (it is of the form 00 ), but can be extended by continuity to θ = 11 8 , thus obtaining for θ → 11 8 a price of anarchy of 289 120 . The Price of Anarchy of Affine Congestion Games with Similar Strategies 7 the dual variable γ(θ) to the primal constraint (4), we get: DLP : min γ(θ) s.t. γ(θ)o2e − ke2 − x(θ) −ke2 + oe (ke + 1) − y(θ) (−ke + θoe ) ≥ 0, ∀e ∈ E (5)  x(θ), y(θ) ≥ 0 For the weak duality theorem, we get that any feasible solution (γ(θ), x(θ), y(θ)) of DLP is such that γ(θ) is an upper bound on the maximum value of LP, i.e. an upper bound √ on the price of anarchy. One√ can show that, by setting (4θ−6) θ 2 −θ+3+4θ 2 +θ−8 θ 2 −θ+3 γ(θ) := 8θ−11 , x(θ) := 10θ−10−2 8θ−11 ≥ 1 and y(θ) := √ 4 θ 2 −θ+3+4θ−13 8θ−11 ≥ 0, constraint (5) is verified for any ke , oe ∈ Z≥0 (a formal proof of this fact is deferred to the full version), and the claim follows. Finally, if θ = 11 8 it suffices considering the quantities γ(θ), x(θ), y(θ) defined above, but for θ → 11 8 , and the claim follows as well. t u We have that the upper bound shown in Theorem 1 is tight (the proof is deferred to the full version). Theorem 2 (Lower Bound). For any  > 0, there exists an affine congestion game with θ-similar strategies CG(θ) such that:  √ 2 2  (4θ−6) θ −θ+3+4θ +θ−8 −   if 1 ≤ θ < 11 or 11 < θ < 23  8θ−11 8 8 PoA(CG(θ)) ≥ 289 −  if θ = 811  120 5  if θ ≥ 23 2 3.1 The Case of Symmetric Singleton Games Now, we focus on the case of symmetric singleton games. In the following the- orem, we compute an upper bound on the price of anarchy of affine symmetric singleton congestion games with θ-similar strategies, for any θ ≥ 1. Theorem 3 (Upper Bound). Let CG(θ) be an arbitrary affine symmetric sin- gleton congestion game with θ-similar strategies. Then: ( 3θ−2 2θ−1 if 1 ≤ θ < 2 PoA(CG(θ)) ≤ 4 3 if θ ≥ 2 Proof. If θ ≥ 2 the upper bound of 34 trivially holds since 43 is the price of anarchy of affine symmetric singleton games, i.e. when θ = ∞. Assume that θ ∈ [1, 2). Let σ := (σ1 , σ2 , . . . , σn ) and σ ∗ := (σ1∗ , σ2∗ , . . . , σn∗ ) be a pure Nash equilibrium and a social optimum of CG(θ), respectively. The discrepancy of resource e ∈ E is defined as de := ke −oe . Resource e is overloaded if de > 0; it is underloaded if de < 0. Define E + := {e ∈ E : de > 0} as the set of overloaded resources and E − := {e ∈ E : de < 0} as the set of underloaded ones. Note that, since in any strategyP profile each P player uses exactly one resource, the following property holds: e∈E +P de + e∈E − de = 0. Define the discrepancy between σ and σ ∗ as the value d = e∈E + de . 8 V. Bilò and C. Vinci A rebalancing deviation is a deviation (σ−i , si ) such that σi ∈ E + and si ∈ − E , that is, the deviating player abandons an overloaded resource to join an underloaded one; hence, a rebalancing deviation can be specified by a triple (p, old, new), where p ∈ N is the deviating player, old ∈ E + is the abandoned resource and new ∈ E − is the newly joined one. A rebalancing is a collection of rebalancing deviations in which each player is involved at most once. It is easy to see that there exists a rebalancing (p(i), old(i), new(i))i∈[d] made up of d rebalancing deviations which recreates σ ∗ starting from σ. Since σ is a Nash equilibrium, for each i ∈ [d], we have αold(i) kold(i) + βold(i) ≤ αnew(i) (knew(i) + 1) + βnew(i) . Moreover, since CG(θ) is a symmetric singleton game withθ-similar strategies, for each i ∈ [d], we have αnew(i) + βnew(i) ≤ θ αold(i) + βold(i) . Hence, by applying the primal-dual method, we get the following linear program: X LP : max αe ke2 + βe ke e∈E s.t. αold(i) kold(i) + βold(i) ≤ αnew(i) (knew(i) + 1) + βnew(i) , ∀i ∈ [d]  αnew(i) + βnew(i) ≤ θ αold(i) + βold(i) , ∀i ∈ [d] X αe o2e + βe oe = 1, αe , βe ≥ 0 ∀e ∈ E e∈E By taking the dual of LP, in which we associate the dual variable xi (θ) to the ith primal constraint of the first family, the dual variable yi (θ) to the ith primal constraint of the second family, and the dual variable γ(θ) to the last primal constraint, we get: DLP : min γ(θ) X X s.t. xi (θ)ke − xi (θ)(ke + 1) i∈[d]:old(i)=e i∈[d]:new(i)=e X X − yi (θ)θ + yi (θ) + γ(θ)o2e ≥ ke2 , ∀e ∈ E i∈[d]:old(i)=e i∈[d]:new(i)=e X X xi (θ) − xi (θ) i∈[d]:old(i)=e i∈[d]:new(i)=e X X − yi (θ)θ + yi (θ) + γ(θ)oe ≥ ke , ∀e ∈ E i∈[d]:old(i)=e i∈[d]:new(i)=e xi (θ), yi (θ) ≥ 0, ∀i ∈ [d] 3θ−2 3θ−1 One can show that, by setting γ(θ) := 2θ−1 , xi (θ) := 2θ−1 ≥ 1 and yi (θ) := 1 2θ−1 ≥ 0 ∀i ∈ [d], both dual constraints are verified for any ke , oe ∈ Z≥0 (a formal proof of this fact is deferred to the full version), thus, for the weak duality theorem, the considered γ(θ) is an upper bound on PoA(CG(θ)). t u In the following theorem, we show that the previous upper bound is almost tight, by exhibiting an almost tight lower bound. Theorem 4 (Lower Bound). For any θ ≥ 1, there exists an affine symmetric singleton congestion game with θ-similar strategies CG(θ), such that: ( 2θ θ+1 if 1 ≤ θ < 2 PoA(CG(θ)) ≥ 4 3 if θ ≥ 2 The Price of Anarchy of Affine Congestion Games with Similar Strategies 9 Proof. For θ ≥ 2 the lower bound defined in [37] is an affine symmetric singleton congestion game with θ-similar strategies and having a price of anarchy of 34 . If θ < 2, consider a symmetric singleton congestion game CG having two players, two resources e1 , e2 with `e1 (x) := (θ − 1)x + 2 − θ and `e2 (x) := θ. One can easily observe that the strategy profile σ in which all players select resource e1 is a pure Nash equilibrium, and that both strategies {e1 } and {e2 } belong to Σ(θ). Let σ ∗ be the strategy profile in which one player selects e1 , and the other SUM(σ) ((θ−1)2+2−θ)2 2θ one selects e2 . We get PoA(CG(θ)) ≥ SUM(σ ∗ ) = (θ−1)+(2−θ)+θ = 1+θ . t u 4 Affine Non-atomic Congestion Games with Similar Strategies Now, we compute an upper bound on the price of anarchy of non-atomic con- gestion games with θ-similar strategies, for any θ ≥ 1 (a formal proof is deferred to the full version). Theorem 5 (Upper Bound). Let NCG(θ) be an arbitrary affine non-atomic congestion game with θ-similar strategies. Then:  √ 2 (θ−1)θ+θ−2  √ if 1 ≤ θ < 43 or 43 < θ    PoA(CG(θ)) ≤ (3θ−4) 2 (θ−1)θ−θ 9  if θ = 43 8 We show that the previous upper bound is tight (a formal proof is deferred to the full version). Theorem 6 (Lower Bound). For any θ ≥ 1 and for any  > 0, there exists an affine non-atomic congestion game with θ-similar strategies NCG(θ) such that:  √ 2 (θ−1)θ+θ−2  √ if 1 ≤ θ < 43 or 43 < θ    − PoA(CG(θ)) ≥ (3θ−4) 2 (θ−1)θ−θ 9 −   if θ = 43 8 We also exhibit an almost tight lower bound for affine symmetric singleton non- atomic congestion games. Theorem 7 (Lower Bound for Symmetric Singleton Games). For any θ ≥ 1, there exists an affine symmetric singleton non-atomic congestion game with θ-similar strategies NCG(θ), such that: 4θ PoA(NCG(θ)) ≥ 3θ + 1 Proof. Consider a symmetric singleton non-atomic congestion game NCG having a unitary amount of players, and two resources e1 , e2 with `e1 (x) := (θ − 1)x + 1 and `e2 (x) := θ. One can easily observe that the strategy profile σ in which all players select resource e1 is a pure Nash equilibrium, and that both strategies {e1 } and {e2 } belong to Σ(θ). Let σ ∗ be the strategy profile in which half of the players select e1 , and the remaining ones select e2 . We get PoA(NCG(θ)) ≥ SUM(σ) (θ−1)+1 4θ SUM(σ ∗ ) = 1 (θ−1)+ 1 + 1 θ = 3θ+1 . t u 4 2 2 10 V. Bilò and C. Vinci 5 Conclusions and Open Problems In this work we have introduced the class of congestion games with similar strate- gies, and we have almost completely characterized the performance of such games in terms of price of anarchy. Our work leaves several open problems. For instance, when considering symmetric singleton games, the given upper and lower bounds are not tight for both the atomic and the non-atomic case. Moreover, it would be interesting considering more general latency functions (e.g. polynomial). Overall, despite its theoretical importance, we think that our parametrization may provide an interesting and reasonable step towards the definition of a more concrete model for selfish routing games. References 1. S. Aland, D. Dumrauf, M. Gairing, B. Monien, and F. Schoppmann. Exact price of anarchy for polynomial congestion games. SIAM Journal on Computing, 40(5):1211–1233, 2011. 2. E. Anshelevich, A. Dasgupta, J. M. Kleinberg, E. Tardos, T. Wexler, and T. Rough- garden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602–1623, 2008. 3. B. Awerbuch, Y. Azar, and L. Epstein. The price of routing unsplittable flow. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, pp. 57–66, 2005. 4. M. J. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of Transportation. Yale University Press, 1956. 5. 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. 6. V. Bilò. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA), LNCS 7846, Springer, pp. 229–241, 2012. 7. V. Bilò. On linear congestion games with altruistic social context. In Proceedings of the 20th International Computing and Combinatorics Conference (COCOON), LNCS 8591, Springer, pp. 547–558, 2014. 8. V. Bilò. On the robustness of the approximate price of anarchy in generalized congestion games. In Proceedings of 9th International Symposium on Algorithmic Game Theory (SAGT), LLNCS 9928, Springer, pp. 93–104, 2016. 9. V. Bilò, A. Celi, M. Flammini, and V. Gallotti. Social context congestion games. Theoretical Computer Science, 514:21–35, 2013. 10. V. Bilò, 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. 11. V. Bilò, M. Flammini, and L. Moscardelli. The price of stability for undirected broadcast network design with fair cost allocation is constant. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, pp. 638–647, 2013. 12. V. Bilò, L. Moscardelli, and C. Vinci. Uniform mixed equilibria in network conges- tion games with link failures. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), to appear. The Price of Anarchy of Affine Congestion Games with Similar Strategies 11 13. V. Bilò and C. Vinci. On Stackelberg strategies in affine congestion games. In Proceedings of the 11th International Conference on Web and Internet Economics (WINE), LNCS 9470, Springer, pp. 132–145, 2015. 14. V. Bilò and C. Vinci. Dynamic taxes for polynomial congestion games. In Proceed- ings of the 17th ACM Conference on Economics and Computation (EC), ACM Press, pp. 839–856, 2016. 15. V. Bilò and C. Vinci. On the impact of singleton strategies in congestion games. In Proceedings of the 25th Anual European Symposium on Algorithms (ESA), Leibniz- Zentrum fuer Informatik, 17:1–17:14, 2017. 16. I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli. Tight bounds for selfish and greedy load balancing. Algorithmica, 61(3):606–637, 2011. 17. I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Taxes for linear atomic con- gestion games. ACM Transactions on Algorithms, 7,1, 2010. 18. I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, M. Kyropoulou, and E. Papaioan- nou. The impact of altruism on the efficiency of atomic congestion games. In Pro- ceedings of the 5th International Symposium on Trustworthly Global Computing (TGC), LNCS 6084, Springer, pp. 172–188, 2010. 19. P. Chen, B. de Keijzer, David Kempe, and G. Schäfer. The robust price of anarchy of altruistic games. ACM Transaction on Economics and Computation, 2(4):17, 2014. 20. G. Christodoulou and E. Koutsoupias. The price of anarchy of finite congestion games. In Proceedings of the 37th Annual ACM Symposium on Theory of Comput- ing (STOC), ACM Press, pp. 67–73, 2005. 21. G. Christodoulou and E. Koutsoupias. On the price of anarchy and stability of correlated equilibria of linear congestion games. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), LNCS 3669, Springer, pp. 59–70, 2005. 22. G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms. Theoretical Computer Science, 410(36):3327–3336, 2009. 23. G. Christodoulou, E. Koutsoupias, and P. G. Spirakis. On the performance of approximate equilibria in congestion games. Algorithmica, 61(1):116–140, 2011. 24. G. Christodoulou, V. S. Mirrokni, and A. Sidiropoulos. Convergence and approxi- mation in potential games. Theoretical Computer Science, 438:13–27, 2012. 25. R. Cole, Y. Dodis, and T. Roughgarden How much can taxes help selfish routing? Journal of Computer and System Sciences, 72(3):444-17467, 2006. 26. R. Cominetti, J. R. Correa, and N. E. Stier Moses. Network games with atomic players. In Proceedings of the 33rd Annual International Colloquium in Automata, Languages, and Programming (ICALP), LNCS 4051, Springer, pp. 525-17536, 2006. 27. J. R. Correa, A. S. Schulz, and N. E. Stier Moses. Selfish routing in capacitated networks. Mathematics of Operations Research, 29(4):961-17976, 2004. 28. J. R. Correa, A. S. Schulz, and N. E. Stier Moses. On the inefficiency of equilibria in congestion games. In Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 16717-181, 2005. 29. A. Czumaj and B. Vöcking. Tight Bounds for Worst-case Equilibria. ACM Trans- actions on Algorithms, 3(1):4:1–4:17, 2007. 30. J. de Jong, W. Kern, B. Steenhuisen, and M. Uetz. The aymptotic price of anarhcy for k-uniform congestion games. In 15th International Workshop on Approximation and Online Algorithms (WAOA), LNCS 10787, Springer, pp. 317–328, 2017. 31. B. de Keijzer, Guido Schäfer, A. Anagnostopoulos, and L. Becchetti. Inefficiency of games with social context. In Proceedings of the 6th International Symposium on Algorithmic Game Theory (SAGT), LNCS 8146, Springer, pp. 219–230, 2013. 12 V. Bilò and C. Vinci 32. D. Fotakis. Stackelberg strategies for atomic congestion games. Theory of Com- puting Systems, 47(1):218–249, 2010. 33. D. Fotakis and P. G. Spirakis. Cost-balancing tolls for atomic network congestion games. In Proceedings of the 3rd International Conference on Internet and Network Economics (WINE), LNCS 4858, Springer, pp. 179-17190, 2007. 34. T. Jelinek, M. Klaas, and G. Schäfer. Computing optimal tolls with arc restric- tions and heterogeneous players. In Proceedings of the 31st International Sympo- sium on Theoretical Aspects of Computer Science (STACS), LIPIcs 25, Schloss DagstuhlLeibniz-Zentrum fuer Informatik, pp. 433-17444, 2014. 35. G. Karakostas and S. Kolliopoulos. Stackelberg strategies for selfish routing in general multicommodity networks. Algorithmica, 53(1):132–153, 2009. 36. 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. 37. T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish routing. Theoretical Computer Science, 406(3):187–206, 2008. 38. J. F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Science, 36(1):48–49, 1950. 39. A. C. Pigou. The economics of welfare. Macmillan. 1920. 40. M. Rahn and G. Schäfer. Bounding the inefficiency of altruism through social contribution games. In Proceedings of the 9th International Conference on Web and Internet Economics (WINE), LNCS 8289, Springer, pp. 391–404, 2013. 41. R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. Inter- national Journal of Game Theory, 2(1):65–67, 1973. 42. T. Roughgarden. The price of anarchy is independent of the network topology. Journal of Computer and System Sciences, 67(2):341–364, 2003. 43. T. Roughgarden. Stackelberg scheduling strategies. SIAM Journal on Computing, 33(2):332-17350, 2004. 44. T. Roughgarden. Selfish routing with atomic players. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press, pp. 1184-171185, 2005. 45. T. Roughgarden. Intrinsic robustness of the price of anarchy. Journal of ACM, 62(5):32:1–32:42, 2015. 46. T. Roughgarden. Selfish routing. In N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Ed.), Algorithmic Game Theory. Cambridge University Press, pp. 461–486, 2007. 47. T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of ACM, 49(2):236–259, 2002. 48. S. Suri, C. D. Tóth, and Y. Zhou. Selfish load balancing and atomic congestion games. Algorithmica, 47(1):79–96, 2007. 49. C. Swamy. The effectiveness of Stackelberg strategies and tolls for network conges- tion games. ACM Transactions on Algorithms, 8(4):36, 2012. 50. C. Vinci. Non-atomic one-round walks in polynomial congestion games. In Pro- ceedings of the 17th Italian Conference on Theoretical Computer Science (ICTCS), CEUR Workshop Proceedings 1720, pp. 11–22, 2016. 51. J. G. Wardrop. Some theoretical aspects of road traffic research. In Proceedings of the Institution of Civil Engineers, Part II, 36(1):352–362, 1952.