AFTD Auto-Formalizing Theoretical Domains

mnw2_case3_denom_pos

theoremverified

A specific cubic polynomial with positive coefficients (plus the constant 1) in ten nonnegative variables is strictly positive. It is the multiplier of the Positivstellensatz certificate in the hard case of the two-agent price-of-MNW upper bound.

Statement

theorem mnw2_case3_denom_pos (p q r s α β γ δ e3 e4 : ℝ) (hp : 0 ≤ p) (hq : 0 ≤ q) (hr : 0 ≤ r) (hs : 0 ≤ s) (hα : 0 ≤ α) (hβ : 0 ≤ β) (hγ : 0 ≤ γ) (hδ : 0 ≤ δ) (he3 : 0 ≤ e3) (he4 : 0 ≤ e4) : 0 < (4753/10)*p^3 + (2271/2)*p^2*q + (8186/5)*p^2*β + (7861/10)*p^2*γ + (13567/10)*p*q^2 + (1084/5)*p*q*s + (2954/5)*p*q*α + (1949/2)*p*q*β + (613/2)*p*r*s + (4165/2)*p*r*α + (4949/5)*p*r*β + (11757/10)*p*r*δ + (10323/5)*p*s*β + (6808/5)*p*s*γ + (3762/5)*p*s*δ + (2772/5)*p*α*γ + (2841/2)*p*α*δ + (9797/5)*p*α*e4 + (329/2)*p*β^2 + (8561/10)*p*β*δ + (6222/5)*p*γ^2 + (3067/2)*p*γ*δ + (15329/10)*p*δ^2 + (587/2)*p*e3^2 + (79/10)*q^2*r + 373*q^2*β + (10957/10)*q^2*δ + (6059/10)*q^2*e3 + (1131/5)*q^2*e4 + (27383/10)*q*r*α + (7341/10)*q*s*α + (5269/10)*q*s*β + 667*q*s*γ + (15733/10)*q*s*δ + (1819/5)*q*α*δ + (13073/5)*q*α*e4 + (5281/10)*q*β*γ + (15979/10)*q*γ^2 + (14483/10)*q*γ*δ + (349/5)*q*δ^2 + (479/5)*r^3 + (2397/10)*r^2*s + (10807/10)*r^2*α + (3213/10)*r^2*γ + (826/5)*r*s^2 + (4156/5)*r*s*α + 65*r*s*β + (11247/10)*r*s*γ + 40*r*s*δ + (3989/5)*r*α*β + (5922/5)*r*α*δ + (7459/10)*r*β^2 + 1402*r*β*δ + (1388/5)*r*β*e3 + (1199/2)*r*γ^2 + (26/5)*r*γ*e3 + (2839/5)*r*δ^2 + (12097/5)*r*δ*e3 + (1184/5)*r*e3^2 + (317/10)*s^2*α + (1123/10)*s*α*β + (6337/10)*s*α*γ + (2396/5)*s*α*δ + (2723/10)*s*α*e4 + 783*s*β^2 + (3594/5)*s*β*γ + (14077/10)*s*β*e3 + (13107/10)*s*γ*δ + (11147/5)*s*γ*e3 + 2080*s*δ*e3 + (293/10)*α*β^2 + (15803/10)*α*β*δ + (5741/5)*α*β*e4 + (2919/10)*α*γ*e4 + 8*β^3 + 566*β^2*δ + (3933/10)*β^2*e4 + (567/10)*β*e3^2 + (2752/5)*β*e4^2 + (3009/10)*γ^2*δ + (1781/10)*γ^2*e3 + (1607/10)*γ*δ*e3 + (793/5)*γ*e4^2 + (8787/10)*δ^2*e3 + 1
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_case3Goods 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

/-- Positivity of the multiplier polynomial in the certificate for the hard case of the two-agent price-of-MNW bound. -/theorem mnw2_case3_denom_pos (p q r s α β γ δ e3 e4 : ℝ) (hp : 0 ≤ p) (hq : 0 ≤ q) (hr : 0 ≤ r) (hs : 0 ≤ s) (hα : 0 ≤ α) (hβ : 0 ≤ β) (hγ : 0 ≤ γ) (hδ : 0 ≤ δ) (he3 : 0 ≤ e3) (he4 : 0 ≤ e4) : 0 < (4753/10)*p^3 + (2271/2)*p^2*q + (8186/5)*p^2*β + (7861/10)*p^2*γ + (13567/10)*p*q^2 + (1084/5)*p*q*s + (2954/5)*p*q*α + (1949/2)*p*q*β + (613/2)*p*r*s + (4165/2)*p*r*α + (4949/5)*p*r*β + (11757/10)*p*r*δ + (10323/5)*p*s*β + (6808/5)*p*s*γ + (3762/5)*p*s*δ + (2772/5)*p*α*γ + (2841/2)*p*α*δ + (9797/5)*p*α*e4 + (329/2)*p*β^2 + (8561/10)*p*β*δ + (6222/5)*p*γ^2 + (3067/2)*p*γ*δ + (15329/10)*p*δ^2 + (587/2)*p*e3^2 + (79/10)*q^2*r + 373*q^2*β + (10957/10)*q^2*δ + (6059/10)*q^2*e3 + (1131/5)*q^2*e4 + (27383/10)*q*r*α + (7341/10)*q*s*α + (5269/10)*q*s*β + 667*q*s*γ + (15733/10)*q*s*δ + (1819/5)*q*α*δ + (13073/5)*q*α*e4 + (5281/10)*q*β*γ + (15979/10)*q*γ^2 + (14483/10)*q*γ*δ + (349/5)*q*δ^2 + (479/5)*r^3 + (2397/10)*r^2*s + (10807/10)*r^2*α + (3213/10)*r^2*γ + (826/5)*r*s^2 + (4156/5)*r*s*α + 65*r*s*β + (11247/10)*r*s*γ + 40*r*s*δ + (3989/5)*r*α*β + (5922/5)*r*α*δ + (7459/10)*r*β^2 + 1402*r*β*δ + (1388/5)*r*β*e3 + (1199/2)*r*γ^2 + (26/5)*r*γ*e3 + (2839/5)*r*δ^2 + (12097/5)*r*δ*e3 + (1184/5)*r*e3^2 + (317/10)*s^2*α + (1123/10)*s*α*β + (6337/10)*s*α*γ + (2396/5)*s*α*δ + (2723/10)*s*α*e4 + 783*s*β^2 + (3594/5)*s*β*γ + (14077/10)*s*β*e3 + (13107/10)*s*γ*δ + (11147/5)*s*γ*e3 + 2080*s*δ*e3 + (293/10)*α*β^2 + (15803/10)*α*β*δ + (5741/5)*α*β*e4 + (2919/10)*α*γ*e4 + 8*β^3 + 566*β^2*δ + (3933/10)*β^2*e4 + (567/10)*β*e3^2 + (2752/5)*β*e4^2 + (3009/10)*γ^2*δ + (1781/10)*γ^2*e3 + (1607/10)*γ*δ*e3 + (793/5)*γ*e4^2 + (8787/10)*δ^2*e3 + 1 := by  positivity
See it in the graphDiscuss this resultChallenge it