Braess' paradox

The following is a re-upload of a post in my previous blog (which was destroyed by mistake).


I've been going back to NUS these few weeks after work. Been attending CS5234 (new syllabus!) and sat in the first CS6101 class. As usual, Seth never disappoints. On the other hand, CS6101 seems like "the blind leading the blind". Everyone is there to learn, but the "teaching" will be "okay, this week, so and so will read the Stanford materials and present". If that's the case, I'd rather just watch the lecture videos here at my own pace. Oh well.


Here's an interesting paradox that I was introduced about a month ago when I sat in Prof Leong Hon Wai's research group meet up. One of his ex-students is looking into "transportation science/smart transportation" as his new research area. He gave us a short introduction of the topic and introduced Braess' paradox1.

The paradox is roughly as follows: If all drivers are self-serving and optimises individually for the Nash equilibrium, having more route options can be worse for everyone. This is counter-intuitive as one may think that if the extra route is introduced causes travelling time to increase, drivers will just ignore it.

In the paper, travelling time on roads $f(\cdot)$ are modeled to be pretty general. They only need to satisfy the following 3 conditions:

  1. $f$ is non-zero. i.e. $f(x) \geq 0, \forall x$

    You cannot take negative time.

  2. $f$ is non-decreasing. i.e. $f(x) \geq f(y)$ whenever $x \geq y$

    Having more vehicles on the road never speeds up the travelling time.

  3. $f$ is semi-continuous. i.e. $\lim_{x \rightarrow y} f(x) = f(y)$ whenever $x < y$

    Used for simplifying mathematical analysis in the paper.

Model

Cars in the future are all equipped with hardware that allows communication to some central traffic server and optimise fastest routes for drivers. Drivers then follow that route while driving. Modelling each car as a player and chosen route as actions, the optimisation is done by solving for a mixed Nash equilibrium. To learn more, read up on the fascinating branch of applied mathematics called Game Theory, which has far reaching implications in even areas such as biology, politics and economics. It even won the Nobel Prize.

  • Drivers are assumed to be rational2 and acting in self-interest, in game theoretic sense. While they are not malicious, they optimise their actions only on their personal gains/losses, and not on the community/society as a whole.
  • Nash equilibrium is a situation where agents/players involved in a game have no incentive to individually switch strategies, assuming everyone else sticks to their current strategies.

A real life3 example of self-interest and Nash equilibrium is as follows:

  • You drive instead of taking public transport because it is more convenient. But this contributes to pollution and global warming.
  • Although it will reduce your carbon footprint if you take the public transport, your individual action does little to help if everyone else continues driving.
  • Hence, you continue driving.

This is a bad equilibrium to stay in! Hence, governments do things that will perturb the game situation and cause rational citizens to choose public transport over driving. These "things" can include making it less convenient/costly to drive, improving public transport experience, etc.

Example

Here, we look at the example that I was introduced to4. While the examples below are symmetric intentionally to simplify analysis, the spirit and methodology should carry through more complicated road networks.

For our purposes, assume that $f$ is non-zero and strictly increasing. This is because we want to differentiate $f$ from a constant (non-decreasing) cost $c$ later on.

Assume there are N number of vehicles starting Point A and are trying to get to Point D. Now consider the following road network with 2 routes - (Route 1) A $\rightarrow$ B $\rightarrow$ D and (Route 2) A $\rightarrow$ C $\rightarrow$ D.

The red labels on the arrows are the time needed to cross that road. When a vehicle chooses a road, it is committed to driving down that particular 1 way street until the next junction. Roads AC and BD are assumed to be very very wide, hence the time needed is always a constant c unit(s).

We can intuitively guess that the Nash equilibrium and optimal point is to pick Route 1 or Route 2 with 50% probability each. Due to symmetry, this strategy will even out the congestion on the roads. If that happens, the travelling time will be $t = (\frac{N}{2} + c)$ for each driver.

Let's be careful and work out the details now:

  • Route 1: A $\rightarrow$ B $\rightarrow$ D
  • Route 2: A $\rightarrow$ C $\rightarrow$ D
  • Let $x$ = Proportion of drivers who pick Route 1
  • Let $1-x$ = Proportion of drivers who pick Route 2

Then, the travelling times are as follows:

  • Route 1: $t_1$ = Time on AB + Time on BD = $f(N * x)$ + $c$
  • Route 2: $t_2$ = Time on AC + Time on CD = $c$ + $f(N * (1 - x))$
  • In a mixed Nash equilibrium, $t_1 = t_2$.

Solving the equations yield $f(N * x) = f(N * (1 - x))$. Since $f$ is strictly increasing, $x = \frac{1}{2}$ and $t_1 = t_2 = \frac{N}{2} + c$, which agrees with our intuition.

