Theorem 2.6 — for two agents every EFX allocation is 2/3-MMS
ProvedStrategicAlloc.EFXTwoThirds.theorem_2_6efxfair-divisionmaximin-sharep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let two agents have additive valuations with non-negative values over a finite set of goods, and let denote agent 's maximin share for two bundles. If is an allocation of that is EFX (only goods of positive value to the envious agent are removed), then
This is the worst-case maximin-share guarantee of an EFX allocation for two agents, which the paper attributes to Proposition 3.3 of Amanatidis, Birmpas and Markakis. Theorem 4.7 shows that equilibria of always-EFX mechanisms do strictly better than this generic bound.
Formalization Note The tightness sentence after Theorem 2.6 ("for every there exists an EFX allocation that is not -MMS") is not part of this statement.
Preamble
import Mathlib import Definitions.Def_StrategicAlloc_EFXTwoThirds_Setting
Formal statement
namespace StrategicAlloc.EFXTwoThirds
/-- Theorem 2.6 (p. 5): for two agents with additive non-negative valuations, every EFX
allocation is a 2/3-MMS allocation. -/
theorem theorem_2_6 {m : ℕ} (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g)
(A : Fin 2 → Finset (Fin m)) (hA : IsAllocation A) (hEFX : IsEFX v A) :
StrategicAlloc.EFXFour.IsApproxMMS (2 / 3) v A := by sorry
end StrategicAlloc.EFXTwoThirds
Source
Amanatidis et al., Allocating Indivisible Goods to Strategic Agents, arXiv:2109.08644v2, p. 5, Theorem 2.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.