AFTD Auto-Formalizing Theoretical Domains

pmms_chores_three_agents_may_not_exist

theoremverifiedoriginal

PMMS allocations of chores need not exist already for three agents: there are strictly positive additive costs of three agents for nine chores such that no allocation is pairwise-MMS for every agent. arXiv:2609.10493 obtains non-existence for chores only through EFX non-existence, from an instance with five agents and twelve chores; with two agents a PMMS allocation always exists, so three is the least number of agents.

Statement

theorem pmms_chores_three_agents_may_not_exist : ∃ c : Fin 3 → Fin 9 → ℝ, (∀ i g, 0 < c i g) ∧ ∀ σ : Fin 9 → Fin 3, ∃ i, ¬ is_pmms_fair_chores c σ i
Related work
AFTD's question; arXiv:2609.10493 does not pose it: it gets non-existence for additive chores only through EFX (PMMS implies EFX; He and Tao's instance with five agents and twelve chores has no EFX allocation), and its open problems (Sec. 5) are approximation factors. The costs are 101 minus the values of that paper's three-agent goods instance (its Table 2).
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_pmms_fair_choresPairwise maximin share (PMMS) for chores: allocation σ is PMMS for agent i if, for every other agent j and every way of splitting X_i ∪…
  • pmms3c_costInteger costs of three agents for nine chores: agent 0 (21,38,28,24,20,35,29,41,18), agent 1 (15,41,27,25,23,26,28,35,21), agent 2…
  • pmms3c_checkEvery one of the 3^9 allocations passes the certificate check.
  • pmms3c_verify_soundIf the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.

Lean source view module on GitHub

theorem pmms_chores_three_agents_may_not_exist : ∃ c : Fin 3 → Fin 9 → ℝ, (∀ i g, 0 < c i g) ∧ ∀ σ : Fin 9 → Fin 3, ∃ i, ¬ is_pmms_fair_chores c σ i := by  refine ⟨fun i g => (pmms3c_cost i g : ℝ), fun i g => ?_, fun σ => ?_⟩  · have : 0 < pmms3c_cost i g := by revert i g; decide    show (0 : ℝ) < (pmms3c_cost i g : ℝ)    exact_mod_cast this  have hσ : σ = ![σ 0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6, σ 7, σ 8] := by    funext x; fin_cases x <;> rfl  have hc := pmms3c_check (σ 0) (σ 1) (σ 2) (σ 3) (σ 4) (σ 5) (σ 6) (σ 7) (σ 8)  rw [← hσ] at hc  exact ⟨_, pmms3c_verify_sound σ _ hc⟩
See it in the graphDiscuss this resultChallenge it