Proof of Theorem 4.7, p. 21 — an EFX allocation giving agent i at most 2µ_i/3 leaves exactly two positive goods to the other agent
ProvedStrategicAlloc.EFXTwoThirds.k_eq_twoefxfair-divisionmaximin-sharep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let two agents have additive non-negative valuations over a finite set of goods, and let be an EFX allocation. Let be an agent with maximin share and , and let be the other agent. Write . Then
This is the first step of the proof of Theorem 4.7: an EFX allocation that is no better than -MMS for some agent must have a very rigid shape.
Formalization Note The page states the claim for agent 1 after a "without loss of generality"; the statement is posed for an arbitrary agent and the other agent . The hypotheses and are the proof's context (p. 20: the negation of the theorem at agent ); the page then notes by Theorem 2.6.
Preamble
import Mathlib import Definitions.Def_StrategicAlloc_EFXTwoThirds_Setting
Formal statement
namespace StrategicAlloc.EFXTwoThirds
/-- Proof of Theorem 4.7 (p. 21, first paragraph): if an EFX allocation gives agent `i` at most
`2µ_i/3` and `µ_i > 0`, then the other agent's bundle `A_j` contains exactly two goods of positive
value to `i`, `v_i(A_j) = 4µ_i/3`, and each of these two goods is worth `2µ_i/3` to `i`. -/
theorem k_eq_two {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)
(i j : Fin 2) (hij : i ≠ j) (hmu : 0 < StrategicAlloc.EFXFour.mu v i)
(hle : val v i (A i) ≤ 2 / 3 * StrategicAlloc.EFXFour.mu v i) :
((A j).filter (fun g => 0 < v i g)).card = 2 ∧
val v i (A j) = 4 / 3 * StrategicAlloc.EFXFour.mu v i ∧
∀ g ∈ (A j).filter (fun g => 0 < v i g), v i g = 2 / 3 * StrategicAlloc.EFXFour.mu v i := by sorry
end StrategicAlloc.EFXTwoThirds
Source
Amanatidis et al., Allocating Indivisible Goods to Strategic Agents, arXiv:2109.08644v2, pp. 20–21, §4.2, proof of Theorem 4.7, last paragraph of p. 20 and first paragraph of p. 21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.