Chapter 8.Modeling Network Traffic using Game Theory

• Chapter 8.Modeling Network Traffic using Game Theory
  • 8.1 Traffic at Equilibrium
    • Equilibrium traffic
  • 8.2 Braess's Paradox
    • Reflections on Braess's paradox
  • 8.3 Advanced Material: The Social Cost of Traffic at Equilibrium
    • Travel-time Function
    • Travel Pattern
    • Social Cost
    • Best-Response Dynamics

8.1 Traffic at Equilibrium

Edge : Highway
Node : Exit
Label : Travel time

$x$ : The number of cars

• Different from games before, the current game generally have an enormous number of players.
• The notions of Nash equilibrium, dominant strategies, mixed strategies etc., all have direct parallels with their definitions for two-player games.

Equilibrium traffic

• Either route has the potential to be the best choice for a player if all the other players are using the other route.
• Any list of strategies in which the drivers balance themselves evenly between the two routes is a Nash equilibrium.

When there are 4000 cars in total,

$x=2000$ on each route is a Nash equilibrium,
and the travel time is

$\frac{2000}{100}+45=65$

8.2 Braess's Paradox

There is a unique Nash equilibrium,
and the travel time is

$\frac{4000}{100}+0+\frac{4000}{100}=80$

To see why, no driver can benefit by changing their route: with traffic snaking through C and D the way it is, any other route would now take 85 minutes.

And to see why it’s the only equilibrium, check that the creation of the edge from C to D has in fact made the route through C and D a dominant strategy for all drivers: regardless of the current traffic pattern, you gain by switching your route to go through C and D.

This phenomenon — that adding resources to a transportation network can sometimes
hurt performance at equilibrium is known as Braess’s Paradox

Reflections on Braess's paradox

• We all have an informal sense that “upgrading” a network has to be a good thing,
  and so it is surprising when it turns out to make things worse.
• Suppose that we allow the graph to be arbitrary,
  and we the travel time on each edge depends in a linear way on the number of cars.
  • In this case, elegant results of Tim Roughgarden and Eva Tardos can be used to show that if we add edges to a network with an equilibrium pattern of traffic, there is always an equilibrium in the new network whose travel time is no more than
    $\frac{4}{3}$ times as large

8.3 Advanced Material: The Social Cost of Traffic at Equilibrium

Purpose

Given a traffic graph, how to find an equilibrium?
How far an equilibrium from social optimal?

Travel-time Function

For

$e\in EG$

$$T_e(x)=a_{e}x+b_e$$
where

$a_e,b_e$ are non-negtive constant.

Travel Pattern

The decisions by each driver.

Social Cost

The sum of all travel times.

Best-Response Dynamics

Best-Response Dynamics(initial traffic):
    while it is not an equilibrium:
        there exists a driver that has a strictly better route
        let it switch to the new route
    output the traffic

Definition.
Given a traffic pattern

$F$, let

$$X_F(e)$$
to be the number of drivers on the edge

$e$.

Definition.
Given a traffic pattern

$F$ on graph

$G$, let

$$E_F(e)=\sum _{i=1}^{X_F(e)}{T}_e(i)$$
and

$$E(F)=\sum _{e\in EG}{E}_F(e)$$

Theorem.
If

$T_e(x)$ is non-negtive for all

$e,x$, then the above algorithm always terminates.
Proof.
Let

$F$ be a traffic pattern, and a driver changes his route from

$P$ to

$P^{\prime }$. By assumption, we have

$$\sum _{e\in P\setminus P^{\prime }}{T}_e(X_F(e))>\sum _{e\in P^{\prime }\setminus P}{T}_e(X_F(e)+1)$$
Also, observe that

$$\begin{array}{r}E(F^{\prime })=E(F)+\sum _{e\in P^{\prime }\setminus P}{T}_e(X_F(e)+1)-\sum _{e\in P\setminus P^{\prime }}{T}_e(X_F(e))<E(F)\end{array}$$
Thus

$E(F)$ is strictly decreasing in the process of the algorithm, and

$E(F)\ge 0$ for all traffic

$F$, hence it always terminates.

Similarly,

Defination.
Given a traffic pattern

$F$ and edge

$e$ on graph

$G$, define

$$S(e)=X_F(e)T_e(X_F(e))$$
and

$$S(F)=\sum _{e\in EG}S(e)$$
which is the social cost of traffic

$F$.

Lemma.
If

$T_e(x)=a_{e}x+b_e$,

$a_e,b_e\ge 0$ for all

$e\in EG$, then

$$\frac{1}{2}S(e)\le E(e)\le S(e)$$
Proof.
Let

$x=X_F(e)$, we have

$$\begin{array}{rl}S(e)& =T_e(x)+\dots +T_e(x)\\ & \ge T_e(1)+\dots +T_e(x)=E(e)\\ & =a_e(1+\dots +x)+x{b}_e\\ & =a_e\frac{x(x+1)}{2}+x{b}_e\\ & \ge \frac{x}{2}(a_{e}x+b_e)\\ & =\frac{1}{2}x{T}_e(x)=\frac{1}{2}S(e)\end{array}$$

Theorem.
There exists an equilibrium whose social cost is no more than twice the social cost of the social optimum.
Proof.
Given a social optimum traffic

$F$, take it as input of Best-Response Dynamics, and output

$F^{\prime }$, we have

$$E(F^{\prime })\le E(F)$$
Hence,

$$S(F^{\prime })\le 2E(F^{\prime })\le 2E(F)\le 2S(F)$$