Eq. (1), proof of Theorem 9 — under round-robin, d_i(S_i) ≥ d_i(S_i′) + d_i^min for all agents i, i′
ProvedMmSChores.RoundRobin.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. Write . Then for all agents ,
This is the comparison between an agent's own bundle and any other bundle, measured with her own utility, on which the guarantee of Theorem 9 rests. It holds for as well, and in both pick orders of and .
Formalization Note Agents are Fin N (agent 1 is index 0), the run is any σ with IsRoundRobinRun d σ, is rrBundle σ i, and is Finset.univ.inf' hm (d i) for hm the nonemptiness of the chore set.
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
/-- Eq. (1), proof of Theorem 9 (PDF p. 4): in every round-robin run on non-positive utilities,
`d_i(S_i) ≥ d_i(S_{i'}) + d_i^min` for all agents `i, i'`, where
`d_i^min = min_{j ∈ M} d_i(j)`. -/
theorem 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 i' : Fin N) :
bval d i (rrBundle σ i') + 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, eq. (1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.