What does Extra Entries, Extra Layers conclude, in numbers, about “Frank and Wolfe in the Standard Library: Equilibrium, Optimum and the Relative Gap”?

Answer: Program p31 reproduces 83.0000 and 92.0000 on Braess's network, with link flows equal to the exact fractions. Program p32 shows that Frank and Wolfe with a line search brings the gap to 1.588e-03 by the tenth step, while successive averages is still at 3.952e-04 after three hundred. Program p33 uses the same code to find the system optimum: the new entry lowers the optimal average from 12.030 to 11.397 but raises the user equilibrium from 12.200 to 16.000, a ratio of 1.4039. The next chapter hands these tools to the shop owner: from minutes to orders, and then closing entries one at a time to see which one is the Braess link.

Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (21 programs), classical sources and the author's hypotheses.

中文版

Data table

The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: -03, -04, 1.588, 16.000, 3.952

iterations Frank-Wolfe gap successive-averages gap
17.466e-02 3.580e-01
33.032e-02 1.765e-01
101.588e-03 4.326e-03
308.352e-05 4.326e-03
1007.260e-09 2.650e-03
3000.000e+00 3.952e-04
equilibrium at 300 iterations, average wait 16.000 minutes
live Q&A load 2.739 wait8.000
live->page load 0.314 wait7.000
pay load 0.575 wait1.000
order desk load 2.425 wait6.999
search load 0.261 wait8.000
search->page load 0.261 wait7.000
NEW live->desk load 2.425 wait1.001
Show the full program
# Chapter 3. p32: how fast does Frank-Wolfe close the gap, against the
# method of successive averages (step 1/k) that many spreadsheets use?
# Network: the purchase funnel of Chapter 4 with the new live-room ->
# order-desk entry open, 300 buyers an hour (illustrative). Waits follow
# the BPR form t0 (1 + 0.15 (x / c)^4) of the US Bureau of Public Roads.
# Relative gap = (total wait - demand * shortest route) / total wait.
import heapq
import math

# (from, to, free minutes, capacity in hundreds of buyers an hour)
FUNNEL = [("V", "L", 3.0, 1.5),    # live-room Q&A, host attention
          ("L", "C", 7.0, 9.0),    # live link to the product page
          ("C", "T", 1.0, 9.0),    # self-service payment
          ("V", "P", 9.0, 9.0),    # private-chat article
          ("P", "K", 1.0, 9.0),    # article to the order desk
          ("K", "T", 2.0, 1.2),    # human order desk queue
          ("V", "S", 8.0, 9.0),    # search and catalogue
          ("S", "C", 7.0, 9.0)]    # catalogue to the product page
NEW = ("L", "K", 1.0, 9.0)         # new entry: live room -> order desk
NAMES = ["live Q&A", "live->page", "pay", "chat page", "chat->desk",
         "order desk", "search", "search->page", "NEW live->desk"]


def cost(link, x):
    # BPR wait: free time * (1 + 0.15 (load / capacity)^4)
    return link[2] * (1.0 + 0.15 * (x / link[3]) ** 4)


def mcost(link, x):
    # marginal social cost: wait + load * d(wait)/d(load)
    return link[2] * (1.0 + 0.75 * (x / link[3]) ** 4)


def shortest(links, times, s, t):
    adj = {}
    for k, link in enumerate(links):
        adj.setdefault(link[0], []).append((link[1], k))
    dist, back, heap = {s: 0.0}, {}, [(0.0, s)]
    while heap:
        du, u = heapq.heappop(heap)
        if du > dist.get(u, math.inf):
            continue
        for v, k in adj.get(u, []):
            nd = du + times[k]
            if nd < dist.get(v, math.inf) - 1e-12:
                dist[v], back[v] = nd, k
                heapq.heappush(heap, (nd, v))
    path, node = [], t
    while node != s:
        k = back[node]
        path.append(k)
        node = links[k][0]
    return dist[t], path


def frank_wolfe(links, d, iters=300, f=cost, s="V", t="T"):
    def aon(x):
        times = [f(lk, xe) for lk, xe in zip(links, x)]
        c, path = shortest(links, times, s, t)
        y = [0.0] * len(links)
        for k in path:
            y[k] = d
        return y
    x = aon([0.0] * len(links))
    for _ in range(iters):
        y = aon(x)

        def slope(a):
            return math.fsum((ye - xe) * f(lk, xe + a * (ye - xe))
                             for lk, xe, ye in zip(links, x, y))
        if slope(1.0) <= 0:
            a = 1.0
        else:
            lo, hi = 0.0, 1.0
            for _ in range(60):
                mid = (lo + hi) / 2
                if slope(mid) > 0:
                    hi = mid
                else:
                    lo = mid
            a = (lo + hi) / 2
        x = [xe + a * (ye - xe) for xe, ye in zip(x, y)]
    return x


def average(links, x, d):
    return math.fsum(xe * cost(lk, xe) for lk, xe in zip(links, x)) / d


def gap(links, x, d):
    times = [cost(lk, xe) for lk, xe in zip(links, x)]
    c = shortest(links, times, "V", "T")[0]
    tot = math.fsum(xe * te for xe, te in zip(x, times))
    return max(0.0, (tot - d * c) / tot)


def msa(links, d, iters):
    x = None
    for k in range(1, iters + 1):
        base = x if x is not None else [0.0] * len(links)
        times = [cost(lk, xe) for lk, xe in zip(links, base)]
        path = shortest(links, times, "V", "T")[1]
        y = [d if j in path else 0.0 for j in range(len(links))]
        if x is None:
            x = y
        else:
            x = [xe + (ye - xe) / k for xe, ye in zip(x, y)]
    return x


NET = FUNNEL + [NEW]
D = 3.0
print("iterations   Frank-Wolfe gap   successive-averages gap")
for n in (1, 3, 10, 30, 100, 300):
    g1 = gap(NET, frank_wolfe(NET, D, iters=n), D)
    g2 = gap(NET, msa(NET, D, n), D)
    print("  %5d        %.3e          %.3e" % (n, g1, g2))
x = frank_wolfe(NET, D, iters=300)
print()
print("equilibrium at 300 iterations, average wait %.3f minutes"
      % average(NET, x, D))
for name, xe, lk in zip(NAMES, x, NET):
    if xe > 1e-6:
        print("  %-15s load %.3f  wait %6.3f"
              % (name, xe, cost(lk, xe)))

Single source and citation

Fan, Y. (2026). Braess's Paradox and Wardrop Equilibrium: When One More Purchase Entry or One More Coordination Layer Slows Everyone Down (Version 1.0.0), Chapter 3: Frank and Wolfe in the Standard Library: Equilibrium, Optimum and the Relative Gap. 5D Library. DOI pending

DOI pending · monograph page goes live after publication · 5DL-B-246 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026246,
  author    = {Fan, Yafu},
  title     = {Braess's Paradox and Wardrop Equilibrium: When One More Purchase Entry or One More Coordination Layer Slows Everyone Down},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  note      = {DOI pending}
}

Other chapter answers in this book