Collegium Omnium Mentium

The College of All Minds

Manent et numerantur

Braess’s paradox

PAPER IX — SOCIOLOGY · QUESTION 28 OF 31

In plain terms: The free original example, hosted by its discoverer — the road that made all the traffic worse.

The question as set

Adding a road to a congested network can lengthen every driver’s journey at equilibrium. Exhibit Braess’s paradox, locate the failure — in the network, in the equilibrium concept, or in the drivers — and state the sense in which such inefficiency is nonetheless bounded.

The question in context

This is question 28 of the 31 set in Paper IX — Sociology of The Truly Hardest Exam in the World, the examination of The College of All Minds. In the College’s subject index it is filed under Cities and settlement. Like every question of the College, it carries three references of record, verified live at publication and described twice — technically, and in plain terms — so the ground can be judged before it is walked. The response required is an argument, not a survey, of at most three thousand words, as technical as the question demands and no more.

The references of record

On a paradox of traffic planning (translation of the 1968 original) D. Braess · 2005 · Transportation Science (author's open copy)

The paradox at source: the four-node network where the new link degrades every equilibrium journey.

In plain terms: The free original example, hosted by its discoverer — the road that made all the traffic worse.

D. Braess (Wikipedia)

How bad is selfish routing? T. Roughgarden, É. Tardos · 2002 · JACM (author's open copy)

The bound the question requests: equilibrium cost within 4/3 of optimal for linear latencies — anarchy priced exactly.

In plain terms: The free landmark proving the selfish outcome is bad by at most a third — the paradox bounded.

T. Roughgarden (Wikipedia); É. Tardos (Wikipedia)

Networks, Crowds, and Markets (open copy) D. Easley, J. Kleinberg · 2010 · Cambridge UP (authors' free copy)

The diagnosis taught: Wardrop equilibrium as the failure's location — the network innocent, the solution concept indicted.

In plain terms: The free textbook chapter locating the fault — not in the road, nor quite the drivers, but in what balance among them means.

D. Easley; J. Kleinberg (Wikipedia)

Background: Braess's paradox · Price of anarchy

Download Paper IX (Markdown) · Subject index