AFTD Auto-Formalizing Theoretical Domains

balanced_high_counts_insufficient_for_sharp_mms

theoremverifiedoriginal

There are seven chores, costs equal to 1 or 3/2, and a bundle S such that three times the number of chores in S is at most 9, three times the number of 3/2-cost chores in S is at most the total number of 3/2-cost chores plus 2, but the cost of S is strictly greater than 5/4 times the three-agent chore maximin share.

Statement

theorem balanced_high_counts_insufficient_for_sharp_mms : ∃ (u : Fin 7 → ℝ) (S : Finset (Fin 7)), (∀ g, u g = 1 ∨ u g = 3/2) ∧ 3*S.card ≤ 9 ∧ 3*(S.filter fun g => u g = (3/2:ℝ)).card ≤ (Finset.univ.filter fun g => u g = (3/2:ℝ)).card + 2 ∧ (5/4:ℝ)*chore_maximin_share 3 u < additive_valuation u S
Related work
A counterexample to a possible strengthening of the sorted-slot counting argument for OP-1112; experiments 15120 and 26800.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • chore_maximin_shareThe maximin share (MMS) of an agent with additive chore costs u among n agents: the infimum over all partitions P : Fin m → Fin n of the…
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • 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

There exist a utility/cost function $u : \mathrm{Fin}\ 7 \to \mathbb{R}$ and a subset $S \subseteq \mathrm{Fin}\ 7$ such that all of the following hold: 1. For every $g \in \mathrm{Fin}\ 7$, either $u(g) = 1$ or $u(g) = 3/2$. 2. $3 \cdot |S| \le 9$ (equivalently, $|S| \le 3$). 3. $3 \cdot |\{g \in S \mid u(g) = 3/2\}| \le |\{g \in \mathrm{Fin}\ 7 \mid u(g) = 3/2\}| + 2$. 4. $\frac{5}{4} \cdot \mathrm{chore\_maximin\_share}(3, u) < \mathrm{additive\_valuation}(u, S)$.

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 an explicit counterexample with seven chores among three agents. Four chores have cost $3/2$ and three chores have cost $1$. A partition into bundles $\{0, 1\}$, $\{2, 3\}$, and $\{4, 5, 6\}$, each costing exactly $3$, proves that the chore maximin share is at most $3$. The bundle $S = \{0, 1, 4\}$ satisfies both the cardinality bound $3|S| \le 9$ and the balanced high-cost count condition $3 \times 2 \le 4 + 2$, but its total cost of $4$ strictly exceeds $5/4$ of the maximin share ($5/4 \times 3 = 3.75$).

  1. Define the chore valuation $u$ and the candidate partition $P_0$

    We define the cost function $u$ assigning cost $3/2$ to the first four chores ($0, 1, 2, 3$) and cost $1$ to the remaining three chores ($4, 5, 6$). We also define a three-way partition $P_0$ assigning chores $0, 1$ to agent $0$, chores $2, 3$ to agent $1$, and chores $4, 5, 6$ to agent $2$.

    lines 2–3

      let u : Fin 7 → ℝ := fun (g : Fin 7) => if (g : ℕ) < 4 then (3/2:ℝ) else 1
      let P0 : Fin 7 → Fin 3 := fun (g : Fin 7) => if (g : ℕ) < 2 then (0:Fin 3) else if (g:ℕ) < 4 then 1 else 2
  2. The bundles produced by partition $P_0$ are $\{0, 1\}$, $\{2, 3\}$, and $\{4, 5, 6\}$

    For each agent $k \in \{0, 1, 2\}$, the bundle of chores assigned by $P_0$ is verified by exhaustive check over all seven chores (`fin_cases g`), showing that agent $0$ receives $\{0, 1\}$, agent $1$ receives $\{2, 3\}$, and agent $2$ receives $\{4, 5, 6\}$.

    lines 4–6

      have hb0 : bundle_of P0 (0:Fin 3) = {0,1} := by ext g; fin_cases g <;> simp [bundle_of, P0]
      have hb1 : bundle_of P0 (1:Fin 3) = {2,3} := by ext g; fin_cases g <;> simp [bundle_of, P0]
      have hb2 : bundle_of P0 (2:Fin 3) = {4,5,6} := by ext g; fin_cases g <;> simp [bundle_of, P0]
  3. Each of the three bundles under partition $P_0$ has total cost equal to $3$

    Using the explicit bundle contents from the previous step and the definition of $u$, we compute the additive valuation of each bundle: the first two bundles cost $3/2 + 3/2 = 3$, and the third bundle costs $1 + 1 + 1 = 3$.

    lines 7–12

      have e0 : additive_valuation u (bundle_of P0 (0:Fin 3)) = 3 := by
        rw [hb0]; simp [u, additive_valuation]
      have e1 : additive_valuation u (bundle_of P0 (1:Fin 3)) = 3 := by
        rw [hb1]; simp [u, additive_valuation]
      have e2 : additive_valuation u (bundle_of P0 (2:Fin 3)) = 3 := by
        rw [hb2]; simp [u, additive_valuation]; norm_num
  4. The three-agent chore maximin share for $u$ is at most $3$

    By definition, the chore maximin share is the infimum over all partitions of the maximum bundle cost. Evaluating at partition $P_0$ gives an upper bound on this infimum via `ciInf_le` (since the partition domain is finite, the range of max bundle costs is finite by `Set.finite_range`, hence bounded below). Because each bundle under $P_0$ costs at most $3$ by `le_of_eq` applied to the bundle valuations, the supremum over all bundles in $P_0$ is at most $3$ by `ciSup_le`. Linear arithmetic combines these to conclude $\text{chore\_maximin\_share}\; 3\; u \le 3$.

    lines 13–24

    uses ciInf_le, Set.finite_range, ciSup_le, le_of_eq

      have hMMS : chore_maximin_share 3 u ≤ 3 := by
        have h1 : chore_maximin_share 3 u ≤ ⨆ (k : Fin 3), additive_valuation u (bundle_of P0 k) := by
          have h : chore_maximin_share 3 u = ⨅ (P : Fin 7 → Fin 3), ⨆ (k : Fin 3), additive_valuation u (bundle_of P k) := rfl
          rw [h]
          exact ciInf_le (Set.finite_range _).bddBelow P0
        have h2 : (⨆ (k : Fin 3), additive_valuation u (bundle_of P0 k)) ≤ 3 := by
          refine ciSup_le (fun k => ?_)
          fin_cases k
          · exact le_of_eq e0
          · exact le_of_eq e1
          · exact le_of_eq e2
        linarith
  5. Provide $u$ and the bundle $S = \{0, 1, 4\}$ as witnesses for the existential statement

    We instantiate the existential quantifier with the valuation $u$ and candidate bundle $S = \{0, 1, 4\}$, splitting the goal into four verification subgoals: every chore cost is $1$ or $3/2$, $3 \cdot |S| \le 9$, the high-cost count condition holds, and the valuation of $S$ strictly exceeds $(5/4) \cdot \text{chore\_maximin\_share}\; 3\; u$.

    line 25

      refine ⟨u, {0,1,4}, ?_, ?_, ?_, ?_⟩
  6. Every chore has cost either $1$ or $3/2$

    For any chore $g$, we split on the definition of $u$: if $g < 4$, the cost is $3/2$; if $g \ge 4$, the cost is $1$. Both cases satisfy the disjunction $u(g) = 1 \lor u(g) = 3/2$.

    line 26

      · intro g; simp only [u]; split_ifs <;> norm_num
  7. Three times the cardinality of bundle $S$ is at most $9$

    The bundle $S = \{0, 1, 4\}$ contains $3$ items, so $3 \cdot |S| = 3 \times 3 = 9 \le 9$, which Lean verifies by simplification.

    line 27

      · simp
  8. The balanced high-cost count condition holds for $S$

    We verify by exhaustive element-by-element evaluation that the set of high-cost chores in $S$ is $\{0, 1\}$ (cardinality 2), while the total set of high-cost chores across all items is $\{0, 1, 2, 3\}$ (cardinality 4). Substituting these sets into the condition yields $3 \times 2 \le 4 + 2$, which evaluates to $6 \le 6$.

    lines 28–32

      · have h1 : (({0,1,4} : Finset (Fin 7)).filter (fun g => u g = (3/2:ℝ))) = {0,1} := by
          ext g; fin_cases g <;> simp [u] <;> norm_num
        have h2 : ((Finset.univ : Finset (Fin 7)).filter (fun g => u g = (3/2:ℝ))) = {0,1,2,3} := by
          ext g; fin_cases g <;> simp [u] <;> norm_num
        rw [h1, h2]; simp
  9. The cost of $S$ strictly exceeds $5/4$ times the chore maximin share

    The additive valuation of $S = \{0, 1, 4\}$ is $u(0) + u(1) + u(4) = 3/2 + 3/2 + 1 = 4$. Since the chore maximin share is at most $3$, $(5/4) \cdot \text{chore\_maximin\_share}\; 3\; u \le (5/4) \times 3 = 15/4 = 3.75 < 4$, which linear arithmetic (`linarith`) completes.

    lines 33–36

      · have hcost : additive_valuation u {0,1,4} = 4 := by
          simp [u, additive_valuation]; norm_num
        rw [hcost]
        linarith
