§4.1, p. 18, proof of Theorem 4.3 — truthful bidding is a dominant strategy for agent 2
ProvedStrategicAlloc.CutChoose.agent2_truthful_dominantcut-and-choosefair-divisionmechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pure-nash-equilibrium
Consider two agents with additive non-negative valuations and Mod-Cut&Choose. For every bid profile with non-negative bids, replace agent 2's bid by her truthful bid . Then agent 2's truthful bid is a best response to : for every ,
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 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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.