=Paper=
{{Paper
|id=Vol-1720/full1
|storemode=property
|title=Non-Atomic One-Round Walks in Polynomial Congestion Games
|pdfUrl=https://ceur-ws.org/Vol-1720/full1.pdf
|volume=Vol-1720
|authors=Cosimo Vinci
|dblpUrl=https://dblp.org/rec/conf/ictcs/Vinci16
}}
==Non-Atomic One-Round Walks in Polynomial Congestion Games==
https://ceur-ws.org/Vol-1720/full1.pdf
Non-Atomic One-Round Walks
in Polynomial Congestion Games
Cosimo Vinci
Gran Sasso Science Institute, L’Aquila - Italy
cosimo.vinci@gssi.infn.it
Abstract. In this paper we study the approximation ratio of the solu-
tions achieved after an -approximate one-round walk in non-atomic con-
gestion games. Prior to this work, the solution concept of one-round walks
had been studied for atomic congestion games with linear latency func-
tions only [Christodoulou et al. 2006, Bilò et al. 2011]. We focus on polyno-
mial latency functions, and, by exploiting the primal-dual technique [Bilò
2012], we prove that the approximation ratio is exactly ((1 + )(p + 1))p+1
for every polynomial of degree p. Then, we show that, by resorting to
static (resp. dynamic) resource taxation, the approximation ratio can be
lowered to (1 + )p+1 (p + 1)p (resp. (1 + )p+1 (p + 1)!).
Keywords: computational social choice, algorithmic game theory, con-
gestion games
1 Introduction
Since the end of the Twentieth Century, the computer science community has
been interested in the study of complex systems populated by (numerous) selfish
agents interacting with each other, and in how their selfish behavior impacts on
the social welfare [24]. As examples, one may think to web users greedily sharing
limited resources, or to drivers who want to move as fast as possible from a
location to another along a street network.
These systems are often modeled by congestion games [25]. In these games,
there is a set of non-cooperative selfish players sharing a set of resources and
each resource incurs a certain latency to the players using it. Each player has an
available set of strategies, where each strategy is a non-empty subset of resources,
and aims at choosing a strategy minimizing her cost which is defined as the sum
of the latencies experienced on all the selected resources. A congestion game is
called atomic when the set of players is finite, and it is called non-atomic when
Copyright c by the paper’s authors. Copying permitted for private and academic pur-
poses.
V. Biló, A. Caruso (Eds.): ICTCS 2016, Proceedings of the 17th Italian Conference
on Theoretical Computer Science, 73100 Lecce, Italy, September 7–9 2016, pp. 11–22
published in CEUR Workshop Proceedins Vol-1720 at http://ceur-ws.org/Vol-1720
12 Cosimo Vinci
the set of players is infinite and the contribution of each player to the social
welfare is infinitesimally small.
In congestion games, selfish behavior always leads to stable outcomes, called
Pure Nash Equilibrium [23], in which each player cannot improve her utility by
unilaterally deviating from her strategy. In general, Pure Nash Equilibria do not
yield an optimal social welfare, hence, to measure the quality of these outcomes,
two metrics have been successfully proposed: the price of anarchy [21] and the
price of stability [2]. They are defined as the highest and the lowest ratio between
the social welfare at any Nash equilibrium and the social optimum, respectively.
Besides Pure Nash Equilibria, in the setting of atomic congestion games,
the notion of one-round walks starting from the empty state has been widely
investigated due to its simplicity and effectiveness. This concept assumes that,
starting from the situation in which no strategy has been specified yet, the players
are processed sequentially and, at each iteration, the selected player irrevocably
chooses her strategy so as to minimize her cost based on the choices of the
previous ones. The approximation ratio of one-round walks starting from the
empty state, an analogous of the price of anarchy instantiated to one-round walks,
measures the quality of the outcomes produced at the end of this process [22,14].
Our Contribution. In this work, we translate the solution concept of one-round
walks from atomic congestion games to non-atomic ones. We define the solution
concept of -approximate non-atomic one-round walk starting from the empty
state, in which there is a continuous flow of selfish players (instead of a discrete
number of players) greedily selecting their strategies with the aim of approxi-
mately (up to a factor of 1 + ) minimizing their costs, given the choices of their
predecessors. The -approximation ratio of a non-atomic one-round walk starting
from the empty state is the highest ratio of the the social value achieved by the
final outcome of an -approximate non-atomic one-round walk and the optimal
social value. In particular, we study this metric for non-atomic congestion games
with polynomial latencies, by proving a tight bound of ((1 + )(p + 1))p+1 , where
p is the the degree of the polynomial functions. Given that the (exact and ap-
proximate)
price of anarchy for these games has been proven to be equal to
Θ max p/ log(p), (1 + )p+1 , our result shows that outcomes generated after
one-round walks are tremendously worse (even asymptotically) than Pure Nash
Equilibria in terms of social welfare.
For such a reason, we also focus on (resource) taxation [4]: an approach that
has been intensively studied in the literature in order to improve the quality
of the outcomes resulting from selfish behavior in congestion games. We prove
that, by resorting to static taxation (taxes are constant with respect to resource
congestion), the -approximation ratio drops to (1 + )p+1 (p + 1)p , thus hav-
ing a good asymptotic reduction with respect to the case without taxes. By
resorting to dynamic taxation (in which taxes can vary as a function of re-
source congestion), we lower the -approximation ratio to (1 + )p+1 (p + 1)! ∈
Θ (1 + )p+1 (p + 1)p+3/2 e−p , thus having a further improvement.
Non-Atomic One-Round Walks in Polynomial Congestion Games 13
Related Work. The inefficiency of equilibria for polynomial congestion games has
been largely studied for both atomic and non-atomic congestion games. Relatively
to the non-atomic setting, Roughgarden [27] proves that the price of anarchy
for congestion games with polynomial latency functions of degree p is [1 − p(p +
1)−(p+1)/p ]−1 and characterizes the price of anarchy for other latency functions.
Christodoulou et al. [12] and Awerbuch et al. [3] prove that the price of
anarchy for linear atomic congestion games is 5/2 for unweighted games and
2.168 for weighted games. Aland. et al [1] generalize the previous results to
polynomial congestion games, and provide tight bounds asymptotically equal to
Θ(p/ log(p))p+1 on the price of anarchy for both unweighted and weighted atomic
congestion games with polynomial latency functions of degree p. Christodoulou
et al. [13] provide bounds on the approximate price of anarchy and stability for
both non-atomic and atomic polynomial congestion games, which are tight for
the former.
Among the mechanisms used to improve the quality of outcomes in congestion
games, the use of taxation has been extensively studied for several decades. The
marginal cost taxation [4] has been proven to enforce an optimal solution in
non-atomic congestion games with very general latency functions. In subsequent
works, the existence and the computation of efficient taxes in many variants of
non-atomic congestion games has been intensively studied [15,16,19,29].
Caragiannis et al. [11] study the efficiency of taxation for linear atomic conges-
tion games, and, among the obtained results, they prove that the price of anarchy
drops from to 2.168 to at least 2 for weighted congestion games. Bilò and Vinci
[8] extend the previous result to polynomial congestion games, and prove that,
by resorting to taxation, the -approximate price of anarchy of unweighted and
weighted atomic congestion games with polynomial latency functions drops to
Tp+1 (1 + ), where Tp+1 is the (p + 1)-th Touchard polynomial.
Other mechanisms used to reduce the price of anarchy in congestion games
are Stackelberg Strategies [26,29,20,7,17], in which the strategies of a fraction of
players can be controlled with the aim of reducing the price of anarchy.
Mirrokni and Vetta [22] initiate the study of the social welfare achieved after
multiple rounds of best-responses in a Nash-dynamics for a particular class of
games, and they also consider the case of a one round of best responses. Christo-
doulou et al. [14] study for the first time the quality of outcomes obtained after
a one round of best responses in linear atomic congestion games. They prove
that,
√ if players start from an empty √ state, the approximation ratio is at most
2+ 5 for unweighted games and 4+2 3 for weighted games. For the unweighted
setting, Bilò et al. [6] prove that the previous upper bound is tight, improving
a lower bound of 4 obtained for load balancing games by Caragiannis et al. [10].
They also consider as a social function the maximum utility among all players,
and provide asymptotically matching bounds for the approximation ratio of one-
round walks starting from the empty state and from an arbitrary state. Bilò
[5] studies the approximation ratio for atomic congestion games with quadratic
and cubic latency functions. The quality achieved by multiple rounds of best
responses in linear congestion games has been studied in [14,18]. Bilò and Vinci
14 Cosimo Vinci
[8] improve via taxation the performances of -approximated one-round walks
starting from the empty state in unweighted and weighted polynomial atomic
congestion games.
2 Preliminaries
For any integer n, set [n] := {1, 2, . . . , n} and [n]0 := [n] ∪ {0}.
Non-Atomic Congestion Games. A non-atomic congestion game is a tuple CG =
(N, E, (`e )e∈E , (ri )i∈N , (Σi )i∈N ), where N is a totally ordered set of n ≥ 2 types of
players, E is a set of resources, `e : R≥0 → R≥0 is the latency function of resource
e ∈ E, and, given i ∈ N, ri ∈ R≥0 is the amount of players of type i and Σi =
{Si,1 , . . . , Si,mi } ⊆ 2E is the set of strategies of a player of type i, that is, each
player of type i has mi ≥ 1 possible choices. A congestion game P has polynomial
latencies of degree p ∈ N when, for each e ∈ E, `e (x) := d∈[p]0 αe,d xd , with
αe,d ≥ 0 for each d ∈ [p]0 ; when p = 1, we speak of affine latencies.
A strategy profile is an n-tuple ∆ = (∆1 , . . . , ∆n ), where ∆i : Σi → R≥0 is a
function denoting, for each strategy P Si ∈ Σi , the amount ∆i (Si ) of players of type
i selecting strategy Si , so that S∈Σi ∆i (S) = ri . For aP strategy profile ∆, the
congestion of resource e ∈ E in ∆, denoted as ke (∆) := i∈N,S∈Σi :e∈S ∆i (S), is
the total amount of players using resourceP e in ∆. The cost of a player selecting
a strategy Si ∈ Σi is defined as cSi (∆) = e∈Si `e (ke (∆)) and each player aims
at minimizing it.
Non-Atomic One-Round Walks. For any type i ∈ N of players, we extend the
set Σi of strategies with the empty strategy ∅i , so as to include also the cases in
which some players have not chosen their strategies yet; in particular, we denote
with ∅ the empty state, that is, the strategy profile in which none of the players
has chosen a strategy.
For any ≥ 0, a strategy Si∗ ∈ Σi \ {∅i } is an -approximate best-response
0
(-best-response, for brevity) for players P of type i in ∆ if, for each Si ∈ Σi \ {∅i },
cSi (∆) ≤ (1 + )cSi0 (∆). Let M := i∈N ri and let f : [0, M ] → N be a right-
∗
R
continuous function such that f −1 [{i}] dx = ri for each i ∈ N. We call f an
ordering function. Let (∆f,t )t∈[0,M ] be a family of strategy profiles such that:
(1) S∈Σi \{∅i } ∆f,t
P R
i (S) = [0,t]∩f −1 [{i}] dx for each i ∈ N and t ∈ [0, M ] (then,
∆f,t f,t
R
i (∅i ) = ri − [0,t]∩f −1 [{i}] dx), (2) ∆i (S) is non-decreasing in t. Such a family
of strategy profiles is called a weak one-round walk starting from the empty state.
Observe that ∆f,ti (S) has to be necessarily a non-decreasing and Lipschitzian
function with respect to t. Informally, a weak one-round walk models a family
of strategy profiles generated by a flow of players sequentially selecting their
strategies, in such a way, for any t ∈ [0, M ], there is an amount ∆f,t i (S) of players
of type i which have already selected strategy S (Point 1), and these players
cannot change their strategy (Point 2). Moreover, observe that f defines the
ordering in which the players appear in the game.
Non-Atomic One-Round Walks in Polynomial Congestion Games 15
A weak one-round walk is simple if t ≤ t0 ⇒ f (t) ≤ f (t0 ), and, for each i ∈ N,
there exists a strategy Si ∈ Σi such that ∆f,M
R
i (Si ) = f −1 [{i}] dx. Informally, a
weak one-round walk is simple if all players select their strategy according to
the ordering by which their types are defined in N, and if players of the same
type play the same strategy. A simple weak one-round walk can be univocally
represented as a sequence of strategies (Si )i∈N such that Si is the strategy played
by a player of type i. The strategy profile generated by a weak one-round walk
is ∆f,M .
A weak one-round walk (∆f,t )t∈[0,M ] is an -approximate non-atomic one-
round walk starting from the empty state (-one-round walk, for brevity) if, for any
t ∈ [0, M ] , ∆f,t
f (t) (S) is right-increasing at t only if strategy S is an -best-response
f,t
in ∆ for player f (t). Informally, an -one-round walk is a weak one-round walk
in which all players sequentially select an -best-response.
Efficiency Metrics. A social function that is usually used as a measure of the
quality of a strategy profile
P in non-atomic congestionPgames, is the total latency,
defined as TL(∆) = i∈N,Si ∈Σ ∆i (Si ) · cSi (∆) = e∈E ke (∆) · `e (ke (∆)). A
social optimum is a strategy profile ∆∗ minimizing TL. The approximation ratio
of -approximate non-atomic one-round walks starting from the empty state (-
approximation ratio, for brevity) of a congestion game CG (resp. a class of
congestion games) with respect to the total latency is the supremum of the ratio
TL(∆)/TL(∆∗ ), where ∆ is the strategy profile generated by an -one-round
walk for CG (resp. for some game CG in the class) and ∆∗ is a social optimum
for CG.
Taxes. A dynamic tax-function T := (Te )e∈E is a class of functions Te : R≥0 →
R≥0 increasing the latency function perceived by each player. The presence of
T determines a new congestion game CG(T ) = (N, E, (`0e )e∈E , (ri )i∈N , (Σi )i∈N ),
equal to CG except the latency functions, such that `0e (x) := `e (x) + Te (x) for
each e ∈ E. However, the total latency function is still evaluated with respect to
the initial latency functions `e s. T is a static tax-function if each Te is a constant
function (with respect to the resource congestion).
3 Approximation Ratio of One-Round Walks
3.1 Upper Bound
We prove our upper bound on the -approximation ratio by using the primal-dual
method: a technique introduced by Bilò in [5] to prove bounds on the performance
guarantee of self-emerging solutions (such as approximate pure Nash equilibria
and their generalizations, approximate one-round walks, and so on) in atomic
and non-atomic congestion games.
In our setting, we want to establish an upper bound on the worst-case per-
formance guarantee of -one-round walks with respect to the total latency in the
class of polynomial congestion games. For a general, but fixed, congestion game
16 Cosimo Vinci
CG, the method requires the construction of a linear program LP(CG) based on
the following steps: (1) the objective function is TL(∆), where ∆ is the strategy
profile generated by an arbitrary fixed -one-round walk for CG, (2) add the
constraint TL(∆∗ ) = 1, where ∆∗ is an arbitrary fixed social optimal for CG, (3)
relate ∆ and ∆∗ by adding, for each i ∈ N, suitable constraints that need to be
satisfied by the choices performed by all players of type i, (4) the coefficients of
the latency functions are treated as variables, while all the other quantities (e.g.
resources congestions) are treated as fixed parameters.
By the generality of CG, it follows that the optimal solution of LP(CG) is
an upper bound on the -approximation ratio in polynomial congestion games.
By the weak-duality theorem [9], any feasible solution to the dual formulation
of LP(CG) yields an upper bound on the -approximation ratio in polynomial
congestion games. The more the constraints defined during step (3) provide an
accurate characterization of the properties of -one-round walks, the more the
achieved upper bound will be significant (and possibly tight).
Theorem 1. The approximation ratio of -approximate one-round walks starting
from the empty state in congestion games with polynomial latency functions of
degree p is at most ((1 + )(p + 1))p+1 .
Proof. For an integer p ≥ 1, fix a congestion game CG having polynomial la-
tencies of degree p. Let f be an ordering function such that (∆f,t )t∈[0,M ] is an
-approximate one-round walk starting from the empty state, and let ∆ := ∆f,M .
Let ∆∗ be an optimal strategy profile, and let (o(t))t∈[0,M ] be a family of strate-
gies such that o(t) is right-continuous with respect to t, o(t) is a strategy of player
f (t) and o−1 [{S}]∩f −1 [{i}] dt = ∆∗i (S). Observe that such a family of strategies
R
always exists. For the sake of conciseness, we set ke := ke (∆) and oe := ke (∆∗ ).
By applying the primal-dual method, we get the following linear program LP(CG):
p
XX
max αe,d ked+1 (1)
e∈E d=0
| {z }
TL(∆)
s.t. c (S ∗ , o(t), ∆f,t ) ≤ 0, ∀S ∗ ∈ Σf (t) (∆f,t ), ∀t ∈ [0, M ] (2)
p
XX
αe,d od+1
e =1 (3)
e∈E d=0
| {z }
TL(∆∗ )
αe,d ≥ 0, ∀e ∈ E, ∀d ∈ [p]0 (4)
where Σi (∆0 ) is the set of all -best-responses of players of type i in a strategy
profile ∆0 , and c (S, S 0 , ∆0 ) is defined as follows:
p
XX p
XX
c (S, S 0 , ∆0 ) := αe,d ked (∆0 ) −(1 + ) αe,d ked (∆0 ) (5)
e∈S d=0 e∈S 0 d=0
| {z } | {z }
cS (∆0 ) cS 0 (∆0 )
Non-Atomic One-Round Walks in Polynomial Congestion Games 17
The constraints (2) come from the definition of -best-responses and -one-round
walks. By replacing constraint (2) with
p
XX p
X X
∗ f,t
ĉ (S , o(t), ∆ ) := αe,d ked (∆f,t ) − (1 + ) αe,d ked (∆) ≤ 0 (6)
e∈S ∗ d=0 e∈o(t) d=0
we obtain a relaxation of LP(CG). Given i ∈ N and S ∈ Σi \ ∅i , ĉ (S, o(t), ∆f,t )
can be defined as a function of ∆f,t f,t
i (S) except for the intervals on which ∆i (S)
is constant. By exploiting (6), we obtain
X Z ∆i (S)
0≥ ĉ (S, o(t), ∆f,t )d(∆f,t
i (S)) (7)
i∈N,S∈Σi 0
p
XX Z ke X
= αe,d ked (∆f,t )d ∆f,t
i (S)
(8)
e∈E d=0 0 i∈N,S∈Σi :e∈S
Z M p
X X
− (1 + ) αe,d ked dt (9)
0 e∈o(t) d=0
p p
Z ke !
XX XZ X
= αe,d ked (∆f,t )d(ke (∆f,t )) − (1 + ) αe,d ked dt
e∈E d=0 0 e∈E {t:e∈o(t)} d=0
(10)
p p
Z ke !
XX X Z oe X
= αe,d k d dk − (1 + ) αe,d ked dk (11)
e∈E d=0 0 e∈E 0 d=0
p p
XX ke d+1 X X
= αe,d − (1 + ) oe αe,d ked (12)
d+1
e∈E d=0 e∈E d=0
The equivalences between all pairs of integrals in the above derivation (along
with the fact that they are well-defined) come from the properties of the ∆f,t
i (S)s
as functions of t, and, more generally, from the Lebesgue theory of integration
[28]. In conclusion, by replacing the left-hand side of (2) with (12), we obtain the
following relaxation of LP(CG):
p
XX
max αe,d ked+1 (13)
e∈E d=0
p p
XX ke d+1 X X
s.t. αe,d − (1 + ) oe αe,d ked ≤ 0 (14)
d+1
e∈E d=0 e∈E d=0
XX p
αe,d od+1
e =1 (15)
e∈E d=0
αe,d ≥ 0, ∀e ∈ E, ∀d ∈ [p]0 (16)
18 Cosimo Vinci
The dual of this problem is the following linear problem LP0 (CG):
min γ (17)
ked+1
s.t. x − (1 + )oe ked + γod+1
e ≥ ked+1 ∀e ∈ E, d ∈ [p]0 (18)
d+1
x, γ ≥ 0 (19)
0
Clearly, any feasible solution for LP (CG) is an upper bound on the -approxima-
tion ratio. We show that, by setting γ := ((1 + )(p + 1))p+1 and x := (p + 1)2 ,
the constraints (18) are always satisfied. Indeed, if oe = 0, the constraints (18)
are satisfied. Conversely, if oe > 0, by rewriting the constraints (18) in terms of
the quantity te := ke /oe , we get the following inequality:
d+1
te
g(te , d) := −td+1
e + (p + 1) 2
− (1 + )t d
e + ((1 + )(p + 1))
p+1
≥ 0 (20)
d+1
for each e ∈ E, d ∈ [p]0 and te ≥ 0. This inequality is always satisfied for each
d ∈ [p]0 and te ≥ 0 (see the full version), and this fact completes the proof of the
theorem. t
u
3.2 Lower Bound
Theorem 2. For each δ > 0 there exists a congestion game having polynomial
latency functions of degree p such that the approximation ratio of -approximate
one-round walks starting from the empty state is higher than ((1+)(p+1))p+1 −δ.
Proof. Let n, m ∈ N and q := b(1 + )(p + 1)nc − 1. Let CGm,n be a congestion
game such that the set of players’ types is N := {a∗1 . . . , a∗q+1 , a01 , a1 , . . . , a0m , am },
the set of resources is E := {e1 , . . . , en+m+q−1 }, the amount of players of type
a∗1 and types a0i s is 2, while the amount of players of the remaining types is 1.
Players of type a∗i can only select the strategy s∗i := {e1 , e2 , . . . , en+i−2 }, players
of type a0i can only select the strategy s0i := {en+i−1 }, and players of type ai
can select si := {en+i , en+i+1 , . . . , en+i+q−1 } or oi := {ei , ei+1 , . . . , en+i−1 }. The
latency function is `e (ke ) := kep /np+1 for each resource e ∈ E.
Consider the simple weak one-round walk
(∆f,t )t∈[0,M ] := (s∗1 . . . , s∗q+1 , s01 , s1 , . . . , s0m , sm ).
To prove that (∆f,t )t∈[0,M ] is an -one-round walk it is sufficient to show that si
is an -best-response in ∆f,t for each t such that f (t) = ai . Given such a t, we
get
q Z (1+)(p+1)n p Z (1+)(p+1)
f,t
X jp 1 x
csi (∆ ) ≤ p+1
≤ dx = y p dy (21)
j=1
n 0 n n 0
p
p+1 p q+2
= (1 + ) (p + 1) ≤ (1 + ) (22)
n
p
1 q+2
= (1 + )n = (1 + )coi (∆f,t ) (23)
n n
Non-Atomic One-Round Walks in Polynomial Congestion Games 19
We conclude that si is an -best-response in the strategy profile ∆f,t for a player
of type ai = f1 (t). Therefore, (∆f,t )t∈[0,M ] is an -one-round walk, and generates
a strategy profile ∆m,n in which all players of type ai select the strategy si . Let
∆∗ m,n be the strategy profile in which each player of type ai selects the strategy
oi .
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0 t1 t2 t3 M
Fig. 1. The figure depicts a lower bounding instance with n = 4, m = 6, `(ke ) = ke /4
and = 0.4. Observe that q = b1.4 · 2 · 4c − 1 = 10 and the total amount of players is
M = 3m + 2 + q = 30. The abscissa represents the amount of players which already
selected their strategy, and the ordinate represents the resources. The ordinate values of
coloured squares having abscissa x ∈ [30] denote the strategies of all players of type f (t)
with t ∈ [x−1, x). The squares labeled with a cross/a black square/a dark grey square/a
tic are related to the resources selected in the the strategies s∗i /s0i /oi /si . For instance,
when an amount t1 /t2 /t3 of players have already entered in the game, a player of type
a∗4 /a2 /a04 can select the strategy s∗4 = {e1 , e2 , . . . , e6 } (crosses)/s2 = {e6 , e7 , . . . , e15 }
(tics) or o2 = {e2 , e3 , . . . , e5 } (dark grey squares)/s04 = {e7 } (black squares).
We get (o(m) is related to the usual asymptotic notation):
p
TL(∆m,n ) q n1 nq (m − o(m)) + o(m)
lim lim ≥ lim lim (24)
n→∞ m→∞ TL(∆∗ m,n ) n→∞ m→∞ n+2 p+1 (m − o(m)) + o(m)
n
p+1
q p+1 b(1 + )(p + 1)nc − 1
= lim = lim
n→∞ n n→∞ n
(25)
= ((1 + )(p + 1))p+1 . (26)
which completes the proof. t
u
20 Cosimo Vinci
4 Efficiency of Taxation
In the following theorems, we prove that by resorting to static or dynamic taxation
the -approximation ratio can be consistently lowered.
Theorem 3. The approximation ratio of -approximate one-round walks starting
from the empty state in congestion games with polynomial latency functions of
degree p is at most (1 + )p+1 (p + 1)p by resorting to the static tax-function:
(1 + )p (p + 1)p−1
Te := αe,p ope ξ, with ξ := . (27)
p
Proof. For an integer p ≥ 1, fix a congestion game CG(T ), where T is the tax-
function defined in (27). Define (∆f,t )t∈[0,M ] , o(t), ∆, ∆∗ , ke and oe as in the
proof of Theorem 1. As done in the proof of Theorem 1, by applying the primal-
dual method and by relaxing the constraints modelling -best-responses (which
take into account taxation in this case), we get the following linear program:
p
XX
max αe,d ked+1 (28)
e∈E d=0
p
! !
X X ke d+1
− (1 + )oe ked + αe,p ope ξke − op+1
s.t. αe,d e ξ ≤0
d+1
e∈E d=0
(29)
p
XX
αe,d od+1
e =1 (30)
e∈E d=0
αe,d ≥ 0, ∀e ∈ E, ∀d ∈ [p]0 (31)
The dual program is
min γ (32)
ked+1
s.t. x − (1 + )oe ked + γod+1
e ≥ ked+1 ∀e ∈ E, d ∈ [p − 1]0 (33)
d+1
p+1
ke
x + ξoe ke − (1 + )oe (ke + ξoe ) + γop+1
p p p
e ≥ kep+1 ∀e ∈ E (34)
p+1
x, γ ≥ 0 (35)
By setting γ := (1 + )p+1 (p + 1)p and x := (p + 1)p, the constraints (33) and
(34) are satisfied (see the full version), and the claim follows. t
u
Theorem 4. The approximation ratio of -approximate one-round walks starting
from the empty state in congestion games with polynomial latency functions of
degree p is at most (1 + )p+1 (p + 1)! by resorting to the dynamic tax-function
(set (d)j := d!/(d − j)!):
p
X d
X
Te (ke ) := αe,d Te,d (ke ) with Te,d (ke ) := (1 + )j (d)j ked−j oje (36)
d=0 j=1
Non-Atomic One-Round Walks in Polynomial Congestion Games 21
Proof. By reconsidering the proof of Theorem 3, but with the tax (36) instead
of the tax (27), we get a dual program having the following constraints:
Z ke !
d+1
k e
− ked+1 + x + Te,d (u)du − (1 + )oe (ked + Te,d (k)) + γod+1
e ≥0
d+1 0
(37)
for each e ∈ E and d ∈ [p]0 . These constraints are always satisfied if x := p + 1
and γ := (1 + )p+1 (p + 1)! (see the full version), and the claim follows. t
u
Remark 1. Observe that finding an optimal strategy profile requires to solve a
convex minimization problem. Therefore, for each δ > 0, one can compute in
polynomial time a strategy profile whose social value is at most 1 + δ times the
social optimum [9]. Then, if õe is the congestion of resource e in that strategy
profile, by using the tax (27) (resp. (36)) with õe in place of oe , one can easily
prove that the resulting -approximation ratio is at most (1 + δ) times that of
Theorem 3 (resp. Theorem 4).
References
1. Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price
of anarchy for polynomial congestion games. SIAM J. Comput. 40(5), 1211–1233
(2011)
2. Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, E., Wexler, T., Roughgarden,
T.: The price of stability for network design with fair cost allocation. In: Proceedings
of the 45th Annual IEEE Symposium on Foundations of Computer Science. pp.
295–304. FOCS, IEEE Computer Society (2004)
3. Awerbuch, B., Azar, Y., Epstein, A.: The Price of Routing Unsplittable Flow. In:
Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Com-
puting. pp. 57–66. STOC, ACM (2005)
4. Beckmann, M.: Studies in the economics of transportation. Yale University Press
for the Cowles Commission for Research in Economics New Haven (1959)
5. Bilò, V.: A Unifying tool for Bounding the quality of Non-Cooperative Solutions
in Weighted Congestion Games. Approximation and Online Algorithms: 10th In-
ternational Workshop, WAOA 2012 pp. 215–228 (2013)
6. Bilò, V., Fanelli, A., Flammini, M., Moscardelli, L.: Performance of one-round walks
in linear congestion games. Theor. Comp. Sys. 49(1), 24–45 (2011)
7. Bilò, V., Vinci, C.: On stackelberg strategies in affine congestion games. In: Web
and Internet Economics: 11th International Conference, WINE 2015. pp. 132–145.
Springer Berlin Heidelberg (2015)
8. Bilò, V., Vinci, C.: Dynamic taxes for polynomial congestion games. In: Proceedings
of the 17th ACM Conference on Electronic Commerce. EC (2016), To appear.
9. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press,
New York, NY, USA (2004)
10. Caragiannis, I., Flammini, M., Kaklamanis, C., Kanellopoulos, P., Moscardelli, L.:
Tight bounds for selfish and greedy load balancing. Algorithmica 61(3), 606–637
(2011)
11. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P.: Taxes for Linear Atomic Con-
gestion Games. ACM Trans. Algorithms 7(1), 13:1–13:31 (2010)
22 Cosimo Vinci
12. Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games.
In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of
Computing. pp. 67–73. STOC ’05, ACM (2005)
13. Christodoulou, G., Koutsoupias, E., Spirakis, P.G.: On the performance of approx-
imate equilibria in congestion games. Algorithmica 61(1), 116–140 (2011)
14. Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation
in potential games. In: Proceedings of the 23th Annual Conference on Theoretical
Aspects of Computer Science. pp. 349–360. STACS, Springer Berlin Heidelberg,
Berlin, Heidelberg (2006)
15. Cole, R., Dodis, Y., Roughgarden, T.: How much can taxes help selfish routing? In:
Proceedings of the 4th ACM Conference on Electronic Commerce. pp. 98–107. EC,
ACM (2003)
16. Cole, R., Dodis, Y., Roughgarden, T.: Pricing Network Edges for Heterogeneous
Selfish Users. In: Proceedings of the Thirty-fifth Annual ACM Symposium on
Theory of Computing. pp. 521–530. STOC, ACM (2003)
17. Fanelli, A., Flammini, M., Moscardelli, L.: Stackelberg Strategies for Network Design
Games. In: Proceedings of the 6th International Conference on Internet and Network
Economics. pp. 222–233. WINE, Springer-Verlag (2010)
18. Fanelli, A., Flammini, M., Moscardelli, L.: The speed of convergence in congestion
games under best-response dynamics. ACM Trans. Algorithms 8(3), 25:1–25:15
(2012)
19. Fleischer, L., Jain, K., Mahdian, M.: Tolls for Heterogeneous Selfish Users in Mul-
ticommodity Networks and Generalized Congestion Games. In: Proceedings of the
45th Annual IEEE Symposium on Foundations of Computer Science. pp. 277–285.
FOCS, IEEE Computer Society (2004)
20. Fotakis, D.: Stackelberg Strategies for Atomic Congestion Games. Theor. Comp.
Sys. 47(1), 218–249 (2010)
21. Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of the
16th Annual Conference on Theoretical Aspects of Computer Science. pp. 404–413.
STACS, Springer-Verlag (1999)
22. Mirrokni, V.S., Vetta, A.: Convergence issues in competitive games. In: Approxima-
tion, Randomization, and Combinatorial Optimization. Algorithms and Techniques,
pp. 183–194. Springer Berlin Heidelberg (2004)
23. Nash, J.F.: Equilibrium points in n-person games. Proceedings of the National
Academy of Sciences of the United States of America 36(1), 48–49 (1950)
24. Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.): Algorithmic Game
Theory (2007)
25. Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Inter-
national Journal of Game Theory 2, 65–67 (1973)
26. Roughgarden, T.: Stackelberg scheduling strategies. In: Proceedings of the Thirty-
third Annual ACM Symposium on Theory of Computing. pp. 104–113. STOC ’01,
ACM (2001)
27. Roughgarden, T.: The price of anarchy is independent of the network topology. J.
Comput. Syst. Sci. 67(2), 341–364 (2003)
28. Rudin, W.: Real and Complex Analysis, 3rd Ed. McGraw-Hill, Inc., New York, NY,
USA (1987)
29. Swamy, C.: The Effectiveness of Stackelberg Strategies and Tolls for Network Con-
gestion Games. ACM Trans. Algorithms 8(4), 36:1–36:19 (2012)