微信客服：xiaoxionga100
微信客服：ITCS521
程序代写案例-ECON30010
时间：2021-05-13
Topic 5: Congestion Games (#T5LL)
ECON30010 Microeconomics
ECON30010 Topic 5: Congestion Games (#T5LL) 1 / 30
Today’s plan
I Many of the games we’ve looked at so far have been either very simple or somewhat
lame:
I We have had to cover a lot of material, and complicated games would be a distraction.
I In this topics, the goal is to take a familiar situation and model it properly: identify the
key issue, make assumptions that simplify the model as much as possible, yet allow us to
address the key issue.
I East-West link and congestion
I (Two versions of) a game with infinitely many players
I Yet the solutions are simple and intuitive:
I In the first version, we use Nash equilibrium, but we could have guessed the outcome without
knowing the definition;
I In the second version, players have a dominant strategy.
I Despite its simplicity, the games has important implications.
I Externalities and government intervention
ECON30010 Topic 5: Congestion Games (#T5LL) 2 / 30
East-West link, 1
Coalition:
I Congestion is a social waste that needs to be reduced.
Labor
I Too costly: return on building the link is much less than a dollar per dollar invested.
I We will not be interested in cost: cost = 0
I “You do not fix North-South problem with East-West solution.”
I Most people coming from M3 want to terminate in the city, rather than go to M2.
ECON30010 Topic 5: Congestion Games (#T5LL) 3 / 30
East-West link, 2
I We will look at the game where
I All people travel from “West” to “East”;
I Road is build from “North” to “South”
I at no cost
I being used a lot;
I Yet congestion increases
I That is, the road should not be built, and it should be demolished if it already exists;
I The result of this game, and related results, are known as Braess’s paradox;
I It may or may not apply to East-West link specifically;
I However, this serves as a warning that when players interact, even an “obvious” solution
– build the road if the cost is zero – can be wrong because it changes how agents are
using the resource (roads).
ECON30010 Topic 5: Congestion Games (#T5LL) 4 / 30
Congestion game 1: Simplifying the problem
Setting: people driving to work from Blackburn
to North Melbourne (for simplicity, we will
assume that all people live in Blackburn and
drive to North Melbourne)
They need to decide whether to drive local
roads then M1 or to M3 and then local roads.
All other drivers are making these decisions as
well.
ECON30010 Topic 5: Congestion Games (#T5LL) 5 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Poll
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
Question: Suppose everyone is driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take those who drive along hl to get
from A to B, in min?
A 11 B 21 C 18 D 14 E I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 7 / 30
Congestion game 1: Poll
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
Question: Suppose everyone is driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take those who drive along hl to get
from A to B, in min?
A 11 B 21 C 18 D 14 E I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 7 / 30
Congestion game 1: Poll
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
Question: Suppose everyone is driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take those who drive along hl to get
from A to B, in min?
A 11 B 21 C 18 D 14 E I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 7 / 30
Congestion game 1: Solution, 1
We will assume that utility of players is just the negative of how many minutes they travel.
Therefore, the payoffs of the players are (y = x because a driver who started on L must continue on H):
ui (LH,
strategies of other players︷ ︸︸ ︷
(xLH, (1− x)hl) ) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
y = x
ECON30010 Topic 5: Congestion Games (#T5LL) 8 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Equilibrium or not, Poll
Suppose that 30% drive along LH.
Question: This is (check all that applies)
A This is not an equilibrium because drivers on LH want to switch to hl
B This is not an equilibrium because drivers on hl want to switch to LH
C It is another equilibrium
D I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 10 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Solution, 2
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
That is, we can solve this game by eliminating dominated strategies. The solution is hsH.
That is, every driver is using hsH.
Total travel time: 10 min + 59 sec + 10 min = 20 min 59 sec. Compare it to 16 min!
ECON30010 Topic 5: Congestion Games (#T5LL) 12 / 30
Congestion game 2: Solution, 2
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
That is, we can solve this game by eliminating dominated strategies. The solution is hsH.
That is, every driver is using hsH.
Total travel time: 10 min + 59 sec + 10 min = 20 min 59 sec. Compare it to 16 min!
ECON30010 Topic 5: Congestion Games (#T5LL) 12 / 30
Notes
I No one wants to switch to an old strategy, LH or hl , because it would now require travel
time of 21 min.
I I am looking for a pure strategy Nash equilibrium
I Indeed, I say that a driver uses either LH or hl (with certainty)
I If I were looking for mixed strategies, then I would say “a driver uses LH with probability α
and uses hl with probability (1− α)
I However, it is easy to find (many) mixed strategies where drivers do properly randomise
between two strategies.
I For example, they can play LH with probability α and hl with probability (1− α)
I In the continuum model, it would still result in exactly α drivers on LH and exactly (1− α)
drivers on hl .
ECON30010 Topic 5: Congestion Games (#T5LL) 12 / 30
Congestion games: Real life
Is it just an oddity of our model?
Some of the examples:
I Cheonggyecheon restoration project
I Closure of 42nd St. in New York during Earth Hour.
I The Big Dig in Boston
I The closure of Broadway around Times Square
ECON30010 Topic 5: Congestion Games (#T5LL) 13 / 30
The Big Dig
I Largest US road project; a 5.6 km tunnel in downtown Boston
I From 1991 to 2007
I at the cost of about US$22 bn
ECON30010 Topic 5: Congestion Games (#T5LL) 14 / 30
Closure of Broadway to traffic
I Five blocks of Broadway are closed to traffic and redeveloped as pedestrian mall;
I Explicit main goal: reduce congestion
I Mixed results: some streets improved, some streets worsened
I But wider benefits seem to be unequivocal
ECON30010 Topic 5: Congestion Games (#T5LL) 15 / 30
Government intervention
Congestion game: Government intervention, Intro 1
I When a driver switches to hsH, she only considers her benefit. She does not take into
account that his decision makes everyone else’s drive longer.
I The decision of a driver imposes an “externality” on other drivers.
I If there are externalities, a government intervention may help.
ECON30010 Topic 5: Congestion Games (#T5LL) 16 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Gov’t intervention, Example, equilibrium
I Suppose gov’t sets τ = 3.
I Then 60% of drivers travel on hsH, 20% on LH and 20% on hl . (We do not know yet
where those numbers came from; we would learn it a little later. We can still check if it is
an equilibrium.)
I For each of them, travel time is 8 + 3 + 8 = 11 + 8 = 8 + 11
I travel time is the same, hence no driver wants to deviate.
A B
L
11 min
0.2
h
10 · 0.8 min
0.8
H
10 · 0.8 min
0.8
l
11 min
0.2
C
D
59 secs
0.6
ECON30010 Topic 5: Congestion Games (#T5LL) 18 / 30
Government intervention
Congestion game: Gov’t intervention, Example, equilibrium
I Suppose gov’t sets τ = 3.
I Then 60% of drivers travel on hsH, 20% on LH and 20% on hl . (We do not know yet
where those numbers came from; we would learn it a little later. We can still check if it is
an equilibrium.)
I For each of them, travel time is 8 + 3 + 8 = 11 + 8 = 8 + 11
I travel time is the same, hence no driver wants to deviate.
A B
L
11 min
0.2
h
10 · 0.8 min
0.8
H
10 · 0.8 min
0.8
l
11 min
0.2
C
D
59 secs
0.6
ECON30010 Topic 5: Congestion Games (#T5LL) 18 / 30
Government intervention
Congestion game: Gov’t intervention, Example, analysis
Gov’t is able to ease the congestion: total travel is
I 19 min in equilibrium with tax τ = 3
I instead of 20 min 59 sec with no tax.
To put it differently, drivers are better off paying a congestion tax, even if tax money are
simply discarded!
ECON30010 Topic 5: Congestion Games (#T5LL) 19 / 30
Government intervention
Congestion game: Gov’t intervention, Gov’t problem
I assume that gov’t is only interested in minimising travel time, and not interested in the
collected revenue (it “disappears”).
Objective function of the gov’t (I’ve added minus sign, so that it becomes a utility that the
gov’t wants to maximise):
uG = −TTT (Total Travel Time)
What the gov’t can decide? (Remember my insistence on writing decision variables)
I Tax τ , but not x and y .
Gov’t problem:
maxτuG
ECON30010 Topic 5: Congestion Games (#T5LL) 20 / 30
Government intervention
Congestion game: Gov’t intervention, Gov’t problem
I assume that gov’t is only interested in minimising travel time, and not interested in the
collected revenue (it “disappears”).
Objective function of the gov’t (I’ve added minus sign, so that it becomes a utility that the
gov’t wants to maximise):
uG = −TTT (Total Travel Time)
What the gov’t can decide? (Remember my insistence on writing decision variables)
I Tax τ , but not x and y .
Gov’t problem:
maxτuG
ECON30010 Topic 5: Congestion Games (#T5LL) 20 / 30
Government intervention
Congestion game: Gov’t intervention, Total travel time 1
Calculating travel time of players by looking at each road individually:
I Road h traveled by (1− x) players
I each spends 10(1− x) min on travel
I all players traveling on h spend in total (10(1− x))(1− x)) min while traveling on h
Similarly,
I x travel on L and together spend 11x minutes.
I y travel on H and together spend (10y)y
I (1− y) travel on l and together spend 11(1− y).
I How many drive on s?
I x drivers arrive to C from L road.
I y drivers leave C through H road.
I Hence, y − x (> 0 – assumption!) arrive to C through s road. Those on s road spend τ
each, making it (y − x)τ total.
ECON30010 Topic 5: Congestion Games (#T5LL) 21 / 30
Government intervention
Congestion game: Gov’t intervention, Total travel time 2
From the last slide:
I (1− x) travel on h and together spend 10(1− x)2;
I x travel on L and together spend 11x ;
I y travel on H and together spend 10y2;
I (1− y) travel on l and together spend 11(1− y);
I (y − x) travel on s and together spend (y − x)τ .
Hence,
(Total travel time)TTT = 10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ
Coming up next: what are x and y?
ECON30010 Topic 5: Congestion Games (#T5LL) 22 / 30
Government intervention
Congestion game: Gov’t intervention, Total travel time 2
From the last slide:
I (1− x) travel on h and together spend 10(1− x)2;
I x travel on L and together spend 11x ;
I y travel on H and together spend 10y2;
I (1− y) travel on l and together spend 11(1− y);
I (y − x) travel on s and together spend (y − x)τ .
Hence,
(Total travel time)TTT = 10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ
Coming up next: what are x and y?
ECON30010 Topic 5: Congestion Games (#T5LL) 22 / 30
Government intervention
Gov’t intervention, Drivers’ decisions
Conjecture: drivers will use LH, hl and hsH (Conjecture that all “reasonable” roads are used is a good
starting point; we will need to check if conjecture holds.).
Let (x , y) be equilibrium fractions of drivers, as described on the previous slide. Then utilities
must be the same:
(1) (2) (3)
ui (LH, (x , y))
=
−11−10y
= ui (hl , (x , y))
=
−10(1−x)−11
= ui (hsH, (x , y))
=
−10(1−x)−τ−10y
Then,
I from (1) = (3): −11− 10y = −10(1− x)− τ − 10y ⇒
−11 + τ = 10(x − 1)⇒ x = 0.1(τ − 1)
I from (2) = (3) we get −11 = −τ − 10y ⇒ y = 0.1(11− τ)
Note that this solution is correct when 1 ≥ y ≥ x ≥ 0⇒ τ ≥ 1 and τ ≤ 6. If those conditions
are not satisfied, our conjecture on the top of the slide is wrong. We will not consider this case
in the interest of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 23 / 30
Government intervention
Gov’t intervention, Drivers’ decisions
Conjecture: drivers will use LH, hl and hsH (Conjecture that all “reasonable” roads are used is a good
starting point; we will need to check if conjecture holds.).
Let (x , y) be equilibrium fractions of drivers, as described on the previous slide. Then utilities
must be the same:
(1) (2) (3)
ui (LH, (x , y))
=
−11−10y
= ui (hl , (x , y))
=
−10(1−x)−11
= ui (hsH, (x , y))
=
−10(1−x)−τ−10y
Then,
I from (1) = (3): −11− 10y = −10(1− x)− τ − 10y ⇒
−11 + τ = 10(x − 1)⇒ x = 0.1(τ − 1)
I from (2) = (3) we get −11 = −τ − 10y ⇒ y = 0.1(11− τ)
Note that this solution is correct when 1 ≥ y ≥ x ≥ 0⇒ τ ≥ 1 and τ ≤ 6. If those conditions
are not satisfied, our conjecture on the top of the slide is wrong. We will not consider this case
in the interest of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 23 / 30
Government intervention
Gov’t intervention, Drivers’ decisions
Conjecture: drivers will use LH, hl and hsH (Conjecture that all “reasonable” roads are used is a good
starting point; we will need to check if conjecture holds.).
Let (x , y) be equilibrium fractions of drivers, as described on the previous slide. Then utilities
must be the same:
(1) (2) (3)
ui (LH, (x , y))
=
−11−10y
= ui (hl , (x , y))
=
−10(1−x)−11
= ui (hsH, (x , y))
=
−10(1−x)−τ−10y
Then,
I from (1) = (3): −11− 10y = −10(1− x)− τ − 10y ⇒
−11 + τ = 10(x − 1)⇒ x = 0.1(τ − 1)
I from (2) = (3) we get −11 = −τ − 10y ⇒ y = 0.1(11− τ)
Note that this solution is correct when 1 ≥ y ≥ x ≥ 0⇒ τ ≥ 1 and τ ≤ 6. If those conditions
are not satisfied, our conjecture on the top of the slide is wrong. We will not consider this case
in the interest of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 23 / 30
Government intervention
Congestion game: Government intervention, Math
Objective function of the gov’t, accounting for drivers’ decisions:
uG = −(10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ)
Note that 1− x = y (see Slide 23, small font equations)
= −(10y2 + 11(1− y) + 10y2 + 11(1− y) + (y − (1− y))τ)
= −20y2 − 22(1− y) + (1− 2y)τ
= −20y2 + 22y + τ − 2yτ − 22.
Recall that y = 0.1(11− τ), hence ∂∂τ y = −0.1. Thus
∂
∂τ
uG = −40× y(−0.1) + 22(−0.1) + 1− 2y − 2τ(−0.1)
= 4y − 2.2 + 1− 2y + 0.2τ = 2y − 1.2 + 0.2τ
= 2× 0.1(11− τ)− 1.2 + 0.2τ
= 1
ECON30010 Topic 5: Congestion Games (#T5LL) 24 / 30
Government intervention
Congestion game: Government intervention, Math
Objective function of the gov’t, accounting for drivers’ decisions:
uG = −(10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ)
Note that 1− x = y (see Slide 23, small font equations)
= −(10y2 + 11(1− y) + 10y2 + 11(1− y) + (y − (1− y))τ)
= −20y2 − 22(1− y) + (1− 2y)τ
= −20y2 + 22y + τ − 2yτ − 22.
Recall that y = 0.1(11− τ), hence ∂∂τ y = −0.1. Thus
∂
∂τ
uG = −40× y(−0.1) + 22(−0.1) + 1− 2y − 2τ(−0.1)
= 4y − 2.2 + 1− 2y + 0.2τ = 2y − 1.2 + 0.2τ
= 2× 0.1(11− τ)− 1.2 + 0.2τ
= 1
ECON30010 Topic 5: Congestion Games (#T5LL) 24 / 30
Government intervention
Congestion game: Government intervention, Math
Objective function of the gov’t, accounting for drivers’ decisions:
uG = −(10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ)
Note that 1− x = y (see Slide 23, small font equations)
= −(10y2 + 11(1− y) + 10y2 + 11(1− y) + (y − (1− y))τ)
= −20y2 − 22(1− y) + (1− 2y)τ
= −20y2 + 22y + τ − 2yτ − 22.
Recall that y = 0.1(11− τ), hence ∂∂τ y = −0.1. Thus
∂
∂τ
uG = −40× y(−0.1) + 22(−0.1) + 1− 2y − 2τ(−0.1)
= 4y − 2.2 + 1− 2y + 0.2τ = 2y − 1.2 + 0.2τ
= 2× 0.1(11− τ)− 1.2 + 0.2τ
= 1
ECON30010 Topic 5: Congestion Games (#T5LL) 24 / 30
Government intervention
Congestion game: Government intervention, Solution
∂
∂τ
uG = 1
What does that mean? uG increases with τ , as long as our solution is valid. Our solution is
valid until τ = 6 (see Slide 23). At τ = 6, no one wants to use s (y = 0.5 and x = 0.5, hence
y − x = 0).
It is optimal to set τ so that no one drives on s!
Extensions
I Maybe it is not all gloom and doom: an emergency vehicle (which does not pay tax) can
get from A to B in 5 min + 59 sec + 5 min = much faster
I Emergency vehicles aside, it suggests that a richer model may have somewhat different
conclusions
I For example, if there are people with very high and very low value of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 25 / 30
Government intervention
Congestion game: Government intervention, Solution
∂
∂τ
uG = 1
What does that mean? uG increases with τ , as long as our solution is valid. Our solution is
valid until τ = 6 (see Slide 23). At τ = 6, no one wants to use s (y = 0.5 and x = 0.5, hence
y − x = 0).
It is optimal to set τ so that no one drives on s!
Extensions
I Maybe it is not all gloom and doom: an emergency vehicle (which does not pay tax) can
get from A to B in 5 min + 59 sec + 5 min = much faster
I Emergency vehicles aside, it suggests that a richer model may have somewhat different
conclusions
I For example, if there are people with very high and very low value of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 25 / 30
Data on the road usage charges
Congestion charges: Sources and Data
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton.
I Melbourne Road Use Study by Transurban
I Installed GPS on cars to collect data
I Late 2015 - early 2016; 8-10 month for each participant
I Three months of baseline
I Three months of “non-targeted” congestion charge scheme (roughly corresponds to taxes on
gasoline)
I 10 cents per km
I $1 per trip
I No charge for X km, then 20 cents per km
I Two months of “targeted” congestion charge scheme
I 15 cents per km Mon-Fri 7am – 9am and 3pm – 6pm; 8 cents per km any other time (per km
charges)
I $8 to enter inner city and 8 cent per km (cordon charges)
I 900 participants in the treatment group, 300 participants in the contol group
I 1.2 million trips
ECON30010 Topic 5: Congestion Games (#T5LL) 26 / 30
Data on the road usage charges
Congestion charges: Sources and Data
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton.
I Melbourne Road Use Study by Transurban
I Installed GPS on cars to collect data
I Late 2015 - early 2016; 8-10 month for each participant
I Three months of baseline
I Three months of “non-targeted” congestion charge scheme (roughly corresponds to taxes on
gasoline)
I 10 cents per km
I $1 per trip
I No charge for X km, then 20 cents per km
I Two months of “targeted” congestion charge scheme
I 15 cents per km Mon-Fri 7am – 9am and 3pm – 6pm; 8 cents per km any other time (per km
charges)
I $8 to enter inner city and 8 cent per km (cordon charges)
I 900 participants in the treatment group, 300 participants in the contol group
I 1.2 million trips
ECON30010 Topic 5: Congestion Games (#T5LL) 26 / 30
Data on the road usage charges
Congestion charges: Sources and Data
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton.
I Melbourne Road Use Study by Transurban
I Installed GPS on cars to collect data
I Late 2015 - early 2016; 8-10 month for each participant
I Three months of baseline
I Three months of “non-targeted” congestion charge scheme (roughly corresponds to taxes on
gasoline)
I 10 cents per km
I $1 per trip
I No charge for X km, then 20 cents per km
I Two months of “targeted” congestion charge scheme
I 15 cents per km Mon-Fri 7am – 9am and 3pm – 6pm; 8 cents per km any other time (per km
charges)
I $8 to enter inner city and 8 cent per km (cordon charges)
I 900 participants in the treatment group, 300 participants in the contol group
I 1.2 million trips
ECON30010 Topic 5: Congestion Games (#T5LL) 26 / 30
Data on the road usage charges
Congestion charges: Results for non-targeted charges
Non-targeted congestion charge (10 cents per km):
I 2.5 km less per day (about 8% reduction in distance, 6% reduction in time)
I Almost the same number of trips
I Half of the reduction is from linking the destinations
I Same destinations traveled
I but go from one destination to a nearby destination (e.g. combine shopping with school
pickup)
I Almost 3/4 of reduction is in off-peak time, and not related to work commutes
I Avoid highways
ECON30010 Topic 5: Congestion Games (#T5LL) 27 / 30
Data on the road usage charges
Congestion charges: Results for non-targeted charges
Non-targeted congestion charge (10 cents per km):
I 2.5 km less per day (about 8% reduction in distance, 6% reduction in time)
I Almost the same number of trips
I Half of the reduction is from linking the destinations
I Same destinations traveled
I but go from one destination to a nearby destination (e.g. combine shopping with school
pickup)
I Almost 3/4 of reduction is in off-peak time, and not related to work commutes
I Avoid highways
ECON30010 Topic 5: Congestion Games (#T5LL) 27 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Conclusion
Summary and conclusions
I In multi-agent situations, it is possible that agents change their decisions so that what
would-be an improvement ends up harming all agents
I In multi-agent situations, actions of some agents affect other agents and may lead to
externalities which the agent taking an action does not take into account
I Government intervention, such as tax on externality, may help in those situations
I However, such taxes need to be carefully targeted
I Tax on km traveled does not change peak demand (intuitively clear)
I Cordon charge when public transport substitution is not readily available (can only learn from
empirical analysis)
ECON30010 Topic 5: Congestion Games (#T5LL) 29 / 30
References
References
No references available for congestion game.
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton. SSRN
Working Paper, 20 October 2017
ECON30010 Topic 5: Congestion Games (#T5LL) 30 / 30
学霸联盟
ECON30010 Microeconomics
ECON30010 Topic 5: Congestion Games (#T5LL) 1 / 30
Today’s plan
I Many of the games we’ve looked at so far have been either very simple or somewhat
lame:
I We have had to cover a lot of material, and complicated games would be a distraction.
I In this topics, the goal is to take a familiar situation and model it properly: identify the
key issue, make assumptions that simplify the model as much as possible, yet allow us to
address the key issue.
I East-West link and congestion
I (Two versions of) a game with infinitely many players
I Yet the solutions are simple and intuitive:
I In the first version, we use Nash equilibrium, but we could have guessed the outcome without
knowing the definition;
I In the second version, players have a dominant strategy.
I Despite its simplicity, the games has important implications.
I Externalities and government intervention
ECON30010 Topic 5: Congestion Games (#T5LL) 2 / 30
East-West link, 1
Coalition:
I Congestion is a social waste that needs to be reduced.
Labor
I Too costly: return on building the link is much less than a dollar per dollar invested.
I We will not be interested in cost: cost = 0
I “You do not fix North-South problem with East-West solution.”
I Most people coming from M3 want to terminate in the city, rather than go to M2.
ECON30010 Topic 5: Congestion Games (#T5LL) 3 / 30
East-West link, 2
I We will look at the game where
I All people travel from “West” to “East”;
I Road is build from “North” to “South”
I at no cost
I being used a lot;
I Yet congestion increases
I That is, the road should not be built, and it should be demolished if it already exists;
I The result of this game, and related results, are known as Braess’s paradox;
I It may or may not apply to East-West link specifically;
I However, this serves as a warning that when players interact, even an “obvious” solution
– build the road if the cost is zero – can be wrong because it changes how agents are
using the resource (roads).
ECON30010 Topic 5: Congestion Games (#T5LL) 4 / 30
Congestion game 1: Simplifying the problem
Setting: people driving to work from Blackburn
to North Melbourne (for simplicity, we will
assume that all people live in Blackburn and
drive to North Melbourne)
They need to decide whether to drive local
roads then M1 or to M3 and then local roads.
All other drivers are making these decisions as
well.
ECON30010 Topic 5: Congestion Games (#T5LL) 5 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Formal representation
Infinitely many (players) have to get from A to B, using either of two routes: green (LH) or
blue (hl) (strategies).
Driving on a local road, either L or l , takes 11 minutes, independently on how many drivers
take these roads (there are many local roads).
Driving on a highway, H or h, depends on the number of people taking it. Let x be the share
of drivers that use L and y the share of drivers that use H.
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
ECON30010 Topic 5: Congestion Games (#T5LL) 6 / 30
Congestion game 1: Poll
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
Question: Suppose everyone is driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take those who drive along hl to get
from A to B, in min?
A 11 B 21 C 18 D 14 E I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 7 / 30
Congestion game 1: Poll
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
Question: Suppose everyone is driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take those who drive along hl to get
from A to B, in min?
A 11 B 21 C 18 D 14 E I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 7 / 30
Congestion game 1: Poll
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
Question: Suppose everyone is driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take them to drive from A to B, in
min?
A 11 B 21 C 18 D 14 E I am not sure
Question: Suppose 30% are driving along LH. How long would it take those who drive along hl to get
from A to B, in min?
A 11 B 21 C 18 D 14 E I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 7 / 30
Congestion game 1: Solution, 1
We will assume that utility of players is just the negative of how many minutes they travel.
Therefore, the payoffs of the players are (y = x because a driver who started on L must continue on H):
ui (LH,
strategies of other players︷ ︸︸ ︷
(xLH, (1− x)hl) ) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
y = x
ECON30010 Topic 5: Congestion Games (#T5LL) 8 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Congestion game 1: Solution, 2
From the last slide, for any driver i :
ui (LH, (xLH, (1− x)hl)) = −11− 10x
ui (hl , (xLH, (1− x)hl)) = −10(1− x)− 11
If ui (LH, (xLH, (1− x)hl)) > ui (hl , (xLH, (1− x)hl)), then a driver who is driving on hl will
want to deviate: not an equilibrium.
Only if ui (LH, (xLH, (1− x)hl)) = ui (hl , (xLH, (1− x)hl)), then no player wants to deviate.
Equation above implies −11− 10x = −10(1− x)− 11⇒ x = 1/2
⇒ An equilibrium where half players drive LH and half drive hl .
Total travel time: 11 + 10 · 12 = 16
ECON30010 Topic 5: Congestion Games (#T5LL) 9 / 30
Equilibrium or not, Poll
Suppose that 30% drive along LH.
Question: This is (check all that applies)
A This is not an equilibrium because drivers on LH want to switch to hl
B This is not an equilibrium because drivers on hl want to switch to LH
C It is another equilibrium
D I am not sure
ECON30010 Topic 5: Congestion Games (#T5LL) 10 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Formal representation and solution, 1
New road: super-fast road (s) between C and D that takes 59 sec to travel.
A BL
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
Consider someone at D going to B. If she takes sH, it will take her at most 10 min 59 sec. If
she takes l, it will take her 11 min. Thus, she should take sH and no one should take l.
In the formal game-theoretic language:
I The set of strategies is LH, Lsl , hsH, hl .
I Strategy hsH dominates every other strategy:
I LH because H portion is the same, and hs portion is 1 sec faster than L portion even when
x = 0
I hl , for a similar reason
I Lsl because the worst case of hsH = 20 m 59 s > 22 m 59 s = Lsl .
ECON30010 Topic 5: Congestion Games (#T5LL) 11 / 30
Congestion game 2: Solution, 2
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
That is, we can solve this game by eliminating dominated strategies. The solution is hsH.
That is, every driver is using hsH.
Total travel time: 10 min + 59 sec + 10 min = 20 min 59 sec. Compare it to 16 min!
ECON30010 Topic 5: Congestion Games (#T5LL) 12 / 30
Congestion game 2: Solution, 2
A B
L
11 min
x
h
10 · (1− x) min
1− x
H
10 · y min
y
l
11 min
1− y
C
D
59 secs
That is, we can solve this game by eliminating dominated strategies. The solution is hsH.
That is, every driver is using hsH.
Total travel time: 10 min + 59 sec + 10 min = 20 min 59 sec. Compare it to 16 min!
ECON30010 Topic 5: Congestion Games (#T5LL) 12 / 30
Notes
I No one wants to switch to an old strategy, LH or hl , because it would now require travel
time of 21 min.
I I am looking for a pure strategy Nash equilibrium
I Indeed, I say that a driver uses either LH or hl (with certainty)
I If I were looking for mixed strategies, then I would say “a driver uses LH with probability α
and uses hl with probability (1− α)
I However, it is easy to find (many) mixed strategies where drivers do properly randomise
between two strategies.
I For example, they can play LH with probability α and hl with probability (1− α)
I In the continuum model, it would still result in exactly α drivers on LH and exactly (1− α)
drivers on hl .
ECON30010 Topic 5: Congestion Games (#T5LL) 12 / 30
Congestion games: Real life
Is it just an oddity of our model?
Some of the examples:
I Cheonggyecheon restoration project
I Closure of 42nd St. in New York during Earth Hour.
I The Big Dig in Boston
I The closure of Broadway around Times Square
ECON30010 Topic 5: Congestion Games (#T5LL) 13 / 30
The Big Dig
I Largest US road project; a 5.6 km tunnel in downtown Boston
I From 1991 to 2007
I at the cost of about US$22 bn
ECON30010 Topic 5: Congestion Games (#T5LL) 14 / 30
Closure of Broadway to traffic
I Five blocks of Broadway are closed to traffic and redeveloped as pedestrian mall;
I Explicit main goal: reduce congestion
I Mixed results: some streets improved, some streets worsened
I But wider benefits seem to be unequivocal
ECON30010 Topic 5: Congestion Games (#T5LL) 15 / 30
Government intervention
Congestion game: Government intervention, Intro 1
I When a driver switches to hsH, she only considers her benefit. She does not take into
account that his decision makes everyone else’s drive longer.
I The decision of a driver imposes an “externality” on other drivers.
I If there are externalities, a government intervention may help.
ECON30010 Topic 5: Congestion Games (#T5LL) 16 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Government intervention, Intro 2
I Assume that the gov’t cannot order people to use particular roads
(side note: some gov’ts do that: Mexico City, Singapore)
I But the gov’t can impose taxes on drivers
I I assume tax τ is imposed on s road.
I And it is good for the drivers!
Tax is usually imposed in $. So I need to convert $ and min into some “common value”
I Converting min into $: Each drives values 1 min at $x
I Converting $ into min: Each driver $x at 1 min
I I will use τ as a total travel time on s, for mathematical convenience. As travel on s is 59
sec, if τ = 59 sec, then there is no tax; if τ < 59 sec, it is a subsidy.
I A tax τ = 1 min means that the gov’t collects the value of 1 second (1 min - 59 sec) from
people (that is, the gov’t collects dollars in the end, I just measure the collected dollars in
minutes). A tax τ = 3 min means that the gov’t collected 2 min 1 sec worth of money.
ECON30010 Topic 5: Congestion Games (#T5LL) 17 / 30
Government intervention
Congestion game: Gov’t intervention, Example, equilibrium
I Suppose gov’t sets τ = 3.
I Then 60% of drivers travel on hsH, 20% on LH and 20% on hl . (We do not know yet
where those numbers came from; we would learn it a little later. We can still check if it is
an equilibrium.)
I For each of them, travel time is 8 + 3 + 8 = 11 + 8 = 8 + 11
I travel time is the same, hence no driver wants to deviate.
A B
L
11 min
0.2
h
10 · 0.8 min
0.8
H
10 · 0.8 min
0.8
l
11 min
0.2
C
D
59 secs
0.6
ECON30010 Topic 5: Congestion Games (#T5LL) 18 / 30
Government intervention
Congestion game: Gov’t intervention, Example, equilibrium
I Suppose gov’t sets τ = 3.
I Then 60% of drivers travel on hsH, 20% on LH and 20% on hl . (We do not know yet
where those numbers came from; we would learn it a little later. We can still check if it is
an equilibrium.)
I For each of them, travel time is 8 + 3 + 8 = 11 + 8 = 8 + 11
I travel time is the same, hence no driver wants to deviate.
A B
L
11 min
0.2
h
10 · 0.8 min
0.8
H
10 · 0.8 min
0.8
l
11 min
0.2
C
D
59 secs
0.6
ECON30010 Topic 5: Congestion Games (#T5LL) 18 / 30
Government intervention
Congestion game: Gov’t intervention, Example, analysis
Gov’t is able to ease the congestion: total travel is
I 19 min in equilibrium with tax τ = 3
I instead of 20 min 59 sec with no tax.
To put it differently, drivers are better off paying a congestion tax, even if tax money are
simply discarded!
ECON30010 Topic 5: Congestion Games (#T5LL) 19 / 30
Government intervention
Congestion game: Gov’t intervention, Gov’t problem
I assume that gov’t is only interested in minimising travel time, and not interested in the
collected revenue (it “disappears”).
Objective function of the gov’t (I’ve added minus sign, so that it becomes a utility that the
gov’t wants to maximise):
uG = −TTT (Total Travel Time)
What the gov’t can decide? (Remember my insistence on writing decision variables)
I Tax τ , but not x and y .
Gov’t problem:
maxτuG
ECON30010 Topic 5: Congestion Games (#T5LL) 20 / 30
Government intervention
Congestion game: Gov’t intervention, Gov’t problem
I assume that gov’t is only interested in minimising travel time, and not interested in the
collected revenue (it “disappears”).
Objective function of the gov’t (I’ve added minus sign, so that it becomes a utility that the
gov’t wants to maximise):
uG = −TTT (Total Travel Time)
What the gov’t can decide? (Remember my insistence on writing decision variables)
I Tax τ , but not x and y .
Gov’t problem:
maxτuG
ECON30010 Topic 5: Congestion Games (#T5LL) 20 / 30
Government intervention
Congestion game: Gov’t intervention, Total travel time 1
Calculating travel time of players by looking at each road individually:
I Road h traveled by (1− x) players
I each spends 10(1− x) min on travel
I all players traveling on h spend in total (10(1− x))(1− x)) min while traveling on h
Similarly,
I x travel on L and together spend 11x minutes.
I y travel on H and together spend (10y)y
I (1− y) travel on l and together spend 11(1− y).
I How many drive on s?
I x drivers arrive to C from L road.
I y drivers leave C through H road.
I Hence, y − x (> 0 – assumption!) arrive to C through s road. Those on s road spend τ
each, making it (y − x)τ total.
ECON30010 Topic 5: Congestion Games (#T5LL) 21 / 30
Government intervention
Congestion game: Gov’t intervention, Total travel time 2
From the last slide:
I (1− x) travel on h and together spend 10(1− x)2;
I x travel on L and together spend 11x ;
I y travel on H and together spend 10y2;
I (1− y) travel on l and together spend 11(1− y);
I (y − x) travel on s and together spend (y − x)τ .
Hence,
(Total travel time)TTT = 10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ
Coming up next: what are x and y?
ECON30010 Topic 5: Congestion Games (#T5LL) 22 / 30
Government intervention
Congestion game: Gov’t intervention, Total travel time 2
From the last slide:
I (1− x) travel on h and together spend 10(1− x)2;
I x travel on L and together spend 11x ;
I y travel on H and together spend 10y2;
I (1− y) travel on l and together spend 11(1− y);
I (y − x) travel on s and together spend (y − x)τ .
Hence,
(Total travel time)TTT = 10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ
Coming up next: what are x and y?
ECON30010 Topic 5: Congestion Games (#T5LL) 22 / 30
Government intervention
Gov’t intervention, Drivers’ decisions
Conjecture: drivers will use LH, hl and hsH (Conjecture that all “reasonable” roads are used is a good
starting point; we will need to check if conjecture holds.).
Let (x , y) be equilibrium fractions of drivers, as described on the previous slide. Then utilities
must be the same:
(1) (2) (3)
ui (LH, (x , y))
=
−11−10y
= ui (hl , (x , y))
=
−10(1−x)−11
= ui (hsH, (x , y))
=
−10(1−x)−τ−10y
Then,
I from (1) = (3): −11− 10y = −10(1− x)− τ − 10y ⇒
−11 + τ = 10(x − 1)⇒ x = 0.1(τ − 1)
I from (2) = (3) we get −11 = −τ − 10y ⇒ y = 0.1(11− τ)
Note that this solution is correct when 1 ≥ y ≥ x ≥ 0⇒ τ ≥ 1 and τ ≤ 6. If those conditions
are not satisfied, our conjecture on the top of the slide is wrong. We will not consider this case
in the interest of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 23 / 30
Government intervention
Gov’t intervention, Drivers’ decisions
Conjecture: drivers will use LH, hl and hsH (Conjecture that all “reasonable” roads are used is a good
starting point; we will need to check if conjecture holds.).
Let (x , y) be equilibrium fractions of drivers, as described on the previous slide. Then utilities
must be the same:
(1) (2) (3)
ui (LH, (x , y))
=
−11−10y
= ui (hl , (x , y))
=
−10(1−x)−11
= ui (hsH, (x , y))
=
−10(1−x)−τ−10y
Then,
I from (1) = (3): −11− 10y = −10(1− x)− τ − 10y ⇒
−11 + τ = 10(x − 1)⇒ x = 0.1(τ − 1)
I from (2) = (3) we get −11 = −τ − 10y ⇒ y = 0.1(11− τ)
Note that this solution is correct when 1 ≥ y ≥ x ≥ 0⇒ τ ≥ 1 and τ ≤ 6. If those conditions
are not satisfied, our conjecture on the top of the slide is wrong. We will not consider this case
in the interest of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 23 / 30
Government intervention
Gov’t intervention, Drivers’ decisions
Conjecture: drivers will use LH, hl and hsH (Conjecture that all “reasonable” roads are used is a good
starting point; we will need to check if conjecture holds.).
Let (x , y) be equilibrium fractions of drivers, as described on the previous slide. Then utilities
must be the same:
(1) (2) (3)
ui (LH, (x , y))
=
−11−10y
= ui (hl , (x , y))
=
−10(1−x)−11
= ui (hsH, (x , y))
=
−10(1−x)−τ−10y
Then,
I from (1) = (3): −11− 10y = −10(1− x)− τ − 10y ⇒
−11 + τ = 10(x − 1)⇒ x = 0.1(τ − 1)
I from (2) = (3) we get −11 = −τ − 10y ⇒ y = 0.1(11− τ)
Note that this solution is correct when 1 ≥ y ≥ x ≥ 0⇒ τ ≥ 1 and τ ≤ 6. If those conditions
are not satisfied, our conjecture on the top of the slide is wrong. We will not consider this case
in the interest of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 23 / 30
Government intervention
Congestion game: Government intervention, Math
Objective function of the gov’t, accounting for drivers’ decisions:
uG = −(10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ)
Note that 1− x = y (see Slide 23, small font equations)
= −(10y2 + 11(1− y) + 10y2 + 11(1− y) + (y − (1− y))τ)
= −20y2 − 22(1− y) + (1− 2y)τ
= −20y2 + 22y + τ − 2yτ − 22.
Recall that y = 0.1(11− τ), hence ∂∂τ y = −0.1. Thus
∂
∂τ
uG = −40× y(−0.1) + 22(−0.1) + 1− 2y − 2τ(−0.1)
= 4y − 2.2 + 1− 2y + 0.2τ = 2y − 1.2 + 0.2τ
= 2× 0.1(11− τ)− 1.2 + 0.2τ
= 1
ECON30010 Topic 5: Congestion Games (#T5LL) 24 / 30
Government intervention
Congestion game: Government intervention, Math
Objective function of the gov’t, accounting for drivers’ decisions:
uG = −(10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ)
Note that 1− x = y (see Slide 23, small font equations)
= −(10y2 + 11(1− y) + 10y2 + 11(1− y) + (y − (1− y))τ)
= −20y2 − 22(1− y) + (1− 2y)τ
= −20y2 + 22y + τ − 2yτ − 22.
Recall that y = 0.1(11− τ), hence ∂∂τ y = −0.1. Thus
∂
∂τ
uG = −40× y(−0.1) + 22(−0.1) + 1− 2y − 2τ(−0.1)
= 4y − 2.2 + 1− 2y + 0.2τ = 2y − 1.2 + 0.2τ
= 2× 0.1(11− τ)− 1.2 + 0.2τ
= 1
ECON30010 Topic 5: Congestion Games (#T5LL) 24 / 30
Government intervention
Congestion game: Government intervention, Math
Objective function of the gov’t, accounting for drivers’ decisions:
uG = −(10(1− x)2 + 11x + 10y2 + 11(1− y) + (y − x)τ)
Note that 1− x = y (see Slide 23, small font equations)
= −(10y2 + 11(1− y) + 10y2 + 11(1− y) + (y − (1− y))τ)
= −20y2 − 22(1− y) + (1− 2y)τ
= −20y2 + 22y + τ − 2yτ − 22.
Recall that y = 0.1(11− τ), hence ∂∂τ y = −0.1. Thus
∂
∂τ
uG = −40× y(−0.1) + 22(−0.1) + 1− 2y − 2τ(−0.1)
= 4y − 2.2 + 1− 2y + 0.2τ = 2y − 1.2 + 0.2τ
= 2× 0.1(11− τ)− 1.2 + 0.2τ
= 1
ECON30010 Topic 5: Congestion Games (#T5LL) 24 / 30
Government intervention
Congestion game: Government intervention, Solution
∂
∂τ
uG = 1
What does that mean? uG increases with τ , as long as our solution is valid. Our solution is
valid until τ = 6 (see Slide 23). At τ = 6, no one wants to use s (y = 0.5 and x = 0.5, hence
y − x = 0).
It is optimal to set τ so that no one drives on s!
Extensions
I Maybe it is not all gloom and doom: an emergency vehicle (which does not pay tax) can
get from A to B in 5 min + 59 sec + 5 min = much faster
I Emergency vehicles aside, it suggests that a richer model may have somewhat different
conclusions
I For example, if there are people with very high and very low value of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 25 / 30
Government intervention
Congestion game: Government intervention, Solution
∂
∂τ
uG = 1
What does that mean? uG increases with τ , as long as our solution is valid. Our solution is
valid until τ = 6 (see Slide 23). At τ = 6, no one wants to use s (y = 0.5 and x = 0.5, hence
y − x = 0).
It is optimal to set τ so that no one drives on s!
Extensions
I Maybe it is not all gloom and doom: an emergency vehicle (which does not pay tax) can
get from A to B in 5 min + 59 sec + 5 min = much faster
I Emergency vehicles aside, it suggests that a richer model may have somewhat different
conclusions
I For example, if there are people with very high and very low value of time.
ECON30010 Topic 5: Congestion Games (#T5LL) 25 / 30
Data on the road usage charges
Congestion charges: Sources and Data
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton.
I Melbourne Road Use Study by Transurban
I Installed GPS on cars to collect data
I Late 2015 - early 2016; 8-10 month for each participant
I Three months of baseline
I Three months of “non-targeted” congestion charge scheme (roughly corresponds to taxes on
gasoline)
I 10 cents per km
I $1 per trip
I No charge for X km, then 20 cents per km
I Two months of “targeted” congestion charge scheme
I 15 cents per km Mon-Fri 7am – 9am and 3pm – 6pm; 8 cents per km any other time (per km
charges)
I $8 to enter inner city and 8 cent per km (cordon charges)
I 900 participants in the treatment group, 300 participants in the contol group
I 1.2 million trips
ECON30010 Topic 5: Congestion Games (#T5LL) 26 / 30
Data on the road usage charges
Congestion charges: Sources and Data
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton.
I Melbourne Road Use Study by Transurban
I Installed GPS on cars to collect data
I Late 2015 - early 2016; 8-10 month for each participant
I Three months of baseline
I Three months of “non-targeted” congestion charge scheme (roughly corresponds to taxes on
gasoline)
I 10 cents per km
I $1 per trip
I No charge for X km, then 20 cents per km
I Two months of “targeted” congestion charge scheme
I 15 cents per km Mon-Fri 7am – 9am and 3pm – 6pm; 8 cents per km any other time (per km
charges)
I $8 to enter inner city and 8 cent per km (cordon charges)
I 900 participants in the treatment group, 300 participants in the contol group
I 1.2 million trips
ECON30010 Topic 5: Congestion Games (#T5LL) 26 / 30
Data on the road usage charges
Congestion charges: Sources and Data
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton.
I Melbourne Road Use Study by Transurban
I Installed GPS on cars to collect data
I Late 2015 - early 2016; 8-10 month for each participant
I Three months of baseline
I Three months of “non-targeted” congestion charge scheme (roughly corresponds to taxes on
gasoline)
I 10 cents per km
I $1 per trip
I No charge for X km, then 20 cents per km
I Two months of “targeted” congestion charge scheme
I 15 cents per km Mon-Fri 7am – 9am and 3pm – 6pm; 8 cents per km any other time (per km
charges)
I $8 to enter inner city and 8 cent per km (cordon charges)
I 900 participants in the treatment group, 300 participants in the contol group
I 1.2 million trips
ECON30010 Topic 5: Congestion Games (#T5LL) 26 / 30
Data on the road usage charges
Congestion charges: Results for non-targeted charges
Non-targeted congestion charge (10 cents per km):
I 2.5 km less per day (about 8% reduction in distance, 6% reduction in time)
I Almost the same number of trips
I Half of the reduction is from linking the destinations
I Same destinations traveled
I but go from one destination to a nearby destination (e.g. combine shopping with school
pickup)
I Almost 3/4 of reduction is in off-peak time, and not related to work commutes
I Avoid highways
ECON30010 Topic 5: Congestion Games (#T5LL) 27 / 30
Data on the road usage charges
Congestion charges: Results for non-targeted charges
Non-targeted congestion charge (10 cents per km):
I 2.5 km less per day (about 8% reduction in distance, 6% reduction in time)
I Almost the same number of trips
I Half of the reduction is from linking the destinations
I Same destinations traveled
I but go from one destination to a nearby destination (e.g. combine shopping with school
pickup)
I Almost 3/4 of reduction is in off-peak time, and not related to work commutes
I Avoid highways
ECON30010 Topic 5: Congestion Games (#T5LL) 27 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Data on the road usage charges
Congestion charges: Results for targeted charges
Per km charge:
I Significantly fewer trips
I Small and insignificant effects on km traveled
I Small and insignificant effect on duration
I Significantly fewer peak trips
I Significantly fewer trips in a traffic jam
I Fewer weekday trips, more weekend trips
Cordon charge:
I Significantly fewer trips
I Small but significant effect on km traveled
I Large and significant effect on duration
I 80% of reduction in off-peak travel; small increase in overall peak travel
I Significant reduction in early-afternoon peak travel
I Reduction in travel to inner city
I Significant for those near public transport
I Insignificant for the rest
ECON30010 Topic 5: Congestion Games (#T5LL) 28 / 30
Conclusion
Summary and conclusions
I In multi-agent situations, it is possible that agents change their decisions so that what
would-be an improvement ends up harming all agents
I In multi-agent situations, actions of some agents affect other agents and may lead to
externalities which the agent taking an action does not take into account
I Government intervention, such as tax on externality, may help in those situations
I However, such taxes need to be carefully targeted
I Tax on km traveled does not change peak demand (intuitively clear)
I Cordon charge when public transport substitution is not readily available (can only learn from
empirical analysis)
ECON30010 Topic 5: Congestion Games (#T5LL) 29 / 30
References
References
No references available for congestion game.
“Can Road Charges Alleviate Congestion?” by Leslie Martin and Sam Thornton. SSRN
Working Paper, 20 October 2017
ECON30010 Topic 5: Congestion Games (#T5LL) 30 / 30
学霸联盟
