# congestion_games_with_distancebased_strict_uncertainty__47e14560.pdf

Congestion Games with Distance-Based Strict Uncertainty

Reshef Meir and David Parkes

Harvard University

We put forward a new model of congestion games where agents have uncertainty over the routes used by other agents. We take a non-probabilistic approach, assuming that each agent knows that the number of agents using an edge is within a certain range. Given this uncertainty, we model agents who either minimize their worst-case cost (WCC) or their worstcase regret (WCR), and study implications on equilibrium existence, convergence through adaptive play, and efﬁciency. Under the WCC behavior the game reduces to a modiﬁed congestion game, and welfare improves when agents have moderate uncertainty. Under WCR behavior the game is not, in general, a congestion game, but we show convergence and efﬁciency bounds for a simple class of games.

Introduction Congestion games (Rosenthal 1973) provide a good abstraction for a wide spectrum of scenarios where self-interested agents contest for resources, and can be conveniently analyzed using game-theoretic tools. Recently, more complex models of congestion games have been suggested, taking into account the incomplete information agents may have when making a decision (e.g. Ashlagi et al. (2009) and Piliouras et al. (2013); see Related Work). Uncertainty may stem from multiple sources, including uncertainty about the state of nature and thus the cost of resources or about other agents actions. We can imagine commuters choosing routes home from work and facing uncertainty about road conditions (e.g., weather, roadworks) as well as about the routes selected by others. Rather than model uncertainty through a distributional model, we adopt a non-probabilistic approach of strict uncertainty. Indeed, extensive experimental and empirical studies have demonstrated that people have difﬁculties in representing probabilities, and often adopt other heuristics in place of probabilistic reasoning (Tversky and Kahneman 1974; Slovic, Fischhoff, and Lichtenstein 1980). With strict uncertainty, each player faces a set of possible states, where the cost of each action depends on the (unknown) actual state, and decisions take into account risk attitudes

Parkes is supported in this work by the Tom Kat Charitable Trust. Copyright c 2015, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

and other biases, often applying heuristics rather than optimization. Such alternative approaches to decision making in general, and to uncertainty in particular, have deep roots in the AI literature, largely due to the works of Herbert Simon on bounded rationality and procedural rationality (Simon 1957; 1987). Having adopted a non-probabilistic approach, we must make two crucial modeling decisions. First, we must decide how each agent acts in the face of strict uncertainty. The simplest behavior follows a minimax approach (Wald 1939; Simon 1957), and assumes that the decision maker is trying to minimize her worst-case cost (WCC). Another approach seeks to minimize the worst-case regret (WCR) of the decision maker, which goes back to Savage (1951), and has been also applied to games (Hyaﬁl and Boutilier 2004). Both cost measures are worst-case approaches, and suitable as an abstraction for the behavior of a rational but risk-averse agent. Second, we need to determine which states are considered possible by the agents. To construct the set of possible states, we adopt the recent model of distance-based uncertainty (Meir, Lev, and Rosenschein 2014). All agents share the same belief about the current reference state of the network (i.e., the load on every edge in a routing game), which may be available for example from an external source such as trafﬁc reports, or from an agent s previous experience. However agents vary in the accuracy they attribute to the reference state. Each agent i has an uncertainty parameter, ri, which reﬂects a belief that the actual load is within some distance ri of the reference load. A higher ri may reﬂect either that an agent is less informed about the true congestion, or, alternatively, that she is more risk-averse. From each heuristic (WCC or WCR) we can derive a natural equilibrium concept. Intuitively, every action proﬁle induces a reference state s, and we consider the heuristic best response of every agent to the set of possible states around s. State s is an equilibrium if every agent minimizes her worst case cost (or regret) by keeping her current action. As a simple example, if in some proﬁle 100 players are using a resource, then agent i believes the actual load to be anywhere between 100/ri and 100ri. If ri = 1 for all agents, we get the standard complete information model as a special case: both minimax cost and minimax regret collapse to simple cost minimization, and our equilibrium notion coincides with Nash equilibrium.

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence

Our contribution. We study equilibrium behavior in nonatomic congestion games, under our strict, distancebased model of uncertainty. For simplicity and concreteness, we focus our presentation on routing games, where resources are edges in a graph, and valid strategies are paths from source to target.1With worst-case cost players, we show that the game reduces to a modiﬁed, completeinformation routing game with player-speciﬁc costs. Further, if all agents have the same uncertainty level we get a potential game. We are interested in how equilibrium quality (measured by the price of anarchy (Roughgarden and Tardos 2004)) is affected by introducing uncertainty. For routing games with afﬁne cost functions, we show that the price of anarchy (Po A) under uncertainty decreases gradually from 4

