SocialChoice.FairDivision.Indivisible.Valuation
structureimported Lean
An abstract valuation assigns a real value to each agent-bundle pair. val i S is the value agent i assigns to bundle S. Lives in namespace SocialChoice.FairDivision.Indivisible to avoid clash with Mathlib's ring-theoretic Valuation.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BigOperators Finset in structure SocialChoice.FairDivision.Indivisible.Valuation (N G : Type*)
- Defined in
- EconCSLib, `SocialChoice.FairDivision.Indivisible.Valuation`
- 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.Valuation← SocialChoice.FairDivision.Indivisible.Valuation (EconCSLib/SocialChoice/FairDivision/Indivisible/Valuation.lean:58): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 47
- 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.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i g. - SocialChoice.FairDivision.Indivisible.mmsValue_nonnegFor nonneg valuations with at least one complete allocation, the MMS value is nonneg.
hneensures theiSupis nonempty.[Fintype G]… - round_robin_three_agents_pne_not_alpha_ef1_of_three_quarters_ltWith three agents and eight goods, there is an instance with nonnegative additive valuations and a pure Nash equilibrium of Round-Robin…
- SocialChoice.FairDivision.Indivisible.CardinalInstance.toValuationThe raw valuation induced by a cardinal indivisible instance.
- SocialChoice.FairDivision.Indivisible.AdditiveInstance.toValuationThe abstract valuation induced by additive per-item weights.
- 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.IsUtilitarianOptimalUtilitarian optimal: no complete allocation of
allGoodsachieves strictly higher utilitarian (sum) social welfare.… - is_picking_sequence_pneA profile of reported strict rankings is a pure Nash equilibrium of the picking-sequence mechanism if no agent can obtain a bundle of…
- 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.agent0_efxSocialChoice.FairDivision.Indivisible.agent0_efx
- picking_sequence_alpha_nil_eq_zeroFor the empty picking sequence every EF1 factor alpha is guaranteed (all bundles are empty), so picking_sequence_alpha, defined as a real…
- 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… - round_robin_pne_ef1_pair_of_count_le_twoIn a pure Nash equilibrium of Round-Robin (nonnegative additive valuations), every agent i is EF1 towards every other agent j that appears…
- 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.
- round_robin_three_agents_seven_goods_pne_ef1With three agents and seven goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1; so the eight-good…
- is_alpha_ef1_one_iff1-EF1 is EF1.
- round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
- 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… - round_robin_pne_envy_zero_ef1_of_deviation_certificateIf the deviation certificate of round_robin_two_mul_add_one_deviation_certificate holds for agent i ≠ 0, then at a pure Nash equilibrium…
- 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) ≥ α ·…
- recursively_balanced_alpha_le_round_robin_universal_alphaThe universal EF1 approximation factor for recursively balanced sequences recursively_balanced_alpha is at most the universal factor for…
- SocialChoice.FairDivision.Indivisible.AdditiveInstance.toCardinalInstanceThe cardinal instance induced by additive per-item weights.
- 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… - round_robin_pne_ef1_of_card_le_two_mul_add_oneWith n agents and at most 2n + 1 goods, every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) is EF1. For three…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation_monoAdditive valuations with nonnegative weights are monotone: sub-bundles have no greater value than their supersets.
- round_robin_pne_not_ef1_three_agents_eight_goodsThere is an instance with 3 agents, 8 goods and strictly positive additive valuations, and a pure Nash equilibrium of the Round-Robin…
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuation_emptyThe value of the empty bundle is zero for additive valuations.
- round_robin_pne_envy_zero_ef1_of_two_mul_add_oneWith n agents and 2n + 1 goods, in every pure Nash equilibrium of Round-Robin (nonnegative additive valuations) every agent i ≠ 0 is EF1…
- 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.AdditiveValuation.toValuation_unionAdditive valuation of a union of disjoint bundles splits as a sum.
- 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 BigOperators Finset in /-- An abstract valuation assigns a real value to each agent-bundle pair. `val i S` is the value agent `i` assigns to bundle `S`. Lives in `namespace SocialChoice.FairDivision.Indivisible` to avoid clash with Mathlib's ring-theoretic `Valuation`. -/ structure SocialChoice.FairDivision.Indivisible.Valuation (N G : Type*) where /-- The valuation function: agent × bundle → value. -/ val : N → Finset G → ℝ