Uncertainty-weighted graph allocation
DefinitionFairReplay_Supplement_gaussAllocfairness-testinginformation-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-testing
For a residual graph and standard deviations , the graph allocation is the convex program
One sample at an active vertex serves every incident fairness edge; captures this reuse. For unit variances one edge costs and the clique costs .
Formalization Note The value is the real infimum of the feasible objective values. The feasible set is nonempty and the values are nonnegative, so the infimum is genuine (and attained). With no edges the value is .
Definition code
import Mathlib
import Definitions.Def_FairReplay_Supplement_activeVertices
namespace FairReplay.Supplement
/-- **The uncertainty-weighted graph allocation** `Ψ(H, ν)` (Sah, Zhang, Lian, *Testing Fairness of
Evolving Software under Uncertainty*, STOC 2027 submission, manuscript of 2026-11-03,
sha256 e23940a0…, §3, eq. (3), p.3 (PDF p.5)):
`Ψ(H, ν) = min_{q_v > 0, v ∈ V+(H)} { Σ_{v ∈ V+(H)} q_v : ν²_u/q_u + ν²_v/q_v ≤ 1, (u, v) ∈ E(H) }`.
`gaussAlloc H ν` is the infimum of `Σ_{v ∈ V+(H)} q_v` over allocations `q` that are positive on the
active vertices and satisfy `ν_u²/q_u + ν_v²/q_v ≤ 1` on every edge of `H`.
**Formalization Note** The value is a real `sInf`. The feasible set is nonempty (a large constant
allocation is feasible) and the values are nonnegative, so the infimum is a genuine one; it is
attained (every feasible `q` has `q_v ≥ ν_v²` on `V+(H)`), matching the paper's `min`. Coordinates of
`q` off `V+(H)` are unconstrained and do not enter the sum. With no edges the value is `0`. -/
noncomputable def gaussAlloc {n : ℕ} (H : SimpleGraph (Fin n)) [DecidableRel H.Adj]
(ν : Fin n → ℝ) : ℝ :=
sInf {t : ℝ | ∃ q : Fin n → ℝ, (∀ v ∈ activeVertices H, 0 < q v) ∧
(∀ u v, H.Adj u v → ν u ^ 2 / q u + ν v ^ 2 / q v ≤ 1) ∧
t = ∑ v ∈ activeVertices H, q v}
end FairReplay.Supplement
Source
Sah, Zhang, Lian, Testing Fairness of Evolving Software under Uncertainty, STOC 2027 submission (manuscript of 2026-11-03, sha256 e23940a0a0f5960aedaf6aba60adc41e966efc604b6379b3180b06590610d025), §3, eq. (3), p.3 (PDF p.5)