Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4.1, p. 18, proof of Theorem 4.3 — truthful bidding is a dominant strategy for agent 2

Proved
StrategicAlloc.CutChoose.agent2_truthful_dominant

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

cut-and-choosefair-divisionmechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pure-nash-equilibrium

Consider two agents with additive non-negative valuations v1,v2v_1,v_2v1​,v2​ and Mod-Cut&Choose. For every bid profile b=(b1,b2)\mathbf b=(\mathbf b_1,\mathbf b_2)b=(b1​,b2​) with non-negative bids, replace agent 2's bid by her truthful bid v2=(v2(g1),…,v2(gm))v_2=(v_2(g_1),\dots,v_2(g_m))v2​=(v2​(g1​),…,v2​(gm​)). Then agent 2's truthful bid is a best response to b1\mathbf b_1b1​: for every b2′∈R≥0m\mathbf b'_2\in\mathbb R^m_{\ge 0}b2′​∈R≥0m​,

v2(M(b1,b2′)2) ≤ v2(M(b1,v2)2).v_2\big(\mathcal M(\mathbf b_1,\mathbf b'_2)_2\big)\ \le\ v_2\big(\mathcal M(\mathbf b_1,v_2)_2\big).v2​(M(b1​,b2′​)2​) ≤ v2​(M(b1​,v2​)2​).

Since agent 1's bid alone determines the cut, agent 2 can only choose between the two bundles, and bidding truthfully picks the one she values more. Truth telling is thus a dominant strategy for agent 2, which settles her part of the equilibrium in Theorem 4.3.

Formalization Note The profile (b1,v2)(\mathbf b_1,v_2)(b1​,v2​) is Function.update b 1 (v 1); agent 2 is 1.

Preamble
import Mathlib
import Definitions.Def_LittleCharity_MMS_Setting
import Definitions.Def_StrategicAlloc_CutChoose_Setting
import Definitions.Def_StrategicAlloc_CutChoose_ModCutChoose
Formal statement
namespace StrategicAlloc.CutChoose

/-- Proof of Theorem 4.3 (p. 18), third paragraph: whatever agent 1 bids, agent 2's truthful bid
`v_2` is a best response in Mod-Cut&Choose (truth telling is a dominant strategy for agent 2). -/
theorem agent2_truthful_dominant {m : ℕ} (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g)
    (b : Fin 2 → Fin m → ℝ) (hb : StrategicAlloc.RRFair.IsBidProfile b) :
    StrategicAlloc.RRFair.IsBestResponse modCutChoose v (Function.update b 1 (v 1)) 1 := by sorry

end StrategicAlloc.CutChoose
Source
Amanatidis et al., Allocating Indivisible Goods to Strategic Agents, arXiv:2109.08644v2, p. 18, §4.1, proof of Theorem 4.3, third paragraph
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 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