# ADR-008 — Boundedly-rational user equilibrium: a band-relaxed UE with a necessary link-flow certificate

**Status:** accepted (shipped in v1)
**File:** `docs/design/adr-008-boundedly-rational-ue.md`

## Context

Every equilibrium so far is *perfectly rational*: at Wardrop UE every used route is exactly
the minimum cost. **Boundedly-rational UE** (Mahmassani & Chang 1987) imports Herbert Simon's
bounded rationality: a traveler does not switch routes to save less than an **indifference
band** `ε` (in native cost units). A flow is an **ε-BRUE** iff for every OD pair and every
route,

```
h_π > 0   ⟹   c_π ≤ κ_rs + ε
```

— used routes lie within an absolute band `ε` above the OD minimum `κ_rs`. This relaxes
Wardrop's *equality* to a one-sided band, with two consequences that this ADR must handle:

1. **The equilibrium is a SET, not a point.** For `ε > 0` the conditions are inequalities, so
   the acceptable flows form a region; the link flows are **not unique** and there is **no
   Beckmann convex program** (Boyles, Lownes & Unnikrishnan, *Transportation Network Analysis*
   ch. 5; the rigorous static set formulation is Di, Liu, Pang & Ban 2013, *TR-B* 57:300–313).
   `ε → 0` recovers Wardrop UE; `ε → ∞` admits *any* feasible flow.
2. **The band is a per-route condition, but the harness sees only link flows.**

## Sourcing

