Tight instance, proof of Theorem 9 — it is a chores instance and every agent's max-min share is −1
ProvedMmSChores.RoundRobin.tight_instance_mmschoresfair-divisionmaximin-sharep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix and consider the tight instance of Theorem 9: chores, of which are worth and one is worth , with the same utility function for all agents. Then this is a chores instance, and every agent's max-min share is
The paper asserts that this instance shows the factor cannot be improved, without computing it; this statement is the max-min-share half of that computation.
Formalization Note The profile is fun _ : Fin N => tightUtil N, and the max-min share is LittleCharity.MMS.mms (bval … i) N univ, over all labelled, possibly empty, -partitions of the chores.
Differences from the source:
- encoding: the page asserts that the instance makes the bound tight, leaving the computation implicit → the max-min share of the instance is stated explicitly as −1; reason: this is the value the tightness claim needs, stated as its own item
Preamble
import Mathlib import Definitions.Def_LittleCharity_MMS_Setting import Definitions.Def_MmSChores_RoundRobin_Setting import Definitions.Def_MmSChores_RoundRobin_TightInstance
Formal statement
namespace MmSChores.RoundRobin
open Finset
/-- Tight instance of Theorem 9 (PDF p. 4): the profile in which every one of the `N` agents has
the utility `tightUtil N` (`(N - 1) * N` chores worth `-1/N`, one chore worth `-1`) is a chores
instance, and every agent's max-min share is `-1`. -/
theorem tight_instance_mms {N : ℕ} (hN : 0 < N) :
IsChores (fun _ : Fin N => tightUtil N) ∧
∀ i : Fin N,
LittleCharity.MMS.mms (bval (fun _ : Fin N => tightUtil N) i) N univ = -1 := 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, last paragraph (the computation the page leaves implicit)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.