AFTD Auto-Formalizing Theoretical Domains

ido_remaining_chores_cost_le_one_third

theoremverified

In an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at least 2n) has cost at most 1/3 for each agent i.

Statement

lemma ido_remaining_chores_cost_le_one_third
    (n m : ℕ) (h2n : 2 * n ≤ m) (c : Fin n → Fin m → ℝ)
    (hc_nonneg : ∀ i e, 0 ≤ c i e)
    (h_ido : is_identically_ordered c)
    (h_mms : ∀ i : Fin n, chore_maximin_share n (c i) = 1)
    (i : Fin n) (g : Fin m) (hg : g ∈ chore_remaining_set m n) :
    c i g ≤ 1 / 3
Source
arXiv:2611.04884 Lemma 4.1
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • is_identically_orderedAn instance of m chores and n agents with cost functions c is identically ordered (IDO) if for every agent i, the cost function c_i is…
  • chore_remaining_setFor m chores and n agents, the set V of remaining chores consists of all chores whose index is at least 2n.
  • 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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • 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.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 1

Read back from the Lean

Given natural numbers $n$ and $m$ satisfying $2n \le m$, and a cost function $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ mapping each agent and chore to a real cost, assume: 1. Every cost is non-negative: $0 \le c(i, e)$ for all $i : \text{Fin } n$ and $e : \text{Fin } m$. 2. Costs are identically ordered: for each agent $i : \text{Fin } n$, the function $c(i)$ is antitone (i.e., non-increasing with respect to the index of the chores). 3. The chore maximin share of each agent $i$ among $n$ partitions equals 1: $\text{chore\_maximin\_share } n (c(i)) = 1$. Then, for any agent $i : \text{Fin } n$ and any chore $g : \text{Fin } m$ whose index satisfies $2n \le g.val$ (i.e., $g \in \text{chore\_remaining\_set } m\ n$), the cost $c(i, g)$ is at most $1/3$.

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

