Published by Ganit Charcha
| Category - Digital Magazine | 2014-09-24 06:09:42
In my childhood days, I had to take a long bicycle ride to my school. I had two choices. One way was to take a road which was long yet mostly empty. The second one was a smart short cut through narrow yet busy streets. Everyday I used to ask myself ``which road should I take?'' Perhaps like most of us, I used to opt for the one that would take the minimum time aka the shortest path. All the experienced commuters know, besides the length of the path, there is an extremely important factor behind the trip duration; the traffic. However, it is very unlikely that any one of us, while choosing the route, considers the congestion we create to the fellow traveler's path. We choose our route selfishly. We expect our fellow travelers to do the same, not to care about our schedule. Have you wondered what would have happened if we all could coordinate and cooperate to choose our path? What effect it would have on the average commute time? Would it decrease? If so, by how much? The problem is extremely relevant to the modern communication networks. Everyone wants to minimize the delay of their traffic. What would be the price if we let the users decide the path selfishly.
Pigou's Example Consider two cities A and B connected by two parallel roads, and a fixed number of drivers who wish to travel from A to B at roughly the same time. Suppose the first road takes a long route, yet wide enough to accomodate all the cars without being packed. The second road is significantly short but narrow. The delay in the second road increases sharply with the number of cars. Let us say, travel time in the first road is one hour, irrespective of the traffic. On the other hand, the time in the second route is the fraction of the overall traffic choosing to use it. If $x$ fraction of the cars are on the second road, then each of them experience $x$ hour of commute time.
What is the average travel time from A to B if all the travelers choose their path selfishly? The travelers on the long highway will experience one hour of travel time irrespective of the traffic. On the other hand, it will take maximum one hour in the second route, less if even a small amount of traffic move to the first path. Naturally, the second route will be an attractive choice for everyone. All the traffic will move to the second path. Everyone will still experience an hour of commute. But no one will move to the long highway as there is no incentive to move. We reach the well known Nash Equilibrium. Now, if we could ``assign'' the path for each driver, we could improve the situation. We could assign half of the traffic in the first path and other half in the second. While the everyone in the first half need an hour, the cars in the second path could reach their destination in half an hour. Thus we could improve the experience of half of the drivers (without worsening the situation of other half). The average time for reaching A to B would have reduced to 45 minutes instead of an hour.
Generalizing Pigou's Example Let us generalize Pigou's Example to arbitrary affine functions $ax+b$ ($a,b\geq 0$). Suppose the latency in the first path is $f_1(x)=a_1x+b_1$ and in the second path is $f_2(x)=a_2x+b_2$, where $x$ is the fraction of traffic along that path. What will be the flow at Nash Equilibrium? The traffic will achieve Nash Equilibrium (stable selfish assignment) when no one will find any incentive to change their choice. If $x_1$ is the fraction of traffic in the first path and $x_2$ is the traffic in the second path, then at Nash Equilibrium $$f_1(x_1)=f_2(x_2)\qquad~\mbox{where}~x_1+x_2=1$$. Solving the linear equations, we get \begin{align} \label{eq:1} x_1=\frac{a_2+b_2-b_1}{a_1+a_2} \hspace{3.5in} [1] \end{align} When $b_1> a_2+b_2$ or $b_2>a_1+b_1$, the flow is trivial as there will be no traffic in one path. We can ignore such trivially inefficient paths.
What about the optimal flow? It can easily be shown that the optimal flow of this network is essentially the Nash Equilibrium flow for the network when $f_i(x)=2a_ix+b_i$, $i=1,2$. So, in the optimal flow \begin{align*} x_1=\frac{2a_2+b_2-b_1}{2(a_1+a_2)} \end{align*} It is interesting to observe, for Pigou's example, if $b_1$ and $b_2$ are equal, the Nash Equilibrium flow is optimal. Unfortunately, for complex networks that is not always true. However, when $f_1$ and $f_2$ are linear functions ($b_1=b_2=0$), Nash Equilibrium flow is indeed the optimal flow. Is it relevant to our daily life? Recall the Kirchhof's rule of equivalent resistance. If $R_1$ and $R_2$ are two resistance joined in parallel, the current flowing through $R_1$ is $I_1=\frac{R_2}{R_1+R_2}$. Notice the similarity with Equation [1]. The potential drop is a linear function and electrons achieve optimal cost through Nash Equilibrium!
Braess' Paradox I shall finish the article with a seemingly bizarre example, known as Braess' paradox. Consider the following extension of Pigou's network. Now both roads are divided into two parts. For the first road, the first part is narrow (the delay is proportional to the traffic) while the second part is a long wide highway. For the second road, the situation is exactly opposite. There the first one hour journey is on highway, then a stretch of narrow street with delay equal to the fraction of traffic. As the cost function in both the routes are same, the traffic will get divided in equal parts. The first half choosing the first route, the other half choosing the second. The average commute time is ninety minutes.
Now suppose to expedite the traffic, the authority decides to join the routes by an extremely short yet very wide highway, say of latency zero. How will the drivers react? Of course, every driver can now save thirty minutes by taking the highway assuming everyone else keep their route unchanged. Naturally, all the drivers simultaneously decide to move to the new route. All the traffic take the path $A->X->Y->B$. Everyone now experiences a two hour journey! As there is no better alternative, no one will change their route, and they now commute for thirty more minutes. Thus a seemingly helpful development can have a negative impact on the whole system. The topic of selfish routing has been studied extensively in recent years. The results, examples and ideas presented here were based on Tim Roughgarden's seminal thesis (http://theory.stanford.edu/~tim/papers/thesis.pdf)
About the Author Rishiraj Bhattacharyya (email: rishiraj.bhattacharyya@gmail.com) is a Lecturer at Indian Statistical Institute, Kolkata, India. He has done his M-Tech and PhD from Indian Statistical Institute, Kolkata. His research interests include Cryptography, Coding Theory and Algorithmic Game Theory.
