5D Library › Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks · 中文

Chapter 1 Braess’s Paradox: One More Road, Everyone Slower

Congestion without an accident

We usually think congestion comes from too few roads: building another one should at least do no harm. Braess’s 1968 paper gave a counterexample (Braess 1968). He considered a road network in which a known number of vehicles leave each origin for known destinations, the travel time on each road rises with its traffic, and every driver chooses the route that is fastest for himself. In this setting he showed that “everyone takes the best route for himself” and “total travel time is as short as possible” are not the same thing, and he gave an example in which adding a road to the network redistributes traffic so that every driver’s travel time increases (Braess et al. 2005).

The key to this result is not the new road itself but the externality of choice: by choosing a road a driver adds a little delay for everyone on it, and he does not count that delay when deciding. This chapter first writes “everyone takes the fastest route” as a precise equilibrium condition, then computes the paradox in full on Braess’s diamond network, and finally looks at how the same equations describe springs and circuits.

Wardrop’s two principles

Evidence

Wardrop’s principles. In a 1952 paper Wardrop, of the British Road Research Laboratory, stated two principles of traffic assignment: first, the journey times on all routes actually used are equal and no longer than on any unused route; second, the average journey time is a minimum (Wardrop 1952). The first became known as the user equilibrium (UE) and the second as the system optimum (SO). Beckmann, McGuire and Winsten showed in 1956 that when the delay on each road depends only on the traffic on that road, the user equilibrium is the solution of a convex optimisation problem; it therefore exists, and when delays rise strictly with traffic, the traffic on each road is unique (Beckmann et al. 1956).

Calculation

Let the network have several routes pp from origin to destination, with route flows fpf_p and total demand d=∑pfpd = \sum_p f_p. The flow on road (edge) ee is xe=∑p∋efpx_e = \sum_{p \ni e} f_p, its delay is ce(xe)c_e(x_e), and the travel time of a route is Cp=∑e∈pce(xe)C_p = \sum_{e \in p} c_e(x_e).

User equilibrium: if fp>0f_p > 0, then Cp=min⁡qCqC_p = \min_q C_q. No one can become faster by switching routes. The users here are nonatomic: each is an infinitesimal share of traffic, and a switch by one of them does not change any road’s delay.

System optimum: minimise total cost ∑exece(xe)\sum_e x_e c_e(x_e). Differentiating with respect to xex_e shows that the optimal flows satisfy a condition of the same form, with the delay ce(x)c_e(x) replaced by the marginal cost ce(x)+xce′(x)c_e(x) + x\,c_e'(x): one more user on this road bears cec_e himself and also slows each of the xx users already there by ce′(x)c_e'(x).

The two conditions differ by the term xce′(x)x\,c_e'(x). Selfish users see only the first term; the social cost includes the second.

The programs in this book use “path equilibration”: repeatedly find the slowest used route and the fastest route of all, and shift traffic between them until their times are equal. For the system optimum the delay is replaced by the marginal cost.

The diamond network

Calculation

Four nodes: origin ss, destination tt, and intermediate nodes vv and ww. Roads s→vs \to v and w→tw \to t have delay equal to their flow xx (they congest); roads v→tv \to t and s→ws \to w have constant delay 1 (broad but long). The two routes s→v→ts \to v \to t and s→w→ts \to w \to t each contain one road of delay xx and one road of delay 1. Total demand is 1. Then a shortcut of delay 0 is built from vv to ww, creating a third route s→v→w→ts \to v \to w \to t. The program finds the user equilibrium and the system optimum with and without the shortcut, checks whether the shortcut is dominant, and varies demand and the network’s parameters.

Calculation

# Wardrop user equilibrium (UE) versus system optimum (SO) on Braess networks.
# Path-based equilibration: repeatedly shift flow from the costliest used path to the
# cheapest path until their costs are equal. Edge latency c(x) = b + a x^d; for SO the
# "cost" is the marginal cost c(x) + x c'(x) = b + (d + 1) a x^d. Nonatomic users: each
# is an infinitesimal share of flow.

