large_low_quota_sharp_mms_counterexample
With eleven agents and sixty-five chores, there is a bivalued cost function with ratio 7/4 and a bundle of six chores that meets the original one-low quota but costs more than 11/8 times the agent’s eleven-agent chore maximin share.
Statement
theorem large_low_quota_sharp_mms_counterexample : ∃ (L : Finset (Fin 65)) (u : Fin 65 → ℝ) (S : Finset (Fin 65)), (∀ g, u g = if g ∈ L then 1 else (7/4 : ℝ)) ∧ S.card ≤ 6 ∧ min 6 (L.card / 10) - 6/2 ≤ (S ∩ L).card ∧ (11/8 : ℝ) * chore_maximin_share 11 u < additive_valuation u S
- Source
- The counterexample to a proposed OP-1112 large-bundle quota bound in experiment 26950.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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…
The proof, explained
The theorem is proved by exhibiting an explicit counterexample with 11 agents and 65 chores: 49 low chores of cost 1 and 16 high chores of cost 7/4. An explicit partition gives 7 agents 7 low chores each and 4 agents 4 high chores each, ensuring every bundle costs 7 and bounding the chore maximin share from above by 7. A 6-chore bundle consisting of 1 low chore and 5 high chores satisfies the size and one-low quota conditions but costs 39/4 = 78/8, strictly exceeding (11/8) * 7 = 77/8.
The chore partition in849_partition is well-defined, assigning each of the 65 chores to an agent index strictly less than 11.
For chore g < 49, the assigned agent index is g / 7 ≤ 48 / 7 = 6 < 11. For chore g ≥ 49, the index is 7 + (g - 49) / 4 ≤ 7 + (64 - 49) / 4 = 10 < 11. Both inequalities follow from g < 65 by splitting on g < 49 and linear integer arithmetic (omega).
⟨if g.val < 49 then g.val / 7 else 7 + (g.val - 49) / 4, by have := g.isLt split_ifs <;> omega⟩
The additive valuation of any chore bundle S under in849_cost equals the number of low chores plus 7/4 times the number of high chores.
By definition, in849_cost assigns cost 1 to chores in in849_low and 7/4 to chores outside it. Rewriting the valuation sum by splitting on membership in in849_low using Finset.sum_ite, the constant values 1 and 7/4 factor out using Finset.sum_const and nsmul_eq_mul, while the filtered sets simplify to the intersection and difference using Finset.filter_mem_eq_inter and Finset.filter_notMem_eq_sdiff.
uses
Finset.sum_ite,Finset.sum_const,Finset.filter_mem_eq_inter,Finset.filter_notMem_eq_sdiff,nsmul_eq_mulclassical simp [additive_valuation, in849_cost, Finset.sum_ite, Finset.sum_const, Finset.filter_mem_eq_inter, Finset.filter_notMem_eq_sdiff, nsmul_eq_mul]Under the partition in849_partition, the bundle assigned to each agent i in Fin 11 has cost exactly 7.
Exhaustive verification over all eleven agents using fin_cases and decide shows that each agent i < 7 receives 7 low chores and 0 high chores, while each agent i ≥ 7 receives 0 low chores and 4 high chores. By in849_value, the cost in both cases is 7 * 1 + 0 * (7/4) = 7 and 0 * 1 + 4 * (7/4) = 7, computed by norm_num.
uses
in849_valuehave hlo : ((bundle_of in849_partition i) ∩ in849_low).card = if i.val < 7 then 7 else 0 := by fin_cases i <;> decide have hhi : ((bundle_of in849_partition i) \ in849_low).card = if i.val < 7 then 0 else 4 := by fin_cases i <;> decide rw [in849_value] rw [hlo, hhi] fin_cases i <;> norm_num
The 11-agent chore maximin share for the cost function in849_cost is at most 7.
The chore maximin share is the infimum over all partitions of the maximum bundle cost. Bounding the infimum by the value at the partition in849_partition using ciInf_le (with boundedness below from Set.finite_range), and bounding the maximum bundle cost by 7 using ciSup_le and in849_partition_cost, shows the share is at most 7.
uses
ciInf_le,Set.finite_range,ciSup_le,in849_partition_costclassical have hmms : chore_maximin_share 11 in849_cost ≤ 7 := by unfold chore_maximin_share exact (ciInf_le (Set.finite_range _).bddBelow in849_partition).trans (ciSup_le fun i => (in849_partition_cost i).le)
It suffices to verify the four counterexample properties for in849_low, in849_cost, and in849_bundle.
We provide explicit witnesses: the 49 low chores {0, ..., 48}, the cost function taking values 1 on low chores and 7/4 on high chores, and the 6-chore bundle {0, 49, 50, 51, 52, 53}.
refine ⟨in849_low, in849_cost, in849_bundle, ?_, ?_, ?_, ?_⟩The cost function matches the bivalued specification, the bundle size is at most 6, and the one-low quota condition holds.
The cost function matches by definition (rfl). Finite evaluation (decide) verifies that the bundle has cardinality 6 ≤ 6 and that min(6, 49 / 10) - 6 / 2 = 4 - 3 = 1 ≤ 1 = |S ∩ L|.
· intro g; rfl · decide · decide
The bundle cost is 39/4, which strictly exceeds 11/8 times the chore maximin share.
Finite evaluation shows the bundle contains 1 low chore and 5 high chores. By in849_value, its cost is 1 + 5 * (7/4) = 39/4 = 78/8. Since the chore maximin share is at most 7, 11/8 times the share is at most 77/8. Linear arithmetic confirms 77/8 < 78/8.
uses
in849_value· have hscore : additive_valuation in849_cost in849_bundle = 39/4 := by have hlo : (in849_bundle ∩ in849_low).card = 1 := by decide have hhi : (in849_bundle \ in849_low).card = 5 := by decide rw [in849_value, hlo, hhi] norm_num rw [hscore] linarith
Finset.sum_ite- The sum of a conditional function if p x then f x else g x over a finite set equals the sum of f over elements satisfying p plus the sum of g over elements satisfying not p.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Finset.filter_mem_eq_inter- Filtering a finite set by membership in another set yields their intersection.
Finset.filter_notMem_eq_sdiff- Filtering a finite set by non-membership in another set yields their set difference.
nsmul_eq_mul- Scalar multiplication by a natural number in a semiring coincides with multiplication by the cast of that natural number.
in849_value- The additive valuation of any chore bundle under in849_cost equals the number of low chores plus 7/4 times the number of high chores.
ciInf_le- The infimum of a bounded-below function is at most the function value at any specific point.
Set.finite_range- The range of a function defined on a finite domain is finite.
ciSup_le- The supremum over a nonempty index set is at most c if every element is at most c.
in849_partition_cost- Under the 11-partition in849_partition, every agent receives a bundle with cost exactly 7.
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.
set_option maxHeartbeats 0set_option maxRecDepth 100000private def in849_low : Finset (Fin 65) := Finset.univ.filter fun g => g.val < 49private noncomputable def in849_cost (g : Fin 65) : ℝ := if g ∈ in849_low then 1 else 7/4private def in849_bundle : Finset (Fin 65) := {0, 49, 50, 51, 52, 53}private def in849_partition (g : Fin 65) : Fin 11 := ⟨if g.val < 49 then g.val / 7 else 7 + (g.val - 49) / 4, by have := g.isLt split_ifs <;> omega⟩private lemma in849_value (S : Finset (Fin 65)) : additive_valuation in849_cost S = ((S ∩ in849_low).card : ℝ) + ((S \ in849_low).card : ℝ) * (7/4) := by classical simp [additive_valuation, in849_cost, Finset.sum_ite, Finset.sum_const, Finset.filter_mem_eq_inter, Finset.filter_notMem_eq_sdiff, nsmul_eq_mul]private lemma in849_partition_cost (i : Fin 11) : additive_valuation in849_cost (bundle_of in849_partition i) = 7 := by have hlo : ((bundle_of in849_partition i) ∩ in849_low).card = if i.val < 7 then 7 else 0 := by fin_cases i <;> decide have hhi : ((bundle_of in849_partition i) \ in849_low).card = if i.val < 7 then 0 else 4 := by fin_cases i <;> decide rw [in849_value] rw [hlo, hhi] fin_cases i <;> norm_numtheorem large_low_quota_sharp_mms_counterexample : ∃ (L : Finset (Fin 65)) (u : Fin 65 → ℝ) (S : Finset (Fin 65)), (∀ g, u g = if g ∈ L then 1 else (7/4 : ℝ)) ∧ S.card ≤ 6 ∧ min 6 (L.card / 10) - 6/2 ≤ (S ∩ L).card ∧ (11/8 : ℝ) * chore_maximin_share 11 u < additive_valuation u S := by classical have hmms : chore_maximin_share 11 in849_cost ≤ 7 := by unfold chore_maximin_share exact (ciInf_le (Set.finite_range _).bddBelow in849_partition).trans (ciSup_le fun i => (in849_partition_cost i).le) refine ⟨in849_low, in849_cost, in849_bundle, ?_, ?_, ?_, ?_⟩ · intro g; rfl · decide · decide · have hscore : additive_valuation in849_cost in849_bundle = 39/4 := by have hlo : (in849_bundle ∩ in849_low).card = 1 := by decide have hhi : (in849_bundle \ in849_low).card = 5 := by decide rw [in849_value, hlo, hhi] norm_num rw [hscore] linarith