AFTD Auto-Formalizing Theoretical Domains

large_low_quota_sharp_mms_counterexample

theoremverified

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.

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

    lines 8–10

      ⟨if g.val < 49 then g.val / 7 else 7 + (g.val - 49) / 4, by
        have := g.isLt
        split_ifs <;> omega⟩
  2. 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.

    lines 15–17

    uses Finset.sum_ite, Finset.sum_const, Finset.filter_mem_eq_inter, Finset.filter_notMem_eq_sdiff, nsmul_eq_mul

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

    lines 21–29

    uses in849_value

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

    lines 36–40

    uses ciInf_le, Set.finite_range, ciSup_le, in849_partition_cost

      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)
  5. 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}.

    line 41

      refine ⟨in849_low, in849_cost, in849_bundle, ?_, ?_, ?_, ?_⟩
  6. 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|.

    lines 42–44

      · intro g; rfl
      · decide
      · decide
  7. 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.

    lines 45–51

    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

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