def lat(e, x, marginal=False):
    a, b, d = e
    return b + (d + 1 if marginal else 1) * a * x ** d

def path_costs(net, paths, f, marginal=False):
    load = {k: 0.0 for k in net}
    for p, q in zip(paths, f):
        for k in p: load[k] += q
    return [sum(lat(net[k], load[k], marginal) for k in p) for p in paths], load

def solve(net, paths, demand, marginal=False, iters=4000):
    f = [demand / len(paths)] * len(paths)
    for _ in range(iters):
        c, _ = path_costs(net, paths, f, marginal)
        used = [i for i in range(len(paths)) if f[i] > 1e-13]
        hi, lo = max(used, key=lambda i: c[i]), min(range(len(paths)), key=lambda i: c[i])
        if c[hi] - c[lo] < 1e-11: break
        s, t = 0.0, f[hi]                    # bisection on the amount shifted
        for _ in range(60):
            m = (s + t) / 2; g = f[:]; g[hi] -= m; g[lo] += m
            cc, _ = path_costs(net, paths, g, marginal)
            if cc[hi] > cc[lo]: s = m
            else: t = m
        f[hi] -= s; f[lo] += s
    return f

def total(net, paths, f):
    c, _ = path_costs(net, paths, f)
    return sum(q * x for q, x in zip(f, c))

# Simplified Braess network: s->v (x), v->t (1), s->w (1), w->t (x); shortcut v->w (0).
NET = {"sv": (1, 0, 1), "vt": (0, 1, 1), "sw": (0, 1, 1), "wt": (1, 0, 1),
       "vw": (0, 0, 1)}
TWO = [("sv", "vt"), ("sw", "wt")]
THREE = TWO + [("sv", "vw", "wt")]

def avg_cost(net, paths, d, marginal=False):
    return total(net, paths, solve(net, paths, d, marginal)) / d

if __name__ == "__main__":
    for lab, ps, m in (("no shortcut, UE", TWO, False), ("shortcut, UE", THREE, False),
                       ("shortcut, SO", THREE, True)):
        f = solve(NET, ps, 1.0, m)
        print(f"{lab:16s} path flows " + " ".join(f"{q:.3f}" for q in f)
              + f"   average time {total(NET, ps, f):.3f}")
    grid = [(u / 20, w / 20) for u in range(21) for w in range(21)]   # loads x_sv, x_wt
    adv = [min(1 + w, 1 + u) - (u + w) for u, w in grid]  # best other route - shortcut
    print(f"shortcut never worse in {sum(a >= 0 for a in adv)} of {len(adv)} load pairs; "
          f"strictly better in {sum(a > 0 for a in adv)}"
          "\n   (ties only when x_sv = 1 or x_wt = 1)")
    print("demand   no shortcut   shortcut (UE)   shortcut (SO)")
    for d in (0.5, 2 / 3, 1.0, 1.5, 2.0, 2.5):
        a, b, c = (avg_cost(NET, TWO, d), avg_cost(NET, THREE, d),
                   avg_cost(NET, THREE, d, True))
        print(f" {d:5.3f}      {a:6.3f}        {b:6.3f}          {c:6.3f}")
    # Braess's own 1968 example (10x, x + 50, new link x + 10): demand 6, time 83 -> 92.
    BIG = {"a": (10, 0, 1), "b": (1, 50, 1), "c": (1, 50, 1), "d": (10, 0, 1),
           "e": (1, 10, 1)}
    P2, P3 = [("a", "c"), ("b", "d")], [("a", "c"), ("b", "d"), ("a", "e", "d")]
    print(f"classic example, demand 6: {avg_cost(BIG, P2, 6):.1f} -> "
          f"{avg_cost(BIG, P3, 6):.1f}")
    hurt = lambda d: avg_cost(BIG, P3, d) - avg_cost(BIG, P2, d) > 1e-7
    def edge(lo, hi):                            # bisection for where "hurt" switches
        for _ in range(30):
            m = (lo + hi) / 2
            if hurt(m) == hurt(lo): lo = m
            else: hi = m
        return (lo + hi) / 2
    print(f"  the added link hurts for demand between {edge(1, 6):.2f} and "
          f"{edge(6, 12):.2f}")
