AFTD Auto-Formalizing Theoretical Domains

ex_post_one_mms_chore_lottery_single_agent

theoremverified

For a single agent (n = 1) and any m indivisible chores with nonnegative additive costs c, there exists an allocation lottery that is simultaneously ex-ante proportional and ex-post 1-MMS.

Statement

theorem ex_post_one_mms_chore_lottery_single_agent
    (m : ℕ) (c : Fin 1 → Fin m → ℝ) (hc : ∀ i e, 0 ≤ c i e) :
    ∃ p ∈ stdSimplex ℝ (Fin m → Fin 1),
      is_ex_ante_proportional_chores c p ∧
      is_ex_post_alpha_mms_chores 1 c p
Source
folklore
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • is_ex_ante_proportional_choresAn allocation lottery p over allocations of m chores among n agents is ex-ante proportional for chore cost functions c if each agent i's…
  • is_ex_post_alpha_mms_choresAn allocation lottery p over allocations of m chores among n agents is ex-post α-MMS for chore costs c if every allocation σ in the…
  • 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…
  • 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.

Read back from the Lean

Given a natural number m (the number of chores), a cost function c : Fin 1 → Fin m → ℝ for a single agent, and a hypothesis hc that all chore costs are non-negative (for all i : Fin 1 and e : Fin m, 0 ≤ c i e), there exists a probability distribution p in the standard simplex over allocations Fin m → Fin 1 such that: 1. p is ex-ante proportional for chores under cost function c, and 2. p is ex-post 1-MMS (maximin share) for chores under cost function c.

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

For a single agent (n = 1), there is only one possible allocation of the m chores, which assigns all chores to that agent. The proof takes the deterministic lottery that assigns probability 1 to this unique allocation. Ex-ante proportionality holds because the agent's expected chore cost equals the total chore cost divided by 1. Ex-post 1-MMS holds because the 1-MMS chore share is the total cost of all chores, which upper-bounds the agent's assigned chore cost since chore costs are nonnegative.

  1. The candidate lottery assigns probability 1 to the unique allocation of chores.

    With a single agent, every chore must be assigned to agent 0, so the space of allocations `Fin m → Fin 1` is a singleton. We witness the existential quantifier with the constant function assigning probability 1 to this allocation, reducing the goal to verifying simplex membership, ex-ante proportionality, and ex-post 1-MMS.

    line 7

      refine ⟨fun _ => (1:ℝ), ?_, ?_, ?_⟩
  2. The candidate lottery is a valid probability distribution in the standard simplex.

    Membership in `stdSimplex` requires nonnegative probabilities summing to 1. Each allocation has probability 1 ≥ 0 (checked by `norm_num`), and because the type of allocations is a singleton, the sum over all allocations is exactly 1 (closed by `simp`).

    lines 8–10

      · constructor
        · intro x; norm_num
        · simp
  3. The lottery is ex-ante proportional.

    Ex-ante proportionality requires the agent's expected chore cost to be at most the total cost divided by 1. For the single agent (i = 0), the unique allocation assigns all chores to this agent, so the expected cost is the sum of all chore costs, which equals (∑ e, c 0 e) / 1.

    lines 11–13

    uses additive_valuation, bundle_of

      · intro i
        fin_cases i
        simp [additive_valuation, bundle_of]
  4. For any agent i, the 1-MMS chore share equals the total cost of all chores ∑ j, c i j.

    We introduce an allocation σ with positive probability and the agent i. The chore maximin share for 1 agent minimizes over 1-partitions the maximum bundle cost. Since there is only one agent, every partition places all chores in that agent's bundle, so the infimum and supremum collapse to the total chore cost ∑ j, c i j.

    lines 14–16

    uses chore_maximin_share, additive_valuation, bundle_of

      · intro σ hp i
        have h : chore_maximin_share 1 (c i) = ∑ j, c i j := by
          simp [chore_maximin_share, additive_valuation, bundle_of]
  5. The lottery is ex-post 1-MMS.

    Substituting the MMS value and unfolding the valuation, we need to show that the cost of the chores assigned to agent 0 under σ is at most 1 * ∑ j, c 0 j = ∑ j, c 0 j. Because chore costs are assumed nonnegative (hc 0 x), the sum over any subset of chores is bounded above by the sum over all chores via `Finset.sum_le_univ_sum_of_nonneg`.

    lines 17–21

    uses additive_valuation, bundle_of, one_mul, Finset.sum_le_univ_sum_of_nonneg

        rw [h]
        simp only [additive_valuation, bundle_of]
        fin_cases i
        simp only [one_mul]
        exact Finset.sum_le_univ_sum_of_nonneg (fun x => hc 0 x)
additive_valuation
The cost of a bundle of items under a cost function is the sum of the costs of the items in that bundle.
bundle_of
The bundle allocated to an agent under an allocation is the set of items mapped to that agent.
chore_maximin_share
The maximin share for chores among n agents is the infimum over all partitions of the maximum bundle cost.
one_mul
Multiplying an element by 1 on the left leaves it unchanged (1 * a = a).
Finset.sum_le_univ_sum_of_nonneg
The sum of a nonnegative function over any subset is at most its sum over the entire domain.

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

/-- For a single agent (n = 1), there exists an ex-ante proportional and ex-post 1-MMS chore lottery. -/theorem ex_post_one_mms_chore_lottery_single_agent    (m : ℕ) (c : Fin 1 → Fin m → ℝ) (hc : ∀ i e, 0 ≤ c i e) :    ∃ p ∈ stdSimplex ℝ (Fin m → Fin 1),      is_ex_ante_proportional_chores c p ∧      is_ex_post_alpha_mms_chores 1 c p := by  refine ⟨fun _ => (1:ℝ), ?_, ?_, ?_⟩  · constructor    · intro x; norm_num    · simp  · intro i    fin_cases i    simp [additive_valuation, bundle_of]  · intro σ hp i    have h : chore_maximin_share 1 (c i) = ∑ j, c i j := by      simp [chore_maximin_share, additive_valuation, bundle_of]    rw [h]    simp only [additive_valuation, bundle_of]    fin_cases i    simp only [one_mul]    exact Finset.sum_le_univ_sum_of_nonneg (fun x => hc 0 x)
See it in the graphDiscuss this resultChallenge it