Preface
COMP559/326
Congestion Games
Giorgos Christodoulou
University of Liverpool, Computer Science Dept
COMP559/326 – Congestion Games · 0.1
Topic 3: Selfish routing / congestion games Ch.18
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.1
Wardrop Model
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.2
Wardrop Model Model
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.3
Wardrop Model Model
3a Wardrop Model
We are given a
I directed graph G = (V ,E)
I k commodities, for each i ∈ [k ]
I si , ti .. source-sink pair
I ri .. flow demand to route from si to ti
I normalise: r =
∑
i∈[k ] ri = 1
I Pi .. set of paths between si and ti
I P = ∪i∈[k ]Pi
I ce : [0,1] 7→ R .. latency (cost) function of edge e ∈ E
I continuous, non-decreasing, non-negative
I The triple (G, r , c) is an instance of the routing problem
COMP559/326 – Congestion Games Selfish Routing · 3.4
Wardrop Model Model
Wardrop Model
Flow and Latency:
I flow vector (fP)P∈P
I fe =
∑
P3e fP
I a flow is feasible if it satisfies flow
demands and flow conservation
I ce(f ) = ce(fe) .. edge latency / cost
I cP(f ) =
∑
e∈P ce(f ) .. path latency
Total latency (the total cost)
C(f ) =
∑
P∈P
fP · cP(f )
=
∑
e∈E
fe · ce(f )
COMP559/326 – Congestion Games Selfish Routing · 3.5
Wardrop Model Model
Wardrop Model
Flow and Latency:
I flow vector (fP)P∈P
I fe =
∑
P3e fP
I a flow is feasible if it satisfies flow
demands and flow conservation
I ce(f ) = ce(fe) .. edge latency / cost
I cP(f ) =
∑
e∈P ce(f ) .. path latency
Total latency (the total cost)
C(f ) =
∑
P∈P
fP · cP(f )
=
∑
e∈E
fe · ce(f )
COMP559/326 – Congestion Games Selfish Routing · 3.5
Wardrop Model Model
Wardrop Model
I So far, we basically just introduced a flow model.
I In the Wardrop model we assume:
I flow is controlled by an infinite number of agents
I each agent is responsible for an infinitesimal fraction of the flow
I agents strive to minimise their own latency
Definition (Wardrop equilibrium)
A feasible flow f is a Wardrop equilibrium if for every commodity i ∈ [k ]
and every pair P1,P2 ∈ Pi with fP1 > 0, we have
cP1(f ) ≤ cP2(f ).
This implies:
I All used paths of the same commodity have the same latency.
COMP559/326 – Congestion Games Selfish Routing · 3.6
Wardrop Model Model
Wardrop Model
I So far, we basically just introduced a flow model.
I In the Wardrop model we assume:
I flow is controlled by an infinite number of agents
I each agent is responsible for an infinitesimal fraction of the flow
I agents strive to minimise their own latency
Definition (Wardrop equilibrium)
A feasible flow f is a Wardrop equilibrium if for every commodity i ∈ [k ]
and every pair P1,P2 ∈ Pi with fP1 > 0, we have
cP1(f ) ≤ cP2(f ).
This implies:
I All used paths of the same commodity have the same latency.
COMP559/326 – Congestion Games Selfish Routing · 3.6
Wardrop Model Model
Examples
Pigou’s Example
Wardrop Model examples
Examples:
2(x) = x
1(x) = 1
s t
COMP558 – Network Games Selfish Routing · 3.1
Braess’ Paradox
1.1.2 Braess’ Paradox
0
x 1
x1
• First ignore dashed edge.
• Optimal solution: split flow 12 via both paths. Then,
OPT =
1
2
·
(
1
2
+ 1
)
+
1
2
·
(
1 +
1
2
)
=
3
2
• Now, insert dashed edge:
• Optimal solution stays the same
• Equilibrium: All agents use zigzag path. Then, cost = 1 · (1 + 1) = 2.
1.2 The Wardrop Model
We are given a
• directed graph G = (V,E)
• k commodities with source-sink pairs si, ti and flow demands ri, i ∈ [k],
normalise r =
∑
i∈[k] ri = 1.
• denote set of paths between si and ti by Pi, let P = ∪i∈[k]Pi (for simplicity,
let the Pi be disjoint)
• latency functions on the edges !e : [0, 1] #→ R≥0 (non-negative, non-
decreasing, differentiable)
• The triple (G, r, !) is an instance of the routing problem.
Agents induce flow and latency:
• flow vector (fP )P∈P , fe =
∑
P#e fP .
• a flow is feasible if it satisfies the flow demands and flow conservation
• edge latency: !e(f) = !e(fe)
• path latency: !P (f) =
∑
e∈P !e(f)
• edge cost : ce(f) = fe · !e(f).
2
COMP559/326 – Congestion Games Selfish Routing · 3.7
Wardrop Model Optimal Flows & Wardrop Equilibria
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.8
Wardrop Model Optimal Flows & Wardrop Equilibria
Characterizing Optimum Flows
Optimum flow: minimise the value of C(f ) among all feasible flows.
Formulation as a convex program
minC(f ) =
∑
e∈E
fe · ce(f )
s.t.
∑
P∈Pi
fP = ri ∀i ∈ [k ]
fe =
∑
P3e
fP ∀e ∈ E
fP ≥ 0 ∀P ∈ P
Remarks:
I The linear constraints of this
program define a convex
polyhedron.
I We assume that the terms
fe · ce(f ) are convex.
I Number of variables is
exponential in network size.
(Can be reduced!)
COMP559/326 – Congestion Games Selfish Routing · 3.9
Wardrop Model Optimal Flows & Wardrop Equilibria
Marginal Cost
I Suppose we are shifting flow from path P1 to P2.
I ⇒ Contribution of edges on P1 to total latency decreases,
contribution of P2 increases.
I If decrease on P1 is more than the increase on P2 then total
latency decreases.
I ⇒ the flow was not optimal.
Definition: Marginal Cost
c∗e(x) = (x · ce(x))′ = ce(x) + x · c′e(x) c∗P(x) =
∑
e∈P
c∗e(x)
Observation
In an optimal flow, for each commodity i ∈ [k ], the marginal cost of all
used paths is the same.
COMP559/326 – Congestion Games Selfish Routing · 3.10
Wardrop Model Optimal Flows & Wardrop Equilibria
Marginal Cost
I Suppose we are shifting flow from path P1 to P2.
I ⇒ Contribution of edges on P1 to total latency decreases,
contribution of P2 increases.
I If decrease on P1 is more than the increase on P2 then total
latency decreases.
I ⇒ the flow was not optimal.
Definition: Marginal Cost
c∗e(x) = (x · ce(x))′ = ce(x) + x · c′e(x) c∗P(x) =
∑
e∈P
c∗e(x)
Observation
In an optimal flow, for each commodity i ∈ [k ], the marginal cost of all
used paths is the same.
COMP559/326 – Congestion Games Selfish Routing · 3.10
Wardrop Model Optimal Flows & Wardrop Equilibria
Marginal Cost
I Suppose we are shifting flow from path P1 to P2.
I ⇒ Contribution of edges on P1 to total latency decreases,
contribution of P2 increases.
I If decrease on P1 is more than the increase on P2 then total
latency decreases.
I ⇒ the flow was not optimal.
Definition: Marginal Cost
c∗e(x) = (x · ce(x))′ = ce(x) + x · c′e(x) c∗P(x) =
∑
e∈P
c∗e(x)
Observation
In an optimal flow, for each commodity i ∈ [k ], the marginal cost of all
used paths is the same.
COMP559/326 – Congestion Games Selfish Routing · 3.10
Wardrop Model Optimal Flows & Wardrop Equilibria
Optimum via marginal costs
Assume x · ce(x) is convex and continuously differentiable for all e ∈ E .
Lemma 3.1 (Characterisation of optimal flows) Prop.18.9
A feasible flow f is optimal if and only if for all commodities i ∈ [k ], and
paths P1,P2 ∈ Pi with fP1 > 0, we have c∗P1(f ) ≤ c∗P2(f ).
Observe the similarity in the characterisation of optimal flows and
Wardrop equilibria.
Theorem 3.2 (Wardrop equilibrium vs. Optimum). Cor.18.10
A feasible flow f is optimal for (G, r , c) if and only if f is a Wardrop
equilibrium for (G, r , c∗).
COMP559/326 – Congestion Games Selfish Routing · 3.11
Wardrop Model Optimal Flows & Wardrop Equilibria
Optimum via marginal costs
Assume x · ce(x) is convex and continuously differentiable for all e ∈ E .
Lemma 3.1 (Characterisation of optimal flows) Prop.18.9
A feasible flow f is optimal if and only if for all commodities i ∈ [k ], and
paths P1,P2 ∈ Pi with fP1 > 0, we have c∗P1(f ) ≤ c∗P2(f ).
Observe the similarity in the characterisation of optimal flows and
Wardrop equilibria.
Theorem 3.2 (Wardrop equilibrium vs. Optimum). Cor.18.10
A feasible flow f is optimal for (G, r , c) if and only if f is a Wardrop
equilibrium for (G, r , c∗).
COMP559/326 – Congestion Games Selfish Routing · 3.11
Wardrop Model Existence of Wardrop Equilibria
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.12
Wardrop Model Existence of Wardrop Equilibria
Existence of Wardrop Equilibria
Theorem 3.3 (Existence and essential uniqueness) Th.18.8
(a) Every instance (G, r , c) admits a Wardrop equilibrium.
(b) If f and f˜ are Wardrop equilibria, then ce(f ) = ce(f˜ ) for every
e ∈ E .
Proofs are based on the following potential function [ BECKMANN, MCGUIRE,
WINSTON, 1956] :
H(f ) =
∑
e∈E
he(fe)
with he(x) =
∫ x
0
ce(u) du
COMP559/326 – Congestion Games Selfish Routing · 3.13
Wardrop Model Existence of Wardrop Equilibria
Existence of Wardrop Equilibria
Theorem 3.3 (Existence and essential uniqueness) Th.18.8
(a) Every instance (G, r , c) admits a Wardrop equilibrium.
(b) If f and f˜ are Wardrop equilibria, then ce(f ) = ce(f˜ ) for every
e ∈ E .
Proofs are based on the following potential function [ BECKMANN, MCGUIRE,
WINSTON, 1956] :
H(f ) =
∑
e∈E
he(fe)
with he(x) =
∫ x
0
ce(u) du
COMP559/326 – Congestion Games Selfish Routing · 3.13
Wardrop Model Price of Anarchy
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.14
Wardrop Model Price of Anarchy
Price of Anarchy
Let f be a Wardrop equilibrium and f ∗ be an optimum for (G, r , c).
Definition: Price of Anarchy
ρ(G, r , c) =
C(f )
C(f ∗)
Corollary 3.4 (polynomial latency functions) Cor.18.17
Suppose latency functions are of the form ce(x) =
∑d
i=0 ae,i · x i . Then,
ρ(G, r , c) ≤ d + 1.
Theorem 3.5 (linear latency functions)
Suppose latency functions are linear with non-negative slope and
offset. Then, ρ(G, r , c) ≤ 43 .
Theorem 3.4 (Upper bound via potential function) Th.18.16
Suppose for every e ∈ E and all x ≥ 0,
x · ce(x) ≤ α ·
∫ x
0
ce(u) du.
Then, ρ(G, r , c) ≤ α.
COMP559/326 – Congestion Games Selfish Routing · 3.15
Wardrop Model Price of Anarchy
Price of Anarchy
Let f be a Wardrop equilibrium and f ∗ be an optimum for (G, r , c).
Definition: Price of Anarchy
ρ(G, r , c) =
C(f )
C(f ∗)
Corollary 3.4 (polynomial latency functions) Cor.18.17
Suppose latency functions are of the form ce(x) =
∑d
i=0 ae,i · x i . Then,
ρ(G, r , c) ≤ d + 1.
Theorem 3.5 (linear latency functions)
Suppose latency functions are linear with non-negative slope and
offset. Then, ρ(G, r , c) ≤ 43 .
Theorem 3.4 (Upper bound via potential function) Th.18.16
Suppose for every e ∈ E and all x ≥ 0,
x · ce(x) ≤ α ·
∫ x
0
ce(u) du.
Then, ρ(G, r , c) ≤ α.
COMP559/326 – Congestion Games Selfish Routing · 3.15
Wardrop Model Price of Anarchy
Price of Anarchy
Corollary 3.5 (polynomial latency functions) Cor.18.17
Suppose latency functions are of the form ce(x) =
∑d
i=0 ae,i · x i . Then,
ρ(G, r , c) ≤ d + 1.
Theorem 3.6 (linear latency functions)
Suppose latency functions are linear with non-negative slope and
offset. Then, ρ(G, r , c) ≤ 43 .
Theorem 3.7 (bicriteria bound) Th.18.29
If f is a Wardrop equilibrium for (G, r , c) and f ∗ a feasible flow for
(G,2r , c), then C(f ) ≤ C(f ∗).
COMP559/326 – Congestion Games Selfish Routing · 3.16
(Atomic) congestion games
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.17
(Atomic) congestion games Model
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.18
(Atomic) congestion games Model
3b (Weighted) congestion games
Γ =
(
[k ], (wi)i∈[k ],E , (Si)i∈[k ], (ce)e∈E
)
I [k ] . . . set of k players
I wi . . . weight of player i ∈ [k ]
I E . . . set of resources
e.g. edges in a graph
I Si ⊆ 2E . . . set of strategies of player i
e.g. set of paths from oi to di
I ce . . . latency function of resource e
vs.
COMP559/326 – Congestion Games Selfish Routing · 3.19
(Atomic) congestion games Model
3b (Weighted) congestion games
Γ =
(
[k ], (wi)i∈[k ],E , (Si)i∈[k ], (ce)e∈E
)
I [k ] . . . set of k players
I wi . . . weight of player i ∈ [k ]
I E . . . set of resources
e.g. edges in a graph
I Si ⊆ 2E . . . set of strategies of player i
e.g. set of paths from oi to di
I ce . . . latency function of resource e
vs.
COMP559/326 – Congestion Games Selfish Routing · 3.19
(Atomic) congestion games Model
3b (Weighted) congestion games
Γ =
(
[k ], (wi)i∈[k ],E , (Si)i∈[k ], (ce)e∈E
)
I [k ] . . . set of k players
I wi . . . weight of player i ∈ [k ]
I E . . . set of resources
e.g. edges in a graph
I Si ⊆ 2E . . . set of strategies of player i
e.g. set of paths from oi to di
I ce . . . latency function of resource e
vs.
o
o
d
d1
2
2
1
COMP559/326 – Congestion Games Selfish Routing · 3.19
(Atomic) congestion games Model
3b (Weighted) congestion games
Γ =
(
[k ], (wi)i∈[k ],E , (Si)i∈[k ], (ce)e∈E
)
I [k ] . . . set of k players
I wi . . . weight of player i ∈ [k ]
I E . . . set of resources
e.g. edges in a graph
I Si ⊆ 2E . . . set of strategies of player i
e.g. set of paths from oi to di
I ce . . . latency function of resource e
vs.
o
o
d
d1
2
2
1
COMP559/326 – Congestion Games Selfish Routing · 3.19
(Atomic) congestion games Model
Subclasses of (weighted) congestion games
I unweighted congestion games (or simply congestion games):
wi = 1 for all player i ∈ [k ]
I symmetric games:
Si = Sj for all player i , j ∈ [k ]
I network congestion games
5
3
2
5
3
2
s
a
b
c
d
e
I singleton congestion games
s t
COMP559/326 – Congestion Games Selfish Routing · 3.20
(Atomic) congestion games Model
Subclasses of (weighted) congestion games
I unweighted congestion games (or simply congestion games):
wi = 1 for all player i ∈ [k ]
I symmetric games:
Si = Sj for all player i , j ∈ [k ]
I network congestion games
5
3
2
5
3
2
s
a
b
c
d
e
I singleton congestion games
s t
COMP559/326 – Congestion Games Selfish Routing · 3.20
(Atomic) congestion games Model
Subclasses of (weighted) congestion games
I unweighted congestion games (or simply congestion games):
wi = 1 for all player i ∈ [k ]
I symmetric games:
Si = Sj for all player i , j ∈ [k ]
I network congestion games
5
3
2
5
3
2
s
a
b
c
d
e
I singleton congestion games
s t
COMP559/326 – Congestion Games Selfish Routing · 3.20
(Atomic) congestion games Model
Subclasses of (weighted) congestion games
I unweighted congestion games (or simply congestion games):
wi = 1 for all player i ∈ [k ]
I symmetric games:
Si = Sj for all player i , j ∈ [k ]
I network congestion games
5
3
2
5
3
2
s
a
b
c
d
e
I singleton congestion games
s t
COMP559/326 – Congestion Games Selfish Routing · 3.20
(Atomic) congestion games Model
Load and Private Cost
Strategy profile
s = (s1, . . . , sn) ∈ S1× . . .×Sn
Traffic on resource e ∈ E
xe(s) =
∑
i∈[k ]:e∈si
wi
Private cost of player i ∈ [k ]
Ci(s) = wi ·
∑
e∈si
ce(xe(s))
5
3
2
5
3
2
s
a
b
c
d
e
C1(s)=3 · (ca(8) + cd (3))
C2(s)=5 · (ca(8) + cc(5) + ce(7))
C3(s)=2 · (cb(2) + ce(7))
COMP559/326 – Congestion Games Selfish Routing · 3.21
(Atomic) congestion games Model
Nash Equilibrium
Nash Equilibrium
A strategy profile s is a Nash equilibrium if and only if all players i ∈ [k ]
are satisfied, that is,
Ci(s) ≤ Ci(s−i , s′i ) for all i ∈ [k ] and s′i ∈ Si .
COMP559/326 – Congestion Games Selfish Routing · 3.22
(Atomic) congestion games Model
Nash Equilibrium
Nash Equilibrium
A strategy profile s is a Nash equilibrium if and only if all players i ∈ [k ]
are satisfied, that is,
Ci(s) ≤ Ci(s−i , s′i ) for all i ∈ [k ] and s′i ∈ Si .
Remarks
I For simplicity we restrict to pure Nash equilibria.
I Many results hold also for mixed Nash equilibria.
I Players randomize over their pure strategies
I Guaranteed to exist [ NASH, 1951]
COMP559/326 – Congestion Games Selfish Routing · 3.22
(Atomic) congestion games Model
Price of Anarchy
Social Cost
SC(s) =
∑
i∈[k ]
Ci(s)
=
∑
e∈E
xe(s) · ce(xe(s))
I Let G be a class of games.
Price of Anarchy [ KOUTSOUPIAS, PAPADIMITRIOU, STACS’99]
PoA(G) = sup
Γ∈G,
s is NE in Γ
SC(s)
OPT
COMP559/326 – Congestion Games Selfish Routing · 3.23
(Atomic) congestion games Existence of Nash equilibria
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.24
(Atomic) congestion games Existence of Nash equilibria
Existence of pure NE: positive result
Theorem 3.6
Every unweighted congestion game possesses a pure Nash
equilibrium.
Define Φ : (S1 × ...× Sn)→ N by
Φ(s) =
∑
e∈E
xe(s)∑
j=1
ce(j).
Consider two strategy profiles s = (s1, . . . , sk ) and s′ = (s′i , s−i):
Φ(s)− Φ(s′) = ∑
e∈si−s′i
ce(xe(s))−
∑
e∈s′i−si
ce(xe(s′))
= Ci(s)− Ci(s′).
Therefore: Φ(s) minimal⇒ s is Nash equilibrium.
COMP559/326 – Congestion Games Selfish Routing · 3.25
(Atomic) congestion games Existence of Nash equilibria
Existence of pure NE: negative result
[LIBMAN & ORDA 2001, FOTAKIS ET AL. 2004, GOEMANS ET AL. 2005]
Theorem 3.7 Ex.18.7
There is a weighted network congestion game that does not admit a
pure Nash equilibrium.
Consider the following instance:
I 2 players
I w1 = 1
I w2 = 2
models and examples 467
s1
u
w
0
x
x
xx
0
s2
t1
t2 t3 s4
s3v t4
Figure 18.3. The AAE example (Example 18.6). In atomic instances with affine cost functions,
different equilibrium flows can have different costs, and the price of anarchy can be as large
as 5/2.
Example 18.7 (Nonexistence in weighted atomic instances) Consider the net-
work shown in Figure 18.4. Extend this network to an atomic selfish routing game
by adding two players, both with source s and sink t , with traffic amounts r1 = 1
and r2 = 2.
We claim that there is no equilibrium flow in this atomic instance. To prove
this, let P1, P2, P3, and P4 denote the paths s → t , s → v→ t , s → w→ t ,
and s → v→ w→ t , respectively. The following four statements then imply the
claim.
(1) If player 2 takes path P1 or P2, then the unique response by player 1 that minimizes
its cost is the path P4.
(2) If player 2 takes path P3 or P4, then the unique best response by player 1 is the
path P1.
(3) If player 1 takes the path P4, then the unique best response by player 2 is the
path P3.
(4) If player 1 takes the path P1, then the unique best response by player 2 is the
path P2.
We leave verification of (1)–(4) to the reader.
On the other hand, Section 18.3.2 proves that every atomic instance in which all
players route the same amount of traffic admits at least one equilibrium flow. We call
s t
w
v
47x
x2 + 443x2
6x2x + 33 13x
Figure 18.4. An atomic instance with no equilibrium flow (Example 18.7).COMP559/326 – Congestion Games Selfish Routing · 3.26
(Atomic) congestion games Existence of Nash equilibria
Existence of pure NE in weighted games
Theorem 3.8 [ FOTAKIS, KONTOGIANNIS, SPIRAKIS, 2004]
Every weighted congestion game with linear latency functions
possesses a pure Nash equilibrium.
Proof is based on the following potential function:
Φ˜(s) =
∑
i∈[k ]
wi ·
∑
e∈si
(ce(xe(s)) + ce(wi))
=
∑
e∈E
xe(s) · ce(xe(s)) +
∑
i∈[k ]
wi ·
∑
e∈si
ce(wi).
If s = (s1, . . . , sk ) and s′ = (s′j , s−j) for some j ∈ [k ] and s′j ∈ Sj , then
Φ˜(s)− Φ˜(s′) = 2 · (Cj(s)− Cj(s′)).
COMP559/326 – Congestion Games Selfish Routing · 3.27
(Atomic) congestion games Price of Anarchy
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.28
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Example
Network with 2 (unweighted) players
Symmetric
OPT
SC = 14 + 10 = 24
Price of Anarchy = 28/24 = 7/6
If multiple equilibria, look at worst one
COMP559/326 – Congestion Games Selfish Routing · 3.29
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Example
Nash Equilibrium
SC = 14 + 14 = 28
OPT
SC = 14 + 10 = 24
Price of Anarchy = 28/24 = 7/6
If multiple equilibria, look at worst one
COMP559/326 – Congestion Games Selfish Routing · 3.29
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Example
Nash Equilibrium
SC = 14 + 14 = 28
OPT
SC = 14 + 10 = 24
Price of Anarchy = 28/24 = 7/6
If multiple equilibria, look at worst one
COMP559/326 – Congestion Games Selfish Routing · 3.29
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Example
Nash Equilibrium
SC = 14 + 14 = 28
OPT
SC = 14 + 10 = 24
Price of Anarchy = 28/24 = 7/6
If multiple equilibria, look at worst one
COMP559/326 – Congestion Games Selfish Routing · 3.29
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Routing Games
(1) Analytical simple classes of cost functions
⇒ exact formula for PoA.
I linear [ CHRISTODOULOU, KOUTSOUPIAS, STOC’05]
[ AWERBUCH, AZAR, EPSTEIN, STOC’05]
I bounded degree polynomials [ ALAND ET AL., STACS’06]
(2) For every set of allowable cost functions
⇒ recipe for computing PoA.
I non-atomic (Wardrop model) [ ROUGHGARDEN, TARDOS, JACM’00]
I unweighted [ ROUGHGARDEN, STOC’09]
COMP559/326 – Congestion Games Selfish Routing · 3.30
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Routing Games
(1) Analytical simple classes of cost functions
⇒ exact formula for PoA.
I linear [ CHRISTODOULOU, KOUTSOUPIAS, STOC’05]
[ AWERBUCH, AZAR, EPSTEIN, STOC’05]
I bounded degree polynomials [ ALAND ET AL., STACS’06]
(2) For every set of allowable cost functions
⇒ recipe for computing PoA.
I non-atomic (Wardrop model) [ ROUGHGARDEN, TARDOS, JACM’00]
I unweighted [ ROUGHGARDEN, STOC’09]
COMP559/326 – Congestion Games Selfish Routing · 3.30
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Routing Games
(1) Analytical simple classes of cost functions
⇒ exact formula for PoA.
I linear [ CHRISTODOULOU, KOUTSOUPIAS, STOC’05]
[ AWERBUCH, AZAR, EPSTEIN, STOC’05]
I bounded degree polynomials [ ALAND ET AL., STACS’06]
(2) For every set of allowable cost functions
⇒ recipe for computing PoA.
I non-atomic (Wardrop model) [ ROUGHGARDEN, TARDOS, JACM’00]
I unweighted [ ROUGHGARDEN, STOC’09]
COMP559/326 – Congestion Games Selfish Routing · 3.30
(Atomic) congestion games Price of Anarchy
Price of Anarchy: Routing Games
(1) Analytical simple classes of cost functions
⇒ exact formula for PoA.
I linear [ CHRISTODOULOU, KOUTSOUPIAS, STOC’05]
[ AWERBUCH, AZAR, EPSTEIN, STOC’05]
I bounded degree polynomials [ ALAND ET AL., STACS’06]
(2) For every set of allowable cost functions
⇒ recipe for computing PoA.
I non-atomic (Wardrop model) [ ROUGHGARDEN, TARDOS, JACM’00]
I unweighted [ ROUGHGARDEN, STOC’09]
COMP559/326 – Congestion Games Selfish Routing · 3.30
(Atomic) congestion games Price of Anarchy
Abstract Setup
I n players, each picks a strategy si
I player i incurs cost Ci(s)
I Important Assumption:
objective function is SC(s) =
∑
i Ci(s)
Definition: [ ROUGHGARDEN, STOC’09]
A game is (λ, µ)− smooth if for every pair s, s∗ of outcomes:∑
i
Ci(s−i , s∗i ) ≤ λ · SC(s∗) + µ · SC(s).
(λ > 0, µ < 1)
COMP559/326 – Congestion Games Selfish Routing · 3.31
(Atomic) congestion games Price of Anarchy
Abstract Setup
I n players, each picks a strategy si
I player i incurs cost Ci(s)
I Important Assumption:
objective function is SC(s) =
∑
i Ci(s)
Definition: [ ROUGHGARDEN, STOC’09]
A game is (λ, µ)− smooth if for every pair s, s∗ of outcomes:∑
i
Ci(s−i , s∗i ) ≤ λ · SC(s∗) + µ · SC(s).
(λ > 0, µ < 1)
COMP559/326 – Congestion Games Selfish Routing · 3.31
(Atomic) congestion games Price of Anarchy
Smoothness =⇒ PoA bound
Definition: [ ROUGHGARDEN, STOC’09]
A game is (λ, µ)− smooth if for every pair s, s∗ of outcomes:∑
i
Ci(s−i , s∗i ) ≤ λ · SC(s∗) + µ · SC(s).
(λ > 0, µ < 1)
Theorem 3.9
If a game G is (λ, µ)− smooth, then
PoA(G) ≤ λ
1− µ.
COMP559/326 – Congestion Games Selfish Routing · 3.32
(Atomic) congestion games Price of Stability
Topic 3: Selfish routing / congestion games
Non-atomic congestion games: Wardrop Model
Model
Optimal Flows & Wardrop Equilibria
Existence of Wardrop Equilibria
Price of Anarchy
(Atomic) congestion games
Model
Existence of Nash equilibria
Price of Anarchy
Price of Stability
COMP559/326 – Congestion Games Selfish Routing · 3.33
(Atomic) congestion games Price of Stability
Potential Games and Price of Stability
Potential Games:
I All games that admit a potential function Φ, s.t. for all outcomes s,
all player i , and all alternative strategies s′i ,
Ci(s′i , s−i)− Ci(s) = Φ(s′i , s−i)− Φ(s).
I Every congestion game is a potential game. (cf. Thm. 3.8)
I For every potential game there exists a congestion game having
the same potential function. [ MONDERER, SHAPLEY, 1996]
Definition: Price of Stability
For a game G:
PoS(G) = min
s is NE
SC(s)
OPT
For a class of games G:
PoS(G) = sup
G∈G
PoS(G)
COMP559/326 – Congestion Games Selfish Routing · 3.34
(Atomic) congestion games Price of Stability
Potential Games and Price of Stability
Potential Games:
I All games that admit a potential function Φ, s.t. for all outcomes s,
all player i , and all alternative strategies s′i ,
Ci(s′i , s−i)− Ci(s) = Φ(s′i , s−i)− Φ(s).
I Every congestion game is a potential game. (cf. Thm. 3.8)
I For every potential game there exists a congestion game having
the same potential function. [ MONDERER, SHAPLEY, 1996]
Definition: Price of Stability
For a game G:
PoS(G) = min
s is NE
SC(s)
OPT
For a class of games G:
PoS(G) = sup
G∈G
PoS(G)
COMP559/326 – Congestion Games Selfish Routing · 3.34
(Atomic) congestion games Price of Stability
Potential Games and Price of Stability
Potential Games:
I All games that admit a potential function Φ, s.t. for all outcomes s,
all player i , and all alternative strategies s′i ,
Ci(s′i , s−i)− Ci(s) = Φ(s′i , s−i)− Φ(s).
I Every congestion game is a potential game. (cf. Thm. 3.8)
I For every potential game there exists a congestion game having
the same potential function. [ MONDERER, SHAPLEY, 1996]
Definition: Price of Stability
For a game G:
PoS(G) = min
s is NE
SC(s)
OPT
For a class of games G:
PoS(G) = sup
G∈G
PoS(G)
COMP559/326 – Congestion Games Selfish Routing · 3.34
(Atomic) congestion games Price of Stability
Potential Games and Price of Stability
Theorem 3.10 (Thm.19.13)
Suppose that we have a potential game with potential function Φ, and
assume that for any outcome s, we have
SC(s)
A
≤ Φ(s) ≤ B · SC(s)
for some constants A,B ≥ 0. Then the price of stability is at most A · B.
COMP559/326 – Congestion Games Selfish Routing · 3.35

欢迎咨询51作业君