AFTD Auto-Formalizing Theoretical Domains

all_agent_bivalued_equal_marginal_divisible_chores

theoremverifiedoriginal

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`.

  1. 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$.

    lines 2–5

    uses equal_marginal_balanced_high_count_allocations

      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
  2. 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}$.

    lines 6–7

      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
  3. 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.

    lines 8–23

    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]
  4. 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.

    line 24

      refine ⟨p, hp_simp, ?_, ?_⟩
  5. 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'`.

    lines 25–55

    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
  6. 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$.

    lines 56–67

    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⟩
  7. 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.

    lines 68–78

    uses balanced_high_count_chore_mms_bound

        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
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.

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

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
See it in the graphDiscuss this resultChallenge it