# ADR-004 — Route-flow proportionality: a diagnostic now, a scored certificate proposed

**Status:** proposed (diagnostic shipped in v1; scored certificate awaits PI decision)
**File:** `docs/design/adr-004-proportionality-certificate.md`

## Context

TAPAS (`tapas`, Bar-Gera 2010) is the first solver whose *point* is a property of route
flows, not link flows. Every UE solver so far is certified on `relative_gap`, which is a
function of link flows alone — and link flows at UE are **unique**. TAPAS converges to the
*proportional* (entropy-consistent) route-flow solution: for every pair of alternative
segments shared by several origins, each origin splits its flow between the two segments
in the **same ratio** (Boyles/Lownes/Unnikrishnan, *Transportation Network Analysis* v1.0,
Theorem 5.4 p. 127; condition eq. 6.94 p. 226; the "condition of proportionality" of
Bar-Gera & Boyce 1999, Bar-Gera 2006, Bar-Gera, Boyce & Nie 2012).

The problem: **proportionality is invisible to link flows.** For a fixed UE link-flow
vector `v*`, the set of route/segment-flow decompositions that produce it is in general a
polyhedron, not a point (Dafermos 1980). Two solvers — or the same solver under different
tie-breaks — can emit byte-identical `v*` while their per-origin segment splits differ
arbitrarily. So the harness **cannot** recompute a proportionality score from `(link_flows,
scenario)` the way P1 requires of every scored metric. The naive fix that works for the UE
gap and for ADR-001/003's SUE residuals — reload `v` at its own induced cost via
all-or-nothing — is not merely biased here, it is *wrong*: an AON reload picks one
arbitrary shortest-path tree per origin, i.e. exactly the tie-broken decomposition that can
show maximal proportionality violation even when `v` is exactly at UE.

This ADR records (a) what v1 ships — a **reported diagnostic**, provenance-only — and (b) a
proposed **scored certificate** whose GO/NO-GO is the maintainer's, because it requires a
genuine P1 trust-boundary change that should not be minted in a solver PR.

## What v1 ships (no decision required) — the proportionality diagnostic

`TapasModel` self-reports, on every checkpoint, from its own PAS bookkeeping:

```
pi_p                = (Σ_{r∈O_p} g^r(σ1)) / (Σ_{r∈O_p} [g^r(σ1)+g^r(σ2)])     # PAS p aggregate share
proportionality_residual = ( Σ_p Σ_{r∈O_p} | g^r(σ1) − w^r · pi_p | ) / D      # eq. 6.94, L1 / total demand
pas_proportionality_max  = max_{p,r} | g^r(σ1)/w^r − pi_p |                     # worst single-origin deviation
```

with `w^r = g^r(σ1)+g^r(σ2)` and `g^r(σ)` the origin-`r` through-flow on segment `σ`. These
are `self_report` scalars — **provenance only, never scored** — exactly like every other
model self-report (P1). The normalization (`L1 / D`, intensive per-traveler) matches the UE
relative gap and the SUE residuals, so the number is cross-scenario comparable.

The diagnostic is meaningful because TAPAS actually drives it down: with the eq. 6.100
proportionality adjustment on, the residual on Sioux Falls falls from ~1.4e-2 (pure UE,
`prop_rounds=0`) to ~7e-8 (`prop_rounds=5`) at the same link flows — the route flows become
proportional. Turned off, TAPAS is a UE solver with arbitrary route flows and the diagnostic
stays large. That contrast is the honest evidence a scored certificate would formalize.

## The scored certificate — proposed, PI to decide

### Decision 1 (proposed) — harness-owned vs model-attested

The central asymmetry vs ADR-003 must be stated up front. ADR-003's auxiliary structure
(the MC perturbation matrix `E`) is **model-blind**: the harness draws it itself from a
documented RNG stream, independent of which solver produced `v`, so pinning it costs no
trust. Proportionality's auxiliary structure **cannot** be model-blind — it *is* the model's
internal route/segment decomposition, and there is no canonical, algorithm-independent
distribution to draw it from. So a scored proportionality certificate must accept
**model-attested, harness-audited** data, not harness-pinned data:

- **Harness-owned (no trust extension):** PAS identification. A PAS (diverge node, merge
  node, two cost-tied positive-flow segments at `t(v)`) is a pure graph object of
  `(v, network)` and can be found by a harness-side label search, reusing `_bush._scan`'s
  min/max DAG labels or `PathEngine`'s shortest-path trees. And the residual formula above,
  given the segment flows, is a pure harness computation.
