Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.2, pp. 13–14, proof of Theorem 3.7 — tight instance: agent 2’s best deviation value is 2 − ε_1 − ε_2, attained by g_3 > g_4 > g_1 > g_2 > g_5

Proved
RoundRobinEq.SubmodularBluff.tight_deviation

by mikedeng1 · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

bluff-profilefair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1round-robintight-example

Consider the tight instance of Theorem 3.7 with 0<ε1<ε2<ε3≤1/20<\varepsilon_1<\varepsilon_2<\varepsilon_3\le 1/20<ε1​<ε2​<ε3​≤1/2, and let agent 1 report the bluff order g1≻g2≻⋯≻g6g_1\succ g_2\succ\cdots\succ g_6g1​≻g2​≻⋯≻g6​. Then (i) whatever ranking ≻2\succ_2≻2​ agent 2 reports, the bundle A2(≻2)A_2(\succ_2)A2​(≻2​) she receives from Round-Robin satisfies

v2(A2(≻2))≤2−ε1−ε2,v_2(A_2(\succ_2))\le 2-\varepsilon_1-\varepsilon_2,v2​(A2​(≻2​))≤2−ε1​−ε2​,

and (ii) this maximum is attained: if agent 2 reports

g3≻g4≻g1≻g2≻g5≻g6,g_3\succ g_4\succ g_1\succ g_2\succ g_5\succ g_6,g3​≻g4​≻g1​≻g2​≻g5​≻g6​,

which is a ranking, then Round-Robin gives her the goods {g3,g4,g6}\{g_3,g_4,g_6\}{g3​,g4​,g6​} and v2({g3,g4,g6})=2−ε1−ε2v_2(\{g_3,g_4,g_6\})=2-\varepsilon_1-\varepsilon_2v2​({g3​,g4​,g6​})=2−ε1​−ε2​.

Since v2(A2)=1v_2(A_2)=1v2​(A2​)=1 in the bluff run, agent 2 improves her value by a factor 2−ε1−ε22-\varepsilon_1-\varepsilon_22−ε1​−ε2​, which tends to 222 as the ε\varepsilonε's vanish.

Formalization Note. The page assumes 1≫ε3>ε2>ε1>01\gg\varepsilon_3>\varepsilon_2>\varepsilon_1>01≫ε3​>ε2​>ε1​>0; here "1≫ε31\gg\varepsilon_31≫ε3​" is read as ε3≤1/2\varepsilon_3\le 1/2ε3​≤1/2. Some such quantitative reading is needed for the maximum: agent 2’s best deviation value is max⁡{1, 2−ε1−ε2}\max\{1,\,2-\varepsilon_1-\varepsilon_2\}max{1,2−ε1​−ε2​}, so the maximum claim fails when ε1+ε2>1\varepsilon_1+\varepsilon_2>1ε1​+ε2​>1 (e.g. 0.6,0.7,0.80.6,0.7,0.80.6,0.7,0.8), and ε3≤1/2\varepsilon_3\le 1/2ε3​≤1/2 rules this out. The dummy good g6g_6g6​ is the paper's device for m=knm=knm=kn (p. 7).

Preamble
import Mathlib
import Definitions.Def_RoundRobinEq_SubmodularBluff_Setting
import Definitions.Def_RoundRobinEq_SubmodularBluff_Bluff
import Definitions.Def_RoundRobinEq_SubmodularBluff_TightInstance
Formal statement
namespace RoundRobinEq.SubmodularBluff

theorem tight_deviation (ε₁ ε₂ ε₃ : ℝ) (h₁ : 0 < ε₁) (h₁₂ : ε₁ < ε₂) (h₂₃ : ε₂ < ε₃)
    (h₃ : ε₃ ≤ 1 / 2) :
    (∀ τ : List (Fin 6), RoundRobinEq.CancelableBluff.IsRanking τ →
      tightVal ε₁ ε₂ ε₃ 1 (RoundRobinEq.CancelableBluff.roundRobin (Function.update (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 1 τ) 1) ≤ 2 - ε₁ - ε₂) ∧
    RoundRobinEq.CancelableBluff.IsRanking tightDeviation ∧
      RoundRobinEq.CancelableBluff.roundRobin (Function.update (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 1 tightDeviation) 1 = {2, 3, 5} ∧
      tightVal ε₁ ε₂ ε₃ 1 {2, 3, 5} = 2 - ε₁ - ε₂ := by sorry

end RoundRobinEq.SubmodularBluff
Source
Amanatidis et al., Round-Robin Beyond Additive Agents, arXiv:2301.13652v1, pp. 13–14, proof of Theorem 3.7 (tight instance, agent 2's deviation)
Human review
  • Endorsed by Shuze Chen · Oct 14, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 14, 2026

    Confirmed by the mission captain (proposal self-audit).

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