is_alpha_ef1
def
For α 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) ≥ α · v_i(A_j \ {g}).
Statement
def is_alpha_ef1 {N G : Type*} [DecidableEq G] (α : ℝ) (v : SocialChoice.FairDivision.Indivisible.Valuation N G) (A : SocialChoice.FairDivision.Indivisible.Allocation N G) : Prop
- Defined in
- arXiv:2610.23686 (Revisiting the Fairness of Pure Nash Equilibria of Round-Robin), Definition 1
- Verified
- 19 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.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.ValuationAn abstract valuation assigns a real value to each agent-bundle pair.
- Used by 5
- 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…
- 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…
- is_alpha_ef1_one_iff1-EF1 is EF1.
- 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.
Lean source view module on GitHub
/-- `α`-EF1 (Definition 1 of arXiv:2610.23686): for all `i ≠ j` with `A j` nonempty, some `g ∈ A j` has `α · v_i(A_j \ {g}) ≤ v_i(A_i)`. -/ def is_alpha_ef1 {N G : Type*} [DecidableEq G] (α : ℝ) (v : SocialChoice.FairDivision.Indivisible.Valuation N G) (A : SocialChoice.FairDivision.Indivisible.Allocation N G) : Prop := ∀ i j : N, i ≠ j → (A j).Nonempty → ∃ g ∈ A j, α * v.val i (A j \ {g}) ≤ v.val i (A i)