To show that any remaining chore g (with index at least 2n) has cost at most 1/3 for agent i, the proof examines an arbitrary partition P of the chores among the n agents. Since there are 2n + 1 chores with index at most 2n, the pigeonhole principle guarantees that some agent receives at least 3 of these chores. In an identically ordered instance, chore costs are non-increasing with respect to chore index, so each of these at least 3 chores costs at least c i g, making that agent's bundle cost at least 3 * c i g. Consequently, the maximum bundle cost in any partition is at least 3 * c i g, which gives a lower bound of 3 * c i g on the chore maximin share. Since agent i's maximin share is 1, this forces 3 * c i g ≤ 1, yielding c i g ≤ 1/3.

  1. The chore b with index 2n is a valid element of Fin m and satisfies b ≤ g.

    The hypothesis that g belongs to the remaining chores means that its index is at least 2n. Because g < m, we have 2n < m, which allows us to define the boundary chore b = 2n in Fin m. Since g has index at least 2n, b ≤ g.

    lines 9–16

    uses Finset.mem_filter, Finset.mem_univ, true_and

      have h2n_lt : 2 * n < m := by
        simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg
        omega
      have hg_val : 2 * n ≤ g.val := by
        simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg
        exact hg
      let b : Fin m := ⟨2 * n, h2n_lt⟩
      have hb_le_g : b ≤ g := hg_val
  2. Under any partition P of chores among the n agents, some agent y receives at least 3 chores from {0, …, b}.

    Fix an arbitrary chore allocation P : Fin m → Fin n. The initial prefix of chores {0, …, b} contains b + 1 = 2n + 1 chores. By the generalized pigeonhole principle (`Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to`), since there are n agents and 2n + 1 > 2n, some agent y must receive strictly more than 2 chores from this set.

    lines 17–26

    uses Finset.card_univ, Fintype.card_fin, Fin.card_Iic, Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to

      have hP : ∀ P : Fin m → Fin n, 3 * c i g ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by
        intro P
        have hmaps : ∀ a ∈ Finset.Iic b, P a ∈ (Finset.univ : Finset (Fin n)) := by simp
        have hcard : (Finset.univ : Finset (Fin n)).card * 2 < (Finset.Iic b).card := by
          rw [Finset.card_univ, Fintype.card_fin, Fin.card_Iic b]
          dsimp [b]
          omega
        obtain ⟨y, -, hy⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to hmaps hcard
        let Sy := Finset.filter (fun x => P x = y) (Finset.Iic b)
        have hy' : 2 < Sy.card := hy
  3. The cost to agent i of the sub-collection Sy ⊆ {0, …, b} assigned to agent y is at most the total cost of agent y's bundle.

    The set Sy consists of the chores up to b allocated to agent y, which is a subset of agent y's full bundle under P. Because all chore costs are non-negative, the sum of costs over Sy is bounded by the sum of costs over the entire bundle.

    lines 27–35

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.sum_le_sum_of_subset_of_nonneg

        have hSy_sub : Sy ⊆ bundle_of P y := by
          intro x hx
          rw [Finset.mem_filter] at hx
          simp only [Finset.mem_filter, bundle_of, Finset.mem_univ, true_and]
          exact hx.2
        have hSy_le_bundle : ∑ x ∈ Sy, c i x ≤ ∑ x ∈ bundle_of P y, c i x := by
          apply Finset.sum_le_sum_of_subset_of_nonneg hSy_sub
          intro x _ _
          exact hc_nonneg i x
  4. Agent y's bundle under partition P has cost at least 3 * c i g for agent i.

    Every chore x in Sy satisfies x ≤ b ≤ g. Since the instance is identically ordered, agent i's cost function is antitone (non-increasing with index), so each x ∈ Sy satisfies c i x ≥ c i g. Summing this over Sy gives |Sy| * c i g ≤ ∑ x ∈ Sy, c i x. Since |Sy| ≥ 3 and chore costs are non-negative, 3 * c i g ≤ |Sy| * c i g. Transitivity with the bundle bound shows that agent y's bundle costs at least 3 * c i g.

    lines 36–52

    uses Finset.mem_filter, Finset.mem_Iic.mp, le_trans, Finset.sum_le_sum

        have h_cg_le_x : ∀ x ∈ Sy, c i g ≤ c i x := by
          intro x hx
          rw [Finset.mem_filter] at hx
          have hxb : x ≤ b := Finset.mem_Iic.mp hx.1
          have hxg : x ≤ g := le_trans hxb hb_le_g
          exact h_ido i hxg
        have h_sum_cg : (Sy.card : ℝ) * c i g ≤ ∑ x ∈ Sy, c i x := by
          have : ∑ _x ∈ Sy, c i g ≤ ∑ x ∈ Sy, c i x := Finset.sum_le_sum h_cg_le_x
          simpa using this
        have h3_card : 3 * c i g ≤ (Sy.card : ℝ) * c i g := by
          have hcig : 0 ≤ c i g := hc_nonneg i g
          have h3_le : (3 : ℝ) ≤ (Sy.card : ℝ) := by
            exact_mod_cast (show 3 ≤ Sy.card by omega)
          nlinarith
        have h3_le_bundle : 3 * c i g ≤ additive_valuation (c i) (bundle_of P y) := by
          dsimp [additive_valuation]
          linarith
  5. Under any partition P, the maximum bundle cost for agent i is at least 3 * c i g.

    The valuation of agent y's bundle is bounded above by the supremum over all agents k of the valuation of agent k's bundle. Since agent y's bundle costs at least 3 * c i g, this supremum is also at least 3 * c i g.

    lines 53–55

    uses le_ciSup, Finite.bddAbove_range

        have hbundle_le_sup : additive_valuation (c i) (bundle_of P y) ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) :=
          le_ciSup (Finite.bddAbove_range (fun k => additive_valuation (c i) (bundle_of P k))) y
        linarith
  6. The cost c i g of remaining chore g is at most 1/3.

    Because 3 * c i g bounds the maximum bundle cost for every partition P, it is at most the infimum over all partitions. By definition, this infimum is agent i's chore maximin share, which is 1. Hence 3 * c i g ≤ 1, which implies c i g ≤ 1/3.

    lines 56–62

    uses le_ciInf

      have h_mms_i := h_mms i
      dsimp [chore_maximin_share] at h_mms_i
      have : Nonempty (Fin m → Fin n) := ⟨fun _ => i⟩
      have h3_le_inf : 3 * c i g ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) :=
        le_ciInf hP
      rw [h_mms_i] at h3_le_inf
      linarith
Finset.mem_filter
An element a belongs to a filtered finset {x ∈ s | p x} if and only if a ∈ s and p a holds.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
true_and
The conjunction True ∧ p simplifies to p.
Finset.card_univ
The cardinality of the universal finset on α equals the cardinality of the finite type α.
Fintype.card_fin
The type Fin n of natural numbers strictly less than n has cardinality n.
Fin.card_Iic
In Fin n, the prefix interval {x | x ≤ b} has cardinality b + 1.
Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to
Generalized pigeonhole principle: if f maps a finset s into a finset t and |t| * k < |s|, then some element y ∈ t has strictly more than k preimages in s.
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t and the summands are non-negative outside s, then the sum over s is at most the sum over t.
Finset.mem_Iic.mp
An element of the closed prefix interval {x | x ≤ b} satisfies x ≤ b.
le_trans
The order relation ≤ is transitive: a ≤ b and b ≤ c imply a ≤ c.
Finset.sum_le_sum
If f x ≤ g x for all elements x in a finset s, then the sum of f over s is at most the sum of g over s.
le_ciSup
In a conditionally complete lattice, every element in the range of a bounded-above function is at most its supremum.
Finite.bddAbove_range
The range of a function from a finite type to a preorder is bounded above.
le_ciInf
In a conditionally complete lattice, if c is a lower bound for f(x) for all x in a nonempty type, then c ≤ ⨅ x, f x.

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

