Proof of Theorem 4.7, p. 21 — under the same hypotheses agent i's own bundle has at least two positive goods
ProvedStrategicAlloc.EFXTwoThirds.two_pos_goods_ownefxfair-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. If agent has maximin share and , then
This is the second step of the proof of Theorem 4.7; it supplies the goods on which the auxiliary instance is built.
Formalization Note As for the previous step, the page argues for agent 1 after a "without loss of generality"; the statement is posed for an arbitrary agent , with the proof's context and as hypotheses.
Preamble
import Mathlib import Definitions.Def_StrategicAlloc_EFXTwoThirds_Setting
Formal statement
namespace StrategicAlloc.EFXTwoThirds
/-- Proof of Theorem 4.7 (p. 21, second paragraph): under the hypotheses of `k_eq_two`, agent
`i`'s own bundle `A_i` contains at least two goods of positive value to `i`. -/
theorem two_pos_goods_own {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 : Fin 2) (hmu : 0 < StrategicAlloc.EFXFour.mu v i)
(hle : val v i (A i) ≤ 2 / 3 * StrategicAlloc.EFXFour.mu v i) :
2 ≤ ((A i).filter (fun g => 0 < v i g)).card := by sorry
end StrategicAlloc.EFXTwoThirds
Source
Amanatidis et al., Allocating Indivisible Goods to Strategic Agents, arXiv:2109.08644v2, p. 21, §4.2, proof of Theorem 4.7, second paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.