# Chapter 8.Modeling Network Traffic using Game Theory
[ToC]

## 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_ex+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

:::success
**Definition.**
Given a traffic pattern $F$, let
$$
X_F(e)
$$
to be the number of drivers on the edge $e$.
:::
:::success
**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)
$$
:::
:::info
**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'$. By assumption, we have
$$
\sum_{e\in P\setminus P'}T_e(X_F(e))>\sum_{e\in P'\setminus P}T_e(X_F(e)+1)
$$
Also, observe that
$$
\begin{split}
E(F')=E(F)+\sum_{e\in P'\setminus P}T_e(X_F(e)+1)-\sum_{e\in P\setminus P'}T_e(X_F(e))<E(F)
\end{split}
$$
Thus $E(F)$ is strictly decreasing in the process of the algorithm, and $E(F)\geq 0$ for all traffic $F$, hence it always terminates.
:::

Similarly,
:::success
**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$.
:::

:::info
**Lemma.**
If $T_e(x)=a_ex+b_e$, $a_e,b_e\geq 0$ for all $e\in EG$, then
$$
\frac{1}{2}S(e)\leq E(e)\leq S(e)
$$
**Proof.**
Let $x=X_F(e)$, we have
$$
\begin{split}
S(e)&=T_e(x)+\ldots+T_e(x)\\
&\geq T_e(1)+\ldots+T_e(x)=E(e)\\
&=a_e(1+\ldots +x)+xb_e\\
&=a_e\frac{x(x+1)}{2}+xb_e\\
&\geq \frac{x}{2}(a_ex+b_e)\\
&=\frac{1}{2}xT_e(x)=\frac{1}{2}S(e)
\end{split}
$$
:::

:::info
**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'$, we have
$$
E(F')\leq E(F)
$$
Hence,
$$
S(F')\leq 2E(F')\leq 2E(F)\leq 2S(F)
$$
:::