Tight instance, proof of Theorem 9 — every round-robin run gives agent 1 a bundle worth exactly −(2 − 1/N)
ProvedMmSChores.RoundRobin.tight_instance_runchoresfair-divisionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1round-robin
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. In every run of the greedy round-robin protocol (Algorithm 1), under any tie-breaking rule, agent 1 receives a bundle with
Together with the max-min share of this instance, agent 1 receives exactly , so the factor of Theorem 9 is attained.
Formalization Note The run is any σ with IsRoundRobinRun (fun _ : Fin N => tightUtil N) σ; agent 1 is index ⟨0, hN⟩ and is rrBundle σ ⟨0, hN⟩.
Differences from the source:
- encoding: the page asserts that the instance makes the bound tight, leaving the computation implicit → agent 1's round-robin value is stated explicitly as −(2 − 1/N) for every run; 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): in every round-robin run on the profile in which every
agent has the utility `tightUtil N`, agent 1 (index `0`) receives a bundle worth exactly
`-(2 - 1/N)`. -/
theorem tight_instance_run {N : ℕ} (hN : 0 < N)
(σ : Fin ((N - 1) * N + 1) ≃ Fin ((N - 1) * N + 1))
(hσ : IsRoundRobinRun (fun _ : Fin N => tightUtil N) σ) :
bval (fun _ : Fin N => tightUtil N) ⟨0, hN⟩ (rrBundle σ ⟨0, hN⟩) =
-(2 - 1 / (N : ℝ)) := 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.