- **Model-attested (the trust extension):** the origin-disaggregated flow decomposition
  `X[o, a]` (flow origin `o` contributes to link `a`). The harness's only new trust is
  auditing `v = Σ_o X[o, :]` to machine precision — the same "exact resync" invariant
  `algb`/`tapas` already enforce internally every iteration. An `X` that fails the audit
  gets **no** proportionality score (NaN), exactly as flows failing the demand-feasibility
  audit get `feasible=0` today.

### Decision 2 (proposed) — `FlowState` schema

`FlowState` today is `link_flows: np.ndarray` + `self_report: dict[str, float]` (scalars
only). A scored certificate is therefore **architecturally blocked**, not just a policy
choice: it needs a new array-valued field, a **sparse** origin-disaggregated structure
(dense `n_origins × n_links` is infeasible at regional scale — Chicago is ~1,790 origins ×
~39,000 links). This ADR proposes the field but does not add it; only bush/origin solvers
(`algb`, `tapas`) can emit it natively (they already carry `_BushState.x`), and a
certification-cost accounting convention (à la ADR-003's "`R_cert` sp-equivalents per
checkpoint") must be pinned before it is buildable.

### Decision 3 (proposed) — scope and naming

PAS-level (first-order) proportionality is **necessary but not sufficient** for the full
maximum-entropy UE route flow (Bar-Gera 2006; the higher-order "general proportionality
condition", Borchers et al. 2015). A certificate scoped to PAS-level proportionality
certifies Bar-Gera's originally-proposed, practically-testable condition — not full MEUE
optimality. So the eventual scored column must be named **`pas_proportionality_residual`**,
never `proportionality_residual` unqualified or `meue_residual`, and its docs must state the
limitation. (The v1 self-report keeps the shorter `proportionality_residual` name because,
as provenance, it makes no ranking claim.)

### Decision 4 (proposed) — anti-gaming

Unlike ADR-003's harness-drawn `E` (ungameable by construction), a model here supplies its
own audit-passing `X`. The conservation audit (`v = Σ_o X`) rules out inconsistent `X` but
cannot verify that an audit-passing `X` is the *causal* decomposition the algorithm computed
rather than one constructed post hoc to look proportional. This is a strictly harder
anti-gaming surface and is the core of why the GO/NO-GO is the maintainer's call, not a
mechanical follow-on.

## Recommendation

Ship the diagnostic (done). Defer the scored certificate to an explicit maintainer decision
on Decisions 1–4 — in particular whether **model-attested, harness-audited** data is an
acceptable P1 extension at all. If accepted, the free next step is to wire `algb` to emit
the same diagnostic from its already-maintained `_BushState.x`, giving cross-model (algb vs
tapas) evidence before any scored column is minted.

## Sourcing (honesty note)

Consistent with `algb.py`/`tapas.py`: the primary texts Bar-Gera (2006, *Transportation
Science* 40(3):269–286) and Bar-Gera, Boyce & Nie (2012, *TR-B* 46(3):440–462) are
paywalled and were **not** read directly. The condition of proportionality, eq. 6.94, and
the eq. 6.100 restoring shift are taken from the open Boyles/Lownes/Unnikrishnan textbook
(§5.2.2, §6.5.3) — the same source cited for Algorithm B — and cross-verified against
Aungsuyanon, Boyce & Ran (2013) and Li, Wang, Feng, Xie & Nie (2024, arXiv:2401.08013, a
paper co-authored by Y. Nie of the 2012 paper). The necessary-but-not-sufficient caveat
(Bar-Gera 2006) and the higher-order condition (Borchers et al. 2015) are known here only
via those secondary restatements; a maintainer spot-check of the paywalled PDFs is
recommended before any scored certificate is finalized.

## References

- Bar-Gera, H. (2010). Traffic assignment by paired alternative segments.
  *Transportation Research Part B* 44(8–9), 1022–1046.
- Bar-Gera, H. (2006). Primal method for determining the most likely route flows in large
  road networks. *Transportation Science* 40(3), 269–286.
- Bar-Gera, H., Boyce, D. & Nie, Y.M. (2012). User-equilibrium route flows and the condition
  of proportionality. *Transportation Research Part B* 46(3), 440–462.
- Boyles, S.D., Lownes, N.E. & Unnikrishnan, A. (2025). *Transportation Network Analysis*,
  Vol. I, v1.0. §5.2.2, §6.5.3. (open textbook)
- Dafermos, S. (1980). Traffic equilibrium and variational inequalities.
  *Transportation Science* 14(1), 42–54.