A Paradox

Dietrich Braess is a professor of mathematics at Ruhr University in Bochum, Germany. He is famous for the discovery of a paradox. When he was doing research on traffic modeling in 1968, he discovered that the flow in a road network could be hindered by adding a new road.

Today we note a connection between him and the new ACM Athena Award winner, Éva Tardos, whom we congratulate.

The paradox has a paradox riding on it. The original is about the game theory of elective actions by drivers individually trying to optimize their routes. Yet it shows up in purely physical dynamics. Consider the following network of springs and strings:

Quoting Clive Feathers, who studies Britain’s railways and the London Underground:

If all the strings are taut, then each of them will be carrying one-third of the weight of the block. So if the purple string is cut, the remaining strings will carry more of the weight and the block will drop down a bit as the springs take up the load, right?

Wrong!

As shown, each string has a tension of 4N, so the springs will each be under a tension of 8N and will stretch accordingly. Now, when the purple string is cut the remaining strings have a tension of 6N, and so does each spring. So there is less tension in the springs, and they will contract accordingly, making the block rise.

The Braess Paradox

Who cares about springs and strings? Indeed.

The point is that this paradox arises in problems we study in CS. It is named now as Braess’s Paradox. Springs and strings can be changed to edges. Edges in turn relate to networks of many kinds; the following figure comes from a paper on power grids:

The original paradox is that adding one or more roads to a road network can slow down overall traffic flow through it. The new road initially makes its use locally optimal for everyone until a saturation point is reached. The limit on choices before and after using the new road, however, also makes the usage increase the cost of the previously optimal strategies. This evolves a worse configuration for everyone that is not locally improvable.

The flip side is that a clog-prone network can sometimes be improved by removing certain parts of it. This paradox has been used to explain instances of improved traffic flow when existing major roads are closed. Here are two examples:

• In Stuttgart, Germany after investments into the road network in 1969, the traffic situation did not improve until a section of newly-built road was closed for traffic again.

• ON Earth Day this year (1990), New York City’s Transportation Commissioner decided to close 42d Street, which as every New Yorker knows is always congested. “Many predicted it would be doomsday,” said the Commissioner, Lucius J. Riccio. “You didn’t need to be a rocket scientist or have a sophisticated computer queuing model to see that this could have been a major problem.”

  But to everyone’s surprise, Earth Day generated no historic traffic jam. Traffic flow actually improved when 42d Street was closed.

Today’s News and the Paradox

This started as a post on Éva Tardos, who is a professor at Cornell University. She just was named the 2022-2023 ACM Athena Lecturer:

This award celebrates women researchers who have made fundamental contributions to Computer Science. Each year ACM honors a preeminent woman computer scientist as the Athena Lecturer. The recipient gives an invited talk at a major ACM conference of her choice.

What is the connection between Tardos as Athena Lecturer and the Braess Paradox? Indeed, the citation notes her contributions to algorithmic game theory. These are game-theory situations in her purview.

She has many papers that bound approximations to optimal solutions. Often the answers are likely to be hard to solve exactly—they are NP-complete for example. But she has some wonderful papers that study questions where paradoxes apply regardless of whether or is true.

One is the paper by Henry Lin, Tim Roughgarden, Eva Tardos, and Asher Walkover, and is titled, “Stronger Bounds On Braess’s Paradox And The Maximum Latency Of Selfish Routing.” It addresses the flip-side paradox: how much can the performance of a network be improved by removing one edge? One might expect that removing an edge might be less likely to improve the smallest networks, as well as less impactful on larger networks, so that the highest improvement would come in some mid-size example. In fact, they show that Braess’s original example of four nodes and five edges has the highest improvement.

They also show that the problem of finding the maximum improvement possible within a sub-network of a large network is -hard to approximate, even sub-exponentially. We wonder how this connects to an earlier paper by Fan Chung, Stephen Young, and Wenbo Zhao showing that expander graphs tend to have many subgraphs exhibiting the Braess paradox. This is surprising because expanders by-and-large promote free network flows.

We add that Tardos is just the third Athena Lecturer from the theory area since the first award in 2006: Shafi Goldwasser in 2008 and Nancy Lynch in 2012. Congrats, Éva.

Open Problems

I did not know about the Braess Paradox before reading about her award; Ken thinks he saw it a decade or so ago. Previously my favorite result of Tardos was in the paper, “The Gap Between Monotone And Non-Monotone Circuit Complexity Is Exponential.” Now not so clear.

What is your favorite of her results?