3 (without uncertainty) to 1, and then climbs back up, proportionally to the amount of uncertainty. We also show that in a population of agents with different uncertainty levels, the Po A is bounded by the Po A of the worst possible uncertainty level. With worst-case regret players the induced game is no longer a congestion game. Yet, we show that for a simple class of games a weak potential function exists, and thus equilibrium existence and convergence results are available. We give some preliminary results on Po A bounds with worst-case regret players. Due to space constraints most of our proofs are omitted, and are available in the full version of this paper.2

Preliminaries Nonatomic routing games. Following Roughgarden (2003) and Roughgarden and Tardos (2004), a nonatomic routing game (NRG) is a tuple G = G, c, m, u, v, n , where

G = (V, E) is a directed graph;

c = (ce)e E, ce(t) 0 is the cost incurred when t agents use edge e;

m N is the number of agent types;

u, v V m, where (ui, vi) are the source and target nodes of type i agents;

n Rm +, where ni R+ is the total mass of type i agents. n = P

i m ni is the total mass of agents.

We denote by Ai 2E the set of all directed paths between the pair of nodes (ui, vi) in the graph. Thus Ai is the the set of actions available to agents of type i. We denote by A = i Ai the set of all directed source-target paths. We assume that the costs ce are non-decreasing, continuous and differentiable. A NRG is symmetric if all agents have the same source and target, i.e., Ai = A for all i. A symmetric NRG is a resource selection game (RSG) if G is a graph of parallel links. That is, if A = E and the action of every agent is to select a single resource (edge).

1Any congestion game is equivalent to a routing game. 2http://arxiv.org/abs/1411.4943

Game states. A state (or action proﬁle) is a vector s R|A| m + , where sf,i is the amount of agents of type i that use path f Ai. In a valid state, P f Ai sf,i = ni. The total trafﬁc on path f A is denoted by sf = Pm i=1 sf,i. The load state s R|E| + is a vector of aggregated edge loads derived from state s, where se = P f:e f sf. This is the total trafﬁc on edge e E via all paths going through e. We also allow load states that cannot be derived from a valid state. Note that all the information relevant to the costs in state s is speciﬁed in the load state s: all agents using a particular edge e suffer a cost of ce(se) in state s, and the cost of using a path f Ai is c(f, s) = P e f ce(se). Thus except in settings where agents types or exact strategies matter, we may use s and s interchangeably. The social cost in a proﬁle s is

f Ai sf,ic(f, s) = X

The second equality is since we multiply the cost c(t) by the mass t ( number of agents ) who experience it.

Equilibrium and potential. Without uncertainty, a state s for an NRG is an equilibrium if for every agent type i and actions f1, f2 Ai with si,f1 > 0, c(f1, s) c(f2, s). That is, if no agent can switch to a path with a lower cost. This is the analogy of a Nash equilibrium in nonatomic games. In nonatomic games, φ(s) is a potential function, if any (inﬁnitesimally small) rational move, i.e., a move that decreases the cost of the moving agents, also lowers the potential. φ(s) is a weak potential function if at any state there is at least one such move (although some rational moves may increase φ). Any game with a potential function is acyclic, in the sense that such inﬁnitesimal best responses of self interested agents are guaranteed to converge to a local minimum of the potential function (and an equilibrium). A game with a weak potential may have cycles, but from any state there is some path of rational moves that leads to an equilibrium. It is well known that NRGs have a potential function, which is deﬁned as (we omit the argument G when it is clear from the context): φ(s) = φ(G, s) = P e E R se t=0 ce(t)dt. Furthermore, in a NRG every local minimum of the potential is also a global minimum; all equilibria have the same social cost; and in every equilibrium all agents of type i experience the same cost (Aashtiani and Magnanti 1981; Milchtaich 2000; Roughgarden and Tardos 2004).

