ex_post_one_mms_chore_lottery_single_agent
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.
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.
refine ⟨fun _ => (1:ℝ), ?_, ?_, ?_⟩
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`).
· constructor · intro x; norm_num · simp
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.
uses
additive_valuation,bundle_of· intro i fin_cases i simp [additive_valuation, bundle_of]
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.
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]
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`.
uses
additive_valuation,bundle_of,one_mul,Finset.sum_le_univ_sum_of_nonnegrw [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.
- Because there is only one agent (n = 1), the allocation space `Fin m → Fin 1` is a singleton. The constant function `fun _ => (1:ℝ)` thus assigns probability 1 to that single allocation and forms a valid lottery in the standard simplex.
- In the ex-post MMS check (line 21), rather than proving that the bundle of the single agent is the entire set of chores, the Lean proof uses the weaker fact that chore costs are nonnegative, so the sum over any subset of chores is at most the total sum over all chores.
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.
/-- 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)