Theorem 2.5 — for two agents every MMS allocation is EFX
ProvedStrategicAlloc.CutChoose.theorem_2_5efxfair-divisionmaximin-sharep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let two agents have additive valuations with non-negative values on a set of goods, and let be an allocation, i.e. a partition of . Write for the maximin share of agent . If is MMS, that is,
then is EFX: for all with and every with , .
The paper attributes this to Theorem 4.6 of Caragiannis et al. It turns the MMS guarantee of the equilibria of Mod-Cut&Choose into an EFX guarantee in the last step of the proof of Theorem 4.3.
Formalization Note EFX is the paper's Definition 2.1, which removes only goods of positive value; with the stronger variant that also removes zero-valued goods the statement would be false.
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
/-- Theorem 2.5 (p. 5): for two agents with additive non-negative valuations, every MMS
allocation is an EFX allocation (EFX as in Definition 2.1: only goods of positive value are
removed). -/
theorem theorem_2_5 {m : ℕ} (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g)
(A : Fin 2 → Finset (Fin m)) (hA : StrategicAlloc.RRFair.IsAllocation A) (hmms : IsApproxMMS 1 v A) :
IsEFX v A := by sorry
end StrategicAlloc.CutChoose
Source
Amanatidis et al., Allocating Indivisible Goods to Strategic Agents, arXiv:2109.08644v2, p. 5, Theorem 2.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.