Selfish Routing
Congestion Games
1
Selfish Routing – Motivation
Many agents want to use
shared resources
Each of them is selfish
and rational
(i.e. maximizes his profit)
Examples: Users of a computer
network, drivers on roads
How they are going to behave?
How much is lost by letting
agents behave selfishly on their
own?
2
Example: Routing in Computer Networks
Imagine a computer network, i.e., computers connected by links.
There are several users, each user wants to route packets from
a source computer zi to a target computer ti. For this, each user i
needs to choose a path in the network from zi to ti.
We assume that the more agents try to route their messages through
the same link, the more the link gets congested and the more costly
the transmission is.
Now assume that the users are selfish and try to minimize their cost
(typically transmission time). How would they behave?
3
Atomic Routing Games
The network routing can be formalized using an atomic routing game
that consists of
a directed multi-graph G = (V, E, δ),
Here V is a set of vertices, E is a set of edges, δ : E → V × V so that if
δ(e) = (u, v) then e leads from u to v. The multigraph G models
the network.
n pairs of source-target vertices (z1, t1), . . . , (zn, tn) where
z1, . . . , zn, t1, . . . , tn ∈ V,
(Each pair (zi, ti) corresponds to a user who wants to route from zi to ti)
for each e ∈ E a cost function ce : N → R such that ce(m) is
the cost of routing through the link e if the amount of traffic
through e is m.
A pure strategy si of player i is a simple path from zi to ti, the payoff is
minus the sum of the costs of the links on the path.
Note that each routing game can be seen as a strategic-form game.
4
Atomic Routing Games
Here we assume at most three users. Each edge is labeled by the cost if one,
two, or all three users route through the edge, respectively.
Here we consider a symmetric case with three users, each has
the source z and target t.
5
Atomic Routing Games
Here, e.g., the red user pays 3 + 2 = 5 :
3 for the first step from z (he shares the edge with the blue one)
2 for the second step to t (he is the only user of the edge)
6
Solving Congestion Games
We consider the following questions:
Are there pure strategy Nash equilibria?
Can the agents "learn" to use the network?
7
Learning: Myopic Best-Response
Given a pure strategy profile s = (s1, . . . , sn), suppose that some
player i has an alternative strategy si
such that ui(si
, s−i) > ui(si, s−i).
Player i can switch (unilaterally) from si to si
improving thus his
payoff. Iterating such improvement steps, we obtain the following:
Myopic best response procedure:
Start with an arbitrary pure strategy profile s = (s1, . . . , sn).
While there exists a player i for whom si is not a best response
to s−i do
si
:= a best-response by player i to s−i
s := (si
, s−i)
return s
By definition, if the myopic best response terminates, the resulting
strategy profile s is a Nash equilibrium.
There is a strategic-form game where it does not terminate.
Theorem 1
For every routing game, the myopic best response terminates in
a Nash equilibrium for an arbitrary starting pure strategy profile.
8
Non-Atomic Selfish Routing
So far we have considered situations where each player
(user, driver) has enough "weight" to explicitly influence
payoffs of others (so a deviation of one player causes
changes in payoffs of other players).
In many applications, especially in the case of highway
traffic problems, individual drivers have negligible influence
on each other. What matters is a "distribution" of drivers on
highways.
To model such situations we use non-atomic routing
games that can be seen as a limiting case of atomic selfish
routing with the number of players going to ∞.
9
Non-Atomic Routing Games
A Non-Atomic Routing Game consists of
a directed multigraph G = (V, E, δ),
n source-target pairs (z1, t1), . . . , (zn, tn),
for each i = 1, . . . , n, the amount of traffic µi ∈ R≥0 from zi
to ti,
for each e ∈ E a cost function ce : R≥0 → R such that
ce(x) is the cost of routing through the link e if the amount
of traffic on e is x ∈ R≥0.
For i = 1, . . . , n, let Pi be the set of all simple paths from zi to ti.
Intuitively, there are uncountably many players, represented by [0, µi], going
from zi to ti, each player chooses his path so that his total cost is minimized.
Assume that Pi ∩ Pj = ∅ for i j.
(This also implies that for all i j we have that either zi zj, or ti tj.)
Denote by P the set of all "relevant" simple paths n
i=1 Pi.
Question: What is a "stable" distribution of the traffic among
paths of P ?
10
Non-Atomic Routing Games
A traffic distribution d is a function d : P → R≥0 such that
p∈Pi
d(p) = µi. Denote by D the set of all traffic distributions.
Let us fix a traffic distribution d ∈ D.
Given an edge e ∈ E, we denote by g(d, e) the amount of congestion
on the edge e :
g(d, e) =
p∈P : e∈p
d(p)
Given p ∈ P, the payoff for players routing through p ∈ P is defined by
u(d, p) = −
e∈p
ce(g(d, e))
Definition 2
A traffic distribution d ∈ D is a Nash equilibrium if for every i = 1, . . . , n
and every path p ∈ Pi such that d(p) > 0 the following holds:
u(d, p) ≥ u(d, p ) for all p ∈ Pi
11
Price of Anarchy
Theorem 3
Every non-atomic routing game has a Nash equilibrium.
We define a social cost of a traffic distribution d by
C(d) =
p∈P
d(p) · (−u(d, p)) =
p∈P
d(p) ·
e∈p
ce(g(d, e))
Theorem 4
All Nash equilibria in non-atomic routing games have the same
social cost.
A price of anarchy is defined by
PoA =
C(d∗)
mind C(d)
where d∗
is a (arbitrary) Nash equilibrium
Intuitively, PoA is the proportion of additional social cost that is
incurred because of agents’ self-interested behavior.
12
Price of Anarchy
Theorem 5 (Roughgarden-Tardos’2000)
For all non-atomic routing games with linear cost functions holds
PoA ≤
4
3
and this bound is tight (e.g. the Pigou’s example).
The price of anarchy can be defined also for atomic routing games:
PoAatom :=
maxs∗ is NE
n
i=1(−ui(s∗
))
mins∈S
n
i=1(−ui(s))
(Intuitively, n
i=1(−ui(s)) is the total amount paid by all players playing
the strategy profile s.)
Theorem 6 (Christodoulou-Koutsoupias’2005)
For all atomic routing games with linear cost functions holds
PoAatom ≤
5
2
(which is again tight, just like 4
3 for non-atomic routing.) 13
Braess’s Paradox
For an example see the green board.
Real-world occurences (Wikipedia):
In Seoul, South Korea, a speeding-up in traffic around the city was seen
when a motorway was removed as part of the Cheonggyecheon
restoration project.
In Stuttgart, Germany after investments into the road network in 1969,
the traffic situation did not improve until a section of newly built road
was closed for traffic again.
In 1990 the closing of 42nd street in New York City reduced the amount
of congestion in the area.
In 2012, scientists at the Max Planck Institute for Dynamics and
Self-Organization demonstrated through computational modeling the
potential for this phenomenon to occur in power transmission networks
where power generation is decentralized.
In 2012, a team of researchers published in Physical Review Letters
a paper showing that Braess paradox may occur in mesoscopic electron
systems. They showed that adding a path for electrons in a nanoscopic
network paradoxically reduced its conductance.
14