Afﬁne routing games. In an afﬁne NRG, all cost functions take the form of a linear function. That is, ce(t) = aet + be for some constants ae, be 0. In an afﬁne game G, the social cost can be written as SC(G, s) = P e E ae(se)2 + bese; and the potential as φ(G, s) = P e E 1 2ae(se)2 + bese. Pigou s example is the special case of an afﬁne RSG with two resources, where c1(t) = 1 and c2(t) is deﬁned with b2 = 0. We will use variations of this example throughout the paper, and denote by GP (a2, n) the instance where c2(t) = a2t, and there is a mass of n agents.

Potential and social cost. The social cost of every NRG can be written as the potential of a suitably modiﬁed game. For this, let ˆG be a modiﬁcation of G, where we replace every ce(t) with ˆce(t) = ce(t)+tc e(t). Then, φ( ˆG, s) = SC(G, s) for all s (Roughgarden 2007). For an afﬁne game, the modiﬁed cost function is ˆce(t) = 2aet + be; and φ( ˆG, s) = P e E ae(se)2 + bese = SC(G, s).

The price of anarchy. Let EQ(G) be the set of equilibria in game G. The price of anarchy (Po A) of a game is the ratio between the social cost in the worst equilibrium in EQ(G) and the optimal social cost. Since all equilibria have the same cost, we can write Po A(G) = SC(s ) SC(OP T ), where s is an arbitrary equilibrium of G. In afﬁne NRGs, it is known that Po A(G) 4

3, and this bound is attained by GP (1, 1) (Roughgarden and Tardos 2004).

Introducing uncertainty

In our strict uncertainty model, there is an underlying base game G, which is a NRG. However given an action proﬁle (state) s, each agent believes that there is some set of possible states, and selects her action based on worst-case assumptions. To deﬁne this set of possible states, we augment the description of every agent type with an uncertainty parameter ri 1, and denote r = (ri)i m. The special case where all ri = r is called homogeneous uncertainty. We adopt distance-based uncertainty, so that in a given state s (where the actual load on edge e is se), a type i agent believes that the load is anywhere in the range [se/ri, se ri]. Consequently, the agent believes that the cost she will suffer from using resource e is between ce(se/ri) and ce(se ri). Agents apply this reasoning separately to each resource, thus the load state s is considered possible in load state s by a type i agent, if s e [se/ri, se ri] for all e E.3

In other words, consider the distance metric d(s, s ) = min{x 0 : e E, se s e 1+x s e se 1+x}. Then

S(s, ri) = S(s, ri) = {s R|E| + : d(s, s ) ri 1} is the set of load states that a type i agent believes possible given s. Note that s may not correspond to any actual state s , e.g. the total load on all paths may not sum up to total mass n, as an agent may not know exactly how many other agents participate.

Behavior and equilibria

Worst-case cost. Under the WCC model, each agent cares about the worst possible cost of each action. Thus for an agent of type i, the effective cost of choosing path (action) f Ai in state s is c i (f, s) = max{c(f, s ) : s S(s, ri)}.

3In the language of modal logic, we say that the s is accessible from s if the above holds. Our accessibility relation is symmetric, but non-transitive. While transitivity is a well accepted axiom in epistemic models (Aumann 1999), we argue that it does not make sense when there is a natural metric over states.

c1(s1) c2(s2)

c 1(s1) c 2(s2)

Figure 1: Two resources with base costs c1(s1) = 5 + s1, c2(s2) = 2 + s2. The ﬁgure shows the true costs for s1 = 3, s2 = 5. The dotted brackets show the range of possible costs for r = 2, where the upper bracket is the WCC cost. The dashed lines are the WCR costs. We can see that the better resource under WCC is e1, but e2 is better under WCR, as c (e2, s) = 12 6.5 = 11 4.5 = c (e1, s).

Every NRG G and uncertainty vector r induce a new nonatomic game G (r), where the cost functions are c i . That is, a type i agent playing so as to minimize her worst-case cost in G, behaves exactly like a rational type i agent (minimizing exact cost) in G (r). A priori, G (r) is not a NRG, but it has a very similar structure. For every action f Ai, according to the WCC model,

c i (f, s) = X

e f max{ce(s e) : s S(s, ri)} = X

e f ce(rise).

Since ce(rit) can be written as a player-speciﬁc cost function, c i,e(t), we have that G (r) is a NRG with playerspeciﬁc costs (Milchtaich 2005), where each player type can adopt a different cost function; e.g., for afﬁne games c i,e(t) = riaet + be.

