mnw2_bracket
theoremverified
For nonnegative reals P, r, g, d with P + r ≤ 1, r(1 − g) ≤ P(g + d) and r d ≤ P g, we have 23 r ≤ 4P + 27 g + 4 d. (Case 23P ≤ 4 is linear after two product estimates; otherwise multiply the target by P² + Pr + r² and write the product as a nonnegative combination of the hypotheses.)
Statement
theorem mnw2_bracket (P r g d : ℝ) (hP : 0 ≤ P) (hr : 0 ≤ r) (hg : 0 ≤ g) (hd : 0 ≤ d) (hPr : P + r ≤ 1) (hC : r * (1 - g) ≤ P * (g + d)) (hD : r * d ≤ P * g) : 23 * r ≤ 4 * P + 27 * g + 4 * d- Source
- step towards mnw_two_agents_welfare_le (upper bound 27/23 for the price of MNW with two agents, The Price of Fairness for Indivisible Goods, arXiv:1905.04910, Theorem 5.4; Positivstellensatz certificate found by computer)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- mnw2_coreGoods are grouped by their owners under an allocation O and an allocation N: A = (O:0, N:0), B = (O:1, N:0), C = (O:0, N:1), D = (O:1,…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Two-variable bracket inequality used in the two easy cases of the two-agent price-of-MNW bound. -/theorem mnw2_bracket (P r g d : ℝ) (hP : 0 ≤ P) (hr : 0 ≤ r) (hg : 0 ≤ g) (hd : 0 ≤ d) (hPr : P + r ≤ 1) (hC : r * (1 - g) ≤ P * (g + d)) (hD : r * d ≤ P * g) : 23 * r ≤ 4 * P + 27 * g + 4 * d := by rcases le_total (23 * P) 4 with h | h · have e1 : 0 ≤ g * (1 - P - r) := mul_nonneg hg (by linarith) have e2 : 0 ≤ d * (4 - 23 * P) := mul_nonneg hd (by linarith) nlinarith · have hk : 0 ≤ (P ^ 2 + P * r + r ^ 2) * (4 * P + 27 * g + 4 * d - 23 * r) := by have e1 : 0 ≤ (27 * r + 4 * P) * (P * (g + d) - r * (1 - g)) := mul_nonneg (by linarith) (by linarith) have e2 : 0 ≤ (23 * P - 4 * r) * (P * g - r * d) := mul_nonneg (by linarith) (by linarith) have e3 : 0 ≤ r * (27 * r + 4 * P) * (1 - P - r) := mul_nonneg (mul_nonneg hr (by linarith)) (by linarith) have e4 : 0 ≤ (2 * r - P) ^ 2 * (r + 4 * P) := mul_nonneg (sq_nonneg _) (by linarith) linear_combination e1 + e2 + e3 + e4 rcases (show 0 ≤ P ^ 2 + P * r + r ^ 2 by positivity).eq_or_lt with h0 | h0 · have hP0 : P = 0 := by nlinarith have hr0 : r = 0 := by nlinarith subst hP0 hr0 linarith · have := (mul_nonneg_iff_of_pos_left h0).mp hk linarith