SocialChoice.FairDivision.Indivisible.efx_two_agents_two_goods
theoremverifiedformalizationimported Lean
EFX for 2 agents and 2 goods: the allocation giving one good to each agent is EFX. For any two goods g₀ and g₁, the allocation A 0 = {g₀}, A 1 = {g₁} satisfies EFX for both agents, provided each agent values the empty bundle at most their own good. This holds for any additive nonneg valuation (v.val i ∅ = 0 ≤ v.val i {g}). *Proof*: Each bundle is a singleton. Removing the one element leaves ∅, so the EFX condition reduces to v.val j ∅ ≤ v.val j (A j), which holds by hypothesis.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset in variable {N G : Type*} in theorem SocialChoice.FairDivision.Indivisible.efx_two_agents_two_goods [DecidableEq G] (v : Valuation (Fin 2) G) {g₀ g₁ : G} (h₀ : v.val 0 ∅ ≤ v.val 0 {g₀}) (h₁ : v.val 1 ∅ ≤ v.val 1 {g₁}) (A : Allocation (Fin 2) G) (hA0 : A 0 = {g₀}) (hA1 : A 1 = {g₁}) : IsEFX v A
- Formalizes
- EconCSLib, `SocialChoice.FairDivision.Indivisible.efx_two_agents_two_goods`
- 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.Indivisible.efx_two_agents_two_goods← SocialChoice.FairDivision.Indivisible.efx_two_agents_two_goods (EconCSLib/SocialChoice/FairDivision/Indivisible/EFX.lean:112): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- SocialChoice.FairDivision.Indivisible.AllocationAn allocation assigns each agent
i : Na bundle (a finite subset of goodsG). This is a plain function type alias. The partition… - SocialChoice.FairDivision.Indivisible.isEFX_of_singleton_bundleIf agent
i's bundle is a singleton{g}, then agentjis EFX with respect to agenti: removing the sole good fromA ileaves∅,… - SocialChoice.FairDivision.Indivisible.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
val i Sis the value agentiassigns to bundleS. Lives in… - SocialChoice.FairDivision.Indivisible.IsEFXEnvy-free up to any good (EFX): for any envied bundle, removing *any* item from it eliminates the envy.…
- SocialChoice.FairDivision.Indivisible.AllocationAn allocation assigns each agent
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 Finset invariable {N G : Type*} in/-- **EFX for 2 agents and 2 goods**: the allocation giving one good to each agent is EFX. For any two goods `g₀` and `g₁`, the allocation `A 0 = {g₀}`, `A 1 = {g₁}` satisfies EFX for both agents, provided each agent values the empty bundle at most their own good. This holds for any additive nonneg valuation (`v.val i ∅ = 0 ≤ v.val i {g}`). *Proof*: Each bundle is a singleton. Removing the one element leaves `∅`, so the EFX condition reduces to `v.val j ∅ ≤ v.val j (A j)`, which holds by hypothesis. -/theorem SocialChoice.FairDivision.Indivisible.efx_two_agents_two_goods [DecidableEq G] (v : Valuation (Fin 2) G) {g₀ g₁ : G} (h₀ : v.val 0 ∅ ≤ v.val 0 {g₀}) (h₁ : v.val 1 ∅ ≤ v.val 1 {g₁}) (A : Allocation (Fin 2) G) (hA0 : A 0 = {g₀}) (hA1 : A 1 = {g₁}) : IsEFX v A := by intro i j hij h hh fin_cases i · -- i = 0 fin_cases j · exact absurd rfl hij -- j = 0: contradiction · -- j = 1: agent 0 EFX w.r.t. agent 1; A 1 = {g₁} is singleton apply isEFX_of_singleton_bundle v A 1 0 hA1 _ h hh rw [hA0]; exact h₀ · -- i = 1 fin_cases j · -- j = 0: agent 1 EFX w.r.t. agent 0; A 0 = {g₀} is singleton apply isEFX_of_singleton_bundle v A 0 1 hA0 _ h hh rw [hA1]; exact h₁ · exact absurd rfl hij -- j = 1: contradiction