AFTD Auto-Formalizing Theoretical Domains

two_agent_balanced_symmetric_swap_lottery

theoremverified

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.

  1. 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).

    lines 8–12

      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)
  2. 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 τ.

    lines 13–24

      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, τ]
  3. 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.

    line 25

      refine ⟨p, ?_, ?_, ?_⟩
  4. 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.

    lines 26–32

    uses Finset.sum_add_distrib

      · constructor
        · intro t
          dsimp [p]
          positivity
        · dsimp [p]
          rw [Finset.sum_add_distrib]
          simp <;> norm_num
  5. 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.

    lines 33–52

    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]
  6. 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.

    lines 53–63

      · 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.

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

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
See it in the graphDiscuss this resultChallenge it