=Paper=
{{Paper
|id=Vol-1678/paper3
|storemode=property
|title=When are Marginal Congestion Tolls Optimal?
|pdfUrl=https://ceur-ws.org/Vol-1678/paper3.pdf
|volume=Vol-1678
|authors=Reshef Meir,David C. Parkes
|dblpUrl=https://dblp.org/rec/conf/ijcai/MeirP16
}}
==When are Marginal Congestion Tolls Optimal?==
https://ceur-ws.org/Vol-1678/paper3.pdf
When are Marginal Congestion Tolls Optimal?
Reshef Meir, Technion David C. Parkes, Harvard University
reshefm@ie.technion.ac.il parkes@eecs.harvard.edu
Abstract optimal congestion, and often require extensive computation
(see e.g. [Bonifaci et al., 2011]).
Marginal tolls are known to provide the existence For atomic games, it is known that marginal tolls guarantee
of an optimal equilibrium in atomic congestion the existence of at least one optimal equilibrium [Sandholm,
games, but unlike nonatomic games, there might be 2007], however there may be other inefficient equilibria, even
additional equilibria even with linear cost functions in games with linear latencies [Caragiannis et al., 2010a].
on resources. In this paper, we show that in games The problem becomes even more involved if we take into ac-
with a large number of players, all equilibria are count more general notions of equilibrium such as mixed and
near-optimal. correlated equilibrium. For a specific classes of atomic rout-
ing games, marginal tolls guarantee optimal behavior in any
pure equilibrium. This is the case for example for symmetric
1 Introduction networks with parallel links (also known as resource selec-
It is well known that selfish routing results in suboptimal so- tion games) since in such networks the equilibrium is unique.
cial behavior and in increased latency [Pigou, 1920]. The The class of networks for which marginal tolls are optimal
modern literature formalizes selfish routing scenarios as con- was extended first in an unpublished (and unfinished) work
gestion games, where the inefficiency due to strategic behav- by Singh [Singh, 2008]. However Singh’s result was very re-
ior is quantified as the Price of Anarchy (PoA)– the ratio be- cently refuted by Igal Milchtaich (personal communications)
tween the optimal total latency and the maximal total latency who provided the correct characterization.
in equilibrium [Roughgarden and Tardos, 2007]. Several other papers studied more complicated taxation
The game theoretic literature on selfish routing can be schemes and how low they can affect the PoA [Fotakis and
classified into models of atomic (unsplittable) flow and non- Spirakis, 2008; Caragiannis et al., 2010a].
atomic flow, where in the latter, each agent accounts for an in-
finitesimally small fraction of the total congestion. While in Our contribution We show that for any fixed network, if
both models a pure equilibrium is guaranteed to exist, and can the number of players is sufficiently large, then any equilib-
be found via a simple local best-response dynamics, atomic rium under marginal tolls is near-optimal. Further, this result
congestion games are considered more challenging to ana- extend to mixed, correlated, and coarse correlated equilibria.
lyze. Atomic games may have multiple equilibria of different We use the smoothness framework [Roughgarden, 2009],
costs, and the price of anarchy can be much higher than in which enables the PoA bounds to be established with rela-
nonatomic games. tively short and simple proofs.
The PoA is well understood in congestion games, both We also consider agents with variable sensitivity to mon-
atomic and nonatomic, and almost independent from the etary tolls [Cole et al., 2006; Karakostas and Kolliopoulos,
topology of the network [Roughgarden, 2009]. That is, the 2004; Fotakis et al., 2010], reflecting how agents trade-off
inefficiency depends mostly on the edge latency functions, money for time. As discussed in [Yang and Zhang, 2008;
and a simple network of two parallel edges (or roads) is suf- Meir and Parkes, 2015b], the parameter may be unobserv-
ficient to create instances with the highest possible PoA. able, and thus unknown to the central authority setting the
Still, it is interesting to look to change the behavior of tolls. Thus, following [Meir and Parkes, 2015b] and in con-
agents by charging them for using a resource. It has been trast to most of the mechanism design literature, we assume
known since [Beckmann et al., 1956] that to enforce opti- that a marginal toll is applied, and analyze the equilibrium for
mal behavior in nonatomic games (i.e. such that all equi- a population as the sensitivity parameter varies.
libria have minimum total latency), it is sufficient to impose Along the way, we state formally some known results on
marginal congestion tolls, i.e., charge each agent based on marginal tolls that seem to have been overlooked in the recent
the latency he currently adds to the other agents.1 Note that study of atomic congestion and routing games.
we assume tolls are dynamic that depend on monitoring the
actual congestion on one hand, but can be easily computed.
This is in contrast to static tolls that typically depend on the 2 Preliminaries
For an integer m, [m] = {1, 2, . . . , m}. We use bold letters
1
It is typically assumed that the tolls themselves are not calcu- to denote vectors, e.g., a = (a1 , . . . , am ).
lated as part of the total cost, e.g. because they return to the society Following the definitions in [Roughgarden, 2007], a rout-
indirectly, or because the central authority only cares about the la- ing game is a tuple G = hV, E, N, c, u, vi, where
tency. Non-refundable tolls are also studied [Cole et al., 2006] but
not in this paper. • (V, E) are vertices and edges of a directed graph;
• N is a finite set of agents of size n; The biased price of anarchy/stability (BPoA/BPoS) com-
• c = (ce )e∈E , where ce (x) ≥ 0 is a non-decreasing func- pares the equilibria of Ĝ to the optimum of G, using
tion indicating the cost incurred when x agents use edge the real social cost of both. Formally, BPoA(G, Ĝ) =
e (ce are called latency functions);2 max{SC(G,a):a∈P N E(Ĝ)}
, and similarly for BPoS.
SC(G,a∗ )
• u, v are vectors of n vertices each, where (ui , vi ) are the The primary bias we will consider in this paper is tolls,
source and target nodes of agent i; and in particular marginal tolls. That is, we define τe (x) =
We denote by Ai ⊆ 2E the set of all directed paths between (x−1)[ce (x)−ce (x−1)], and set ĉM e (x) = ce (x)+τe (x). Toll
the pair of nodes (ui , vi ) in the graph. Thus Ai is the set of τe (x) is exactly the marginal cost inflicted upon the remaining
actions available to agent i. We denote by A = ∪i Ai the set x − 1 agents who use e due to an additional agent. Other tool
of all directed source-target paths. A routing game is symmet- schemes T can be similarly defined, replacing τe (x) with any
ric (also called single-source-single-target) if all agents have other non-negative function Te (x).
the same set of actions, i.e., Ai = A for all i. A toll scheme T strongly enforces optimal flow in a game
An action profile a = (ai )i∈N specifies the path ai ∈ Ai G if all equilibria of ĜT (i.e., the game with biased costs ĉT )
of each agent i, and A = ×i∈N Ai is the set of all action are optimal in G (equivalently, if BPoA(G, ĜT ) = 1) [Fotakis
profiles. We denote by se (a) ∈ N the congestion on edge and Spirakis, 2008]. Similarly, a toll scheme weakly enforces
e ∈ E in profile a, i.e., se = se (a) = |{i ∈ N : e ∈ ai }| (a optimal flows if BPoS(G, ĜT ) = 1.
is omitted when clear from context). Marginal tolls in the nonatomic Pigouvian model were sug-
The costPfor agent i in profile a is summed over all edges, gested by Beckmann [Beckmann et al., 1956], who showed
Ci (a) = e∈ai ce (se ). The social cost in a profile a in game they strongly enforce optimal flows in that model. Our goal
G is attained by summing over all agents: is to understand the power of marginal tolls in atomic routing
n n X
X X X games.
SC (G, a) = Ci (a) = ce (se ) = se ce (se ). (1)
i=1 i=1 e∈ai e∈E
3 Marginal tolls are weakly optimal
We denote by a∗ = a∗ (G) = argmina∈A SC(G, a) the pro-
file that minimizes the social cost (optimal profile). The marginal toll scheme for atomic games coincides with the
A profile a is a pure Nash equilibrium if no agent can gain taxes proposed by Sandholm [Sandholm, 2007], albeit Sand-
by changing her strategy, i.e. if for all i ∈ N, a0i ∈ Ai , holm defined taxes at the strategy level, rather than tolls on
Ci (a) ≤ Ci (a−i , a0i ), where a−i = (aj )j6=i . The definition particular edges. The observation that marginal tolls weakly
of equilibrium extends to mixed and correlated strategies. We enforce optimal flows was also made in an unpublished report
omit the formal details. Denote by P N E(G) ⊆ A the sets of by Singh [Singh, 2008].4 We state the result for the standard
pure Nash equilibria of G. routing games framework.
The price of anarchy (PoA) of G is the ratio between Theorem 1 ([Sandholm, 2007; Singh, 2008]). For any
the social cost of worst equilibrium and the optimal profile, atomic congestion game G, there is a pure Nash equilibrium
i.e. PoA(G) = max{SC(G,a):a∈PSC(G,a∗ )
N E(G)}
(the definition of in ĜM that is optimal in G. Equivalently, BPoS(G, ĜM ) = 1.
mixed- and correlated-POA is similar). It is well known that The theorem follows from a simple observation: ĜM is
the PoA can be upper bounded using only the class of latency a potential game [Rosenthal, 1973], whose potential func-
functions in G, regardless of the structure of (V, E). For ex- tion φ(ĜM , a) coincides with the social welfare of G. Thus
ample, if all of ce are affine functions (ce (x) = ae x + be for the optimum of SC(G, a) must a be local minimum of
ae , be ≥ 0) then PoA(G) ≤ 52 , and this is true for mixed and
φ(ĜM , a), i.e. a pure Nash equilibrium. Quite strikingly, the
correlated-PoA as well [Roughgarden, 2009].
theorem was extended to a much more general framework
The price of stability (PoS) of G is similarly defined as
where agents have idiosyncratic preferences over strategies,
the ratio between the best equilibrium and the optimal pro-
and congestion may depend on agents weight or other fea-
file [Christodoulou and Koutsoupias, 2005], i.e. PoS(G) =
min{SC(G,a):a∈P N E(G)} tures [Sandholm, 2007; Singh, 2008].
SC(G,a∗ ) . Unfortunately, in atomic games there may be additional
suboptimal equilibria.
Biased games We are interested in a biased game, in our Example 1. Consider a game with 3 parallel links, E =
case because of the use of tolls.3 A biased game is a pair {a, b, c} and 3 agents N = {1, 2, 3}. A1 = {a, b}, A2 =
(G, Ĝ) such that G, Ĝ are identical except in their latency {b, c}, and A3 = {c}. Latency functions are cb (x) =
functions. Informally, we assume that players behave accord- cc (x) = x, ca ≡ 2 (see Fig. 1). The modified cost functions
ing to the “biased costs” (ĉe )e∈E (e.g. play an equilibrium of under any edge-independent nonnegative tolls can be written
Ĝ), but social cost is measured w.r.t. the “real costs” (ce )e∈E . as ĉb (x) = ĉc (x) = (1, 2 + T (x), 3 + T 0 (x)). The unique
2
optimum is a∗ = (a, b, c) with cost SC(a∗ ) = 2 + 1 + 1 = 4,
Some authors prefer the term “arc” for directed edges. We stick which is also a PNE. However, there is another PNE a0 =
with the common term in computer science.
3 4
Biased games are also used to model cognitive and behavioral Recent works on tolls in routing games seem to be unaware of
traits such as risk aversion [Ordóñez and Stier-Moses, 2010] or al- this observation [Fotakis and Spirakis, 2008; Fotakis et al., 2010;
truism [Caragiannis et al., 2010b]. Swamy, 2012].
(almost identical to the ones in [Roughgarden, 2009; Chen et
(a) c(x) (b) a∗ (c) a0 al., 2011]) in the appendix.
u u u In particular, (1, 0)-BS means that BPoA(G, Ĝ) = 1, i.e.
that any PNE of Ĝ is optimal in G.
ca (x) ≡ 2 We are interested in showing that (G, ĜM ) is BS for some
cc (x) = x
cb (x) = x
{3} {2} {1} {2, 3} {1} ∅
reasonable parameters λ̂, µ̂.
4.1 Smoothness in the large
When an atomic game becomes large, i.e. when we fix the
v v v network and increase the number of players, there is evi-
dence that the game behaves more similarly to a nonatomic
Figure 1: Figure (1a) shows the base game G. The other game [Feldman et al., 2015]. We show how to extend biased-
figures show the optimal state a∗ and the state a0 which is an smoothness analysis (and in particular marginal tolls) to large
atomic games. While we can not apply the results of Feldman
additional equilibrium of both G and ĜT .
et al. directly, our techniques are inspired by theirs.
Lemma 3. Let a, a0 be any two profiles in G with n agents,
(b, c, c) with cost SC(a0 ) = 1 + 2 + 2 = 5. This remains and let = (G) = maxe∈E,x∈N (ce (x + 1) − ce (x)). Then
a PNE of ĜT as long as ĉTb (x) = ĉTc (x): agent 2 is not al- P 0
j∈N Cj (a−j , aj ) − Cj (a)) ≤
P 0
e∈E(se −se )ce (se ) + O(n).
lowed to use edge a, and agent 1 does not want to use it since
ĉa (1) = 2 > 1 = ĉb (1). Proof.
X
This means that marginal tolls in atomic games do not, in (Cj (a−j , a0j ) − Cj (a))
the general case, strongly enforce optimal flows. j∈N
X X X X
= (( ce (se + 1) + ce (se )) − ce (se )).
4 Strongly Enforcing Optimal Flows
j∈N e∈a0j \aj e∈aj ∩a0j e∈aj
The prominent technique for proving PoA bounds is smooth-
ness analysis. In short, a game G isP (λ, µ)-smooth if for By definition of , we continue:
all a ∈ A there is a0 ∈ A such that i∈N Ci (a−i , a0i ) ≤
X X X X
≤ (( (ce (se ) + ) + ce (se )) − ce (se ))
λSC(G, OPT(G))+µSC(G, a). If a game G (not just a rout- j∈N e∈a0j \aj e∈aj ∩a0j e∈aj
λ [
ing game) is (λ, µ)-smooth, then PoA(G) ≤ 1−µ Roughgar- X X X XX
den, 2009]. Further, this holds for the mixed, correlated, and ≤ ( ce (se ) − ce (se )) +
coarse-correlated PoA as well. For routing games, it is also j∈N e∈a0j e∈aj j∈N e∈E
shown that restricting the class of latency functions results in X
= (s0e ce (se ) − se ce (se )) + n|E|.
smooth games. For example, if all cost functions are affine,
j∈N
then G is ( 35 , 13 )-smooth (thereby showing PoA(G) ≤ 52 ).
Given a biased game (G, Ĝ), we can similarly define the
property of biased smoothness. That is, we can write the sum of deviations as a function of
Definition 1. (G, Ĝ) is (λ̂, µ̂)-biased smooth (BS), if there is the aggregate congestion (approximately).
a0 s.t. for any profile a, Next, we think of a sequence of atomic games with increas-
X ing n: We fix a network (V, E) and continuous quasi-convex
(Cj (a)+Ĉj (a−j , a0j )−Ĉj (a)) ≤ λ̂SC (G, OPT(G))+µ̂SC (G, a). cost functions c = (ce )e∈E , where ce : [0, 1] → R+ . For ease
j∈N of presentation, we consider symmetric games (i.e. where
(2) there is just one source-target pair u, v ∈ V ), although simi-
It is easy to see that if G is (λ, µ)-smooth, then lar arguments extend to asymmetric games. This already in-
(G, G) is (λ, µ)-BS: we set a0 = OPT(G), and note that duces a symmetric nonatomic game G̃ = (V, E, u, v, c). For
0 0
P P
j∈N (Cj (a)+Cj (a−j , aj )−Cj (a)) = j∈N Cj (a−j , aj ). n ∈ N, we define Gn by setting Gn = (V, E, N, u, v, cn ),
Theorem 2. Suppose that (G, Ĝ) is (λ̂, µ̂)-BS. Let σ be any where cn (x) = c(x/n). Thus G̃ is the limit of (Gn )n=1,2,...
equilibrium (pure, mixed, correlated, or coarse-correlated) of (we call it the limit game).
λ̂ Our continuous cost functions can also be subject to bi-
the game Ĝ. Then SC (G, σ) ≤ 1−µ̂ SC (G, OPT(G)).
ases. Let c̃ˆe be the biased continuous cost of c̃e , and ĉne (x) =
The original proof of Roughgarden [Roughgarden, 2009] c̃ˆe (x/n). Biased-smoothness for continuous cost functions
for the PoA (and coarse-correlated PoA) naturally extends to was defined and explored in [Meir and Parkes, 2015b]: we
biased smoothness.5 For completeness, we provide the proof say that c is (λ̂, µ̂)-biased smooth w.r.t. ĉ if for all t, t0 ∈ R+ ,
5
A similar definition of smoothness was applied, for example, for c(t)t + ĉ(t)(t0 − t) ≤ λ̂c(t0 )t0 + µ̂c(t)t.
finite congestion games with altruism: when Ĉ(a) is a combination
of C(a) and SC(a), then the BPoA coincides with the “robust PoA” ˆ then cn is (λ̂, µ̂)-
Clearly, if c̃ is (λ̂, µ̂)-biased smooth w.r.t. c̃,
n
of Chen et al. [Chen et al., 2011]. biased smooth w.r.t. ĉ for any n.
Theorem 4. Consider a limit game G̃, where c̃e are quasi-
ˆ Then for
convex and (λ̂, µ̂)-biased smooth w.r.t. the bias c̃. 2
any δ > 0 there are > 0, n() s.t. for all n > n(), the
BPoA
atomic game (Gn , Ĝn ) is ((1 + δ)λ̂, µ̂)-BS. In particular, 1.5
λ̂
BPoA(Gn , Ĝn ) ≤ (1 + δ) , 1
1 − µ̂
0 1 2 3 4 5 6 7
and this extends to any coarse-correlated equilibrium. β
Proof. Let a0 = OPT(Gn ), Z n = SC(Gn , a0 ). Since Figure 2: The X-axis shows the tax-sensitivity of agents,
SC(Gn , a0 ) = Ω(n) (the cost for each agent is at least some where β = 0 means they ignore the tax.
constant), we write Z n > ρn for some ρ > 0 and n > n(ρ). The double red lines are the tight bounds on the BPoA for
Since c̃e is bounded and continuous for all e ∈ E, large games with affine costs stated in Corollary 6.
x 1 x
max {cne (x + 1) − cne (x)} = max {c̃e ( + ) − c̃e ( )}
x∈[n] x∈[n] n n n
1 n→∞
5 Tax-sensitivity
≤ sup {c̃e (t + ) − c̃e (t)} → 0,
t∈[0,1] n We next consider agents with variable sensitivity to monetary
tolls, as in [Cole et al., 2006]. Formally, the marginal toll
and thus for all > 0 there is some n() s.t. for all n > n(), τe (x) is imposed on edge e, but the cost experienced by the
we have cne (x + 1) − cne (x) < . By Lemma 3 agents is ĉβe (x) = c(x) + β · τe (x), where β is a parame-
ter reflecting how agents trade-off money for time. Denote
X
SC(Gn , a) + Ĉjn (a−j , a0j ) − Ĉjn (a))
j∈N by Ĝβ the biased game obtained from G by replacing every
≤ SC(G , a) +n
X
(s0e − se )ĉn cost function ce (x) with ĉβ (x). We analyze the equilibrium
e (se ) + O(n)
e∈E
for a population with parameter β (where β = 1 means that
X 0 0
ĉβe (x) = ĉM
e (x)).
= (se cn n
e (se ) + (se − se )ĉe (se )) + n In Meir and Parkes, 2015b], various BPoA bounds are
[
e∈E
X derived for nonatomic games with various classes of cost
≤ (λ̂cn (s0e )s0e + µ̂cn (se )se ) + n0 (smoothness) functions (general/convex/polynomial/linear). We show how
e∈E these bounds extend to large games.
= λ̂Z n + µ̂SC(Gn , a) + n0 For large atomic games, all the biased smoothness bounds
1 n 0 from [Meir and Parkes, 2015b] for tax-sensitivity and other
< λ̂SC(Gn , a0 ) + µ̂SC(Gn , a) + Z (Z n > ρn) biases immediately apply. These bounds are also known to
ρ
be tight.
0 n
= (λ̂ + )Z + µ̂SC(Gn , a) For example, it was shown that affine cost functions (of
ρ 2
0 the form c̃(t) = at + b for a, b ≥ 0) are (1, (1+β)4 − β)-
≤ (1 + )λ̂Z n + µ̂SC(Gn , a). (λ̂ ≥ 1) ˆ as defined above for all β ≤ 1 and
ρ biased smooth w.r.t. c̃(t)
2
Selecting 0 < δρ (and thus sufficiently small > 0, and n > ( (1+β)
4β , 0)-biased smooth for β ≥ 1. We get the following
max{n(ρ), n()}), completes the proof. The BPoA bound corollary due to Theorem 4:
then follows directly from Theorem 2.
Corollary 6. Consider any limit game G̃, where c̃e are
Since biased smoothness hold for various pairs of cost affine. Then for any δ > 0 there is some n(δ) s.t. for all
1
functions, Theorem 4 is quite useful. Mainly, we get that n > n(δ), BPoA(Gn , Ĝn ) ≤ (1+β)2
if β ≤ 1, and
marginal tolls strongly enforce near-optimal flow if there are (β+1)− 4
n n (1+β)2
enough players. BPoA(G , Ĝ ) ≤ 4β if β ≥ 1.
Corollary 5. Consider any limit game G̃, where c̃e are quasi- Another benefit of smoothness-in-the-large is that the pa-
convex. Then for any δ > 0 there is some n(δ) s.t. for all
rameters λ̂, µ̂ are typically much smaller for classes of con-
n > n(δ), BPoA(Gn , Ĝn ) ≤ 1 + δ. tinuous functions than for the corresponding class of discrete
Proof. Consider the continuous version of marginal tolls costs. Indeed, [Feldman et al., 2015] show that the PoA of
ˆ = c̃(t) + t · ∂c(t) [Beckmann et al., 1956].6 The proof large games is significantly smaller due to this: for linear
c̃(t) ∂t costs the PoA drops from 52 to 43 , and for polynomials of
follows directly from Theorem 4 and from the fact that any
degree d, the PoA drops from Ω(2d ) to O( lndd ). Our re-
quasi-convex function c̃ is (1, 0)-biased smooth w.r.t. c̃ˆ [Meir
sult shows that this still holds for large games with biases.
and Parkes, 2015b].
For brevity we do not re-state all the results from [Meir and
6
Due to rounding, ĉn (x) is very close, but not identical to the Parkes, 2015b] for large atomic games, however Fig. 2 shows
discrete ĉM (x) we previously defined. the bounds for affine costs.
6 Discussion [Fotakis et al., 2010] Dimitris Fotakis, George Karakostas, and
Stavros G Kolliopoulos. On the existence of optimal taxes for net-
We have studied the problem of strongly enforcing optimal
work congestion games with heterogeneous users. In SAGT’10,
flows in atomic congestion games through marginal conges- pages 162–173. Springer, 2010.
tion tolls. Such tolls always weakly enforce optimal flows,
[Karakostas and Kolliopoulos, 2004] George Karakostas and
and strongly enforce optimal tolls in large games. Further,
Stavros G Kolliopoulos. Edge pricing of multicommodity
our analysis extends to games where agents’ tax-sensitivity
networks for heterogeneous selfish users. In FOCS’04, pages
is not aligned with that of the designer. This is particu- 268–276, 2004.
larly important in the context of mechanism design where
[Meir and Parkes, 2015a] Reshef Meir and David Parkes. Conges-
we seek to shape drivers’ incentives and lead the system to
tion games with distance-based strict uncertainty. In Proceedings
a good equilibrium [Tumer and Agogino, 2006], and when
of the 29th AAAI Conference on Artificial Intelligence, 2015.
drivers are subject to cognitive and behavioral biases such
as risk-aversion [Ordóñez and Stier-Moses, 2010; Nikolova [Meir and Parkes, 2015b] Reshef Meir and David Parkes. Playing
and Stier-Moses, 2015]. One important challenge is to ex- the wrong game: Smoothness bounds for congestion games with
behavioral biases. In NETECON’15, pages 67–70, 2015.
tend the BPoA bounds to games where agents differ in their
levels of risk aversion or tax sensitivity. This has been done [Nikolova and Stier-Moses, 2015] Evdokia Nikolova and Nicolas E
to some extent in nonatomic games [Meir and Parkes, 2015a; Stier-Moses. The burden of risk aversion in mean-risk selfish
2015b]. routing. In ACM-EC’15, pages 489–506. ACM, 2015.
More broadly, this work provides more evidence for the [Ordóñez and Stier-Moses, 2010] Fernando Ordóñez and Nicolás E
usefulness of “biased-smoothness” analysis, in the line of Stier-Moses. Wardrop equilibria with risk-averse users. Trans-
[Chen et al., 2011; Meir and Parkes, 2015b], and we hope portation Science, 44(1):63–86, 2010.
it can lead to a better understanding of routing games where [Pigou, 1920] Arthur Cecil Pigou. The economics of welfare. Pal-
agents are subject to either external influences (like tolls) or grave Macmillan, 1920.
behavioral biases. [Rosenthal, 1973] Robert W Rosenthal. A class of games possess-
ing pure-strategy Nash equilibria. International Journal of Game
Acknowledgments Theory, 2(1):65–67, 1973.
We thank Itai Ariely for pointing us to Sandholm’s work. [Roughgarden and Tardos, 2007] Tim Roughgarden and Eva Tar-
dos. Introduction to the inefficiency of equilibria. In Noam Nisan
et al., editor, Algorithmic Game Theory, pages 443–459. Cam-
References bridge University Press, 2007.
[Beckmann et al., 1956] M. Beckmann, B. McGuire, and C. Win-
[Roughgarden, 2007] Tim Roughgarden. Routing games. In
sten. Studies in the Economics of Transportation. Yale University
Press, New Haven, 1956. Noam Nisan et al., editor, Algorithmic game theory, pages 459–
484. Cambridge University Press, 2007.
[Bonifaci et al., 2011] Vincenzo Bonifaci, Mahyar Salek, and
[Roughgarden, 2009] Tim Roughgarden. Intrinsic robustness of the
Guido Schäfer. Efficiency of restricted tolls in non-atomic net-
work routing games. In SAGT’11, pages 302–313, 2011. price of anarchy. In STOC’09, pages 513–522. ACM, 2009.
[Caragiannis et al., 2010a] Ioannis Caragiannis, Christos Kaklama- [Sandholm, 2007] William H Sandholm. Pigouvian pricing and
nis, and Panagiotis Kanellopoulos. Taxes for linear atomic con- stochastic evolutionary implementation. Journal of Economic
gestion games. ACM Transactions on Algorithms, 7(1):13, 2010. Theory, 132(1):367–382, 2007.
[Caragiannis et al., 2010b] Ioannis Caragiannis, Christos Kaklama- [Singh, 2008] Chandramani Singh. Marginal cost pricing for
nis, Panagiotis Kanellopoulos, Maria Kyropoulou, and Evi Pa- atomic network congestion games. Technical report, Department
paioannou. The impact of altruism on the efficiency of atomic of Electrical Communication Engineering, Indian Institute of Sci-
congestion games. In TGC, pages 172–188. Springer, 2010. ence, 2008.
[Chen et al., 2011] Po-An Chen, Bart De Keijzer, David Kempe, [Swamy, 2012] Chaitanya Swamy. The effectiveness of stackelberg
and Guido Schäfer. The robust price of anarchy of altruistic strategies and tolls for network congestion games. ACM Trans-
games. In WINE’11, pages 383–390. Springer, 2011. actions on Algorithms, 8(4):36, 2012.
[Christodoulou and Koutsoupias, 2005] George Christodoulou and [Tumer and Agogino, 2006] Kagan Tumer and Adrian Agogino.
Elias Koutsoupias. On the price of anarchy and stability of corre- Agent reward shaping for alleviating traffic congestion. In Work-
lated equilibria of linear congestion games. In Algorithms–ESA shop on Agents in Traffic and Transportation. Citeseer, 2006.
2005, pages 59–70. Springer, 2005. [Yang and Zhang, 2008] Hai Yang and Xiaoning Zhang. Existence
[Cole et al., 2006] Richard Cole, Yevgeniy Dodis, and Tim Rough- of anonymous link tolls for system optimum on networks with
garden. How much can taxes help selfish routing? Journal of mixed equilibrium behaviors. Transportation Research Part B:
Computer and System Sciences, 72(3):444–467, 2006. Methodological, 42(2):99–112, 2008.
[Feldman et al., 2015] Michal Feldman, Nicole Immorlica, Bren-
dan Lucier, Tim Roughgarden, and Vasilis Syrgkanis. The price
of anarchy in large games. arXiv preprint arXiv:1503.04755,
2015.
[Fotakis and Spirakis, 2008] Dimitris Fotakis and Paul G Spirakis.
Cost-balancing tolls for atomic network congestion games. In-
ternet Mathematics, 5(4):343–363, 2008.
A Omitted proofs where Inequality (4) follows from Eq. (3) with bi = a0i ,
(5)+(7) from linearity of expectation, and (6) from Eq. (2)
Theorem 2. Suppose that (G, Ĝ) is (λ̂, µ̂)-BS. Let σ be any applied for each a. By rearranging terms, we get the bound
equilibrium (pure, mixed, correlated, or coarse-correlated) of in the theorem.
λ̂
the game Ĝ. Then SC (G, σ) ≤ 1−µ̂ SC (G, OPT(G)).
Proof. For a correlated profile σ we denote SC(G, σ) =
Ea∼σ [SC(G, a)].
By Def. 1, there is a profile a0 s.t. Eq. (2) holds for every
profile a.
It is sufficient to prove for a CCE σ. By definition of CCE,
for any i ∈ N, bi ∈ Ai ,
Ea∼σ [Ĉi (a)] ≤ Ea∼σ [Ĉi (a−i , bi )]. (3)
SC(G, σ) = Ea∼σ [SC(G, a)] ≤ Ea∼σ [SC(G, a)] (4)
n
!
X
0
+ Ea∼σ [Ĉi (a−i , ai )] − Ea∼σ [Ĉi (a)]
i=1
" n
#
X
= Ea∼σ SC(G, a) + Ĉi (a−i , a0i ) − Ĉi (a) (5)
i=1
" n #
X
0
= Ea∼σ Ci (a) + Ĉi (a−i , ai ) − Ĉi (a)
i=1
h i
≤ Ea∼σ λ̂SC(G, OPT(G)) + µ̂SC(G, a) (6)
= λ̂SC(G, OPT(G)) + µ̂SC(G, σ), (7)