Proof of Theorem 9, last sentence (second half) — d_i^min ≥ MmS^N_{d_i}(M) for chores
ProvedMmSChores.RoundRobin.mms_le_dminchoresfair-divisionmaximin-sharep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let agents have additive utilities over a nonempty finite set of items, and let agent 's utilities be non-positive: for every . With and her max-min share over all allocations into (possibly empty) bundles,
For chores, no allocation can give every bundle more than the worst single chore. Together with the proportional-share bound and the averaged form of eq. (1) it gives Theorem 9.
Formalization Note is Finset.univ.inf' hm (d i) and the max-min share is LittleCharity.MMS.mms (bval d i) N univ.
Differences from the source:
- generalization: in every chores setting (all agents, d_i(j) ≤ 0, d_i ≢ 0) → only agent i's utilities are non-positive, and d_i ≢ 0 is dropped; reason: the bound for agent i uses only her own signs; chores instances satisfy the hypotheses
- encoding: M nonempty, implicit in d_i^min = min_{j∈M} d_i(j) → explicit hypothesis that the chore set is nonempty; reason: the minimum is defined only on a nonempty set
Preamble
import Mathlib import Definitions.Def_LittleCharity_MMS_Setting import Definitions.Def_MmSChores_RoundRobin_Setting
Formal statement
namespace MmSChores.RoundRobin
open Finset
/-- Proof of Theorem 9 (PDF p. 4), second half of the last sentence: `d_i^min ≥ MmS^N_{d_i}(M)`
when all of agent `i`'s utilities are non-positive. -/
theorem mms_le_dmin {N m : ℕ} (hN : 0 < N) (hm : (univ : Finset (Fin m)).Nonempty)
(d : Fin N → Fin m → ℝ) (i : Fin N) (hd : ∀ j, d i j ≤ 0) :
LittleCharity.MMS.mms (bval d i) N univ ≤ univ.inf' hm (d i) := by sorry
end MmSChores.RoundRobin
Source
Aziz, Rauchecker, Schryen & Walsh, Algorithms for Max-Min Share Fair Allocation of Indivisible Chores, AAAI 2017, PDF p. 4, proof of Theorem 9, sentence after the display after eq. (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.