Worst-case regret. We get a different modiﬁed game, G (r), under the WCR model. The regret (for a type i agent) of playing action f in state s is deﬁned as REGi(f, s ) = c(f, s ) minf Ai c(f , s ). Given this, the cost c i (f, s) in the modiﬁed game, which is the worst-case regret a type i agent may suffer for playing f, is deﬁned as:

c i (f, s) = max{REGi(f, s ) : s S(s, ri)}.

This cost function c i (f, s) does not have a natural decomposition to edge-wise costs, since regret depends also on the load on unused edges. An example of WCC and WCR costs in a simple 2-resource RSG appear in Figure 1.

Equilibrium. A WCC equilibrium is a state where no agent can improve her worst-case cost w.r.t. her uncertainty level. By deﬁnition of the cost function c , the WCC equilibria of G for uncertainty values r are exactly the Nash equilibria of G (r). Similarly , a WCR equilibrium is a Nash equilibrium of G (r). Since both of G (r) and G (r) are special cases of nonatomic games, existence of equilibria follows from general existence theorems (Schmeidler 1973). However the other properties of NRG, such as the existence of a potential function, and bounds on the Po A, are not guaranteed.

Routing Games with WCC players Equilibrium and convergence. For the special case of ri = r for all i m, it is not hard to see that G (r) is a non player-speciﬁc NRG. This is since c e,i(s) = ce(r se) is only a function of se. We denote this modiﬁed cost function by cr e(t). It follows that G (r) is a potential game, where φ(G (r), s) = P e R se t=0 cr e(t)dt. Thus G (r) is acyclic, the equilibria of G (r) are the minima of φ(G (r), s), and all equilibria have the same social cost. The more interesting question is what properties of NRG are maintained when agents have different uncertainty parameters. We have already noted that in G (r) there is at least one equilibrium. Player-speciﬁc RSGs are known to have a weak potential (Milchtaich 1996), but this does not preclude cycles. Indeed, we show that a cycle may occur even in an RSG where agents only differ in their uncertainty level.

Proposition 1. There is an RSG G with 3 resources, and a vector r s.t. G (r) contains a cycle.

Equilibrium quality for afﬁne games Recall that under the WCC model, agents play as if they take part of the game G (r), while their actual, realized costs are those in underlying game G. We thus deﬁne the Price of Anarchy for WCC players with uncertainty vector r as:

C-Po A(G, r) = max s EQ(G (r)) SC(G, s) SC(G, OPT(G)).

We focus our analysis on games with afﬁne costs, and look for bounds on C-Po A(G, r). In particular, we explore whether players with uncertainty reach better or worse social outcomes under WCC behavior than under standard, complete information equilibria.

Homogeneous uncertainty. We start with the simplifying assumption that ri = r for all types. Recall that in this case G (r) is a non player speciﬁc NRG, where the cost of each edge is modiﬁed to cr e(t) = raet + be. These modiﬁed costs can be attained in other contexts that do not involve uncertainty. For example, this can be achieved through taxation (Cole, Dodis, and Roughgarden 2003). Following the discussion in Potential and Social Cost, an optimal taxation scheme would perturb the cost functions so that the realized cost is ˆce(t) = ce(t) + tc e(t), as this will guarantee that

φ( ˆG, s) = SC(G, s) for all s. In this way, minimizing the potential of ˆG, as happens in equilibrium, also minimizes the social cost in G (see Section 18.3.1 in Roughgarden (2007) for a detailed explanation). For the special case of afﬁne games, it is easy to see that the effect of uncertainty level r = 2 is equivalent to that of an optimal taxation scheme. That is, φ(G (2), s) = SC(G, s) for all s. This means that if all agents adopt the WCC viewpoint for an uncertainty type of r = 2, then they would play the social optimum. Unfortunately, the value of r is not a design parameter we cannot decide for the agents how uncertain they should be, since this reﬂects their beliefs. We would therefore like to have guarantees on equilibrium quality for any value of r. The next lemma provides our ﬁrst result in this direction. We denote φr(s) = φ(G (r), s). It will be convenient to treat the cases r 2 and r 2 separately.

Lemma 2. Let G be an afﬁne NRG, and suppose that r 2. Then for all s, φr(s) [SC(G, s), r

2SC(G, s)].

Proposition 3. For r 2, and any afﬁne NRG G, C-Po A(G, r) r

Proof. Let s be a global optimum of φr, s O = OPT(G). By Lemma 2 SC(G, s ) φr(s ) φr(s O) r 2SC(G, s O).