/-- In an IDO instance with MMS 1, each remaining chore has cost at most 1/3. -/lemma ido_remaining_chores_cost_le_one_third    (n m : ℕ) (h2n : 2 * n ≤ m) (c : Fin n → Fin m → ℝ)    (hc_nonneg : ∀ i e, 0 ≤ c i e)    (h_ido : is_identically_ordered c)    (h_mms : ∀ i : Fin n, chore_maximin_share n (c i) = 1)    (i : Fin n) (g : Fin m) (hg : g ∈ chore_remaining_set m n) :    c i g ≤ 1 / 3 := by  have h2n_lt : 2 * n < m := by    simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg    omega  have hg_val : 2 * n ≤ g.val := by    simp only [chore_remaining_set, Finset.mem_filter, Finset.mem_univ, true_and] at hg    exact hg  let b : Fin m := ⟨2 * n, h2n_lt⟩  have hb_le_g : b ≤ g := hg_val  have hP : ∀ P : Fin m → Fin n, 3 * c i g ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) := by    intro P    have hmaps : ∀ a ∈ Finset.Iic b, P a ∈ (Finset.univ : Finset (Fin n)) := by simp    have hcard : (Finset.univ : Finset (Fin n)).card * 2 < (Finset.Iic b).card := by      rw [Finset.card_univ, Fintype.card_fin, Fin.card_Iic b]      dsimp [b]      omega    obtain ⟨y, -, hy⟩ := Finset.exists_lt_card_fiber_of_mul_lt_card_of_maps_to hmaps hcard    let Sy := Finset.filter (fun x => P x = y) (Finset.Iic b)    have hy' : 2 < Sy.card := hy    have hSy_sub : Sy ⊆ bundle_of P y := by      intro x hx      rw [Finset.mem_filter] at hx      simp only [Finset.mem_filter, bundle_of, Finset.mem_univ, true_and]      exact hx.2    have hSy_le_bundle : ∑ x ∈ Sy, c i x ≤ ∑ x ∈ bundle_of P y, c i x := by      apply Finset.sum_le_sum_of_subset_of_nonneg hSy_sub      intro x _ _      exact hc_nonneg i x    have h_cg_le_x : ∀ x ∈ Sy, c i g ≤ c i x := by      intro x hx      rw [Finset.mem_filter] at hx      have hxb : x ≤ b := Finset.mem_Iic.mp hx.1      have hxg : x ≤ g := le_trans hxb hb_le_g      exact h_ido i hxg    have h_sum_cg : (Sy.card : ℝ) * c i g ≤ ∑ x ∈ Sy, c i x := by      have : ∑ _x ∈ Sy, c i g ≤ ∑ x ∈ Sy, c i x := Finset.sum_le_sum h_cg_le_x      simpa using this    have h3_card : 3 * c i g ≤ (Sy.card : ℝ) * c i g := by      have hcig : 0 ≤ c i g := hc_nonneg i g      have h3_le : (3 : ℝ) ≤ (Sy.card : ℝ) := by        exact_mod_cast (show 3 ≤ Sy.card by omega)      nlinarith    have h3_le_bundle : 3 * c i g ≤ additive_valuation (c i) (bundle_of P y) := by      dsimp [additive_valuation]      linarith    have hbundle_le_sup : additive_valuation (c i) (bundle_of P y) ≤ ⨆ k, additive_valuation (c i) (bundle_of P k) :=      le_ciSup (Finite.bddAbove_range (fun k => additive_valuation (c i) (bundle_of P k))) y    linarith  have h_mms_i := h_mms i  dsimp [chore_maximin_share] at h_mms_i  have : Nonempty (Fin m → Fin n) := ⟨fun _ => i⟩  have h3_le_inf : 3 * c i g ≤ ⨅ P, ⨆ k, additive_valuation (c i) (bundle_of P k) :=    le_ciInf hP  rw [h_mms_i] at h3_le_inf  linarith
See it in the graphDiscuss this resultChallenge it