# no shortcut, UE  path flows 0.500 0.500   average time 1.500
# shortcut, UE     path flows 0.000 0.000 1.000   average time 2.000
# shortcut, SO     path flows 0.500 0.500 0.000   average time 1.500
# shortcut never worse in 441 of 441 load pairs; strictly better in 400
#    (ties only when x_sv = 1 or x_wt = 1)
# demand   no shortcut   shortcut (UE)   shortcut (SO)
#  0.500       1.250         1.000           1.000
#  0.667       1.333         1.333           1.250
#  1.000       1.500         2.000           1.500
#  1.500       1.750         2.000           1.750
#  2.000       2.000         2.000           2.000
#  2.500       2.250         2.250           2.250
# classic example, demand 6: 83.0 -> 92.0
#   the added link hurts for demand between 2.58 and 8.89

Without the shortcut, traffic splits equally between the two routes; each road of delay xx carries 0.5, and the travel time is 0.5+1=1.50.5 + 1 = 1.5. With the shortcut, the user equilibrium puts all traffic on s→v→w→ts \to v \to w \to t; both congestible roads are full and the travel time is 1+0+1=21 + 0 + 1 = 2. Everyone is a third slower than before, while the system optimum still ignores the shortcut and splits traffic equally, for an average of 1.5.

Why does no one want to leave the shortcut? The shortcut route takes xsv+xwtx_{sv} + x_{wt}, the other two take xsv+1x_{sv} + 1 and 1+xwt1 + x_{wt}. Since no road carries more than 1, the shortcut is never slower than the other two. The program checks this on 441 combinations of loads: the shortcut is never slower in any of them, strictly faster in 400, and ties only when a congestible road is full (xsv=1x_{sv} = 1 or xwt=1x_{wt} = 1). Taking the shortcut is therefore a weakly dominant strategy for everyone, and the outcome when everyone takes it lies exactly at the tie: all three routes take 2.

Note

Two corrections. The author’s framework says “the two routes have delay functions tA(x)=xt_A(x) = x and tB(x)=1t_B(x) = 1”. More precisely, each route is made of one road of delay xx and one road of constant delay, arranged crosswise; if one route were entirely xx and the other entirely 1, that would be Pigou’s network of Chapter 2, and there would be nowhere to put a shortcut. The framework also calls the shortcut a “strictly dominant strategy”; strictly speaking it is weakly dominant: never worse, but equal to the others at the equilibrium. This “xx and 1” version is the simplified textbook form; Braess’s own numerical example of 1968 has demand 6, delay functions 10x10x and x+50x + 50, and a new road x+10x + 10, with travel time rising from 83 to 92 when the road is added (Braess et al. 2005); it is also the example most often quoted when the paradox is introduced (Nagurney 2010). The last part of the program reproduces it.

The paradox does not appear at every level of demand. The table shows that at demand 0.5 the shortcut lowers everyone’s time from 1.25 to 1.0; at demand 2/3 the two are equal; for demand between 2/3 and 2 the shortcut worsens the equilibrium (worst at demand 1, 2.0 against 1.5); and from demand 2 onward the congestible roads are already slower than the constant ones, the shortcut is unused and the paradox disappears. The larger example behaves the same way: the added road hurts only for demand between about 2.58 and 8.89. Nagurney discussed this “negation of the Braess paradox as demand increases” in 2010 and computed that in this example the new road stops being used once demand reaches 8898\frac{8}{9} (Nagurney 2010).

