Sup norm of additive coefficients, choices and condition (16), and the exponential comparison
DefinitionSubadditiveMMS580_Amplification_Supplement_ReservationGoods form a finite set . Nonnegative additive coefficients are a vector , valued on a bundle by .
- The sup norm , with value zero when is empty.
- A choice is a triple of a reserved set , auxiliary coefficients and a threshold . The empty choice is .
- Condition (16) for a valuation and a target : for every ,
A choice for is one whose coefficients are nonnegative, vanish on , and satisfy (16). 4. Exponential comparison. Let be independent mean-one exponential random variables ( for ). For coefficients put , with an empty maximum equal to zero, and
These objects state the reservation theorem (Theorem 5.2) and the supporting results of §5.2–5.3 and Appendix C.
Formalization Note The competitors are indexed by an arbitrary finite type ; the variables and are the coordinates none and some j of the product probability space under the product of the mean-one exponential laws (Mathlib's expMeasure 1). is the Bochner integral of ; for and this function is integrable (it is at most almost surely), so the integral is the expectation. The file also registers the instance that expMeasure 1 is a probability measure.
import Mathlib
/-!
# Additive coefficients, choices `(H, ṽ, τ)`, condition (16) and the exponential comparison `R_V`
Bo Li, Ankang Sun, *Toward Constant-Factor Maximin Share Guarantees for Subadditive
Valuations*, STOC 2027 submission #580 (October 2026), §5.2, pp. 30–31: the sup norm `‖ṽ‖∞` of
nonnegative additive coefficients (zero on an empty ground set), choices `(H, ṽ, τ)` and the
reservation condition (16), the mean-one exponential variables `Z, Z_1, …, Z_k`,
`V = max_j b_j Z_j` (empty maximum zero) and `R_V(x) = E (xZ − V)^+`.
Conventions. Goods are `Fin m`. Additive coefficients are vectors `a : Fin m → ℝ`, valued on a
bundle by `∑_{g ∈ B} a g`. The variables `Z` and `Z_j` (`j ∈ ι`) are the coordinates of the
product probability space `Option ι → ℝ` under `Measure.pi` of the mean-one exponential law
`ProbabilityTheory.expMeasure 1` (coordinate `none ↦ Z`, `some j ↦ Z_j`).
-/
set_option autoImplicit false
namespace SubadditiveMMS580.Amplification.Supplement
open MeasureTheory ProbabilityTheory
/-- §5.2 (p. 30): `‖ṽ‖∞ = max_{g ∈ M} ṽ(g)`, with value zero when `M` is empty. -/
noncomputable def supNorm {m : ℕ} (a : Fin m → ℝ) : ℝ :=
if h : (Finset.univ : Finset (Fin m)).Nonempty then Finset.univ.sup' h a else 0
/-- §5.2 (p. 31): a triple `(H, ṽ, τ)`: a reserved set `H ⊆ M`, auxiliary additive coefficients
`ṽ` and a threshold `τ ∈ ℝ`. -/
structure Choice (m : ℕ) where
/-- The reserved set `H`. -/
H : Finset (Fin m)
/-- The auxiliary coefficients `ṽ(g)`. -/
coef : Fin m → ℝ
/-- The threshold `τ`. -/
τ : ℝ
/-- §5.2 (p. 31): the empty choice `(∅, 0, 0)`. -/
def emptyChoice (m : ℕ) : Choice m := ⟨∅, fun _ => 0, 0⟩
/-- Condition (16) (p. 31) for a valuation `v` and a target `β`: for every `B ⊆ M \ H`,
`ṽ(B) > τ − ‖ṽ‖∞` implies `v(H ∪ B) ≥ β`. -/
def SatisfiesReservation {m : ℕ} (v : Finset (Fin m) → ℝ) (β : ℝ) (c : Choice m) : Prop :=
∀ B : Finset (Fin m), Disjoint B c.H →
c.τ - supNorm c.coef < ∑ g ∈ B, c.coef g → β ≤ v (c.H ∪ B)
/-- §5.2 (p. 31): `(H, ṽ, τ)` is a choice for `(v, β)`: the auxiliary coefficients are
nonnegative and supported outside `H`, and (16) holds. -/
def IsChoice {m : ℕ} (v : Finset (Fin m) → ℝ) (β : ℝ) (c : Choice m) : Prop :=
(∀ g, 0 ≤ c.coef g) ∧ (∀ g ∈ c.H, c.coef g = 0) ∧ SatisfiesReservation v β c
/-- The mean-one exponential law is a probability measure (`P(Z > t) = e^{-t}`, `t ≥ 0`). -/
instance : IsProbabilityMeasure (expMeasure 1) := isProbabilityMeasure_expMeasure one_pos
/-- §5.2 (p. 31): the joint law of independent mean-one exponential variables `Z` (coordinate
`none`) and `Z_j`, `j ∈ ι` (coordinate `some j`). -/
noncomputable def expPi (ι : Type) [Fintype ι] : Measure (Option ι → ℝ) :=
Measure.pi fun _ : Option ι => expMeasure 1
/-- §5.2 (p. 31): `V = max_j b_j Z_j` at the outcome `ω`, with an empty maximum equal to zero. -/
noncomputable def maxProd {ι : Type} [Fintype ι] (b : ι → ℝ) (ω : Option ι → ℝ) : ℝ :=
if h : (Finset.univ : Finset ι).Nonempty then
Finset.univ.sup' h (fun j => b j * ω (some j)) else 0
/-- §5.2 (p. 31): `R_V(x) = E (xZ − V)^+` for `V = max_j b_j Z_j`, with `Z` independent of the
`Z_j`. -/
noncomputable def expComparison {ι : Type} [Fintype ι] (b : ι → ℝ) (x : ℝ) : ℝ :=
∫ ω, max (x * ω none - maxProd b ω) 0 ∂(expPi ι)
end SubadditiveMMS580.Amplification.Supplement