SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_isAllocation
theoremverifiedformalizationimported Lean
For any cut point t, the cut-and-choose allocation is a complete measurable partition of [0,1] into two pieces. This holds regardless of whether the cut is fair.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped unitInterval in theorem SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_isAllocation (μ : Fin 2 → Measure I) (t : I) : IsAllocation (cutAndChooseAlloc μ t)
- Formalizes
- EconCSLib, `SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_isAllocation`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_isAllocation← SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_isAllocation (EconCSLib/SocialChoice/FairDivision/Divisible/CutAndChoose.lean:107): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_zeroCutter (agent 0) receives the right piece when the chooser prefers left, and the left piece otherwise.
- SocialChoice.FairDivision.Divisible.IsAllocationA complete divisible allocation is a measurable partition of the cake.
- SocialChoice.FairDivision.utilitarianWelfare_uniqueFor a unique agent, utilitarian welfare is just that agent's utility.
- SocialChoice.FairDivision.Divisible.cutAndChooseAllocThe cut-and-choose allocation at cut point
t ∈ [0,1]. The chooser (agent 1) receives the half they value more: - If… - SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_oneChooser (agent 1) receives the left piece if they prefer it, the right piece otherwise.
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen MeasureTheory Set inopen scoped unitInterval in/-- For any cut point `t`, the cut-and-choose allocation is a complete measurable partition of `[0,1]` into two pieces. This holds regardless of whether the cut is fair. -/theorem SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_isAllocation (μ : Fin 2 → Measure I) (t : I) : IsAllocation (cutAndChooseAlloc μ t) := by have hmL : MeasurableSet (Iic t : Set I) := measurableSet_Iic have hmR : MeasurableSet (Ioi t : Set I) := measurableSet_Ioi have hdLR : Disjoint (Iic t : Set I) (Ioi t) := Iic_disjoint_Ioi le_rfl have hcov : (Iic t : Set I) ∪ Ioi t = univ := Iic_union_Ioi refine ⟨fun i => ?_, fun i j hij => ?_, ?_⟩ · -- Each piece is measurable (either Iic t or Ioi t). -- `show` uses definitional equality to expose the underlying if-expression. fin_cases i · show MeasurableSet (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Ioi t else Iic t) split_ifs <;> assumption · show MeasurableSet (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Iic t else Ioi t) split_ifs <;> assumption · -- Distinct agents receive disjoint pieces fin_cases i <;> fin_cases j · exact absurd rfl hij · show Disjoint (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Ioi t else Iic t) (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Iic t else Ioi t) split_ifs with h · exact hdLR.symm · exact hdLR · show Disjoint (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Iic t else Ioi t) (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Ioi t else Iic t) split_ifs with h · exact hdLR · exact hdLR.symm · exact absurd rfl hij · -- The two pieces cover the entire cake ext x simp only [mem_iUnion, mem_univ, iff_true] have hx : x ∈ Iic t ∨ x ∈ Ioi t := (mem_union x (Iic t) (Ioi t)).mp (hcov ▸ mem_univ x) by_cases h : μ 1 (Iic t) ≥ μ 1 (Ioi t) · -- cutter gets Ioi, chooser gets Iic rcases hx with hx | hx · exact ⟨1, by rw [cutAndChooseAlloc_one, if_pos h]; exact hx⟩ · exact ⟨0, by rw [cutAndChooseAlloc_zero, if_pos h]; exact hx⟩ · -- cutter gets Iic, chooser gets Ioi rcases hx with hx | hx · exact ⟨0, by rw [cutAndChooseAlloc_zero, if_neg h]; exact hx⟩ · exact ⟨1, by rw [cutAndChooseAlloc_one, if_neg h]; exact hx⟩