Left: Braess’s network; the dashed arrow is the zero-delay shortcut. Right: average travel time as demand varies. For demand between 2/3 and 2 (grey band), the selfish equilibrium with the shortcut (purple) is slower than without it (green); the system optimum with the shortcut (gold, dotted) is never worse than without it.

In real road networks

Evidence

Model estimates on real road networks. In 2008 Youn, Gastner and Jeong computed the user equilibrium and the system optimum on the real street networks of Boston, London and New York (217 to 319 road segments each), using a standard congestion function. In Boston the price of anarchy (Chapter 2) peaked at about 1.30 at 10,000 vehicles per hour; in London it reached about 24 % above the optimum, and in New York about 28 % at 12,000 vehicles per hour. They also identified “Braess roads” whose closure in the model would lower equilibrium travel time: 6 in their Boston calculation and 7 in London, and 12 in New York (Youn et al. 2008).

These are conclusions within a model: the networks are real, but demand and delay functions are assumed, and drivers fully rational and informed. Anecdotes about cities where “traffic improved after a road was closed” are often repeated; the author found no systematic before-and-after data and does not treat them as evidence. The laboratory evidence discussed in Chapter 8 is more direct: in controlled route-choice experiments, participants in networks with an added link did converge to the worse equilibrium (Rapoport et al. 2009).

Springs, strings and circuits

Evidence

The paradox in mechanics and circuits. In a 1991 paper in Nature, Cohen and Horowitz described a mechanical version. A spring hangs from a support; its lower end is tied by a short string to a second spring, from which a weight hangs. Two longer “safety” strings, one from the support to the top of the second spring and one from the bottom of the first spring to the weight, hang slack. When the short middle string is cut, the springs change from being in series to being in parallel, each through a safety string; each now carries only half the weight and stretches less, and the weight rises. The numbers they give are a support-to-weight distance falling from about 1.5 m to about 1.25 m. They also gave an electrical version, with resistors in place of springs and Zener diodes in place of inextensible strings, in which adding a branch to the circuit raises the total voltage drop, and they pointed out that these physical paradoxes are closely related to Braess’s traffic paradox (Cohen and Horowitz 1991).

Traffic network Spring–string network Circuit
flow tension current
delay ce=be+aexc_e = b_e + a_e x length = string length + tension / spring constant voltage = Zener voltage + current × resistance
road whose delay rises with flow (ae>0a_e > 0) spring resistor
road of fixed delay (beb_e) inextensible string Zener diode
unused route slack string non-conducting diode
common travel time support-to-weight distance voltage across the terminals

Calculation

# One equilibrium problem, three physical readings (after Cohen and Horowitz 1991).
# Element "cost" = b + a x: traffic (time = free time + congestion), spring + string
# (length = string length + force / k), resistor + Zener diode (voltage = Zener voltage
# + I R). Flow = traffic, force or current. The equilibrium is found by minimising
# Beckmann's potential (sum over elements of the integral of cost) on a fine grid of
# splits: for springs this is the complementary energy, for circuits the content. A path
# whose cost exceeds the common value carries no flow (an unused road, a slack string, a
# diode that does not conduct).

def braess(flex, fixed, link):
    """Two load-dependent elements (a = flex), two fixed ones (b = fixed), middle link."""
    return {"s1": (flex, 0), "f1": (0, fixed), "f2": (0, fixed), "s2": (flex, 0),
            "m": (0, link)}

PATHS = [("s1", "f1"), ("f2", "s2"), ("s1", "m", "s2")]

def evaluate(net, f):
    x = {k: sum(q for p, q in zip(PATHS, f) if k in p) for k in net}
    phi = sum(b * x[k] + a * x[k] ** 2 / 2 for k, (a, b) in net.items())
    cost = [sum(net[k][1] + net[k][0] * x[k] for k in p) for p in PATHS]
    return phi, cost

def equilibrium(net, load, link=True, n=200):
    splits = [(load * i / n, load * j / n, load * (n - i - j) / n)
              for i in range(n + 1) for j in range(n + 1 - i) if link or i + j == n]
    f = min(splits, key=lambda s: evaluate(net, s)[0])
    phi, cost = evaluate(net, f)
    return f, max(c for c, q in zip(cost, f) if q > 1e-12), phi