Concept: **Mahmassani & Chang (1987)**, *Transportation Science* 21(2):89–99 — paywalled, a
behavioural (departure-time + route-search) paper, **attributed unread**. The static ε-BRUE
condition, non-uniqueness, and the ε-monotone acceptable set are from **Di–Liu–Pang–Ban
(2013)** and cross-verified in **Boyles TNA ch. 5** (used-path band condition; "no convex
program; link-flow uniqueness not guaranteed"). The absolute band + VI form were cross-checked
against open restatements. No numeric result from the primary is claimed.

## Decision 1 — Represent the band as content-hashed scenario data

`Scenario.br_epsilon: float | None` (`core/scenario.py`) carries the band width. Validated `> 0`
and finite; **mutually exclusive** with `sue_theta` / `elastic_demand` / `combined_demand`
(BR-UE is a deterministic fixed-demand route equilibrium; those make demand non-fixed);
**content-hashed only when set**, appended last, so every existing scenario keeps its
byte-identical hash (golden Braess `cf00f411…` asserted preserved). Two scenarios differing
only in `ε` are different benchmark instances, and the model cannot choose its own `ε`. The
band unit is network-specific (scenario cards state it, P9).

## Decision 2 — Find an acceptable flow at the BAND EDGE (not an early-stopped UE)

`br-ue` (`BoundedlyRationalUEModel`, paradigm `static_br_ue`) reuses the `gp` gradient-projection
skeleton (per-OD path sets, column generation, exact route→link resync) with a **band-thresholded
Newton shift**: from a **pinned free-flow all-or-nothing** start, for each OD pair shift flow off
every route whose cost exceeds the OD minimum by more than the band, onto the cheapest ("basic")
route, by a projected Newton step sized to reduce that route's excess to *exactly* `ε` — not to
zero. Routes already inside the band are never touched (the incentive is boundedly-rational). It
stops at a **rest point** where no used route on any OD exceeds its OD minimum by more than `ε` —
ε-BRUE by construction.

**This is a genuine BR-UE, not a renamed early-stopped UE.** A UE solver stopped at `gap ≤ ε`
truncates the trajectory inside an ε-ball of the *unique* UE point (used-route excess `≈ 0`). The
band-thresholded shift instead stops at the **band edge** (used-route excess `≈ ε`), generally
far from UE, and stable under bounded-rational perturbation. On the two-route anchor the emitted
split is `f_A* + ε/2` (excess exactly `ε`), *not* `f_A*` — the distinctness gate, regression-tested.
Because the shift is a Newton step (not a proportional route swap, which drains a low-flow
out-of-band route only at a rate `∝` its vanishing flow — verified to need ~30× more iterations
and to leave the band violated on congested nets within budget), convergence is fast (one step
per OD on a linear network) and the band is satisfied on congested multi-OD networks (0 band
violations over a 107-net power-4 fuzz). Path-dependence/hysteresis is real (different starts →
different edges); the pinned free-flow-AON start makes it deterministic.

## Decision 3 — A necessary link-flow certificate, honest about its one-sidedness

The identity `TSTT − SPTT = Σ_rs Σ_π h_π (c_π − κ_rs) = D · AEC` makes the average excess cost
the **demand-weighted mean per-traveler excess**. So from link flows the harness scores

```
br_acceptable = 1.0  iff  AEC ≤ ε        (metrics/gaps.py, gated on scenario.br_epsilon)
```

**Necessary:** a true ε-BRUE has every used route within `ε` of `κ`, so mean excess `≤ ε` and
`AEC ≤ ε` — every BR-UE flow passes.

**Not sufficient, and we do not pretend otherwise.** Because `AEC` *averages* excess weighted by
flow, a flow can concentrate a little traffic on a route far outside the band and still average
under it: 1% of an OD's travelers at excess `50ε` and 99% at excess `0` give a per-route
violation of `50ε` yet `AEC = 0.5ε ≤ ε`. This is the **same aggregate-vs-disaggregate limitation
the node-balance audit documents** (and elastic/combined inherit): link flows never carry the
per-route information a fully sufficient check needs (route flows are not emitted). It is
**pinned transparently** by `test_certificate_is_necessary_not_sufficient` (the false accept)
and its complement (a grossly out-of-band flow *is* rejected). The **two-route anchor is the
exception** where per-route band membership *is* link-visible (`|c_A − c_B| ≤ ε` directly), so
the anchor validates tightly; a sufficient longest-positive-flow-path certificate for general
acyclic-positive-flow instances is possible and left as future work.

## Consequences

- **New:** `Scenario.br_epsilon`; paradigm `static_br_ue`; the `br-ue` model; `br_acceptable`
  scored flag; `br_two_route_scenario` anchor (`f_A* = (D+1)/2 = 5.5`, band edge `f_A* + ε/2`,
  half-width `ε/(b_A+b_B)`; at `D=10, ε=1` flows `(6,6,4,4)`, `AEC = 0.6 ≤ 1`, band edge
  regression-tested against the UE's `5.5`); `tabench run --scenario br-tworoute`.
- **Unchanged:** every prior scenario hash (golden Braess preserved); all other certificate
  paths; all prior models and tests.
- **Honest limitation:** the scored `br_acceptable` is necessary, not sufficient (documented,
  pinned) — the one-sidedness is inherent to a link-flow-only certificate for a per-route
  condition.
- **Post-commit hardening (adversarial review).** Two defects were found after the first
  commit and fixed: (M2) `br-ue` no longer honors a caller's Wardrop `target_relative_gap` —
  the wrong stop for a band equilibrium (it could stop before the band and certify a non-BR-UE);
  it stops only on the band rest condition. (M1) the undamped Newton shift can oscillate on
  *extreme* synthetic high-curvature instances; an adaptive `scale` (halve when the true
  `band_excess` rises, recover when it falls) mitigates it while keeping the full step on the
  monotone case. A residual limit remains and is documented in the model: on such pathological
  instances the model may not reach the band within budget, and the necessary-only certificate
  can then false-accept the concentrated residual. Real benchmark networks (Sioux Falls,
  Anaheim) converge cleanly; the sufficient longest-positive-flow-path certificate would close
  the gap and is deferred.
- **Deferred:** the sufficient longest-positive-flow-path certificate (when the positive-flow
  subnetwork is acyclic); per-OD / relative bands; the full path-dependent acceptable-set
  characterisation (Di–Liu–Ban).