Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Table 5 — ordinary and exaggerated reports and a single deviation

Definition
ChoresTIE197_Main_Supplement_Table5

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

algorithmic-game-theorychoresmaximin-sharep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For n≥4n\ge4n≥4 agents take m=n+7m=n+7m=n+7 chores. The first eleven indices are s1,s2,t1,t2,t3,t4,u1,u2,ℓ1,ℓ2,es_1,s_2,t_1,t_2,t_3,t_4,u_1,u_2,\ell_1,\ell_2,es1​,s2​,t1​,t2​,t3​,t4​,u1​,u2​,ℓ1​,ℓ2​,e, and the remaining n−4n-4n−4 indices are huge chores. For a nonnegative real parameter ε\varepsilonε, the core singleton costs are

c0=(2,2,3,3,3,3,4+ε,4,6,6,8),c1=(2,2,3,3,3,3,5,5,7,7,8).c_0=(2,2,3,3,3,3,4+\varepsilon,4,6,6,8),\qquad c_1=(2,2,3,3,3,3,5,5,7,7,8).c0​=(2,2,3,3,3,3,4+ε,4,6,6,8),c1​=(2,2,3,3,3,3,5,5,7,7,8).

Every huge chore costs 111111 under both reports. Bundle costs use the published finite additive sum. At the single-deviation profile, any specified agent iii reports c1c_1c1​ and all others report c0c_0c0​.

These data define the concrete instance for Lemma 5.4. No MMS values, approximation property, packing or ordinary-cost bound is supplied by the definition. The lemma imposes ε>0\varepsilon>0ε>0 and the source's smallness inequality. Indices start at zero; at n=4n=4n=4 there are no huge chores. The functions are total for n<4n<4n<4, but that range is never used.

Definition code
import Mathlib
import Definitions.Def_ChoresTIE197_Main_Setting

open scoped NNReal ENNReal

noncomputable section

namespace ChoresTIE197.Main.Supplement

/-- Table 5, printed/PDF p.28. Indices 0,...,10 are
s1,s2,t1,t2,t3,t4,u1,u2,ℓ1,ℓ2,e; later indices are huge chores.
For n ≥ 4 there are exactly eleven core chores and n - 4 huge chores. -/
def ordinary (n : ℕ) (ε : ℝ≥0) : Fin (n + 7) → ℝ≥0 := fun e =>
  match e.val with
  | 0 | 1 => 2
  | 2 | 3 | 4 | 5 => 3
  | 6 => 4 + ε
  | 7 => 4
  | 8 | 9 => 6
  | 10 => 8
  | _ => 11

/-- Table 5's exaggerated row. No MMS value or packing property is assumed. -/
def exaggerated (n : ℕ) : Fin (n + 7) → ℝ≥0 := fun e =>
  match e.val with
  | 0 | 1 => 2
  | 2 | 3 | 4 | 5 => 3
  | 6 | 7 => 5
  | 8 | 9 => 7
  | 10 => 8
  | _ => 11

/-- Any named agent reports c1, with every other agent reporting c0. -/
def singleReport (n : ℕ) (ε : ℝ≥0) (i : Fin n) : Profile n (n + 7) :=
  Function.update (fun _ => ordinary n ε) i (exaggerated n)

end ChoresTIE197.Main.Supplement
Source
Zehan Lin, Biaoshuai Tao, Xiaowei Wu, Yuhao Zhang, STOC 2027 submission #859 (October 2026), Table 5 and §5.3, 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