CASES = [("traffic: time x, time 1, shortcut 0, demand 1", 1, 1, 0, 1, "units"),
         ("springs k=1 N/m, safety strings 1 m, link string 0 m, weight 1 N",
          1, 1, 0, 1, "m"),
         ("Cohen-Horowitz numbers: link string 0.5 m, weight 0.5 N", 1, 1, 0.5, 0.5, "m"),
         ("circuit: 1 ohm, 1 V Zener diodes, bridging wire, 1 A", 1, 1, 0, 1, "V")]
for lab, a, b, link, load, unit in CASES:
    net = braess(a, b, link)
    f3, with_link, phi = equilibrium(net, load)
    f2, without, _ = equilibrium(net, load, link=False)
    print(f"{lab}\n   with the middle link {with_link:.2f} {unit} (flows "
          + " ".join(f"{q:.2f}" for q in f3) + f"); without it {without:.2f} {unit}")
net = braess(1, 1, 0)
f, _, phi = equilibrium(net, 1)
total = sum(q * c for q, c in zip(f, evaluate(net, f)[1]))
print(f"at the equilibrium: potential {phi:.4f} (its minimum over 20,301 splits),"
      f" total cost {total:.2f};\n   the split 0.5/0.5/0 has potential "
      f"{evaluate(net, (0.5, 0.5, 0))[0]:.4f} but total cost 1.50")
# traffic: time x, time 1, shortcut 0, demand 1
#    with the middle link 2.00 units (flows 0.00 0.00 1.00); without it 1.50 units
# springs k=1 N/m, safety strings 1 m, link string 0 m, weight 1 N
#    with the middle link 2.00 m (flows 0.00 0.00 1.00); without it 1.50 m
# Cohen-Horowitz numbers: link string 0.5 m, weight 0.5 N
#    with the middle link 1.50 m (flows 0.00 0.00 0.50); without it 1.25 m
# circuit: 1 ohm, 1 V Zener diodes, bridging wire, 1 A
#    with the middle link 2.00 V (flows 0.00 0.00 1.00); without it 1.50 V
# at the equilibrium: potential 1.0000 (its minimum over 20,301 splits), total cost 2.00;
#    the split 0.5/0.5/0 has potential 1.2500 but total cost 1.50

One solver gives the results for all three systems. With unit parameters (weight 1 N, spring constant 1 N/m, safety strings 1 m, middle string of length 0), the distance is 2 m with the middle string and 1.5 m after it is cut, exactly the 2 and 1.5 of the traffic network; in the circuit the voltage drop is 2 V with the bridging wire and 1.5 V without it. With Cohen and Horowitz’s numbers (middle string 0.5 m, weight 0.5 N), the distance changes from 1.5 m to 1.25 m, in agreement with the values they report.

The isomorphism is not a coincidence. In a traffic network the user equilibrium minimises Beckmann’s potential ∑e∫0xece(u)du\sum_e \int_0^{x_e} c_e(u)\,\mathrm{d}u (Beckmann et al. 1956); the program in fact finds each equilibrium by “searching 20,301 splits for the one with the smallest potential”: the minimum, 1.0000, is at everyone-on-the-shortcut, where total cost is 2.00, while the even split, whose total cost is only 1.50, has a potential of 1.2500. In a structure of springs and strings under a given weight, the equilibrium minimises the “complementary energy”; in a circuit of resistors and ideal diodes, the distribution of currents fixed by Kirchhoff’s laws minimises the circuit’s “content” (the sum over elements of the integral of voltage with respect to current). All three minimise the same quantity, not the total cost: like selfish drivers, a physical system obeys only local equilibrium conditions.

Note

