A ne congestion games are a well-studied model for sel sh behavior in distributed systems, such as transportation and communication networks. Seminal in uential papers in Algorithmic Game Theory have bounded the worst-case ine ciency of Nash equilibria, termed as price of anarchy, in several variants of these games. In this work, we investigate 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 nite value of . For the atomic case, instead, < 3=2 and < 2 are necessary and su cient conditions to obtain better bounds in games played on general graph topologies and on parallel link graphs, respectively. It is worth noticing that small values of model the behavioral attitude of players who are partially oblivious to congestion and are not willing to signi cantly deviate from what is their best strategy in absence of congestion.
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 diversi ed. In an ideal situation
in which travel time is not a ected by tra c, 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 tra c delay. As every worker can be seen as a sel sh 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 [
There is a vast scienti c literature on routing games, started from the
beginning of the last century with the early works on transportation networks by
Pigou [
Two versions of congestion games are usually considered in the literature
depending on the amount of tra c controlled by the players: the atomic case
and the non-atomic one. In the atomic case [
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 [
In this work, we investigate to what extent the price of anarchy of a ne congestion games is a ected by 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.
For the non-atomic case, we show that the price of anarchy is exactly
(3 p4)( 2p1)+( 12) 2 for any 2 R 1 n 34 and 98 for = 34 . Hence, improvements
on the 43 -bound shown by Roughgarden and Tardos [
The price of anarchy of non-atomic congestion games has been rst considered in
the seminal papers by Roughgarden and Tardos [
For an integer i, set [i] := f1; 2; : : : ; ig. An atomic congestion game, or simply congestion game, is a tuple CG = [n]; E; (`e)e2E ; ( i)i2[n] , where [n] is a set of n 2 players, E is a set of resources, `e : R 0 ! R 0 is the latency function of resource e 2 R, and, for each player i 2 [n], i 2R n ; is her set of strategies (i.e. a strategy is a non-empty subset of resources).
A congestion game is a ne when, for each e 2 E, `e(x) = ex + e, with e; e 0. If e = 0 for any e 2 E we speak of linear congestion games. A singleton congestion game is a congestion game in which, for each i 2 [n] and S 2 i, jSj = 1, i.e., each player can only select single resources, and a symmetric congestion game is one in which i = for each i 2 [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 pro le is an n-tuple of strategies = ( 1; : : : ; n), that is, a state of the game in which each player i 2 [n] is adopting strategy i 2 i, so that i2[n] i denotes the set of strategy pro les which can be realized in CG. For a strategy pro le , the congestion of resource e 2 E in , denoted as ke( ) := jfi 2 [n] : e 2 igj, is the number of players using resource e in .
The cost of player i in is de ned as ci( ) := Pe2 i `e(ke( )) and each
player aims at minimizing it. For the sake of conciseness, when the strategy
pro le 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 i 2 [n] has a strategy set i( ) i de ned
as follows: i( ) := S 2 i : Pe2S `e(1) Pe2S0 `e(1) 8S0 2 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 = 1, CG( ) coincides with CG.
Pure Nash Equilibria Fix a strategy pro le and a player i 2 [n]. We
denote with i the restriction of to all the players other than i; moreover,
for a strategy S 2 i, we denote with ( i; S) the strategy pro le obtained from
when player i changes her strategy from i to S, while the strategies of all the
other players are kept xed. A pure Nash equilibrium [
Quality of Equilibria A social function that is usually used as a measure of the quality of a strategy pro le in congestion games is the total latency, de ned as SUM( ) := Pi2[n] ci( ) = Pe2E ke( )`e(ke( )). A social optimum is a strategy pro le minimizing SUM. Again, for the sake of conciseness, once a particular social optimum has been xed, we write oe to denote the value ke( ).
The price of anarchy of a congestion game CG (with respect to the social function 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.
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 [
Non-atomic Congestion Games Non-atomic congestion games [
The concepts de ned for atomic congestion games can be adapted to the nonatomic case. A strategy pro le is a tuple := ( i;S )i2[n];S2 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 2 [n] and S 2 i. Given a strategy pro le , ke( ) := Pi2[n];S2 i:e2S i;S is the total amount of players selecting e in , and given a strategy S, cS ( ) := Pe2S `e(ke( )) is the cost of players selecting S in .
A pure Nash equilibrium (often called Wardrop equilibrium [
Given 1, a non-atomic congestion game with -similar strategy NCG( ) is equal to a given non-atomic congestion game NCG, but where the set of strategy is i( ) := S 2 i : Pe2S `e(0) Pe2S0 `e(0) 8S0 2 i 3: 3
A
ne Congestion Games with Similar Strategies
In the following theorem we compute an upper bound on the price of anarchy
of a ne congestion games with -similar strategies for any 1, when there is
no restrictions on the players' strategic space.
3 To de ne 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, di erently from atomic games in which the contribution to the congestion is
unitary.
Theorem 1 (Upper Bound). Let CG( ) be an arbitrary a ne congestion
game with -similar strategies. Then4:
Proof. If 23 the upper bound of 52 trivially holds since 52 is the price of
anarchy of general a ne congestion games [
Assume that 1 < 181 or 181 < < 32 . 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 Bilo [
X e2E X e2E X e2E X e2E e
2 eke
2 eke eke eoe2 = 1 0; the objective function (1) is the total latency of ; (2) has been obtained by relaxing inequality ci( ) ci( i; i ) (that holds because of the pure Nash equilibrium condition) to obtain inequalities of the form Pe2 i eke Pe2 i e(ke + 1), and by summing them for any i 2 [n]; (3) has been obtained by summing all the inequalities Pe2 i e
Pe2 i e for each i 2 [n] (holding since strategies are -similar); the linear coe cients e's are the variables of the linear program, and the other quantities are xed 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 = 181 since the function determining the price of anarchy for the cases 1 < 181 or 181 < < 32 (so as other functions considered in the proof) is not de ned for = 181 (it is of the form 00 ), but can be extended by continuity to = 181 , thus obtaining for ! 181 a price of anarchy of 122809 . the dual variable ( ) to the primal constraint (4), we get: DLP : min
( ) 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)p 28 +131+4 2+ 8 , x( ) := 10 108 2p112 +3 1 and y( ) := 4p 2 8 +31+14 13 0, constraint (5) is veri ed for any ke; oe 2 Z 0 (a formal proof of this fact is deferred to the full version), and the claim follows. above, but for =!181181it, saund the claim follows as well. tu
Finally, if ces considering the quantities ( ); x( ); y( ) de ned 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 a ne congestion game with -similar strategies CG( ) such that: Now, we focus on the case of symmetric singleton games. In the following theorem, we compute an upper bound on the price of anarchy of a ne symmetric singleton congestion games with -similar strategies, for any 1. Theorem 3 (Upper Bound). Let CG( ) be an arbitrary a ne symmetric singleton congestion game with -similar strategies. Then: Proof. If 2 the upper bound of 43 trivially holds since 43 is the price of anarchy of a ne symmetric singleton games, i.e. when = 1.
Assume that 2 [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 2 E is de ned as de := ke oe. Resource e is overloaded if de > 0; it is underloaded if de < 0. De ne E+ := fe 2 E : de > 0g as the set of overloaded resources and E := fe 2 E : de < 0g as the set of underloaded ones. Note that, since in any strategy pro le each player uses exactly one resource, the following property holds: Pe2E+ de + Pe2E de = 0. De ne the discrepancy between and as the value d = Pe2E+ de.
A rebalancing deviation is a deviation ( i; si) such that i 2 E+ and si 2 E , that is, the deviating player abandons an overloaded resource to join an underloaded one; hence, a rebalancing deviation can be speci ed by a triple (p; old; new), where p 2 N is the deviating player, old 2 E+ is the abandoned resource and new 2 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))i2[d] made up of d rebalancing deviations which recreates starting from . Since is a Nash equilibrium, for each i 2 [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 2 [d], we have new(i) + new(i) old(i) + old(i) : Hence, by applying the primal-dual method, we get the following linear program: LP : max
eke2 + eke s.t.
old(i)kold(i) + old(i) new(i)(knew(i) + 1) + new(i); 8i 2 [d] new(i) + new(i) X eoe2 + eoe = 1; old(i) + old(i) ; e; e 0
8i 2 [d] By taking the dual of LP, in which we associate the dual variable xi( ) to the ith primal constraint of the rst 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 s.t.
xi( )ke
xi( )(ke + 1) ( )
X i2[d]:old(i)=e
X i2[d]:old(i)=e
X
xi( ) i2[d]:old(i)=e
X i2[d]:old(i)=e xi( ); yi( ) 0; yi( ) + yi( ) + i2[d]:new(i)=e
X 8i 2 [d]
X i2[d]:new(i)=e
X i2[d]:new(i)=e X
xi( ) i2[d]:new(i)=e yi( ) + ( )oe2
2 ke ;
8e 2 E yi( ) + ( )oe ke; One can show that, by setting ( ) := 23 12 , xi( ) := 32 11 1 and yi( ) := 2 1 1 0 8i 2 [d]; both dual constraints are veri ed for any ke; oe 2 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( )). tu 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 a ne symmetric
singleton congestion game with -similar strategies CG( ), such that:
Proof. For 2 the lower bound de ned in [
A ne Non-atomic Congestion Games with Similar Strategies Now, we compute an upper bound on the price of anarchy of non-atomic congestion 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 a ne non-atomic congestion game with -similar strategies. Then: if = 43 < 43 or 43 < 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 a ne non-atomic congestion game with -similar strategies NCG( ) such that: if = 43 < 43 or 43 < We also exhibit an almost tight lower bound for a ne symmetric singleton nonatomic congestion games.
Theorem 7 (Lower Bound for Symmetric Singleton Games). For any 1, there exists an a ne symmetric singleton non-atomic congestion game with -similar strategies NCG( ), such that:
PoA(NCG( ))
4 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 pro le in which all players select resource e1 is a pure Nash equilibrium, and that both strategies fe1g and fe2g belong to ( ). Let be the strategy pro le in which half of the players select e1, and the remaining ones select e2. We get PoA(NCG( )) SSUUMM(( )) = 14 ( ( 1)1+) +21+1 12 = 3 4+1 : tu
In this work we have introduced the class of congestion games with similar strategies, 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 de nition of a more concrete model for sel sh routing games.