all_agent_bivalued_equal_marginal_divisible_chores
For every n at least two and k at least two, any common ratio r at least one, and any n-agent scaled bivalued additive cost profile on n*k chores, there is a nonnegative weight for every complete allocation, with all weights summing to 1, such that each chore is assigned to each agent with marginal probability 1/n and every allocation with positive weight gives each agent at most (r+1)/2 times her n-agent chore maximin share.
Statement
theorem all_agent_bivalued_equal_marginal_divisible_chores (n k : ℕ) (hn : 2 ≤ n) (hk : 2 ≤ k) (r : ℝ) (hr : 1 ≤ r) (c : Fin n → Fin (n*k) → ℝ) (hc : is_scaled_bivalued_chores r c) : ∃ p ∈ stdSimplex ℝ (Fin (n*k) → Fin n), is_equal_marginal_lottery p ∧ is_ex_post_alpha_mms_chores ((r+1)/2) c p- Related work
- OP-1112; compare the equal-marginal sorted-slot mechanism in arXiv:2609.35280, Lemma 3.1, and the two-agent bound in https://rainwangphy.github.io/aftd-platform/blog/2026-11-06-op-1112/.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- equal_marginal_balanced_high_count_allocationsFor at least two agents, k at least two, and n*k chores, each agent has an arbitrary set of high chores. There are n allocations such that…
- balanced_high_count_chore_mms_boundFor n at least two, k at least two and n*k bivalued chores, a bundle of size k whose high-cost count times n is at most the total…
- is_equal_marginal_lotteryA lottery p over complete allocations of m chores to n agents has equal marginals if every chore g is assigned to every agent i with…
- is_scaled_bivalued_choresGiven ratio r : ℝ and a chore cost profile c : Fin n → Fin m → ℝ over n agents and m chores, c is scaled bivalued with ratio r if there…
- is_ex_post_alpha_mms_choresAn allocation lottery p over allocations of m chores among n agents is ex-post α-MMS for chore costs c if every allocation σ in the…
- is_alpha_mms_choresAn allocation σ of m chores among n agents is α-MMS for cost functions c if each agent i's total cost for her assigned bundle bundle_of σ…
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
Read back from the Lean
Given natural numbers $n, k \ge 2$, a real number $r \ge 1$, and an agent-chore cost matrix $c : \text{Fin } n \to \text{Fin }(n \cdot k) \to \mathbb{R}$ that is scaled bivalued with parameter $r$ (meaning for each agent $i$, there is a base cost $a_i > 0$ such that every chore's cost to agent $i$ is either $a_i$ or $r \cdot a_i$): There exists a probability distribution $p$ in the standard simplex over allocations $\sigma : \text{Fin }(n \cdot k) \to \text{Fin } n$ (i.e., $p(\sigma) \ge 0$ for all $\sigma$ and $\sum_\sigma p(\sigma) = 1$) such that: 1. $p$ has equal marginals: for every chore $g \in \text{Fin }(n \cdot k)$ and every agent $i \in \text{Fin } n$, the total probability under $p$ that chore $g$ is assigned to agent $i$ ($\sum_{\sigma : \sigma(g) = i} p(\sigma)$) equals $1 / n$; and 2. $p$ is ex-post $\frac{r+1}{2}$-MMS for chores: for every allocation $\sigma$ with $p(\sigma) > 0$ and every agent $i \in \text{Fin } n$, the cost of the chores assigned to $i$ under $\sigma$ ($\sum_{g : \sigma(g) = i} c(i, g)$) is at most $\frac{r+1}{2}$ times agent $i$'s chore maximin share ($\inf_{P : \text{Fin}(n \cdot k) \to \text{Fin } n} \sup_{j : \text{Fin } n} \sum_{g : P(g) = j} c(i, g)$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by constructing a uniform lottery over a set of $n$ complete allocations. Using the lemma `equal_marginal_balanced_high_count_allocations`, the $n k$ chores are partitioned across $n$ allocations $F_0, \dots, F_{n-1}$ such that every chore is assigned to each agent exactly once across the allocations, and each agent receives a bundle of size $k$ with balanced high-cost chore count. The uniform distribution over these $n$ allocations yields marginal probability $1/n$ for every agent-chore pair, and each allocation in its support satisfies the $((r+1)/2)$-MMS bound by `balanced_high_count_chore_mms_bound`.
Identify each agent's high-cost chores and obtain $n$ allocations balancing high-cost chores.
From the assumption that costs are scaled bivalued, each agent $i$ has a base cost $a_i > 0$ such that all chore costs are either $a_i$ or $r a_i$. We let $H_i$ be the set of chores where agent $i$ incurs the high cost $r a_i$. Applying `equal_marginal_balanced_high_count_allocations` to $H$ provides $n$ allocations $F_0, \dots, F_{n-1}$ such that for every chore $g$, the assignment $t \mapsto F_t(g)$ is a bijection onto the agents, and each bundle has size $k$ with high-cost count satisfying $n \cdot |F_t(i) \cap H_i| \le |H_i| + n - 1$.
uses
equal_marginal_balanced_high_count_allocationsopen Finset in rcases hc with ⟨a, ha_pos, ha_val⟩ let H : Fin n → Finset (Fin (n*k)) := fun i => univ.filter (fun g => c i g = r * a i) obtain ⟨F, hF_bij, hF_prop⟩ := equal_marginal_balanced_high_count_allocations n k hn hk H
Define the uniform distribution $p$ over the $n$ allocations and note $n \ne 0$.
We define the lottery $p(\sigma)$ to be $1/n$ if $\sigma = F_t$ for some $t \in \{0, \dots, n-1\}$ and $0$ otherwise. Since $n \ge 2$, $n$ is nonzero in $\mathbb{R}$.
let p : (Fin (n*k) → Fin n) → ℝ := fun σ => ∑ t : Fin n, if σ = F t then 1 / (n : ℝ) else 0 have hn_pos : (n : ℝ) ≠ 0 := by positivity
The function $p$ is a probability distribution in the standard simplex.
Each weight $p(\sigma)$ is non-negative because it is a sum of terms that are either $1/n > 0$ or $0$ (`sum_nonneg`). Furthermore, the total probability sums to 1: exchanging the order of summation (`sum_comm`) turns $\sum_\sigma \sum_t \mathbf{1}_{\sigma = F_t} \frac{1}{n}$ into $\sum_t \sum_\sigma \mathbf{1}_{\sigma = F_t} \frac{1}{n}$. The inner sum over all allocations evaluates to $1/n$ by `sum_ite_eq'`, and summing $1/n$ over the $n$ values of $t$ yields 1.
uses
sum_nonneg,sum_comm,sum_ite_eq'have hp_simp : p ∈ stdSimplex ℝ (Fin (n*k) → Fin n) := by dsimp [stdSimplex, p] constructor · intro σ apply sum_nonneg intro t _ split_ifs · positivity · rfl · rw [sum_comm] have h1 : ∀ t : Fin n, (∑ x : Fin (n * k) → Fin n, if x = F t then 1 / (n : ℝ) else 0) = 1 / (n : ℝ) := by intro t rw [sum_ite_eq'] simp simp_rw [h1] simp [hn_pos]
It suffices to verify equal marginal probabilities and the ex-post MMS guarantee for $p$.
We instantiate the existential goal with the lottery $p$ and its simplex membership, reducing the remaining proof to showing that $p$ has equal marginal probabilities and that every allocation in the support of $p$ satisfies the $((r+1)/2)$-MMS chore guarantee.
refine ⟨p, hp_simp, ?_, ?_⟩Every chore is assigned to each agent with marginal probability $1/n$.
For a fixed chore $g$ and agent $i$, the marginal probability is $\sum_\sigma \mathbf{1}_{\sigma(g) = i} p(\sigma)$. We rewrite the summand (`h_split`) and swap the order of summation (`sum_comm`) so the sum over allocations $\sigma$ is on the inside. That inner sum evaluates to $\mathbf{1}_{F_t(g) = i} \frac{1}{n}$ by `sum_ite_eq'`. Since $t \mapsto F_t(g)$ is a bijection from the $n$ allocations to the $n$ agents (`Equiv.ofBijective`), reindexing the sum via `Equiv.sum_comp` transforms it into $\sum_x \mathbf{1}_{x = i} \frac{1}{n}$, which equals $1/n$ by `sum_ite_eq'`.
uses
sum_comm,sum_ite_eq',Equiv.ofBijective,Equiv.sum_comp· intro g i dsimp [p] have h_split : ∀ σ : Fin (n * k) → Fin n, (if σ g = i then (∑ t : Fin n, if σ = F t then 1 / (n : ℝ) else 0) else 0) = ∑ t : Fin n, (if σ = F t then (if F t g = i then 1 / (n : ℝ) else 0) else 0) := by intro σ have h1 : (if σ g = i then (∑ t : Fin n, if σ = F t then 1 / (n : ℝ) else 0) else 0) = ∑ t : Fin n, (if σ g = i then (if σ = F t then 1 / (n : ℝ) else 0) else 0) := by split_ifs with hg · rfl · simp rw [h1] congr 1; ext t by_cases heq : σ = F t · subst heq split_ifs <;> rfl · simp [heq] simp_rw [h_split] rw [sum_comm] have h_inner : ∀ t : Fin n, (∑ σ : Fin (n * k) → Fin n, if σ = F t then (if F t g = i then 1 / (n : ℝ) else 0) else 0) = if F t g = i then 1 / (n : ℝ) else 0 := by intro t rw [sum_ite_eq'] simp simp_rw [h_inner] let e := Equiv.ofBijective (fun t => F t g) (hF_bij g) have h := (Equiv.sum_comp e (fun x => if x = i then 1 / (n : ℝ) else 0)).symm have he : ∀ t, e t = F t g := fun _ => rfl simp_rw [he] at h rw [← h, sum_ite_eq'] simp
Any allocation with positive probability in $p$ is one of the allocations $F_t$.
Suppose for contradiction that an allocation $\sigma$ is not equal to $F_t$ for any $t$. Then every term in the definition of $p(\sigma)$ is zero by `if_neg`, so the sum is zero by `sum_const_zero`. This contradicts $p(\sigma) > 0$. Hence $\sigma = F_t$ for some $t$.
uses
if_neg,sum_const_zero· intro σ hσ have h_ex : ∃ t : Fin n, σ = F t := by by_contra h_not have h_zero : p σ = 0 := by dsimp [p] have : ∀ t : Fin n, (if σ = F t then 1 / (n : ℝ) else 0) = 0 := by intro t have : ¬ σ = F t := fun h => h_not ⟨t, h⟩ rw [if_neg this] simp_rw [this, sum_const_zero] linarith rcases h_ex with ⟨t, rfl⟩
Every allocation $F_t$ gives each agent at most $\frac{r+1}{2}$ times her chore maximin share.
For each agent $i$, her bundle $F_t(i)$ has cardinality $k$, and the number of high-cost chores in it satisfies $n \cdot |F_t(i) \cap H_i| \le |H_i| + n - 1$. Applying `balanced_high_count_chore_mms_bound` with these hypotheses establishes that agent $i$'s total cost in allocation $F_t$ is at most $\frac{r+1}{2}$ times her maximin share.
uses
balanced_high_count_chore_mms_boundintro i have h_inter : bundle_of (F t) i ∩ univ.filter (fun g => c i g = r * a i) = (bundle_of (F t) i).filter (fun g => c i g = r * a i) := by ext g simp have hh : n * ((bundle_of (F t) i).filter (fun g => c i g = r * a i)).card ≤ (univ.filter (fun g => c i g = r * a i)).card + n - 1 := by rw [← h_inter] exact (hF_prop t i).2 exact balanced_high_count_chore_mms_bound n k hn hk r hr (a i) (ha_pos i) (c i) (ha_val i) (bundle_of (F t) i) (hF_prop t i).1 hh
equal_marginal_balanced_high_count_allocations- Given $n$ agents, $n k$ chores, and a target subset of chores $H_i$ for each agent $i$, there exists a family of $n$ allocations $F_t$ such that every chore is assigned bijectively across the $n$ allocations, and every agent in each allocation receives $k$ chores with balanced high-cost count $n \cdot |F_t(i) \cap H_i| \le |H_i| + n - 1$.
sum_nonneg- A finite sum of non-negative elements in an ordered additive monoid is non-negative.
sum_comm- The order of summation in a double finite sum can be interchanged.
sum_ite_eq'- Summing an indicator that tests equality to a fixed element $a$ over a finite set evaluates to the term at $a$ if $a$ belongs to the set, and $0$ otherwise.
Equiv.ofBijective- A bijective function between two types induces an equivalence (bijection) between them.
Equiv.sum_comp- Summing a function over a finite type yields the same result when reindexed by an equivalence of the domain.
if_neg- An if-then-else expression whose condition is false evaluates to its else branch.
sum_const_zero- A finite sum where every term is zero equals zero.
balanced_high_count_chore_mms_bound- For scaled bivalued chore costs with ratio $r \ge 1$ and base cost $a > 0$, any bundle of $k$ chores whose high-cost chore count satisfies $n \cdot |S \cap H| \le |H| + n - 1$ has total cost at most $\frac{r+1}{2}$ times the agent's chore maximin share.
- The proof relies on two substantial combinatorial results from the knowledge base: `equal_marginal_balanced_high_count_allocations`, which constructs a family of allocations balancing the high-cost chores while assigning each chore bijectively across the allocations, and `balanced_high_count_chore_mms_bound`, which converts the balance inequality on high-cost chores into the $((r+1)/2)$-maximin share bound.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem all_agent_bivalued_equal_marginal_divisible_chores (n k : ℕ) (hn : 2 ≤ n) (hk : 2 ≤ k) (r : ℝ) (hr : 1 ≤ r) (c : Fin n → Fin (n*k) → ℝ) (hc : is_scaled_bivalued_chores r c) : ∃ p ∈ stdSimplex ℝ (Fin (n*k) → Fin n), is_equal_marginal_lottery p ∧ is_ex_post_alpha_mms_chores ((r+1)/2) c p := by open Finset in rcases hc with ⟨a, ha_pos, ha_val⟩ let H : Fin n → Finset (Fin (n*k)) := fun i => univ.filter (fun g => c i g = r * a i) obtain ⟨F, hF_bij, hF_prop⟩ := equal_marginal_balanced_high_count_allocations n k hn hk H let p : (Fin (n*k) → Fin n) → ℝ := fun σ => ∑ t : Fin n, if σ = F t then 1 / (n : ℝ) else 0 have hn_pos : (n : ℝ) ≠ 0 := by positivity have hp_simp : p ∈ stdSimplex ℝ (Fin (n*k) → Fin n) := by dsimp [stdSimplex, p] constructor · intro σ apply sum_nonneg intro t _ split_ifs · positivity · rfl · rw [sum_comm] have h1 : ∀ t : Fin n, (∑ x : Fin (n * k) → Fin n, if x = F t then 1 / (n : ℝ) else 0) = 1 / (n : ℝ) := by intro t rw [sum_ite_eq'] simp simp_rw [h1] simp [hn_pos] refine ⟨p, hp_simp, ?_, ?_⟩ · intro g i dsimp [p] have h_split : ∀ σ : Fin (n * k) → Fin n, (if σ g = i then (∑ t : Fin n, if σ = F t then 1 / (n : ℝ) else 0) else 0) = ∑ t : Fin n, (if σ = F t then (if F t g = i then 1 / (n : ℝ) else 0) else 0) := by intro σ have h1 : (if σ g = i then (∑ t : Fin n, if σ = F t then 1 / (n : ℝ) else 0) else 0) = ∑ t : Fin n, (if σ g = i then (if σ = F t then 1 / (n : ℝ) else 0) else 0) := by split_ifs with hg · rfl · simp rw [h1] congr 1; ext t by_cases heq : σ = F t · subst heq split_ifs <;> rfl · simp [heq] simp_rw [h_split] rw [sum_comm] have h_inner : ∀ t : Fin n, (∑ σ : Fin (n * k) → Fin n, if σ = F t then (if F t g = i then 1 / (n : ℝ) else 0) else 0) = if F t g = i then 1 / (n : ℝ) else 0 := by intro t rw [sum_ite_eq'] simp simp_rw [h_inner] let e := Equiv.ofBijective (fun t => F t g) (hF_bij g) have h := (Equiv.sum_comp e (fun x => if x = i then 1 / (n : ℝ) else 0)).symm have he : ∀ t, e t = F t g := fun _ => rfl simp_rw [he] at h rw [← h, sum_ite_eq'] simp · intro σ hσ have h_ex : ∃ t : Fin n, σ = F t := by by_contra h_not have h_zero : p σ = 0 := by dsimp [p] have : ∀ t : Fin n, (if σ = F t then 1 / (n : ℝ) else 0) = 0 := by intro t have : ¬ σ = F t := fun h => h_not ⟨t, h⟩ rw [if_neg this] simp_rw [this, sum_const_zero] linarith rcases h_ex with ⟨t, rfl⟩ intro i have h_inter : bundle_of (F t) i ∩ univ.filter (fun g => c i g = r * a i) = (bundle_of (F t) i).filter (fun g => c i g = r * a i) := by ext g simp have hh : n * ((bundle_of (F t) i).filter (fun g => c i g = r * a i)).card ≤ (univ.filter (fun g => c i g = r * a i)).card + n - 1 := by rw [← h_inter] exact (hF_prop t i).2 exact balanced_high_count_chore_mms_bound n k hn hk r hr (a i) (ha_pos i) (c i) (ha_val i) (bundle_of (F t) i) (hF_prop t i).1 hh