ADR-019: vickrey — Vickrey (1969) single-bottleneck departure-time equilibrium

Status: accepted (implemented) Date: 2026-07-09 Deciders: analytical-DTA track — the first departure-time-equilibrium model File: docs/design/adr-019-vickrey.md

Context

The analytical-DTA track opens with Vickrey’s (1969) single-bottleneck model — the canonical departure-time equilibrium. N travelers each choose a departure time to trade point-queue delay at a bottleneck of capacity s against schedule delay relative to a desired arrival t* (early penalty beta, late gamma, travel-time value alpha, with 0 < beta < alpha). This is a different paradigm from the repo’s route-choice and link-loading models — there is no network topology, just six scalars and a departure-rate decision — so it gets its own parallel module, exactly as transit/ and dnl/ did (ADR-014/010).

Decision

  1. A parallel module src/tabench/bottleneck/ touching no road/DNL/transit code (the golden Braess hash cf00f411… re-asserted in the tests). BottleneckScenario (scenario.py) is the six scalars, frozen and content-hashed under a "tabench-bottleneck-scenario-v1;" domain prefix.

  2. Closed-form UE and SO (solve.py), each emitting a BottleneckSchedule — a cumulative departure curve R(t) on a time grid, the P1-certifiable artifact (analogue of FlowState/TransitStrategy). The UE queue-builds at r_early = s·alpha/(alpha-beta) on [t1, t_n] then queue-dissipates at r_late = s·alpha/(alpha+gamma) on [t_n, t2], with t1 = t* - C*/beta, t2 = t* + C*/gamma, t_n = t* - C*/alpha, and C* = beta·gamma/(beta+gamma)·N/s. The SO meters departures uniformly at s over the same window (no queue).

  3. P1 certificate (metrics/bottleneck_gaps.py, BottleneckEvaluator). From (scenario, emitted R(t)) alone — never the solver’s r_early/t1/C* provenance — the harness simulates the deterministic point queue n_{k+1} = max(0, n_k + dR_k - s·dt), recomputes each used departure time’s generalized cost c(t) = alpha·T + beta·[t*-(t+T)]+ + gamma·[(t+T)-t*]+ (T = n/s), and scores equilibrium_gap = (max c - min c)/C* over used departure times — 0 iff no traveler can improve by shifting (a user equilibrium), positive otherwise. Feasibility gates on conservation (R ends at N), monotonicity, and the scenario hash. Total/expected cost, max queue, and total travel delay are recomputed and reported.

Analytic anchors (machine-verified — test_bottleneck.py)

Worked instance N=6000, s=3000, alpha=1, beta=0.5, gamma=2, t*=9:

  • C* = 0.8; window t1=7.4, t2=9.4 (width N/s = 2); peak t_n=8.2; r_early=6000, r_late=1000; max queue 2400; UE total 4800, mean 0.8.

  • The UE certifies equilibrium_gap = 0 (every used departure time yields exactly C*), while the SO certifies a positive gap (uniform metering spreads schedule delay, so it is not a departure-time equilibrium) with no queue and total 2400.

  • Price of anarchy = 2 for any beta, gamma (UE_total / SO_total = 2, a general bottleneck result, regression-fuzzed over random penalties — not just the symmetric case).

  • A schedule perturbed off the equilibrium curve certifies a positive gap; non-conserving / non-monotone / wrong-hash schedules are censored.

Alternatives considered

  • Reusing the DNL point queue (dnl/_reference.py::PointQueueLink): rejected — that is a numerical loading kernel driven by a grid loop; Vickrey is an analytic departure-time equilibrium over a decision (the departure rate), with a schedule-delay objective the DNL machinery has no notion of. The certifier’s own tiny point-queue recomputation keeps the module self-contained.

  • Trusting the solver’s C*/rates: rejected (P1) — the certifier recomputes the queue and costs from the emitted curve, so it certifies any departure-time schedule (a future heuristic/learned solver included), not just the closed form.

Adversarial review

The review confirmed the closed form (c(t) ≡ C* re-derived algebraically for any alpha,beta,gamma), the PoA-2 result at extremes, the feasibility gates, hash, and isolation — and caught two real certifier bugs, both fixed:

  • CRITICAL false-accept: the first certifier sampled each step’s cost at the start-of-step queue, so a “burst dump” schedule (all mass at the window boundaries) certified gap ≈ 0 despite a total cost 2.1× the true UE — the intra-step congestion was never seen. Fixed by scoring per traveler: invert both the arrival curve A(t)=R(t) and the bottleneck-served curve D(t) = min(A, D_prev + s·dt) at each count level to get each traveler’s actual departure and exit times (the level-based approach the DNL/transit certifiers use).

  • False-censor: a fixed eps = tol·N “used-step” mask censored legitimate schedules on very fine grids / tiny N. Removed — level sampling needs no such threshold.

Both are regression-pinned (test_burst_dump_is_not_a_false_equilibrium, test_fine_grid_and_small_n_not_false_censored).

Consequences

The benchmark gains its first departure-time equilibrium and the entry point of the analytical-DTA track (Merchant–Nemhauser, Friesz VI-DUE, Ziliaskopoulos LP to follow). All changes are additive (a new module + a new certifier + tests), so the 592-test suite, every road/DNL/transit hash, and the golden Braess content hash are byte-untouched.

Sourcing

Vickrey (1969) “Congestion Theory and Transport Investment,” AER P&P 59(2):251-260 (no DOI; JSTOR 1823678) — attributed. The bottleneck equilibrium closed form is standard textbook; taken from Boyles Transportation Network Analysis Ch. 10 (open, the repo’s own tna_ch10_tdsp.md grounding) and independently re-derived from the first-order equal-cost conditions and machine-verified against a discrete-event queue simulation. Arnott–de Palma–Lindsey (1990, JUE 27(1)) is the standard general-alpha,beta,gamma reference (attributed, not full-text-read). No DOIs or page-precise quotes reproduced.