We can similarly derive a bound of 2/r for the range r [1, 2), but we can do better. We next show that as we increase the uncertainty level r from 1 towards 2, we get a smooth improvement in social cost.

Theorem 4. For r [1, 2], and for any afﬁne NRG G, C-Po A(G, r) 2 2

r 1)Po A(G) 2+2r

Let q (r) = max G C-Po A(G, r); and q P (r) = max GP C-Po A(GP , r). The results above give us an upper bound on q (r). By a careful analysis of the Pigou-type instances, we can compute q P (r) exactly, which also provides us with a lower bound on q (r).

Corollary 5. For r [1, 2], q (r) [ 4 4r r2 , 2+2r

r > 2, we have q (r) [ r2 4(r 1), r/2] = [r/4 + o(1), r/2]. Also, q P (r) is equal to our lower bound on q (r).4

Note that for r = 1 and r = 2, we have q (r) = q P (r), and both are equal to the familiar values of 4/3 and 1, respectively. See Figure 2 for a graphical comparison of the bounds.

Diverse population. We would like to show that if we have a population of agents with different uncertainty levels, the social cost does not exceed that of the upper bound we have on the worst type; i.e., that q (r) q (ri) for some type i in the mixture. We show something very close (our

4Roughgarden (2003) showed that for any class of cost functions, a worst-case example for the Po A can be constructed on an RSG with two resources. It is not clear if this is also true for the C-Po A, as in our case the optimum and the equilibrium are computed for two different games. However if a similar result can be proved, then our upper bounds would collapse to the lower bounds.

Figure 2: The solid red lines are upperand lower-bounds on q (r), i.e. the maximum Po A, across all games, for WCC players with uncertainty parameter r (the lower bound is also exactly q P (r), the maximum Po A across Pigou examples). The blue dashed line is exactly q P (r). The dotted lines mark 4/3 and 1.

bound is slightly worse when there are types both below and above r = 2). Let j = argmini ri, k = argmaxi ri; let αj = C-Po A(G, rj) if rj < 2 and 1 otherwise; let αk = rk

2 if rk > 2 and 1 otherwise. Lemma 6. Let s, s be any two states in afﬁne NRG G, and consider r3 r2 r1. If φr3(s) φr3(s ) and φr2(s) φr2(s ), then φr1(s) φr1(s ) as well. Theorem 7. Let G be an afﬁne NRG, r be an uncertainty vector. Then C-Po A(G, r) αj αk.

Proof of Theorem 7 for rj 2. Let s be an equilibrium of G (r). Let s i be a state minimizing φri(s). Note that φr(s) < φr (s) for all r < r and any s. By Lemma 2, φ2(s) = SC(G, s) for any s. We next bound SC(G, s ), dividing into cases: rj 2; rk 2; rj < 2 < rk. We prove for rj 2. Consider the state s k, which is an equilibrium of the game G (rk). If φrk(s ) = φrk(s k), then s is also an equilibrium of G (rk). Since G (rk) is an NRG, all equilibria have the same social cost, thus

φ2rk(s ) = SC(G (rk), s ) = SC(G (rk), s k) = φ2rk(s k).

As 2rk > rk 2, by Lemma 6 φ2(s k) φ2(s ) (in fact equal). Thus

SC(s ) = φ2(s ) φ2(s k) = SC(s k). (1)

Thus suppose that φrk(s k), φrk(s ) differ. By deﬁnition, φrk(s k) < φrk(s ). There must be some (non zero measure of) agents with different actions in both states. It cannot be that all of these agents have uncertainty rk, since the states s , s k have a different φk potential. Consider any such agent of type i, ri < rk, whose action under s differs from the one in s k. If φri(s k) < φri(s ) then s is not an equilibrium of G (r), as some agents of type i would deviate. We conclude that there is at least one type i s.t. ri < rk, and φri(s k) φri(s ). Since rk > ri 2, and φ2(s k) φ2(s ) by Lemma 6, we get Eq. (1) again. Thus SC(s ) SC(s k). By Lemma 2, we have that C-Po A(G, r) C-Po A(G, rk) αk (note that αj = 1).

Finally, in a RSG a small fraction of the agents with high uncertainty cannot inﬂict too much damage. Theorem 8. Let G be an afﬁne RSG. Suppose that r is composed of two types, rk > rj. Then C-Po A(G, r) rj

Worst-Case Regret For what follows, we assume that ri = r for all i. In addition, we focus on RSGs, as the analysis is non-trivial even for such simple games.

Equilibrium and convergence. In a RSG, the set of edges E is also the set of actions. For every resource e in state s, we have

c ({e}, s) = WCR(e, s) = ce(rse) min d =e cd(sd/r).

As G is an RSG, s EQ(G (r)) if and only if WCR(e, s) is the same for all occupied edges, and at least as high in unoccupied edges. Denote MR(s) = maxe E:se>0 WCR(e, s). Recall that every RSG with player-speciﬁc costs has a weak potential (Milchtaich 1996). We show a similar result for an RSG played by WCR players. Our result requires an additional technical property, but allows an explicit construction of the potential. We say that a function z(t) is rconvex if z (t/r)/r r z (r t) for all t, where c is the derivative of c. We note that r-convexity holds for convex and other commonly used functions (see full version). Proposition 9. Consider an RSG G, and suppose that all cost functions are r-convex. Then MR(s) is a weak potential function of G (r). Then if there are WCR moves, there is a WCR move that reduces MR(s).

Equilibrium quality for Pigou instances. In the special case of the family of Pigou instances, we have: Proposition 10. Let q P (r) = max GP R-Po A(GP , r).

(1) For any r [1, 2+

3], we have q P (r) = 16 8(r+1

(2) For any r 2 +

3, we have q P (r) = (r+ 1

Thus R-Po A(GP , r) for r 2+

3 is an increasing function in r, and asymptoting to r/8+o(r) (see Figure 2). It remains an open question to derive an upper bound for games over more complex networks.

Discussion Related work. We focus on previous work on uncertainty (especially strict uncertainty) in congestion games (CG). Strict uncertainty been considered by Ashlagi et al. (2006; 2009). They analyze safety-level strategies (similar to WCC) for agents who do not know the total number of players k, but only an upper bound on k, and focus on proving the existence of a symmetric mixed equilibrium. For atomic RSGs, they show that (as in our case) uncertainty improves the social welfare. Both the the analysis techniques

and the reasoning required from agents in their setting are quite complex, despite the focus on a simple class of games, whereas in our case the game with WCC behavior reduces to a modiﬁed (player-speciﬁc) congestion game. The next two papers are closer to our approach, where agents react to some noisy variation of the current state. Meir et al. (2012) study the effect of Bayesian uncertainty due to agents who may fail to play with some probability (in the spirit of trembling-hand perfection). They focus mainly on RSGs and show that the Po A generally improves if failure probabilities are negligible, but not if they are bounded from 0. Angelidakis et al. (2013) study a related model of RSGs with agents who react based on a quantile of the cost distribution. We further discuss these two papers below. Piliouras et al. (2013) also study CGs with strict uncertainty with motivation similar to ours, and look at a wide range of decision-making approaches including WCC and WCR. However, agents in their model know the actions of others exactly, and uncertainty over costs stems from the unknown order in which players arrive. Our model is more direct, and closer to the traditional view of congestion games. Babaioff et al. (2007) study the effect of introducing a small fraction v of malicious agents. This is related to our WCC model, where agents behave as if the load on each edge is increased by v = (r 1)se additional (malicious) agents. However, in our model this added load only affects the behavior of real agents, and does not affect the outcome directly. Babaioff et al. (2007) observe that adding some amount of malicious agents may decrease the social cost in equilibrium; see also followup work (Blum et al. 2008; Roth 2008). Lastly, Halpern and Pass (2012) suggested iterated regret minimization as an explanation to human behavior in many games. We emphasize that in contrast to our model, such behavior requires agents to explicitly reason about the incentives of other agents.

Distance-based uncertainty. Our epistemic model adapts the multiplicative distance-based uncertainty model, initially introduced in the context of voting theory (Meir, Lev, and Rosenschein 2014; Meir 2015). There, the state was the number of votes for each candidate, analogous to the measure of agents on each resource in the present setting. While the epistemic model in both papers is derived from a similar approach, both the behavioral heuristics and the techniques for analysis are quite different. For example in voting games payoffs are highly discontinuous, so it is not a priori clear whether pure equilibria exist. There may appear to be a contradiction between our notion of uncertainty and equilibrium play: if agents converge to a particular state and play it repeatedly, then after a while we might expect them to be certain about this state. However even in standard congestion game the state (action proﬁle) is only an abstraction of reality, where there is noise from various sources from players actions and failures, to varying costs. Thus an equilibrium is a ﬁxed point in the abstract model, although in reality there remain ﬂuctuations around the equilibrium point. Thus even in equilibrium there may

be some uncertainty about the exact loads. Some papers model the underlying distribution explicitly (e.g.,(Meir et al. 2012; Angelidakis, Fotakis, and Lianeas 2013)), and assume a belief structure that is derived from this distribution. Such an approach does not necessarily provide a better description of the way human players perceive the game. In our model we avoid such an explicit description, and instead use s (as an abstraction of the current state) and derive agents beliefs directly from this state using the distance metric. These beliefs may or may not be consistent with the real underlying distribution, which may be highly complex. This simple belief structure allows us to derive Po A bounds on a much wider class of games. Distance-based uncertainty can also be derived from a statistical viewpoint. Suppose that an agent believes that the actual load is distributed around the reference load se. A simple heuristic considers a conﬁdence interval around se, with the size of the interval modeled through ri. Under this interpretation, ri is higher for agent types that are either more risk-averse or less-informed.5 A crucial point is that if agents act independently the actual congestion would be highly concentrated around its expectation (that is, ri should approach 1 as the size of the population grows), and for nonatomic agents there should be no uncertainty at all. However, experimental work in behavioral decision making suggests people perceive uncertainty over quantities as if the standard deviation is proportional to the expectation, even when this is false (Kahneman and Tversky 1974; Tversky and Kahneman 1974).6 While in our model the uncertainty is over the actions of the other agents, an alternative way is to present it as strict uncertainty over the agent s own cost function, also known as Knightian Uncertainty (Knight 1921). Chiesa et al. (2014) have recently applied Knightian uncertainty to auctions, where an agent may have a valuation for an item, but only be aware of some interval in which this valuation resides. Further studying the conceptual and technical connection between distance-based uncertainty and Knightian uncertainty may help to gain better understanding of both concepts.

Conclusions Game-theoretic models should explain and predict the behavior of players in games. Merely adding to such models uncertainty about the environment is insufﬁcient, since as Simon (1957) wrote: ...the state of information may as well be regarded as a characteristic of the decision-maker as a characteristic of his environment. Indeed, psychological studies suggest that people are both risk-averse and avoid

5For example, if the noise on edge e is a normal distribution with standard deviation σ and mean 0, and an agent of type i requires conﬁdence of 95% (roughly two standard deviations), then this translates to a strict uncertainty interval of [se 2σ, se + 2σ] 6The most famous example is an experiment where subjects are told the average number of girls born daily in a hospital is s. People believe that the probability that on a given day the number is within [(1 r )s, (1+r )s] is ﬁxed and does not depend on s. Kahneman and Tversky (1974) highlight the contrast with standard, statistical analysis, where the range r is proportional to 1/ s.

probabilistic calculations (Tversky and Kahneman 1974; Slovic, Fischhoff, and Lichtenstein 1980), and raise concerns with standard models of rationality. We believe that our model captures these behavioral assumptions, and that it is simpler than other approaches for uncertainty representation. In addition, we show that the model still permits the use of standard game-theoretic tools such as equilibrium analysis. The model is ﬂexible, and variations of the belief structure (the distance metric) can be easily made. One limitation of our approach is that distance based uncertainty (an interval) cannot capture bi-modal scenarios. For example, when congestion is usually mild, but in rare cases (an accident) congestion is very high. This is similar to the reason that a normal distribution cannot capture such a scenario. Our results show that in a risk-averse population, an intermediate level of uncertainty helps to align the incentives of the agents with those of the society. This message is emphasized by showing similar results for two different interpretation of risk-aversion, and is consistent with ﬁndings from other models of uncertainty (see Related Work). Finally, lab experiments with routing games show that human subjects converge to states that are close to, but do not coincide with the Nash equilibria (Rapoport et al. 2009) (especially when looking at individual behavior rather than aggregate congestion). We believe that these discrepancies might be at least partially due to bounded-rational behavior of the agents, who may be risk-averse and/or applying simple variations of best-response heuristics. Thus our model might be able to better explain observed outcomes in congestion games. More empirical and experimental work is required in that respect.

References Aashtiani, H. Z., and Magnanti, T. L. 1981. Equilibria on a congested transportation network. SIAM Journal on Algebraic Discrete Methods 2(3):213 226. Angelidakis, H.; Fotakis, D.; and Lianeas, T. 2013. Stochastic congestion games with risk-averse players. In Algorithmic Game Theory. Springer. 86 97. Ashlagi, I.; Monderer, D.; and Tennenholtz, M. 2006. Resource selection games with unknown number of players. In AAMAS 06, 819 825. Ashlagi, I.; Monderer, D.; and Tennenholtz, M. 2009. Twoterminal routing games with unknown active players. Artiﬁcial Intelligence 173(15):1441 1455. Aumann, R. J. 1999. Interactive epistemology I: Knowledge. International Journal of Game Theory 28(3):263 300. Babaioff, M.; Kleinberg, R.; and Papadimitriou, C. H. 2007. Congestion games with malicious players. In EC 07, 103 112. Blum, A.; Hajiaghayi, M.; Ligett, K.; and Roth, A. 2008. Regret minimization and the price of total anarchy. In STOC 08, 373 382. Chiesa, A.; Micali, S.; and Zhu, Z. A. 2014. Knightian self uncertainty in the vcg mechanism for unrestricted combinatorial auctions. In EC 14, 619 620. Cole, R.; Dodis, Y.; and Roughgarden, T. 2003. How much can taxes help selﬁsh routing? In EC 03, 98 107. Halpern, J. Y., and Pass, R. 2012. Iterated regret minimization: A new solution concept. Games and Economic Behavior 74(1):184 207.

Hyaﬁl, N., and Boutilier, C. 2004. Regret minimizing equilibria and mechanisms for games with strict type uncertainty. In UAI 04, 268 277. Kahneman, D., and Tversky, A. 1974. Subjective probability: A judgment of representativeness. In The Concept of Probability in Psychological Experiments. Springer. 25 48. Knight, F. H. 1921. Risk, Uncertainty and Proﬁt. Houghton Mifﬂin. Meir, R.; Tennenholtz, M.; Bachrach, Y.; and Key, P. 2012. Congestion games with agent failures. In AAAI 12. Meir, R.; Lev, O.; and Rosenschein, J. S. 2014. A local-dominance theory of voting equilibria. In EC 14. Meir, R. 2015. Plurality voting under uncertainty. In AAAI 15. To appear. Milchtaich, I. 1996. Congestion games with player-speciﬁc payoff functions. Games and economic behavior 13(1):111 124. Milchtaich, I. 2000. Generic uniqueness of equilibrium in large crowding games. Mathematics of Operations Research 25(3):349 364. Milchtaich, I. 2005. Topological conditions for uniqueness of equilibrium in networks. Mathematics of Operations Research 30(1):225 244. Piliouras, G.; Nikolova, E.; and Shamma, J. S. 2013. Risk sensitivity of price of anarchy under uncertainty. In EC 13, 715 732. Rapoport, A.; Kugler, T.; Dugar, S.; and Gisches, E. J. 2009. Choice of routes in congested trafﬁc networks: Experimental tests of the braess paradox. Games and Economic Behavior 65(2):538 571. Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2(1):65 67. Roth, A. 2008. The price of malice in linear congestion games. In Internet and Network Economics. Springer. 118 125.

Roughgarden, T., and Tardos, E. 2004. Bounding the inefﬁciency of equilibria in nonatomic congestion games. Games and Economic Behavior 47(2):389 403. Roughgarden, T. 2003. The price of anarchy is independent of the network topology. Journal of Computer and System Sciences 67(2):341 364. Roughgarden, T. 2007. Routing games. In et al., N., ed., Algorithmic game theory. Cambridge University Press New York. Savage, L. J. 1951. The theory of statistical decision. Journal of the American Statistical association 46(253):55 67. Schmeidler, D. 1973. Equilibrium points of nonatomic games. Journal of Statistical Physics 7(4):295 300. Simon, H. 1957. A behavioral model of rational choice. New York: Wiley. Simon, H. A. 1987. Bounded rationality. The New Palgrave: utility and probability 15 18. Slovic, P.; Fischhoff, B.; and Lichtenstein, S. 1980. Facts and fears: Understanding perceived risk. In Societal risk assessment. Springer. 181 216. Tversky, A., and Kahneman, D. 1974. Judgment under uncertainty: Heuristics and biases. science 185(4157):1124 1131. Wald, A. 1939. Contributions to the theory of statistical estimation and testing hypotheses. The Annals of Mathematical Statistics 10(4):299 326.