SocialChoice.FairDivision.Divisible.chooser_isEnvyFree
theoremverifiedformalizationimported Lean
The chooser (agent 1) never envies the cutter, regardless of the cut point. Since agent 1 selects whichever piece they value more, their own piece is always at least as valuable as the cutter's piece. No fairness condition on the cut is needed. This is the key asymmetry of cut-and-choose: the chooser's guarantee is unconditional; only the cutter's guarantee depends on the cut being fair.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MeasureTheory Set in open scoped unitInterval in theorem SocialChoice.FairDivision.Divisible.chooser_isEnvyFree (μ : Fin 2 → Measure I) (t : I) : (MeasureValuation μ).val 1 (cutAndChooseAlloc μ t 0) ≤ (MeasureValuation μ).val 1 (cutAndChooseAlloc μ t 1)
- Formalizes
- EconCSLib, `SocialChoice.FairDivision.Divisible.chooser_isEnvyFree`
- 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.chooser_isEnvyFree← SocialChoice.FairDivision.Divisible.chooser_isEnvyFree (EconCSLib/SocialChoice/FairDivision/Divisible/CutAndChoose.lean:159): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- SocialChoice.FairDivision.Divisible.cutAndChooseAlloc_zeroCutter (agent 0) receives the right piece when the chooser prefers left, and the left piece otherwise.
- SocialChoice.FairDivision.Divisible.CakeValuationAn abstract cake valuation assigns a value in
Vto each agent-piece pair. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - SocialChoice.FairDivision.Divisible.MeasureValuation.val_emptyThe value of the empty piece is zero.
- SocialChoice.FairDivision.Divisible.MeasureValuationA measure-based cake valuation: each agent's value for a piece is given by their personal measure
μ ion the cakeΩ. - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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.
- Used by 1
- SocialChoice.FairDivision.Divisible.cutAndChoose_isEnvyFreeBoth agents are envy-free at any fair cut point. This combines
chooser_isEnvyFree(unconditional) andcutter_isEnvyFree_of_fair…
- SocialChoice.FairDivision.Divisible.cutAndChoose_isEnvyFreeBoth agents are envy-free at any fair cut point. This combines
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/-- **The chooser (agent 1) never envies the cutter**, regardless of the cut point. Since agent 1 selects whichever piece they value more, their own piece is always at least as valuable as the cutter's piece. No fairness condition on the cut is needed. This is the key asymmetry of cut-and-choose: the chooser's guarantee is unconditional; only the cutter's guarantee depends on the cut being fair. -/theorem SocialChoice.FairDivision.Divisible.chooser_isEnvyFree (μ : Fin 2 → Measure I) (t : I) : (MeasureValuation μ).val 1 (cutAndChooseAlloc μ t 0) ≤ (MeasureValuation μ).val 1 (cutAndChooseAlloc μ t 1) := by -- Reduce to μ 1 (if ...) ≤ μ 1 (if ...) via definitional equality show μ 1 (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Ioi t else Iic t) ≤ μ 1 (if μ 1 (Iic t) ≥ μ 1 (Ioi t) then Iic t else Ioi t) split_ifs with h · exact h · push_neg at h; exact le_of_lt h