AFTD Auto-Formalizing Theoretical Domains

ido_chore_opposite_pairs_cost_bounds

theoremverifiedformalization

In an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1, for every agent i : Fin n, every chore g in chore_remaining_set m n has cost c i g ≤ 1/3, and for every index j : Fin n, the additive valuation of chore_opposite_pair h2n j under c i is at most 4/3.

Statement

theorem ido_chore_opposite_pairs_cost_bounds
    (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), g ∈ chore_remaining_set m n → c i g ≤ 1 / 3) ∧
    (∀ (i : Fin n) (j : Fin n), additive_valuation (c i) (chore_opposite_pair h2n j) ≤ 4 / 3)
Formalizes
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_opposite_pairGiven implicit natural numbers m and n, a hypothesis h2n : 2 * n ≤ m, and an element j : Fin n, chore_opposite_pair is defined as the…
  • chore_remaining_setFor m chores and n agents, the set V of remaining chores consists of all chores whose index is at least 2n.
  • ido_remaining_chores_cost_le_one_thirdIn an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at…
  • ido_opposite_pair_cost_le_four_thirdsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
  • 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.

Read back from the Lean

For any natural numbers n and m such that 2 * n ≤ m, and any cost matrix c : Fin n → Fin m → ℝ, assume: 1. Every cost is non-negative: for all i : Fin n and e : Fin m, 0 ≤ c i e. 2. The costs are identically ordered: for each agent i : Fin n, the function c i is antitone (i.e., non-increasing: if a ≤ b in Fin m, then c i b ≤ c i a). 3. The chore maximin share of each agent i among n agents equals 1, where the chore maximin share is defined as the infimum over all partitions P : Fin m → Fin n of the supremum over k : Fin n of the sum of costs of items assigned to k by P. Then: 1. For every agent i : Fin n and every item g : Fin m with index g.val ≥ 2 * n (i.e., g is in the remaining set), c i g ≤ 1 / 3. 2. For every agent i : Fin n and every index j : Fin n, the total cost under c i of the opposite pair {j, 2 * n - 1 - j} in Fin m is at most 4 / 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

The theorem combines two cost bounds for an identically ordered chore allocation instance with $2n \le m$ and maximin share 1 into a single conjunction. The proof directly constructs the pair from two previously established lemmas. The first lemma (`ido_remaining_chores_cost_le_one_third`) bounds the cost of any remaining chore by $1/3$, and the second (`ido_opposite_pair_cost_le_four_thirds`) bounds the total cost of any opposite pair by $4/3$.

  1. For every agent, each chore in the remaining set costs at most $1/3$, and each opposite pair of chores has total cost at most $4/3$.

    The theorem is a conjunction of two bounds under the assumptions of nonnegative costs, identical ordering, and maximin share 1. The proof directly constructs the conjunction pair from two established lemmas: `ido_remaining_chores_cost_le_one_third` gives the upper bound of $1/3$ on remaining chores, and `ido_opposite_pair_cost_le_four_thirds` gives the upper bound of $4/3$ on each opposite pair.

    lines 8–9

    uses ido_remaining_chores_cost_le_one_third, ido_opposite_pair_cost_le_four_thirds

        (∀ (i : Fin n) (j : Fin n), additive_valuation (c i) (chore_opposite_pair h2n j) ≤ 4 / 3) := ⟨ido_remaining_chores_cost_le_one_third n m h2n c hc_nonneg h_ido h_mms,
        ido_opposite_pair_cost_le_four_thirds n m h2n c hc_nonneg h_ido h_mms⟩
ido_remaining_chores_cost_le_one_third
In an identically ordered chore instance with $2n \le m$, nonnegative costs, and MMS 1 for all agents, any chore in the remaining set (index at least $2n$) has cost at most $1/3$ for every agent.
ido_opposite_pair_cost_le_four_thirds
In an identically ordered chore instance with $2n \le m$, nonnegative costs, and MMS 1 for all agents, the opposite pair of chores $\{j, 2n - 1 - j\}$ has total cost at most $4/3$ for every agent.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Cost bounds for opposite pairs and remaining chores in an IDO instance with MMS 1. -/theorem ido_chore_opposite_pairs_cost_bounds    (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), g ∈ chore_remaining_set m n → c i g ≤ 1 / 3) ∧    (∀ (i : Fin n) (j : Fin n), additive_valuation (c i) (chore_opposite_pair h2n j) ≤ 4 / 3) := ⟨ido_remaining_chores_cost_le_one_third n m h2n c hc_nonneg h_ido h_mms,    ido_opposite_pair_cost_le_four_thirds n m h2n c hc_nonneg h_ido h_mms⟩
See it in the graphDiscuss this resultChallenge it