Algorithmic Game Theory

Nash's existence proof applies Kakutani's fixed-point theorem, and fixed-point theorems are notoriously non-constructive. Whether that mattered was an open question for fifty years, and in 2006 it was answered. Constantinos Daskalakis, Paul Goldberg and Papadimitriou showed that computing a Nash equilibrium is complete for PPAD — the class of problems whose solutions are guaranteed by a parity argument on a directed graph, with finding a fixed point as the archetype — and Chen and Deng extended the result to two-player games.

PPAD-completeness is a weaker statement than NP-hardness, and in this context it is bad enough: these problems are not believed to admit polynomial-time algorithms, and the same barriers that obstruct P versus NP obstruct progress here. The consequence for economics is sharp. An equilibrium can exist, be unique, and be beyond the reach of any efficient procedure. Predicting that agents will be at it then requires believing they can do something no algorithm can.

The field's response is instructive, because it did not consist of trying harder. It consisted of weakening the assumption. Real participants do not compute equilibria; they adjust, repeatedly, using simple learning rules that guarantee only that in hindsight no single fixed strategy would have done much better — the no-regret property. Roughgarden's smoothness framework shows that price-of-anarchy bounds proved in a particular short form automatically apply to the time-averaged behaviour of any such learners. The 4/3 bound for selfish routing therefore holds without anyone ever being at equilibrium, which is a considerably more defensible claim about traffic.

Return to the first of the two questions — what decentralisation costs — where the answers are more cheerful.

One unit of traffic, two routes. This example is due to Arthur Pigou in 1920 and is the worst case of the general theorem. A unit of traffic travels from $s$ to $t$. The upper road is wide: its travel time is 1 regardless of load. The lower road is short but congests: carrying a fraction $x$ of the traffic, its travel time is $x$.

At equilibrium, every driver takes the lower road, because its time is at most 1 and strictly less whenever anyone is on the upper road. Total travel time is

$$C_{\text{eq}} = 1 \times 1 = 1.$$

The social optimum splits the traffic. Sending a fraction $x$ below and $1-x$ above costs

$$C(x) = x \cdot x + (1-x)\cdot 1 = x^{2} - x + 1,$$

minimised at $x = 1/2$:

$$C_{\text{opt}} = \tfrac{1}{4} - \tfrac{1}{2} + 1 = 0.75.$$

So the price of anarchy is

$$\frac{C_{\text{eq}}}{C_{\text{opt}}} = \frac{1}{0.75} = \frac{4}{3}.$$

Tim Roughgarden and Éva Tardos proved that this is not merely an example but the bound: for any network of any size and topology, with travel times that are linear in load, selfish routing costs at most 4/3 of the optimum, and this little two-edge graph attains it. The size of the network is irrelevant. That is a remarkable thing to be able to say about an arbitrary graph, and it is the kind of result that made the field.

Now add a road. Four nodes. From $s$ to $a$ the delay is $x$ (the flow on that edge); from $a$ to $t$ it is 1; from $s$ to $b$ it is 1; from $b$ to $t$ it is $x$. One unit of traffic goes from $s$ to $t$ by one of two routes, $s\!\to\!a\!\to\!t$ or $s\!\to\!b\!\to\!t$, which are symmetric. At equilibrium the traffic splits evenly and each driver's time is

$$0.5 + 1 = 1.5.$$

Build a new road from $a$ to $b$ with zero delay. Consider a driver on the upper route: on reaching $a$, the remaining journey via $t$ costs 1, while via $b$ it costs $0 + x_{bt}$. Every driver now prefers $s\!\to\!a\!\to\!b\!\to\!t$, and once all of them do, both congesting edges carry the full unit:

$$1 + 0 + 1 = 2.$$

Everyone's journey is a third longer than before the road was built, and no one can improve by deviating: the old routes now cost $1 + 1 = 2$ as well. This is Dietrich Braess's paradox, it is a consequence of equilibrium rather than of anything irrational, and it has been seen in practice — traffic in New York improved when 42nd Street was closed in 1990.

Both examples point to the same remedy, which is why this is a mathematical result with a policy attached. The inefficiency arises because a driver pays their own delay and not the delay they add to everyone else. Charge the difference — a congestion toll equal to the externality — and the equilibrium moves to the optimum exactly.

The design side ran into the complementary obstacle. The general truthful mechanism — Vickrey–Clarke–Groves, the multi-item generalisation of the second-price auction — works by charging each participant the harm they do to everyone else, computed as a difference of two optimal allocations. Noam Nisan and Amir Ronen pointed out in 1999 that for combinatorial problems those optima are NP-hard, and that substituting an approximation generally destroys truthfulness, because a participant can now gain by reporting values that steer the heuristic.

Two decades of work went into finding mechanisms that are both approximately optimal and exactly truthful, with real successes in restricted settings and no general solution. Meanwhile the practical world did not wait. Search advertising was sold for years by a ranking rule that resembles a second-price auction and is not truthful with more than one slot, a fact established by Benjamin Edelman and colleagues and by Hal Varian only after the mechanism was handling enormous sums.

The clearest demonstration that the two halves can be made to meet is the American spectrum incentive auction of 2016. Broadcasters bid to give up channels while mobile operators bid for cleared bandwidth, and the price offered to each broadcaster depended on whether the remaining stations could be repacked into fewer channels without interference — an NP-hard graph-colouring question that had to be answered tens of thousands of times, in seconds each, inside the auction's own pricing rule. A purpose-built satisfiability solver did it, and the auction reallocated 84 MHz of spectrum. It is the closest thing the subject has to a controlled demonstration that incentives and computation can be designed together, and it took sixty years from Vickrey's paper to get there.