ADR-013: multiclass — Dafermos (1972) multiclass-user equilibrium

Status: accepted (implemented) Date: 2026-07-09 Deciders: static-extensions track — the multiclass half of the “multiclass / VI” roadmap item File: docs/design/adr-013-multiclass.md

Context

vi-asym (adr-011) shipped the single-class asymmetric variational inequality t(v) = t_BPR(v) + C v. adr-011 explicitly deferred the multiclass case (Dafermos 1972) for one reason: certifying a per-class Wardrop condition needs per-class link flows, but FlowState.link_flows / Trace / Evaluator.evaluate were all hardwired to a single aggregate (n_links,) vector — a harness-contract change, not a self-contained model.

Dafermos (1972, Transportation Science 6(1):73-87, dafermos1972traffic) generalizes UE to K user classes that share the network but perceive class-specific, mutually-coupled costs. Each class i routes its own demand g^i to a Wardrop equilibrium in its cost t^i, but every class’s cost depends on the joint flow, so the equilibria are simultaneous. Stacking the class-indexed flows V = (v^1, ..., v^K) this is a block-structured single-class asymmetric VI

find V* in K = K_1 x ... x K_K  s.t.  <T(V*), V - V*> >= 0  for all V in K,

i.e. exactly vi-asym promoted one level up (K = 1 recovers it) — with two genuinely new ingredients: the feasible set is a product of per-class demand polytopes (routing is per class), and the emitted flow gains a class axis. Dafermos (1972)’s specific contribution is the model and the symmetry condition under which it reduces to a single convex program (the integrable case); the genuinely-asymmetric VI with no equivalent optimization is Smith (1979) / Dafermos (1980).

Decision

  1. Cost model (linear class interaction). t_a^i(V) = t_a^BPR(v_a) + sum_j M_ij v_a^j, where v_a = sum_j v_a^j is the total link flow and M = scenario.multiclass.interaction is a (K, K) matrix applied per link. M is what makes the per-class split well-defined: with M = 0 every class sees the identical cost t_a^BPR(v_a) and the split is arbitrary (the model degenerates to single-class UE on the summed demand). A symmetric M is the integrable case (the equilibrium minimizes a convex multiclass-Beckmann potential; Dafermos 1972); an asymmetric M is a genuine VI with no equivalent optimization (Smith 1979; Dafermos 1980). This is the block-diagonal generalization of vi-asym’s C.

  2. Schema — MulticlassDemand + Scenario.multiclass. A new frozen dataclass (core/scenario.py) holds matrices ((K, n_zones, n_zones), K >= 2 per-class OD) and interaction ((K, K)). It is referenced by a new optional Scenario.multiclass field, content-hashed only when present (appended last, after link_interaction), so every scenario without it — the golden Braess instance included — hashes byte-identically (cf00f411… re-asserted in tests/test_multiclass.py). It is mutually exclusive with the other six optional task fields, and the aggregate demand is validated to equal the class sum so every single-class consumer of demand (feasibility scale, fairness gate, aggregate loading) stays consistent.

  3. Output-contract change (the crux adr-011 deferred), done additively. An OPTIONAL class_link_flows: (K, n_links) | None is added to FlowState and Trace.record, defaulting to None. Every single-class model leaves it None, so their emissions, the aggregate link_flows contract, and the CSV schema are byte-identical to before this field existed (the full suite is the guard). It is a first-class emitted object, not a self_report entry — so the harness recomputes the per-class VI residual from it (P1), never trusts it. When present, link_flows is the class sum. This is the additive form of exactly the reshape adr-011 flagged as the “real” fix: no existing signature changes, no existing model touched.

  4. Solver multiclass (models/multiclass.py, MulticlassModel, paradigm static_ue_multiclass). Multiclass diagonalization (nonlinear Gauss-Seidel): sweep the classes; for class i freeze the other classes’ flows, which makes class i’s cost separable in its own flow — an ordinary single-class UE that Frank-Wolfe (exact Brent line search on the diagonalized cost) solves — then relax v^i <- v^i + step (v^i_inner - v^i) and use each class’s updated flow immediately. It reuses vi-asym’s inner FW verbatim, once per class. K = 1 would collapse to vi-asym. Convergence follows the Dafermos (1982) / Florian & Spiess (1982) diagonal-dominance condition, not monotonicity alone; a coupling that drives a cost non-positive stops the sweep and emits a flow the certificate censors (never a false accept).

  5. Certificate (P1). The harness recomputes, from the emitted V, the class-summed VI residual — the product feasible set makes the VI gap decompose into per-class all-or-nothing minima:

    gap = (sum_i <t^i(V), v^i> - sum_i min_{y^i in K_i} <t^i(V), y^i>) / sum_i <t^i(V), v^i>,

    the ordinary relative gap summed over classes at the coupled cost (0 iff V solves the multiclass VI). Feasibility is a per-class conservation audit (each class routes its own demand). beckmann_objective is NaN (no potential for an asymmetric M). No new scored CSV key: the residual reuses relative_gap / average_excess_cost. A multiclass scenario emitted without per-class flows is censored (an aggregate flow cannot certify a per-class equilibrium).

  6. Analytic anchors (multiclass_two_route_scenario, both recomputed in the tests). Diamond routes 1->3->2 / 1->4->2, two classes (cars g=4, trucks g=2), zero BPR slopes so congestion is purely the per-link M. Because a 2-link route applies the per-link coupling on both legs, the route-level coupling is 2 M, and the equilibrium route-A flows solve 4 M [p - g_cars/2, q - g_trucks/2]^T = [a2, a2]^T, i.e. [p, q] = [g_cars/2, g_trucks/2] + (a2/4) M^{-1} [1,1]^T:

    • symmetric M = [[0.5, 0.25], [0.25, 0.5]] → cars (2.5, 1.5), trucks (1.5, 0.5), aggregate (4, 4, 2, 2), class costs equalized 3.25 / 2.75 — the integrable / multiclass-Beckmann check;

    • asymmetric M = [[0.5, 0.5], [0, 0.5]] (trucks slow cars, not vice versa) → cars (2, 2), trucks (1.75, 0.25), aggregate (3.75, 3.75, 2.25, 2.25) — a genuine-VI flow no Beckmann/FW solver reaches; classes route differently (the multiclass signature). All values are exact multiples of 0.125.