Now imagine we build a super wide highway from B to C. That is, we augment the existing network with an additional "short cut" lane (B $\rightarrow$ C) that costs $c' < c$.

Intuitively, additional roads can only improve the current situation, right? If it doesn't, drivers should just default to the previous situation and ignore the new road. However, the analysis shows that drivers who are acting in self-interest will in fact use the new road and cause the overall travelling time to increase!

Now, we have 3 routes:

  • (Old) Route 1: A $\rightarrow$ B $\rightarrow$ D
  • (Old) Route 2: A $\rightarrow$ C $\rightarrow$ D
  • (New) Route 3: A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ D

We know that in the previous situation, Route 1 and 2 are each chosen with 50% probability, leading to a travelling time of $t = (\frac{N}{2} + c)$ for each driver. How many drivers will pick each route now? Let's do some calculations:

  • Let $x$ = Proportion of drivers who pick Route 1
  • Let $y$ = Proportion of drivers who pick Route 2
  • Let $1-x-y$ = Proportion of drivers who pick Route 3

Then, the travelling times are as follows:

  • Route 1:
    $t_1$ = Time on AB + Time on BD = $f(N * [x + (1 - x - y)])$ + $c$ = $f(N * [1 - y]) + c$
  • Route 2:
    $t_2$ = Time on AC + Time on CD = $c$ + $f(N * [y + (1 - x - y)])$ = $f(N * [1 - x]) + c$
  • Route 3:
    $t_3$ = Time on AB + Time on BC + Time on CD = $f(N * [x + (1 - x - y)])$ + $c'$ + $f(N * [y + (1 - x - y)])$ = $f(N * [1 - y]) + f(N * [1 - x]) + c'$
  • In a mixed Nash equilibrium, $t_1 = t_2 = t_3$.

The first 2 equations yield $x = y$. Combining with the 3$^{rd}$ equation, we get $f(N * [1 - x]) = c - c'$. This means the proportion of people choosing either routes 1 or 2 are depending on the difference between $c$ and $c'$.

In the Wikipedia example, $N = 4000$, $f(T) = \frac{T}{100}$, $c = 45$, $c' = 0$. Plugging these in, we get $\frac{4000 * (1 - x)}{100} = 45 \Rightarrow x = 1 - \frac{45}{40} < 0$. So, we set $x = y = 0$. This means everyone will take Route 3, incurring $t_3 = \frac{4000}{100} + 0 + \frac{4000}{100} = 80$. Under this same setup, in the previous network without ($B \rightarrow C$), each driver would have only taken $\frac{4000/2}{100} + 45 = 65$ units of time!

You may think: Hm, this paradox only happened because it violates "triangle inequality"! It costs cheaper for everyone to take ($A \rightarrow B \rightarrow C$) than ($A \rightarrow C$), and ($B \rightarrow C \rightarrow D$) than ($B \rightarrow D$).

Unfortunately, the increase in time happens even if "triangle inequality" is maintained - Consider the following setting where $f$(everyone) $> c$:

  • $N = 4000$
  • $f(T) = \frac{T}{100}$
  • $c = 35$
  • $c' = 0$

Here, we only decreased $c$, but you may try other ways of making sure the triangle inequality holds (such as increasing $c'$, etc). Now, $f(N * [1 - x]) = c - c' \Rightarrow \frac{4000 * (1 - x)}{100} = 35 \Rightarrow x = 1 - \frac{35}{40} = \frac{1}{8}$.

That means $\frac{1}{8}$ of the cars should take Route 1, $\frac{1}{8}$ should take Route 2, and $\frac{3}{4}$ should take Route 3. This yields $t_1 = t_2 = t_3 = \frac{4000 * (1 - \frac{1}{8})}{100} + 35 = 70$. Without the "shortcut" ($B \rightarrow C$), it would have taken only $\frac{4000/2}{100} + 35 = 55$ units of time.

Going further

Definitely read up Game Theory if all these action selection situations seem interesting to you. One of the most famous game is probably Prisoner's dilemma.

If you like to read up on interesting people, check out the lauded polymath and inventor of Game theory, John von Neumann. Lots of fascinating stories and crazy stuff that he did in his life.

References and Footnotes

  1. Original paper: http://homepage.ruhr-uni-bochum.de/Dietrich.Braess/paradox.pdf

  2. Translated paper: http://homepage.rub.de/Dietrich.Braess/Paradox-BNW.pdf
  3. Huge assumption in real life. Hahaha...

  4. Hopefully this is more relatable than all the abstract definitions of players, actions and Nash equilibrium.

  5. I generalised the instance that I was introduced to. In the meet up, $c = 1$ and $c' = 0$. The Wikipedia page uses a similar graph instance as the example.