Marginal tolls are known to provide the existence of an optimal equilibrium in atomic congestion games, but unlike nonatomic games, there might be additional equilibria even with linear cost functions on resources. In this paper, we show that in games with a large number of players, all equilibria are near-optimal.
It is well known that selfish routing results in suboptimal social behavior and in increased latency [Pigou, 1920]. The modern literature formalizes selfish routing scenarios as congestion games, where the inefficiency due to strategic behavior is quantified as the Price of Anarchy (PoA)– the ratio between the optimal total latency and the maximal total latency in equilibrium [Roughgarden and Tardos, 2007].
The game theoretic literature on selfish routing can be classified into models of atomic (unsplittable) flow and nonatomic flow, where in the latter, each agent accounts for an infinitesimally small fraction of the total congestion. While in both models a pure equilibrium is guaranteed to exist, and can be found via a simple local best-response dynamics, atomic congestion games are considered more challenging to analyze. Atomic games may have multiple equilibria of different costs, and the price of anarchy can be much higher than in nonatomic games.
atomic and nonatomic, and almost independent from the topology of the network [Roughgarden, 2009]. That is, the inefficiency depends mostly on the edge latency functions, and a simple network of two parallel edges (or roads) is sufficient to create instances with the highest possible PoA.
Still, it is interesting to look to change the behavior of agents by charging them for using a resource. It has been known since [Beckmann et al., 1956] that to enforce optimal behavior in nonatomic games (i.e. such that all equilibria have minimum total latency), it is sufficient to impose marginal congestion tolls, i.e., charge each agent based on the latency he currently adds to the other agents.1 Note that we assume tolls are dynamic that depend on monitoring the actual congestion on one hand, but can be easily computed.
lated as part of the total cost, e.g. because they return to the society
indirectly, or because the central authority only cares about the
latency. Non-refundable tolls are also studied [Cole et al., 2006] but
not in this paper.
optimal congestion, and often require extensive computation
the existence of at least one optimal equilibrium [Sandholm, 2007], however there may be other inefficient equilibria, even in games with linear latencies [Caragiannis et al., 2010a]. The problem becomes even more involved if we take into account more general notions of equilibrium such as mixed and correlated equilibrium. For a specific classes of atomic routing games, marginal tolls guarantee optimal behavior in any pure equilibrium. This is the case for example for symmetric networks with parallel links (also known as resource selection games) since in such networks the equilibrium is unique.
was extended first in an unpublished (and unfinished) work by Singh [Singh, 2008]. However Singh’s result was very recently refuted by Igal Milchtaich (personal communications) who provided the correct characterization.
schemes and how low they can affect the PoA [Fotakis and
the number of players is sufficiently large, then any equilibrium under marginal tolls is near-optimal. Further, this result extend to mixed, correlated, and coarse correlated equilibria.
which enables the PoA bounds to be established with relatively short and simple proofs.
etary tolls [Cole et al., 2006; Karakostas and Kolliopoulos, 2004; Fotakis et al., 2010], reflecting how agents trade-off money for time. As discussed in [Yang and Zhang, 2008;
able, and thus unknown to the central authority setting the tolls. Thus, following [Meir and Parkes, 2015b] and in contrast to most of the mechanism design literature, we assume that a marginal toll is applied, and analyze the equilibrium for a population as the sensitivity parameter varies.
2
For an integer m, [m] = f1; 2; : : : ; mg. We use bold letters to denote vectors, e.g., a = (a1; : : : ; am).
ing game is a tuple G = hV; E; N; c; u; vi, where (V; E) are vertices and edges of a directed graph;
c = (ce)e2E , where ce(x) 0 is a non-decreasing function indicating the cost incurred when x agents use edge e (ce are called latency functions);2 u; v are vectors of n vertices each, where (ui; vi) are the source and target nodes of agent i;
the pair of nodes (ui; vi) in the graph. Thus Ai is the set of actions available to agent i. We denote by A = [iAi the set of all directed source-target paths. A routing game is symmetric (also called single-source-single-target) if all agents have the same set of actions, i.e., Ai = A for all i.
An action profile a = (ai)i2N specifies the path ai 2 Ai of each agent i, and A = i2N Ai is the set of all action profiles. We denote by se(a) 2 N the congestion on edge e 2 E in profile a, i.e., se = se(a) = jfi 2 N : e 2 aigj (a is omitted when clear from context).
Ci(a) = P G is attainede2bayi scuem(sme)i.nTghoevseorcailallacgoesnttisn: a profile a in game n n SC (G; a) = XCi(a) = X
Xce(se) =
Xsece(se): (1) i=1 i=1e2ai e2E We denote by a = a (G) = argmina2A SC(G; a) the profile that minimizes the social cost (optimal profile).
by changing her strategy, i.e. if for all i 2 N; a0i 2 Ai, Ci(a) Ci(a i; a0i), where a i = (aj )j6=i. The definition of equilibrium extends to mixed and correlated strategies. We omit the formal details. Denote by P N E(G) A the sets of pure Nash equilibria of G.
The price of anarchy (PoA) of G is the ratio between the social cost of worst equilibrium and the optimal profile, i.e. PoA(G) = maxfSC(SGC;a(G):a;a2P) NE(G)g (the definition of mixed- and correlated-POA is similar). It is well known that the PoA can be upper bounded using only the class of latency functions in G, regardless of the structure of (V; E). For example, if all of ce are affine functions (ce(x) = aex + be for ae; be 0) then PoA(G) 52 , and this is true for mixed and correlated-PoA as well [Roughgarden, 2009].
the ratio between the best equilibrium and the optimal profile [Christodoulou and Koutsoupias, 2005], i.e. PoS(G) = minfSC(G;a):a2P NE(G)g .
SC(G;a )
case because of the use of tolls.3 A biased game is a pair (G; G^) such that G; G^ are identical except in their latency functions. Informally, we assume that players behave according to the “biased costs” (c^e)e2E (e.g. play an equilibrium of G^), but social cost is measured w.r.t. the “real costs” (ce)e2E .
with the common term in computer science.
traits such as risk aversion [Ordo´ n˜ez and Stier-Moses, 2010] or altruism [Caragiannis et al., 2010b].
The biased price of anarchy/stability (BPoA/BPoS) compares the equilibria of G^ to the optimum of G, using the real social cost of both. Formally, BPoA(G; G^) = maxfSC(G;a):a2P NE(G^)g , and similarly for BPoS.
SC(G;a )
The primary bias we will consider in this paper is tolls, and in particular marginal tolls. That is, we define e(x) = (x 1)[ce(x) ce(x 1)], and set c^eM (x) = ce(x)+ e(x). Toll e(x) is exactly the marginal cost inflicted upon the remaining x 1 agents who use e due to an additional agent. Other tool schemes T can be similarly defined, replacing e(x) with any other non-negative function Te(x).
are optimal in G (equivalently, if BPoA(G; G^T ) = 1) [Fotakis and Spirakis, 2008]. Similarly, a toll scheme weakly enforces optimal flows if BPoS(G; G^T ) = 1.
gested by Beckmann [Beckmann et al., 1956], who showed they strongly enforce optimal flows in that model. Our goal is to understand the power of marginal tolls in atomic routing games. 3
The marginal toll scheme for atomic games coincides with the taxes proposed by Sandholm [Sandholm, 2007], albeit Sandholm defined taxes at the strategy level, rather than tolls on particular edges. The observation that marginal tolls weakly enforce optimal flows was also made in an unpublished report by Singh [Singh, 2008].4 We state the result for the standard routing games framework.
atomic congestion game G, there is a pure Nash equilibrium in G^M that is optimal in G. Equivalently, BPoS(G; G^M ) = 1.
The theorem follows from a simple observation: G^M is a potential game [Rosenthal, 1973], whose potential function (G^M ; a) coincides with the social welfare of G. Thus the optimum of SC(G; a) must a be local minimum of (G^M ; a), i.e. a pure Nash equilibrium. Quite strikingly, the theorem was extended to a much more general framework where agents have idiosyncratic preferences over strategies, and congestion may depend on agents weight or other features [Sandholm, 2007; Singh, 2008].
Example 1. Consider a game with 3 parallel links, E = fa; b; cg and 3 agents N = f1; 2; 3g. A1 = fa; bg, A2 = fb; cg, and A3 = fcg. Latency functions are cb(x) = cc(x) = x, ca 2 (see Fig. 1). The modified cost functions under any edge-independent nonnegative tolls can be written as c^b(x) = c^c(x) = (1; 2 + T (x); 3 + T 0(x)). The unique optimum is a = (a; b; c) with cost SC(a ) = 2 + 1 + 1 = 4, which is also a PNE. However, there is another PNE a0 =
this observation [Fotakis and Spirakis, 2008; Fotakis et al., 2010;
Swamy, 2012].
(a) c(x)
(b) a
In particular, (1; 0)-BS means that BPoA(G; G^) = 1, i.e. that any PNE of G^ is optimal in G.
reasonable parameters ^; ^. 4.1 Smoothness in the large When an atomic game becomes large, i.e. when we fix the network and increase the number of players, there is evidence that the game behaves more similarly to a nonatomic game [Feldman et al., 2015]. We show how to extend biasedsmoothness analysis (and in particular marginal tolls) to large atomic games. While we can not apply the results of Feldman et al. directly, our techniques are inspired by theirs. Lemma 3. Let a; a0 be any two profiles in G with n agents, and let = (G) = maxe2E;x2N(ce(x + 1) ce(x)). Then Pj2N Cj(a j; a0j) Cj(a)) Pe2E(s0e se)ce(se) + O(n ): X ce(se)): e2aj
X ce(se)) e2aj
Cj (a)) ce(se + 1) + ce(se)) f3g f2g f1g (b; c; c) with cost SC(a0) = 1 + 2 + 2 = 5. This remains a PNE of G^T as long as c^bT (x) = c^cT (x): agent 2 is not allowed to use edge a, and agent 1 does not want to use it since c^a(1) = 2 > 1 = c^b(1).
4
ness analysis. In short, a game G is ( ; )-smooth if for all a 2 A there is a0 2 A such that Pi2N Ci(a i; a0i)
SC(G; OPT(G))+ SC(G; a). If a game G (not just a routing game) is ( ; )-smooth, then PoA(G) 1 [Roughgarden, 2009]. Further, this holds for the mixed, correlated, and coarse-correlated PoA as well. For routing games, it is also shown that restricting the class of latency functions results in smooth games. For example, if all cost functions are affine, then G is ( 53 ; 31 )-smooth (thereby showing PoA(G) 52 ).
property of biased smoothness.
X(Cj(a)+C^j(a j; a0j) C^j(a)) j2N Definition 1. (G; G^) is (^; ^)-biased smooth (BS), if there is a0 s.t. for any profile a,
Pj2N (Cj (a)+Cj (a j ; a0j ) Cj (a)) = Pj2N Cj (a j ; a0j ). Theorem 2. Suppose that (G; G^) is (^; ^)-BS. Let be any equilibrium (pure, mixed, correlated, or coarse-correlated) of the game G^. Then SC (G; ) 1 ^ ^ SC (G; OPT(G)).
for the PoA (and coarse-correlated PoA) naturally extends to biased smoothness.5 For completeness, we provide the proof
the aggregate congestion (approximately).
Next, we think of a sequence of atomic games with increasing n: We fix a network (V; E) and continuous quasi-convex ^SC (G; OPT(G))+^SC (G; a): cost functions c = (ce)e2E , where ce : [0; 1] ! R+. For ease of presentation, we consider symmetric games (i.e. where (2) there is just one source-target pair u; v 2 V ), although similar arguments extend to asymmetric games. This already induces a symmetric nonatomic game G~ = (V; E; u; v; c). For n 2 N, we define Gn by setting Gn = (V; E; N; u; v; cn), where cn(x) = c(x=n). Thus G~ is the limit of (Gn)n=1;2;::: (we call it the limit game).
Our continuous cost functions can also be subject to biases. Let c~^e be the biased continuous cost of c~e, and c^en(x) = c~^e(x=n). Biased-smoothness for continuous cost functions was defined and explored in [Meir and Parkes, 2015b]: we say that c is (^; ^)-biased smooth w.r.t. c^ if for all t; t0 2 R+, 5A similar definition of smoothness was applied, for example, for finite congestion games with altruism: when C^(a) is a combination of C(a) and SC(a), then the BPoA coincides with the “robust PoA” of Chen et al. [Chen et al., 2011]. c(t)t + c^(t)(t0 t)
^c(t0)t0 + ^c(t)t:
biased smooth w.r.t. c^n for any n. Proof.
X (Cj (a j ; a0j ) j2N = X (( X j2N e2a0jnaj j2N e2a0jnaj X ( X ce(se) j2N e2a0j =
X (s0ece(se) j2N
X (( X (ce(se) + ) + ce(se))
X e2aj\a0j
X e2aj\a0j X ce(se)) + X X e2aj
j2N e2E sece(se)) + njEj : Theorem 4. Consider a limit game G~, where c~e are quasiconvex and (^; ^)-biased smooth w.r.t. the bias c~^. Then for any > 0 there are > 0; n( ) s.t. for all n > n( ), the atomic game (Gn; G^n) is ((1 + )^; ^)-BS. In particular, BPoA(Gn; G^n) (1 + ) 1 ^ ^ ; and this extends to any coarse-correlated equilibrium. Proof. Let a0 = OPT(Gn), Zn = SC(Gn; a0). Since SC(Gn; a0) = (n) (the cost for each agent is at least some constant), we write Zn > n for some > 0 and n > n( ).
Since c~e is bounded and continuous for all e 2 E, maxfcen(x + 1) x2[n] x 1 cen(x)g = maxfc~e( n + ) x2[n] n
x c~e( n )g sup fc~e(t + t2[0;1]
c~e(t)g n!!1 0; and thus for all > 0 there is some n( ) s.t. for all n > n( ), we have cen(x + 1) cen(x) < . By Lemma 3
SC(Gn; a) +
X C^jn(a j; a0j)
C^jn(a)) j2N SC(Gn; a) + X(s0e
se)c^en(se) + O(n ) = X(secen(se) + (s0e
se)c^en(se)) + n 0 1 n
) e2E e2E e2E X(^cn(s0e)s0e + ^cn(se)se) + n 0 (smoothness) = ^Zn + ^SC(Gn; a) + n 0 < ^SC(Gn; a0) + ^SC(Gn; a) + 1 Zn 0
0 = (^ +
)Zn + ^SC(Gn; a) (1 + 0 )^Zn + ^SC(Gn; a): (Zn > n) (^ 1)
maxfn( ); n( )g), completes the proof. The BPoA bound then follows directly from Theorem 2.
Corollary 5. Consider any limit game G~, where c~e are quasiconvex. Then for any > 0 there is some n( ) s.t. for all n > n( ), BPoA(Gn; G^n) 1 + : Proof. Consider the continuous version of marginal tolls c~^(t) = c~(t) + t @c@(tt) [Beckmann et al., 1956].6 The proof follows directly from Theorem 4 and from the fact that any quasi-convex function c~ is (1; 0)-biased smooth w.r.t. c~^ [Meir and Parkes, 2015b].
discrete c^M (x) we previously defined. A o PB1:5 1 0 1 2 3 4 5 6 7 We next consider agents with variable sensitivity to monetary tolls, as in [Cole et al., 2006]. Formally, the marginal toll e(x) is imposed on edge e, but the cost experienced by the agents is c^e (x) = c(x) + e(x), where is a parameter reflecting how agents trade-off money for time. Denote by G^ the biased game obtained from G by replacing every cost function ce(x) with c^ (x). We analyze the equilibrium for a population with parameter (where = 1 means that c^e (x) = c^eM (x)).
derived for nonatomic games with various classes of cost functions (general/convex/polynomial/linear). We show how these bounds extend to large games.
from [Meir and Parkes, 2015b] for tax-sensitivity and other biases immediately apply. These bounds are also known to be tight.
For example, it was shown that affine cost functions (of 2 the form c~(t) = at + b for a; b 0) are (1; (1+ ) 4 biased smooth w.r.t. c~^(t) as defined above for all 2 ( (1+ ) ; 0)-biased smooth for
4 corollary due to Theorem 4:
)1 and BPoA(Gn; G^n) (1+ )2 if 4
Corollary 6. Consider any limit game G~, where c~e are affine. Then for any > 0 there is some n( ) s.t. for all n > n( ), BPoA(Gn; G^n) ( +1) 1(1+ )2 if 1, and 4
Another benefit of smoothness-in-the-large is that the parameters ^; ^ are typically much smaller for classes of continuous functions than for the corresponding class of discrete costs. Indeed, [Feldman et al., 2015] show that the PoA of large games is significantly smaller due to this: for linear costs the PoA drops from 52 to 34 , and for polynomials of degree d, the PoA drops from (2d) to O( lndd ). Our result shows that this still holds for large games with biases.
the bounds for affine costs.
We have studied the problem of strongly enforcing optimal flows in atomic congestion games through marginal congestion tolls. Such tolls always weakly enforce optimal flows, and strongly enforce optimal tolls in large games. Further, our analysis extends to games where agents’ tax-sensitivity is not aligned with that of the designer. This is particularly important in the context of mechanism design where we seek to shape drivers’ incentives and lead the system to a good equilibrium [Tumer and Agogino, 2006], and when drivers are subject to cognitive and behavioral biases such as risk-aversion [Ordo´ n˜ ez and Stier-Moses, 2010; Nikolova and Stier-Moses, 2015]. One important challenge is to extend the BPoA bounds to games where agents differ in their levels of risk aversion or tax sensitivity. This has been done to some extent in nonatomic games [Meir and Parkes, 2015a; 2015b].
usefulness of “biased-smoothness” analysis, in the line of [Chen et al., 2011; Meir and Parkes, 2015b], and we hope it can lead to a better understanding of routing games where agents are subject to either external influences (like tolls) or behavioral biases.
n X Ea i=1
" + = Ea = Ea
Ea = ^SC(G; OPT(G)) + ^SC(G; );
SC(G; a) + " n
X i=1 h^SC(G; OPT(G)) + ^SC(G; a) Ea [SC(G; a)]
! [C^i(a)] n X C^i(a i; a0i) i=1 Ci(a) + C^i(a i; a0i) C^i(a)
C^i(a) # #
Theorem 2. Suppose that (G; G^) is (^; ^)-BS. Let be any equilibrium (pure, mixed, correlated, or coarse-correlated) of the game G^. Then SC (G; ) 1 ^ ^ SC (G; OPT(G)). Proof. For a correlated profile we denote SC(G; ) = Ea [SC(G; a)].
for any i 2 N; bi 2 Ai, where Inequality (4) follows from Eq. (3) with bi = a0i, (5)+(7) from linearity of expectation, and (6) from Eq. (2) applied for each a. By rearranging terms, we get the bound in the theorem.
Ea [C^i(a)]
Ea [C^i(a i; bi)]: SC(G; ) = Ea [SC(G; a)] (3) (4) (5) (6)