uniform_bivalued_unit_ratio_exact_mms
For any number of chores m and any two-agent chore cost profile c satisfying is_uniform_bivalued_chores 1 c, there exists a lottery p in the standard simplex stdSimplex ℝ (Fin m → Fin 2) satisfying is_equal_marginal_lottery p and is_ex_post_alpha_mms_chores 1 c p.
Statement
theorem uniform_bivalued_unit_ratio_exact_mms
(m : ℕ) (c : Fin 2 → Fin m → ℝ)
(hc : is_uniform_bivalued_chores 1 c) :
∃ p ∈ stdSimplex ℝ (Fin m → Fin 2),
is_equal_marginal_lottery p ∧
is_ex_post_alpha_mms_chores 1 c p- Source
- OP-1697
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- is_uniform_bivalued_choresA chore cost profile for two agents and m chores is uniform bivalued with ratio r if the first agent assigns cost 1 to every chore and the…
- is_equal_marginal_lotteryA lottery p over complete allocations of m chores to n agents has equal marginals if every chore g is assigned to every agent i with…
- 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…
- two_agent_bivalued_equal_marginal_sharp_mmsFor two agents (n = 2), ratio r with 1 ≤ r and r ≤ 2, and m chores with a cost profile c : Fin 2 → Fin m → ℝ satisfying…
- is_scaled_bivalued_choresGiven ratio r : ℝ and a chore cost profile c : Fin n → Fin m → ℝ over n agents and m chores, c is scaled bivalued with ratio r if there…
Read back from the Lean
For any number of chores $m : \mathbb{N}$ and any cost function $c : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$ for two agents such that agent 0 assigns cost 1 to every chore ($c(0)(g) = 1$ for all $g$) and agent 1 assigns cost 1 or 1 (i.e., cost 1) to every chore ($c(1)(g) = 1$ for all $g$), there exists a probability distribution $p \in \text{stdSimplex } \mathbb{R} (\text{Fin } m \to \text{Fin } 2)$ over chore allocations such that: 1. $p$ has equal marginals: for every chore $g : \text{Fin } m$ and every agent $i : \text{Fin } 2$, the probability that chore $g$ is assigned to agent $i$, $\sum_{\sigma : \text{Fin } m \to \text{Fin } 2} (\text{if } \sigma(g) = i \text{ then } p(\sigma) \text{ else } 0)$, equals $1/2$. 2. Every allocation $\sigma$ in the support of $p$ ($p(\sigma) > 0$) is an exact (1-)MMS chore allocation: for each agent $i : \text{Fin } 2$, the additive cost of the bundle $\sigma^{-1}(i)$ received by agent $i$, $\sum_{g \in \text{Fin } m, \sigma(g) = i} c(i)(g)$, is at most $1 \times \text{chore\_maximin\_share } 2 (c(i))$, where $\text{chore\_maximin\_share } 2 (c(i)) = \inf_{P : \text{Fin } m \to \text{Fin } 2} \sup_{k : \text{Fin } 2} \sum_{j \in \text{Fin } m, P(j) = k} c(i)(j)$.
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 reduces the unit-ratio case to the general sharp MMS theorem for two-agent scaled bivalued chores. First, when the cost ratio is r = 1, the uniform bivalued condition implies that all chore costs are 1, so the profile is trivially scaled bivalued with unit scaling factors. Applying the general two-agent theorem with r = 1 yields an equal-marginal lottery with ex-post ratio (1 + 1) / 2, which simplifies directly to exact MMS (ratio 1).
The cost profile c is a scaled bivalued chore profile with ratio 1.
We witness the definition of a scaled bivalued profile with ratio r = 1 by setting the base scale a_i = 1 for each agent i ∈ {0, 1}. The scale is strictly positive (1 > 0). For any chore g, agent 0 has cost c(0, g) = 1 by assumption hc.1, and agent 1 has cost c(1, g) = 1 (or 1) by assumption hc.2. In all cases, c(i, g) = a_i, satisfying the condition.
have hc' : is_scaled_bivalued_chores 1 c := by refine ⟨fun _ => 1, by intro i; norm_num, ?_⟩ intro i g fin_cases i · left; exact hc.1 g · rcases hc.2 g with h | h · left; exact h · left; simpa using h
There exists an equal-marginal lottery p in the standard simplex achieving an ex-post ((1 + 1) / 2)-MMS guarantee.
We apply the sharp MMS theorem for two-agent scaled bivalued chores (`two_agent_bivalued_equal_marginal_sharp_mms`) with ratio r = 1. The bounds 1 ≤ 1 and 1 ≤ 2 are checked by arithmetic, and the scaled bivalued property was proved in the previous step. This yields a lottery p in the simplex with equal marginals and ex-post ((1 + 1) / 2)-MMS.
uses
two_agent_bivalued_equal_marginal_sharp_mmsobtain ⟨p, hp, hEq, hMMS⟩ := two_agent_bivalued_equal_marginal_sharp_mms (r := (1:ℝ)) (by norm_num : (1:ℝ) ≤ 1) (by norm_num : (1:ℝ) ≤ 2) m c hc'
The lottery p achieves an ex-post exact MMS (ratio 1) guarantee.
We instantiate the existential goal with p, its simplex membership, and its equal-marginal property. The remaining requirement, ex-post 1-MMS, follows from the ex-post ((1 + 1) / 2)-MMS guarantee by simplifying the arithmetic (1 + 1) / 2 = 1.
refine ⟨p, hp, hEq, ?_⟩ simpa using hMMS
two_agent_bivalued_equal_marginal_sharp_mms- For two agents with a scaled bivalued chore cost profile of ratio r with 1 ≤ r ≤ 2, there exists a lottery in the standard simplex with equal marginal probabilities achieving an ex-post ((r + 1) / 2)-MMS guarantee.
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 unit ratio r = 1, every two-agent uniform bivalued chores instance admits an equal-marginal exact-MMS lottery. -/theorem uniform_bivalued_unit_ratio_exact_mms (m : ℕ) (c : Fin 2 → Fin m → ℝ) (hc : is_uniform_bivalued_chores 1 c) : ∃ p ∈ stdSimplex ℝ (Fin m → Fin 2), is_equal_marginal_lottery p ∧ is_ex_post_alpha_mms_chores 1 c p := by have hc' : is_scaled_bivalued_chores 1 c := by refine ⟨fun _ => 1, by intro i; norm_num, ?_⟩ intro i g fin_cases i · left; exact hc.1 g · rcases hc.2 g with h | h · left; exact h · left; simpa using h obtain ⟨p, hp, hEq, hMMS⟩ := two_agent_bivalued_equal_marginal_sharp_mms (r := (1:ℝ)) (by norm_num : (1:ℝ) ≤ 1) (by norm_num : (1:ℝ) ≤ 2) m c hc' refine ⟨p, hp, hEq, ?_⟩ simpa using hMMS