Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§3.2, p. 13, proof of Theorem 3.7 — tight instance: the bluff order is g_1 > ⋯ > g_5 and the bluff run gives A_1 = {g_1, g_3, g_5}, A_2 = {g_2, g_4}

Proved
RoundRobinEq.SubmodularBluff.tight_bluff_run

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<10<\varepsilon_1<\varepsilon_2<\varepsilon_3<10<ε1​<ε2​<ε3​<1 (additive agent 1, OXS agent 2, and a dummy good g6g_6g6​). Then:

  1. g1≻g2≻g3≻g4≻g5≻g6g_1\succ g_2\succ g_3\succ g_4\succ g_5\succ g_6g1​≻g2​≻g3​≻g4​≻g5​≻g6​ is an output of Algorithm 2, so the profile in which both agents report it is a bluff profile;
  2. Round-Robin on this profile gives agent 1 the bundle A1={g1,g3,g5}A_1=\{g_1,g_3,g_5\}A1​={g1​,g3​,g5​} and agent 2 the bundle A2={g2,g4,g6}A_2=\{g_2,g_4,g_6\}A2​={g2​,g4​,g6​};
v1(A1)=4−ε1−ε3,v2(A2)=1.v_1(A_1)=4-\varepsilon_1-\varepsilon_3,\qquad v_2(A_2)=1.v1​(A1​)=4−ε1​−ε3​,v2​(A2​)=1.

Together with agent 2's deviation, this shows that the factor 12\tfrac1221​ of Theorem 3.7 cannot be improved.

Formalization Note. Goods gℓg_\ellgℓ​ are ℓ - 1 : Fin 6 and agents 1, 2 are 0, 1 : Fin 2. The dummy good g6g_6g6​ (value 000) comes from the paper's standing convention m=knm=knm=kn (p. 7) and ends up in A2A_2A2​ without changing any value. The order g1≻⋯≻g6g_1\succ\cdots\succ g_6g1​≻⋯≻g6​ is the one Algorithm 2 produces with lexicographic tie-breaking (agent 2 is indifferent among g4,g5,g6g_4,g_5,g_6g4​,g5​,g6​ at her second turn). The paper's "1≫ε3>ε2>ε1>01\gg\varepsilon_3>\varepsilon_2>\varepsilon_1>01≫ε3​>ε2​>ε1​>0" is encoded as 0<ε1<ε2<ε3<10<\varepsilon_1<\varepsilon_2<\varepsilon_3<10<ε1​<ε2​<ε3​<1, under which all three claims hold.

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_bluff_run (ε₁ ε₂ ε₃ : ℝ) (h₁ : 0 < ε₁) (h₁₂ : ε₁ < ε₂) (h₂₃ : ε₂ < ε₃)
    (h₃ : ε₃ < 1) :
    IsGreedyOrder (tightVal ε₁ ε₂ ε₃) tightBluffOrder ∧
      RoundRobinEq.CancelableBluff.roundRobin (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 0 = {0, 2, 4} ∧
      RoundRobinEq.CancelableBluff.roundRobin (bluff tightBluffOrder : Fin 2 → List (Fin 6)) 1 = {1, 3, 5} ∧
      tightVal ε₁ ε₂ ε₃ 0 {0, 2, 4} = 4 - ε₁ - ε₃ ∧
      tightVal ε₁ ε₂ ε₃ 1 {1, 3, 5} = 1 := by sorry

end RoundRobinEq.SubmodularBluff
Source
Amanatidis et al., Round-Robin Beyond Additive Agents, arXiv:2301.13652v1, p. 13, proof of Theorem 3.7 (tight instance, bluff run)
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