balanced_high_counts_insufficient_for_sharp_mms
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$).
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$.
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
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\}$.
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]
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$.
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
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$.
uses
ciInf_le,Set.finite_range,ciSup_le,le_of_eqhave 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
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$.
refine ⟨u, {0,1,4}, ?_, ?_, ?_, ?_⟩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$.
· intro g; simp only [u]; split_ifs <;> norm_num
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.
· simpThe 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$.
· 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
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.
· 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.
- The bundle assignments and sets of high-cost chores are verified by exhaustive case analysis over the finite type `Fin 7` using `fin_cases`.
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 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