allocation_is_ef1
def
An allocation is envy-free up to one good (EF1) if for all agents i, j, either i does not envy j, or removing some good from j's bundle removes i's envy.
Statement
def allocation_is_ef1 {N M : Type*} [Fintype M] [DecidableEq N] [DecidableEq M] (v : N → Finset M → ℝ) (A : M → N) : Prop
- Defined in
- arXiv:2610.14994 (Best-of-both-worlds fair division via subsidies), Sec. 2 (definition of EF1).
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Built on 1
- allocation_bundleFor a complete allocation A of the goods M to the agents N (each good to one agent), the bundle of agent i is the set of goods A assigns…
- Used by 2
- allocation_is_ef1_of_envy_freeAn envy-free allocation is EF1.
- exists_submodular_instance_no_ef1_envy_freeable_allocation_with_bobw_lotteryThere is an instance with three agents and four indivisible goods, each agent having a normalized monotone submodular valuation, in which…
Lean source view module on GitHub
/-- EF1: for all `i j`, `v_i(A_j) ≤ v_i(A_i)` or some `g ∈ A_j` has `v_i(A_j \ {g}) ≤ v_i(A_i)`. -/ def allocation_is_ef1 {N M : Type*} [Fintype M] [DecidableEq N] [DecidableEq M] (v : N → Finset M → ℝ) (A : M → N) : Prop := ∀ i j, v i (allocation_bundle A j) ≤ v i (allocation_bundle A i) ∨ ∃ g ∈ allocation_bundle A j, v i ((allocation_bundle A j).erase g) ≤ v i (allocation_bundle A i)