Game Theory
Network Games and Wardrop Equilibrium
Cities spend billions building roads that... create more congestion. Internet providers add bandwidth that is instantly overloaded. Braess's paradox is the reason why. Network game theory explains this irrationality and offers solutions.
- **GPS navigation**: Waze routes everyone along the 'best route', which is immediately congested; this is real-time Wardrop equilibrium
- **Seoul, 2003**: demolition of a six-lane motorway improved traffic in the city centre, a textbook Braess paradox in urban planning
- **Congestion pricing**: London, Stockholm, and Singapore charge fees for driving into the centre, a tax to shift from UE to System Optimum
Предварительные знания
Games on Networks: Routing and Congestion
Wardrop equilibrium in London's road network with 3.5M daily trips demonstrates Braess's paradox: adding a new road increases average travel time by 15% at Nash equilibrium. Network games study strategic behaviour of agents on networks, road, communication, and social. Each agent chooses a route, connection, or strategy without accounting for the impact on others. The result is **congestion** and socially suboptimal equilibria.
when chooseing a route along a congested road, one impose a **negative externality** on everyone else on that road, but one don't account for it in the own decision. The aggregate result of selfish decisions is worse than a centralised optimum.
• **Internet routing**: TCP packets choose paths; protocols must account for congestion • **Power grids**: consumers and generators; flows obey physical laws • **Social networks**: viral spread; each node 'decides' whether to share content • **Financial markets**: traders overload some assets and ignore others
Why does an individually rational route choice by a user create a negative externality?
Wardrop Equilibrium
John Wardrop (1952)
British traffic engineer John Wardrop formulated two principles for the distribution of flows in road networks in 1952, which now bear his name. The first principle, User Equilibrium (UE), describes equilibrium selfish behaviour. The second principle, System Optimum (SO), describes the centralised optimum. Wardrop laid the foundations of Transportation Science, a branch of game theory and operations research.
Wardrop equilibrium exists and is unique when cost functions are convex (monotonically increasing latency with load). This is an important theoretical property: unlike Nash equilibrium in general form, here we have a uniqueness guarantee.
In Wardrop equilibrium (User Equilibrium) all used routes have equal latency. Why?
Braess's Paradox: More Roads, More Traffic
One of the most counterintuitive results in game theory: **adding a new road can slow down traffic for everyone**. This is Braess's paradox (1968), a direct consequence of the gap between individual and social optima.
Real-World Instances of Braess's Paradox
In 1990 Seoul closed the Cheonggyecheon elevated motorway (river restoration project). Traffic engineers expected a collapse. Instead congestion decreased, Braess's paradox in real life. Similar cases: Stuttgart (1969), demolition of a San Francisco freeway after the 1989 earthquake. In internet routing: BGP routing, where adding a new path increased congestion.
The paradox occurs because adding a new road creates a new strategically dominant route. Everyone rationally switches to it, not accounting for others doing the same. Individually rational decisions produce a collectively irrational outcome, the quintessence of the common good problem.
In Braess's paradox, adding a new road made things worse for everyone. What would fix the situation?
Price of Anarchy: The Cost of Selfishness
The **Price of Anarchy (PoA)** is a formal measure of how much worse selfish behaviour is compared to the centralised optimum. Introduced by Papadimitriou and Roughgarden.
The result PoA ≤ 4/3 for linear networks is one of the most beautiful in algorithmic game theory. It says: even without coordination, in the worst case selfish routing is only a third worse than the optimum. For many practical networks, an acceptable result.
| Mechanism | Description | Effect |
|---|---|---|
| Congestion pricing | Fee for using congested roads/networks | Shifts UE toward SO |
| Stackelberg routing | Centre controls part of traffic, rest is selfish | Reduces PoA |
| Information design | Showing only partial route information | Can improve equilibrium |
| Road removal | Reverse Braess, remove strategically harmful edges | Reduces total latency |
Price of Anarchy = 4/3 for linear routing games means:
Key Ideas
- **Network games**: users choose routes minimising their latency, creating congestion externalities
- **Wardrop equilibrium (UE)**: all used paths have equal latency; Nash equilibrium in continuous flow
- **System Optimum**: minimises total latency; requires accounting for marginal, not average, cost
- **Braess's paradox**: adding a new road can increase latency for everyone by shifting the equilibrium
- **Price of Anarchy**: ratio of worst Nash to optimum; for linear networks PoA ≤ 4/3
Related Topics
Network games sit at the intersection of game theory, algorithms, and the economics of externalities:
- Algorithmic Game Theory — PoA and routing games are central topics in AGT; computational complexity of finding equilibria
- Zero-Sum Games — Routing games are non-zero-sum; congestion losses create a social cost
- Mechanism Design — Congestion pricing is a mechanism to correct externalities and shift toward social optimum
Вопросы для размышления
- Do using a navigation app? What happens when EVERYONE follows Waze's recommendations simultaneously?
- Congestion pricing is effective but politically unpopular. How would one explain its benefit to an ordinary driver?
- Is Braess's paradox applicable to social networks? What would a 'road' be in Facebook/Twitter?