Lemma 4.6 — v_1({h_1, h_4}) ≥ µ_1 and max{v_1({h_1}), v_1({h_2, h_3})} ≥ µ_1 for four sorted positive goods
ProvedStrategicAlloc.EFXFour.lemma_4_6Consider two agents and four goods with additive non-negative valuations, and name the goods so that agent 1's values are sorted and all positive:
Then the maximin share of agent 1 satisfies
The paper attributes the lemma to the proof of Theorem 5.1 of Amanatidis, Birmpas and Markakis, On truthful mechanisms for maximin share allocations (IJCAI 2016). In the proof of Theorem 4.5 it identifies three bundles that always guarantee agent 1 her maximin share, which reduces the possible bundles of an agent who misses it to a short list.
Formalization Note The renaming of the goods is a bijection of Fin 4, with = h (j - 1). The page writes in the conclusion; the context (" as above") makes clear that is meant, and the Lean states it for agent 1 (0).
import Mathlib import Definitions.Def_StrategicAlloc_EFXFour_Setting
namespace StrategicAlloc.EFXFour
theorem lemma_4_6 (v : Fin 2 → Fin 4 → ℝ) (hv : ∀ i g, 0 ≤ v i g) (h : Fin 4 ≃ Fin 4)
(h01 : v 0 (h 1) ≤ v 0 (h 0)) (h12 : v 0 (h 2) ≤ v 0 (h 1)) (h23 : v 0 (h 3) ≤ v 0 (h 2))
(h3pos : 0 < v 0 (h 3)) :
mu v 0 ≤ StrategicAlloc.RRFair.val v 0 {h 0, h 3} ∧ mu v 0 ≤ max (StrategicAlloc.RRFair.val v 0 {h 0}) (StrategicAlloc.RRFair.val v 0 {h 1, h 2}) := by sorry
end StrategicAlloc.EFXFour
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.