ciInf_le
In a conditionally complete lattice, the infimum of a set bounded below is less than or equal to any element in the set.
ciSup_le
In a conditionally complete lattice, the supremum of a non-empty family is at most $c$ if every element of the family is at most $c$.
le_of_eq
If two elements in a preorder are equal, then the first is less than or equal to the second.
Set.finite_range
The range of a function defined on a finite domain is a finite set.

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 balanced_high_counts_insufficient_for_sharp_mms : ∃ (u : Fin 7 → ℝ) (S : Finset (Fin 7)), (∀ g, u g = 1 ∨ u g = 3/2) ∧ 3*S.card ≤ 9 ∧ 3*(S.filter fun g => u g = (3/2:ℝ)).card ≤ (Finset.univ.filter fun g => u g = (3/2:ℝ)).card + 2 ∧ (5/4:ℝ)*chore_maximin_share 3 u < additive_valuation u S := by  let u : Fin 7 → ℝ := fun (g : Fin 7) => if (g : ℕ) < 4 then (3/2:ℝ) else 1  let P0 : Fin 7 → Fin 3 := fun (g : Fin 7) => if (g : ℕ) < 2 then (0:Fin 3) else if (g:ℕ) < 4 then 1 else 2  have hb0 : bundle_of P0 (0:Fin 3) = {0,1} := by ext g; fin_cases g <;> simp [bundle_of, P0]  have hb1 : bundle_of P0 (1:Fin 3) = {2,3} := by ext g; fin_cases g <;> simp [bundle_of, P0]  have hb2 : bundle_of P0 (2:Fin 3) = {4,5,6} := by ext g; fin_cases g <;> simp [bundle_of, P0]  have e0 : additive_valuation u (bundle_of P0 (0:Fin 3)) = 3 := by    rw [hb0]; simp [u, additive_valuation]  have e1 : additive_valuation u (bundle_of P0 (1:Fin 3)) = 3 := by    rw [hb1]; simp [u, additive_valuation]  have e2 : additive_valuation u (bundle_of P0 (2:Fin 3)) = 3 := by    rw [hb2]; simp [u, additive_valuation]; norm_num  have hMMS : chore_maximin_share 3 u ≤ 3 := by    have h1 : chore_maximin_share 3 u ≤ ⨆ (k : Fin 3), additive_valuation u (bundle_of P0 k) := by      have h : chore_maximin_share 3 u = ⨅ (P : Fin 7 → Fin 3), ⨆ (k : Fin 3), additive_valuation u (bundle_of P k) := rfl      rw [h]      exact ciInf_le (Set.finite_range _).bddBelow P0    have h2 : (⨆ (k : Fin 3), additive_valuation u (bundle_of P0 k)) ≤ 3 := by      refine ciSup_le (fun k => ?_)      fin_cases k      · exact le_of_eq e0      · exact le_of_eq e1      · exact le_of_eq e2    linarith  refine ⟨u, {0,1,4}, ?_, ?_, ?_, ?_⟩  · intro g; simp only [u]; split_ifs <;> norm_num  · simp  · have h1 : (({0,1,4} : Finset (Fin 7)).filter (fun g => u g = (3/2:ℝ))) = {0,1} := by      ext g; fin_cases g <;> simp [u] <;> norm_num    have h2 : ((Finset.univ : Finset (Fin 7)).filter (fun g => u g = (3/2:ℝ))) = {0,1,2,3} := by      ext g; fin_cases g <;> simp [u] <;> norm_num    rw [h1, h2]; simp  · have hcost : additive_valuation u {0,1,4} = 4 := by      simp [u, additive_valuation]; norm_num    rw [hcost]    linarith
See it in the graphDiscuss this resultChallenge it