Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.4 — ordinary-cost bound at a single exaggerated report

Open
ChoresTIE197.Main.Supplement.lemma_5_4

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmic-game-theorychoresmaximin-sharemechanism-designp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1

Fix n≥4n\ge4n≥4, 1≤α<13/121\le\alpha<13/121≤α<13/12 and ε>0\varepsilon>0ε>0 with α(11+ε)<12\alpha(11+\varepsilon)<12α(11+ε)<12. Use exactly the two Table 5 rows on n+7n+7n+7 chores, and let FFF be any complete payment-free randomized mechanism with the ex-post α\alphaα-MMS guarantee at every positive report profile. For any named agent iii, form the profile c(i)c^{(i)}c(i) where she reports c1c_1c1​ and every other agent reports c0c_0c0​. For every complete allocation AAA with nonzero probability under F(c(i))F(c^{(i)})F(c(i)),

c0(Ai)≤11.c_0(A_i)\le11.c0​(Ai​)≤11.

The cost in this conclusion is the ordinary row c0c_0c0​, even though the recipient reports c1c_1c1​. The statement is support-wise, not merely an expectation bound. The condition on ε\varepsilonε implies ε<1\varepsilon<1ε<1; singleton costs may be zero in the general domain, while these two particular rows have positive singleton costs. Their actual MMS values are computed by the published definition, rather than supplied as assumptions.

This supports Theorem 5.3. The combinatorial restriction needs no truthfulness assumption, which is explicitly recorded as a generalization below.

Differences from the source:

  • encoding: finite agents and chores, arbitrary nonnegative additive costs, complete payment-free randomized allocations → Fin-indexed nonnegative real singleton tables and the published PMF on complete owner maps, with cost MMS the sign dual of utility MMS; reason: finite relabeling and sign duality preserve every source instance, empty bundles, real probabilities and support-wise guarantees
  • encoding: the standing convention on p.7 assumes positive MMS for every agent → MMSOn Positive α F on all profiles with positive row total; reason: for nonnegative additive costs and n≥2, positive total is equivalent to positive MMS; no singleton positivity is required, and full-domain guarantees restrict to this domain
  • encoding: eleven named core chores and n−4 huge chores with the Table 5 rows → Fin (n+7), with the first eleven zero-based indices in Table 5 order and a nonnegative real subtype for ε; reason: when n≥4 the indexing gives exactly the source chores and every positive real ε is represented; n=4 gives no huge chores
  • encoding: §5.3 fixes n≥4, an approximation ratio below 13/12 and sufficiently small ε>0 → 4≤n, 1≤α, α<13/12, 0<ε and α(11+ε)<12; reason: the lower bound α≥1 is Definition 2.3’s approximation convention; the explicit smallness condition is the source choice and already implies ε<1, so no redundant ε<1 hypothesis is added
  • generalization: Lemma 5.4 occurs within the assumed complete TIE mechanism of §5.3 → only completeness and the assumed ex-post α-MMS guarantee on Positive are premises; TIE is omitted; reason: the support restriction in the proof uses only the MMS caps and packing the remaining chores; adding TIE specializes back to every source mechanism
Preamble
import Mathlib
import Definitions.Def_ChoresTIE197_Main_Setting
import Definitions.Def_ChoresTIE197_Main_Supplement_Table5

open scoped NNReal ENNReal

open Finset
Formal statement
namespace ChoresTIE197.Main.Supplement

/-- Lemma 5.4, printed/PDF pp.28–29, with the hypotheses inherited from §5.3.
No TIE premise is needed for this support restriction. MMS values and the
ordinary-cost bound are conclusions of the source argument, not input data. -/
theorem lemma_5_4 (n : ℕ) (hn : 4 ≤ n) (α : ℝ)
    (hα_lower : 1 ≤ α) (hα_upper : α < 13 / 12)
    (ε : ℝ≥0) (hε : 0 < ε) (hsmall : α * (11 + (ε : ℝ)) < 12)
    (F : Mechanism n (n + 7)) (hMMS : MMSOn Positive α F)
    (i : Fin n) (A : Allocation n (n + 7))
    (hsupport : F (singleReport n ε i) A ≠ 0) :
    cost (ordinary n ε) (bundle A i) ≤ 11 := by sorry

end ChoresTIE197.Main.Supplement
Source
Zehan Lin, Biaoshuai Tao, Xiaowei Wu, Yuhao Zhang, STOC 2027 submission #859 (October 2026), Lemma 5.4, printed p.28, PDF p.28; https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/859.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me