Braess-like effects in power grids are a different matter. In 2012 Witthaut and Timme found in oscillator models of alternating-current grids that adding a transmission line in an already heavily loaded region can make generators and loads lose synchrony and cause an outage; they called this Braess’s paradox in oscillator networks, and traced it to the new line adding a constraint on phase relationships that cannot be satisfied together with the others (Witthaut and Timme 2012). This is related to the isomorphism of this chapter, but the mechanism differs: power flow in an AC grid is set by phase differences, not by “each unit of current choosing the cheapest route”. Where the author’s framework lists traffic networks, power grids and spring networks together as “isomorphic”, this book writes the isomorphism only for springs and direct-current circuits and treats the power grid as a related phenomenon.

Hypothesis · not established

The fast-track hypothesis (not yet established). The author conjectures that “fast tracks” open to all requests in organisations often have the structure of Braess’s network: they make the few key people who each handled one kind of business the compulsory passage for all business. The testable prediction is that after such a fast track is introduced, the average handling time of all requests rises. If a pre-registered stepped introduction shows that average handling time did not rise, the hypothesis is refuted. Step 1 of the Chapter 8 checklist gives a fictional example.

Summary

The user equilibrium requires all used routes to be equally fast; the system optimum requires total cost to be as low as possible; the two differ by the marginal delay each person adds for others. In Braess’s diamond network a zero-delay shortcut, weakly dominant for each person, raises everyone’s travel time from 1.5 to 2.0, while the optimum ignores it; the paradox appears only in a range of demand. The same conditions describe springs and strings and direct-current circuits. The next chapter asks how much worse than the optimum selfish choices can be.

References

Beckmann, Martin J., C. B. McGuire, and Christopher B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press.
Braess, Dietrich. 1968. “Über Ein Paradoxon Aus Der Verkehrsplanung.” Unternehmensforschung 12: 258–68. https://doi.org/10.1007/BF01918335.
Braess, Dietrich, Anna Nagurney, and Tina Wakolbinger. 2005. “On a Paradox of Traffic Planning.” Transportation Science 39 (4): 446–50. https://doi.org/10.1287/trsc.1050.0127.
Cohen, Joel E., and Paul Horowitz. 1991. “Paradoxical Behaviour of Mechanical and Electrical Networks.” Nature 352: 699–701. https://doi.org/10.1038/352699a0.
Nagurney, Anna. 2010. “The Negation of the Braess Paradox as Demand Increases: The Wisdom of Crowds in Transportation Networks.” EPL (Europhysics Letters) 91 (4): 48002. https://doi.org/10.1209/0295-5075/91/48002.
Rapoport, Amnon, Tamar Kugler, Subhasish Dugar, and Eyran J. Gisches. 2009. “Choice of Routes in Congested Traffic Networks: Experimental Tests of the Braess Paradox.” Games and Economic Behavior 65 (2): 538–71. https://doi.org/10.1016/j.geb.2008.02.007.
Wardrop, John Glen. 1952. “Some Theoretical Aspects of Road Traffic Research.” Proceedings of the Institution of Civil Engineers 1 (3): 325–62. https://doi.org/10.1680/ipeds.1952.11259.
Witthaut, Dirk, and Marc Timme. 2012. “Braess’s Paradox in Oscillator Networks, Desynchronization and Power Outage.” New Journal of Physics 14: 083036. https://doi.org/10.1088/1367-2630/14/8/083036.
Youn, Hyejin, Michael T. Gastner, and Hawoong Jeong. 2008. “Price of Anarchy in Transportation Networks: Efficiency and Optimality Control.” Physical Review Letters 101 (12): 128701. https://doi.org/10.1103/PhysRevLett.101.128701.

Fan, Y. (2026). Algorithmic Game Theory, Braess's Paradox and the Price of Anarchy in Traffic and Attention Networks: From Wardrop Equilibria and Selfish Routing to Platform Congestion, Read Beside Classical Chinese Hydraulic Engineering [算法博弈论、布雷斯悖论与流量分配的无秩序代价] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23782094 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).