Eq. (2) — the water level exists and is unique when
ProvedChoresEFX.water_level_uniquechoresefxfair-divisionp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , , let be a positive vector indexed by chores, and suppose . Then the equation
has a unique solution .
This makes the prices of each round of MFCP well defined.
Differences from the source:
- generalization: r is the base price vector r(v) of a round, and n ≥ 2 → any positive vector r, and n ≥ 1; reason: base prices are positive, so the page's case is a special case; the argument uses nothing more
Preamble
import Mathlib
Formal statement
namespace ChoresEFX
/-- **The water level exists and is unique**, §3.1, p.7, the sentence after Eq. (2).
Qin, Fang, Li, Liu, Chen, *Polynomial-Time Approximate EFX for Chores via Flow and Matching*, STOC 2027
submission (manuscript sha256 b26d14cf…).
If `mβ > n`, the equation `∑_g min{s · r_g, β} = n` has a unique solution `s > 0`.
**Formalization Note.** `r` is any positive vector, in particular the base prices `r_g(v)` of a round;
`n > 0` is the paper's standing `n ≥ 2` weakened as far as the sentence needs. -/
theorem water_level_unique {κ : Type*} [Fintype κ] (n : ℕ) (hn : 0 < n) (β : ℝ) (hβ : 0 < β)
(r : κ → ℝ) (hr : ∀ g, 0 < r g) (hmβ : (n : ℝ) < (Fintype.card κ : ℝ) * β) :
∃! s : ℝ, 0 < s ∧ ∑ g, min (s * r g) β = (n : ℝ) := by sorry
end ChoresEFX
Source
Qin, Fang, Li, Liu, Chen, Polynomial-Time Approximate EFX for Chores via Flow and Matching, STOC 2027 submission (manuscript sha256 b26d14cf…), §3.1, the sentence after Eq. (2), p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.