two_agent_balanced_symmetric_swap_lottery
If both bundles of a two-way partition cost at most alpha times the maximin share of each agent, the equal mixture of that allocation and its swap is an equal-marginal lottery whose support is alpha-MMS.
Statement
theorem two_agent_balanced_symmetric_swap_lottery
(m : ℕ) (α : ℝ) (c : Fin 2 → Fin m → ℝ) (S : Finset (Fin m))
(hS : ∀ i, additive_valuation (c i) S ≤ α * chore_maximin_share 2 (c i))
(hSc : ∀ i, additive_valuation (c i) (Finset.univ \ S) ≤
α * chore_maximin_share 2 (c i)) :
∃ p ∈ stdSimplex ℝ (Fin m → Fin 2),
is_equal_marginal_lottery p ∧ is_ex_post_alpha_mms_chores α c p- Source
- Symmetric two-allocation lottery reduction for the equal-marginal problem in IN-570.
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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.
- 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.
The proof, explained
The proof explicitly constructs a lottery p that places probability 1/2 on an allocation σ (assigning S to agent 0 and Sᶜ to agent 1) and probability 1/2 on its swap τ (assigning Sᶜ to agent 0 and S to agent 1). Because σ and τ assign each chore to different agents, every agent receives each chore with probability exactly 1/2, making p an equal-marginal lottery. Furthermore, every allocation in the support of p gives each agent either S or Sᶜ, both of which are bounded in cost by α times the chore maximin share by assumption.
Define the baseline allocation σ, the swapped allocation τ, and the lottery p.
The allocation σ assigns chore g to agent 0 if g ∈ S and to agent 1 otherwise. The swapped allocation τ inverts this, assigning chore g to agent 1 if g ∈ S and to agent 0 otherwise. The lottery p is defined as the equal 50–50 mixture of σ and τ (giving probability 1/2 to each, and 0 to all other allocations).
classical let σ : Fin m → Fin 2 := fun g => if g ∈ S then 0 else 1 let τ : Fin m → Fin 2 := fun g => if g ∈ S then 1 else 0 let p : (Fin m → Fin 2) → ℝ := fun t => (if t = σ then 1 / 2 else 0) + (if t = τ then 1 / 2 else 0)
Determine the bundles assigned to each agent under σ and τ.
By the definitions of σ, τ, and bundle_of, agent 0 receives chore bundle S under σ and Sᶜ = univ \ S under τ, while agent 1 receives Sᶜ under σ and S under τ.
have bσ0 : bundle_of σ 0 = S := by ext g simp [bundle_of, σ] have bσ1 : bundle_of σ 1 = Finset.univ \ S := by ext g simp [bundle_of, σ] have bτ0 : bundle_of τ 0 = Finset.univ \ S := by ext g simp [bundle_of, τ] have bτ1 : bundle_of τ 1 = S := by ext g simp [bundle_of, τ]
The lottery p is a candidate witness for the theorem.
We provide p as the existential witness. This reduces the theorem to three subgoals: p is a probability distribution in the standard simplex, p is an equal-marginal lottery, and p is ex-post α-MMS for chores.
refine ⟨p, ?_, ?_, ?_⟩The lottery p is a valid probability distribution in the standard simplex.
For any allocation t, the probability p(t) is non-negative since each term is either 1/2 or 0. Summing p(t) over all possible allocations and distributing the sum over addition using Finset.sum_add_distrib gives (1/2) + (1/2) = 1.
uses
Finset.sum_add_distrib· constructor · intro t dsimp [p] positivity · dsimp [p] rw [Finset.sum_add_distrib] simp <;> norm_num
The lottery p has equal marginals: every chore g is allocated to each agent i with probability 1/2.
Fix chore g and agent i. First, σ ≠ τ because they disagree on chore g. Next, the marginal sum is expanded into two indicator sums over t = σ and t = τ. Using Finset.sum_ite_eq', the sum simplifies to (1/2 if σ(g) = i else 0) + (1/2 if τ(g) = i else 0). Case analysis on i ∈ {0, 1} and whether g ∈ S shows that exactly one of σ(g) = i or τ(g) = i is true, so the sum is always 1/2.
uses
congrFun,Ne.symm,Finset.sum_add_distrib,Finset.sum_ite_eq',Finset.mem_univ,if_true· intro g i change (∑ t : Fin m → Fin 2, if t g = i then p t else 0) = 1 / (2 : ℝ) have hστ : σ ≠ τ := by intro h have hv := congrFun h g by_cases hg : g ∈ S <;> simp [σ, τ, hg] at hv have hexpand (t : Fin m → Fin 2) : (if t g = i then p t else 0) = (if t = σ then (if σ g = i then (1 / 2 : ℝ) else 0) else 0) + (if t = τ then (if τ g = i then (1 / 2 : ℝ) else 0) else 0) := by by_cases hσ : t = σ · subst t simp [p, hστ] · by_cases hτ : t = τ · subst t simp [p, Ne.symm hστ] · simp [p, hσ, hτ] simp only [hexpand, Finset.sum_add_distrib] simp only [Finset.sum_ite_eq', Finset.mem_univ, if_true] fin_cases i <;> by_cases hg : g ∈ S <;> simp [σ, τ, hg]
The lottery p is ex-post α-MMS for chores.
Any allocation t with positive probability p(t) > 0 must be either σ or τ. In either allocation, each agent receives either bundle S or bundle Sᶜ. By the hypotheses hS and hSc, each of these two bundles costs at most α times the agent's chore maximin share.
· intro t hp i change additive_valuation (c i) (bundle_of t i) ≤ α * chore_maximin_share 2 (c i) have ht : t = σ ∨ t = τ := by by_contra hh push_neg at hh simp [p, hh.1, hh.2] at hp rcases ht with rfl | rfl <;> fin_cases i · simpa [bσ0] using hS 0 · simpa [bσ1] using hSc 1 · simpa [bτ0] using hSc 0 · simpa [bτ1] using hS 1
Finset.sum_add_distrib- The sum of a pointwise sum of two functions over a finite set equals the sum of the individual sums.
congrFun- Equal functions yield equal values when evaluated at the same argument.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.sum_ite_eq'- Summing an indicator that evaluates to b(x) when x = a and 0 otherwise over a finite set s yields b(a) if a ∈ s, and 0 otherwise.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
if_true- A conditional expression with a True condition evaluates to the then-branch.
- In lines 35–38, the fact that σ ≠ τ is proved by evaluating both allocations at the chore g introduced in line 33, relying on the existence of the chore g from the outer context.
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.
theorem two_agent_balanced_symmetric_swap_lottery (m : ℕ) (α : ℝ) (c : Fin 2 → Fin m → ℝ) (S : Finset (Fin m)) (hS : ∀ i, additive_valuation (c i) S ≤ α * chore_maximin_share 2 (c i)) (hSc : ∀ i, additive_valuation (c i) (Finset.univ \ S) ≤ α * chore_maximin_share 2 (c i)) : ∃ p ∈ stdSimplex ℝ (Fin m → Fin 2), is_equal_marginal_lottery p ∧ is_ex_post_alpha_mms_chores α c p := by classical let σ : Fin m → Fin 2 := fun g => if g ∈ S then 0 else 1 let τ : Fin m → Fin 2 := fun g => if g ∈ S then 1 else 0 let p : (Fin m → Fin 2) → ℝ := fun t => (if t = σ then 1 / 2 else 0) + (if t = τ then 1 / 2 else 0) have bσ0 : bundle_of σ 0 = S := by ext g simp [bundle_of, σ] have bσ1 : bundle_of σ 1 = Finset.univ \ S := by ext g simp [bundle_of, σ] have bτ0 : bundle_of τ 0 = Finset.univ \ S := by ext g simp [bundle_of, τ] have bτ1 : bundle_of τ 1 = S := by ext g simp [bundle_of, τ] refine ⟨p, ?_, ?_, ?_⟩ · constructor · intro t dsimp [p] positivity · dsimp [p] rw [Finset.sum_add_distrib] simp <;> norm_num · intro g i change (∑ t : Fin m → Fin 2, if t g = i then p t else 0) = 1 / (2 : ℝ) have hστ : σ ≠ τ := by intro h have hv := congrFun h g by_cases hg : g ∈ S <;> simp [σ, τ, hg] at hv have hexpand (t : Fin m → Fin 2) : (if t g = i then p t else 0) = (if t = σ then (if σ g = i then (1 / 2 : ℝ) else 0) else 0) + (if t = τ then (if τ g = i then (1 / 2 : ℝ) else 0) else 0) := by by_cases hσ : t = σ · subst t simp [p, hστ] · by_cases hτ : t = τ · subst t simp [p, Ne.symm hστ] · simp [p, hσ, hτ] simp only [hexpand, Finset.sum_add_distrib] simp only [Finset.sum_ite_eq', Finset.mem_univ, if_true] fin_cases i <;> by_cases hg : g ∈ S <;> simp [σ, τ, hg] · intro t hp i change additive_valuation (c i) (bundle_of t i) ≤ α * chore_maximin_share 2 (c i) have ht : t = σ ∨ t = τ := by by_contra hh push_neg at hh simp [p, hh.1, hh.2] at hp rcases ht with rfl | rfl <;> fin_cases i · simpa [bσ0] using hS 0 · simpa [bσ1] using hSc 1 · simpa [bτ0] using hSc 0 · simpa [bτ1] using hS 1