Today's Math Lesson: Braess's Paradox

So, it seems like this whole summer around Wauconda we have been practicing merging from two lanes down to one. A six mile stretch of Route 12 is in the process of being repaved and each day they block off a new section to fill in all the potholes. I assume they want the road fairly level before they install the new surface. During one of these interminable waits, I happened to recall a problem from network theory (with some connections to game theory) that I remember talking about with my advanced students fifteen or twenty years ago. It took a while to find it, but it turns out it appeared in the New York Times in December of 1990. It was probably used in a talk that I heard at a math conference sometime after that and I knew my students would be interested in it.    

It is called Braess's Paradox, first described by Dietrich Braess of the Institute for Numerical and Applied Mathematics in Munster, Germany in 1968. To understand the paradox, we need the diagram below (from Wikipedia):   

Assume that there are two roads leading from START to END, one that passes through A and one that passes through B. For the moment, ignore the dashed line that is a road from A to B. The travel time in minutes for the passengers on the START to A road is the number of passengers (T) divided by 100 and the travel time from START to B is a constant 45 minutes. As you can see the times are flipped for the next section of the trip (A or B to END). To do the math, let's assume there are 4000 passengers who want to make the trip from START to END. For A passengers, the START to A to END trip takes A/100 + 45 minutes, and the START to B to END trip for B passengers takes 45 + B/100 minutes. For any one person (who cannot by themselves affect what A or B is to any extent) both paths look pretty much the same. Since A + B = 4000, it can be shown that the optimal solution is to just randomly pick a path with the result that A = B = 2000 (roughly). Then the total time to travel from START to END would be 2000/100 (which is 20) + 45 for a total time of 65 minutes regardless of the path you picked. Even if you are a selfish driver, there is no incentive to pick one path over the other. (For you econ and game theory buffs, this is called a Nash equilibrium, after John Nash, the mathematician profiled in the movie A Beautiful Mind.)    

Braess's paradox has to do with what happens when you try to ease the congestion by adding another road that runs from A to B that has a very short driving time (think 0 minutes for the purpose of the problem). Now when a single driver looks at the choices from START to the middle, even if all 4000 drivers go to A, the driving time is 40 minutes (4000/100), which is less than the 45 minutes to go from START to B. And similarly when they get to the middle, every driver sees that they can save five minutes by switching from from A to B. That makes each part of their drive 40 minutes for a total driving time of 80 minutes, 15 minutes longer than the time without the road from A to B.  From a game theory viewpoint, when everyone in the game acts selfishly, then everyone suffers.    

In an inverse way, that's what prompted the New York Times article. In the late 1980's, the Earth Day celebration in New York caused a lot of traffic congestion. In 1990, the Traffic Commissioner decided to lessen the car traffic congestion by closing one of the streets - in fact, a fairly major street, 42nd Avenue, which is always congested. Everyone thought it would be a disaster. In fact, traffic flow got better that year. Braess's paradox in action. When the streets are crowded, sometimes traffic improves when there are fewer streets to choose from.     

From the Times article:   

Dr. Joel E. Cohen, a mathematician at Rockefeller University in New York, says the paradox does not always hold; each traffic network must be analyzed on its own. When a network is not congested, adding a new street will indeed make things better. But in the case of congested networks, adding a new street probably makes things worse at least half the time, mathematicians say.     

Something to think about the next time you are stuck on Ohio Street, trying to get to the Garrett's popcorn store on Michigan Avenue.