In this paper we study the approximation ratio of the solutions achieved after an -approximate one-round walk in non-atomic congestion games. Prior to this work, the solution concept of one-round walks had been studied for atomic congestion games with linear latency functions only [Christodoulou et al. 2006, Bilò et al. 2011]. We focus on polynomial 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)!).
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 [
These systems are often modeled by congestion games [
In congestion games, selfish behavior always leads to stable outcomes, called
Pure Nash Equilibrium [
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 [
For such a reason, we also focus on (resource) taxation [
Christodoulou et al. [
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 [
Caragiannis et al. [
Other mechanisms used to reduce the price of anarchy in congestion games
are Stackelberg Strategies [
Mirrokni and Vetta [
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 has polynomial latencies of degree p ∈ N when, for each e ∈ E, `e(x) := Pd∈[p]0 αe,dxd, 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 Si ∈ Σi, the amount Δi(Si) of players of type i selecting strategy Si, so that PS∈Σi Δi(S) = ri. For a strategy profile , the congestion of resource e ∈ E in , denoted as ke( ) := Pi∈N,S∈Σi:e∈S Δi(S), is the total amount of players using resource e in . The cost of a player selecting a strategy Si ∈ Σi is defined as cSi ( ) = Pe∈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 ( -best-response, for brevity) for players of type i in if, for each Si0 ∈ Σi \ {∅i}, cSi∗ ( ) ≤ (1 + )cSi0 ( ). Let M := Pi∈N ri and let f : [0, M ] → N be a rightcontinuous function such that Rf−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) P Δif,t(S) = R[0,t]∩f−1[{i}] dx for each i ∈ N and t ∈ [0, M ] (then,
S∈Σi\{∅i} Δif,t(∅i) = ri − R[0,t]∩f−1[{i}] dx), (2) Δif,t(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,t(S) has to be necessarily a non-decreasing and Lipschitzian i 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(S) of players i 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.
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 Δif,M (Si) = Rf−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 oneround walk starting from the empty state ( -one-round walk, for brevity) if, for any t ∈ [0, M ] , Δff,(tt)(S) is right-increasing at t only if strategy S is an -best-response in f,t 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 in non-atomic congestion games, is the total latency, defined as TL( ) = Pi∈N,Si∈Σ Δi(Si) · cSi ( ) = P ) · `e(ke( )). A social optimum is a strategy profile ∗ minimizing TL.e∈TEhekea(pproximation 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 `es. T is a static tax-function if each Te is a constant function (with respect to the resource congestion). 3 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 [
In our setting, we want to establish an upper bound on the worst-case performance 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 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 [
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 latencies 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 strategies such that o(t) is right-continuous with respect to t, o(t) is a strategy of player f (t) and Ro−1[{S}]∩f−1[{i}] dt = Δi∗(S). Observe that such a family of strategies 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): f,t) ≤ 0, ∀S∗ ∈ Σf(t)( f,t), ∀t ∈ [0, M ] max
X The constraints (2) come from the definition of -best-responses and -one-round walks. By replacing constraint (2) with p
X αe,dked( ) ≤ 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, cˆ (S, o(t), f,t) can be defined as a function of Δf,t(S) except for the intervals on which Δif,t(S) i is constant. By exploiting (6), we obtain max s.t.
p X X αe,dked+1 e∈E d=0 p
ked+1 p X X αe,d d + 1 − (1 + ) X oe X αe,dked ≤ 0 e∈E d=0 e∈E d=0
p
X X αe,doed+1 = 1
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(S)s
i
as functions of t, and, more generally, from the Lebesgue theory of integration
[
γ Clearly, any feasible solution for LP0(CG) is an upper bound on the -approximation 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: g(te, d) := −ted+1 + (p + 1)2 td+1 e d + 1 − (1 + )ted + ((1 + )(p + 1))p+1 ≥ 0 (20) 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. tu 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 := {a1∗ . . . , aq∗+1, a01, a1, . . . , a0m, am}, the set of resources is E := {e1, . . . , en+m+q−1}, the amount of players of type a1∗ and types a0is is 2, while the amount of players of the remaining types is 1. Players of type ai∗ can only select the strategy si∗ := {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] := (s1∗ . . . , sq∗+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 csi ( f,t) ≤ Xq njp+p1 ≤ j=1
0 Z (1+ )(p+1)n 1 x p
Z (1+ )(p+1) ypdy = (1 + )p+1(p + 1)p ≤ (1 + ) = (1 + )n 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
We get (o(m) is related to the usual asymptotic notation): lim lim TL( m,n) lim n→∞ m→∞ TL( ∗m,n) ≥ nl→im∞ m→∞ q n1 nq p (m − o(m)) + o(m) n+n2 p+1 (m − o(m)) + o(m) = lim n→∞ q p+1 n = lim n→∞ b(1 + )(p + 1)nc − 1
n = ((1 + )(p + 1))p+1. which completes the proof.
(24) p+1 (25) (26) tu max s.t.
X
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: Te := αe,poepξ, with ξ := (1 + )p(p + 1)p−1 p .
Proof. For an integer p ≥ 1, fix a congestion game CG(T ), where T is the taxfunction 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 primaldual method and by relaxing the constraints modelling -best-responses (which take into account taxation in this case), we get the following linear program: ked+1 d + 1 − (1 + )oeked ! + αe,p oepξke − oep+1ξ
≤ 0 ! (27) (28) (29) (30) (31) (32) (33) (35) kd+1
e d + 1 − (1 + )oeked 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. tu 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)!):
Te(ke) :=
p X αe,dTe,d(ke) d=0 with
Te,d(ke) :=
d X(1 + )j (d)j ked−j oj
e j=1 (36) 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: − ked+1 + x kd+1
e d + 1 +
Z ke 0
Te,d(u)du − (1 + )oe(ked + Te,d(k))
+ γoed+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.
tu
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 [