SocialChoice.FairDivision.Indivisible.AdditiveValuation
structureimported Lean
An additive valuation is determined by per-item weights. weight i g is the value agent i assigns to good g individually. The bundle value is v_i(S) = Σ_{g ∈ S} weight i g.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BigOperators Finset in structure SocialChoice.FairDivision.Indivisible.AdditiveValuation (N G : Type*)
- Defined in
- EconCSLib, `SocialChoice.FairDivision.Indivisible.AdditiveValuation`
- 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.AdditiveValuation← SocialChoice.FairDivision.Indivisible.AdditiveValuation (EconCSLib/SocialChoice/FairDivision/Indivisible/Valuation.lean:68): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 23
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Valuation.(w.toValuation).val i S = Σ_{g ∈ S} w.weight i 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.rawBestGood_mem
rawBestGoodlies in the candidate sets. - is_guaranteed_round_robin_ef1_factorA factor α is guaranteed for n agents under Round-Robin if for every number of goods m, every nonnegative additive valuation profile w,…
- is_guaranteed_sequence_ef1_factorA factor α is guaranteed for a picking sequence mechanism seq with n agents if for every nonnegative additive valuation profile and every…
- 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.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.AdditiveInstance.toAdditiveValuationThe raw additive valuation induced by additive per-item weights.
- SocialChoice.FairDivision.Indivisible.rawBestGood_leEvery element of
sis no more valuable (to agenti) thanrawBestGood. - 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…
- 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…
- not_is_guaranteed_round_robin_ef1_factor_three_of_three_quarters_ltFor three agents, no factor strictly greater than 3/4 is guaranteed for Round-Robin pure Nash equilibria.
- 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…
- 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…
- 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…
- 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.
- SocialChoice.FairDivision.Indivisible.rawBestGood
rawBestGood w i s hsis a good insthat maximisesw.weight iovers. Defined noncomputably viaClassical.chooseon… - 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.AdditiveValuation.toValuation_unionAdditive valuation of a union of disjoint bundles splits as a sum.
- SocialChoice.FairDivision.Indivisible.AdditiveValuation.toValuationLift an additive valuation to an abstract
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in open BigOperators Finset in /-- An additive valuation is determined by per-item weights. `weight i g` is the value agent `i` assigns to good `g` individually. The bundle value is `v_i(S) = Σ_{g ∈ S} weight i g`. -/ structure SocialChoice.FairDivision.Indivisible.AdditiveValuation (N G : Type*) where /-- Per-item weight: agent × good → value. -/ weight : N → G → ℝ