§4.1, p. 18, proof of Theorem 4.3 — by bidding truthfully agent 2 gets at least v₂(M)/2
ProvedStrategicAlloc.CutChoose.agent2_truthful_halfcut-and-choosefair-divisionmaximin-sharemechanism-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider two agents with additive non-negative valuations on the set of goods and Mod-Cut&Choose. Whatever agent 1 bids, if agent 2 declares her truthful bid she receives a bundle of value at least half of her value for all goods:
Combined with , this shows that deviating to the truthful bid would give agent 2 at least her maximin share, which is the agent-2 half of the MMS part of Theorem 4.3.
Formalization Note The profile is Function.update b 1 (v 1) for an arbitrary profile b; only b 0 (agent 1's bid) matters.
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), fourth paragraph: whatever agent 1 bids, agent 2's truthful
bid gives her a bundle of value at least `v_2(M)/2`. -/
theorem agent2_truthful_half {m : ℕ} (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g)
(b : Fin 2 → Fin m → ℝ) :
StrategicAlloc.RRFair.val v 1 Finset.univ / 2 ≤ StrategicAlloc.RRFair.val v 1 (modCutChoose (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, fourth paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.