SocialChoice.FairDivision.Indivisible.Allocation
defimported Lean
An allocation assigns each agent i : N a bundle (a finite subset of goods G). This is a plain function type alias. The partition property is stated separately in IsAllocation, keeping structure and assumptions decoupled.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset in def SocialChoice.FairDivision.Indivisible.Allocation (N G : Type*)
- Defined in
- EconCSLib, `SocialChoice.FairDivision.Indivisible.Allocation`
- 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.Allocation← SocialChoice.FairDivision.Indivisible.Allocation (EconCSLib/SocialChoice/FairDivision/Indivisible/Basic.lean:42): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 30
- SocialChoice.FairDivision.Indivisible.not_paretoImproved_selfThe allocation itself is not a Pareto improvement over itself.
- SocialChoice.FairDivision.Indivisible.isProportionalNoncomputable proportionality Boolean reflection helper for
nagents. Returnstrueiff every agent's bundle value is ≥ 1/n of the… - SocialChoice.FairDivision.Indivisible.mmsValue_nonnegFor nonneg valuations with at least one complete allocation, the MMS value is nonneg.
hneensures theiSupis nonempty.[Fintype G]… - SocialChoice.FairDivision.Indivisible.IsAlphaMMSAn allocation
Ais α-MMS if every agent receives at leastαtimes their MMS value.… - SocialChoice.FairDivision.Indivisible.isEnvyFreeNoncomputable envy-free Boolean reflection helper. Returns
trueiffAis envy-free under valuationv. - SocialChoice.FairDivision.Indivisible.isMaxminShare_iff_isAlphaMMS_one
IsMaxminSharefromFairness.leancoincides withIsAlphaMMS 1. → direction (IsMaxminShare → IsAlphaMMS 1): for every complete… - SocialChoice.FairDivision.Indivisible.isAlphaMMS_zeroEvery allocation trivially satisfies 0-MMS for nonneg valuations.
0 * mmsValue = 0 ≤ v_i(A_i)byzero_muland nonnegativity. - SocialChoice.FairDivision.Indivisible.mmsValue_le_proportional_share_additiveFor additive valuations, the MMS value is at most the proportional share:
n * mmsValue ≤ v_i(allGoods). *Proof*: For any completeB,… - SocialChoice.FairDivision.Indivisible.IsAllocationA complete allocation partitions all goods among agents. *
disjoint: distinct agents receive disjoint bundles. *complete: every good… - SocialChoice.FairDivision.Indivisible.IsUtilitarianOptimalUtilitarian optimal: no complete allocation of
allGoodsachieves strictly higher utilitarian (sum) social welfare.… - SocialChoice.FairDivision.Indivisible.IsEF1Envy-free up to one good (EF1): for any envied bundle, removing *some* item from it eliminates the envy.…
- SocialChoice.FairDivision.Indivisible.IsMaxminShare.isAlphaMMS
IsMaxminShareimplies α-MMS forα ≤ 1and nonneg MMS values. - SocialChoice.FairDivision.Indivisible.IsParetoOptimalAn allocation
Ais Pareto optimal if no complete allocationBweakly improves every agent's bundle value and strictly improves at… - SocialChoice.FairDivision.Indivisible.mmsValue_le_of_forallThe MMS value is at most any upper bound on all per-allocation minimum bundle values. If
ubis an upper bound — for every complete… - SocialChoice.FairDivision.Indivisible.isAlphaMMS_mono_alphaα-MMS is monotone decreasing in α: if
Ais α-MMS andβ ≤ α, thenAis β-MMS. *Proof*:β * mmsValue ≤ α * mmsValue ≤ v_i(A_i)… - SocialChoice.FairDivision.Indivisible.IsMaxminShareMaximin share (MMS) guarantee: each agent's bundle is at least as valuable as their maximin share value — the best worst-piece they could…
- 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.IsEFX.isEF1EFX implies EF1: the universal witness in EFX is in particular an existential witness for EF1.
- is_alpha_ef1_one_iff1-EF1 is EF1.
- 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.utilitarianWelfare_monoUtilitarian welfare is monotone: pointwise improvement implies welfare improvement. The valuation codomain is fixed to
ℝ, so no… - SocialChoice.FairDivision.Indivisible.utilitarianWelfareUtilitarian social welfare: the sum of all agents' bundle values.
sw_U(A) = ∑_{i ∈ N} v_i(A_i). Maximizing utilitarian welfare produces… - SocialChoice.FairDivision.Indivisible.efx_two_agents_two_goodsEFX for 2 agents and 2 goods: the allocation giving one good to each agent is EFX. For any two goods
g₀andg₁, the allocation… - is_alpha_ef1For α in [0,1], an allocation is α-EF1 if for every pair of agents i ≠ j with A_j nonempty there is a good g in A_j with v_i(A_i) ≥ α ·…
- SocialChoice.FairDivision.Indivisible.mkAllocEFX existence for 2 agents (general m goods, additive nonneg valuations). For any set of goods and additive nonneg valuation, a…
- SocialChoice.FairDivision.Indivisible.mmsValueThe maximin share (MMS) value of agent
iwith respect to valuationvand good setallGoods.… - SocialChoice.FairDivision.Indivisible.iInf_partition_le_mmsValueThe min-bundle value of any complete allocation is at most the MMS value. For any complete allocation
B:… - SocialChoice.FairDivision.Indivisible.IsMaxminMaximin (egalitarian) optimal: no complete allocation of
allGoodsachieves higher egalitarian (minimum-agent) welfare. A maximin… - SocialChoice.FairDivision.Indivisible.egalitarianWelfareEgalitarian social welfare: the minimum of all agents' bundle values.
sw_E(A) = min_{i ∈ N} v_i(A_i). Maximizing egalitarian welfare… - SocialChoice.FairDivision.Indivisible.IsEquitableEquitable (EQ): all agents achieve the same utility from their own bundle.
∀ i j, v_i(A_i) = v_j(A_j). Equitability requires comparable…
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset in /-- An allocation assigns each agent `i : N` a bundle (a finite subset of goods `G`). This is a plain function type alias. The partition property is stated separately in `IsAllocation`, keeping structure and assumptions decoupled. -/ def SocialChoice.FairDivision.Indivisible.Allocation (N G : Type*) := N → Finset G