Display after (1), proof of Theorem 9 — d_i(S_i) ≥ (1/N)·d_i(M) + (1 − 1/N)·d_i^min
ProvedMmSChores.RoundRobin.display_after_eq_1choresfair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1round-robin
Let agents have additive utilities over a nonempty finite set of chores with for all and , and let be the allocation produced by a run of the greedy round-robin protocol (Algorithm 1), under any tie-breaking rule. With , every agent satisfies
This averaged form of eq. (1) bounds an agent's round-robin bundle by her proportional share plus a correction of at most times her worst chore; together with the two upper bounds on the max-min share it yields Theorem 9.
Formalization Note As for eq. (1): the run is any σ with IsRoundRobinRun d σ, is rrBundle σ i, is bval d i univ, and is Finset.univ.inf' hm (d i). The factor is the real number 1 / (N : ℝ).
Differences from the source:
- generalization: chores instance (d_i(j) ≤ 0 and d_i ≢ 0) → only d_i(j) ≤ 0 for all i, j; reason: the condition d_i ≢ 0 is not used, and every chores instance satisfies the Lean 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
/-- Display after (1), proof of Theorem 9 (PDF p. 4): in every round-robin run on non-positive
utilities, `d_i(S_i) ≥ (1/N) · d_i(M) + (1 - 1/N) · d_i^min` for every agent `i`. -/
theorem display_after_eq_1 {N m : ℕ} (hN : 0 < N) (hm : (univ : Finset (Fin m)).Nonempty)
(d : Fin N → Fin m → ℝ) (hd : ∀ i j, d i j ≤ 0) (σ : Fin m ≃ Fin m)
(hσ : IsRoundRobinRun d σ) (i : Fin N) :
(1 / (N : ℝ)) * bval d i univ + (1 - 1 / (N : ℝ)) * univ.inf' hm (d i)
≤ bval d i (rrBundle σ 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, display after eq. (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.