=Paper=
{{Paper
|id=Vol-2243/paper3
|storemode=property
|title=The Price of Anarchy of Affine Congestion Games with Similar Strategies
|pdfUrl=https://ceur-ws.org/Vol-2243/paper3.pdf
|volume=Vol-2243
|authors=Vittorio Bilò,Cosimo Vinci
|dblpUrl=https://dblp.org/rec/conf/ictcs/BiloV18
}}
==The Price of Anarchy of Affine Congestion Games with Similar Strategies==
https://ceur-ws.org/Vol-2243/paper3.pdf
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.