Alternatives considered

  • Breaking reshape of link_flows to (K, n_links) everywhere: rejected — it would touch all 25 single-class models and the CSV schema. The optional class_link_flows field is the additive equivalent (this ADR is the realization of adr-011’s deferred item, done without a breaking change).

  • Per-class flows in self_report: rejected — the certificate would then be recomputing a scored metric from a trusted self-report, violating P1. Per-class flows must be a first-class emitted object to keep the residual harness-pure.

  • Nonlinear / flow-dependent PCE coupling (Riente de Andrade et al. 2017): deferred — the linear M is the minimal faithful coupling that gives a closed-form anchor and reuses vi-asym’s affine machinery; a flow-dependent interaction is a separately-scoped follow-up.

  • A dedicated sequential multiclass solver instead of reusing vi-asym’s FW: the per-class diagonalized subproblem is an ordinary UE, so the established FW+brentq inner loop is reused rather than reimplemented.

Consequences

The benchmark gains its first multiclass-user equilibrium model and its first per-class-flow output, with a sound, harness-recomputed VI certificate and hand-derived integrable + genuine-VI anchors. The class_link_flows extension is additive: every prior model and the golden Braess hash are provably unchanged. Follow-ups: flow-dependent-PCE coupling, per-link (rather than uniform) M, and reporting the per-class residual breakdown alongside the class sum.

Sourcing

Dafermos (1972, Transportation Science 6(1):73-87, dafermos1972traffic, DOI 10.1287/trsc.6.1.73, Crossref-verified) is the multiclass model and the symmetry/integrability condition; Smith (1979, smith1979existence) and Dafermos (1980, dafermos1980traffic) are the asymmetric-VI characterization; the diagonalization / relaxation convergence is Dafermos (1982) / Florian & Spiess (1982). All three primaries were already in the verified reference canon. The block-VI reading and both analytic anchors are hand-derived here (cross-verified against an independent multiclass diagonalization); no number from any paper is reproduced.