is_ef1_pd
An allocation A : Agent → Finset Object satisfies EF1 under pairwise dominance with respect to item preferences le : Agent → Object → Object → Prop if for all agents i and j, either there is an injection from A j into A i mapping each object to a weakly preferred object according to le i, or for some object y in A j there is an injection from (A j).erase y into A i mapping each object to a weakly preferred object according to le i.
Statement
def is_ef1_pd {Agent Object : Type*} [DecidableEq Object] (le : Agent → Object → Object → Prop) (A : Agent → Finset Object) : Prop
- Defined in
- arXiv:2611.09685 Section 3
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 3
- block_snake_two_agent_spe_nel_ef1For any two agents with positive additive values that are distinct across the items for each agent, every subgame-perfect continuation…
- block_snake_two_agent_spe_nel_ef1_three_itemsFor two agents with positive additive values that are distinct across three items for each agent, every subgame-perfect continuation…
- block_snake_reverse_crossout_nel_ef1For any two real item-value functions and any valid reverse crossout sequence for the two-agent block-snake picking order, the resulting…
Read back from the Lean
Given types Agent and Object with decidable equality on Object, a ternary relation le : Agent → Object → Object → Prop, and an allocation A : Agent → Finset Object, the proposition asserts that for all agents i and j, at least one of the following two conditions holds:
1. There exists a function f : Object → Object such that:
- for all z ∈ A j, f z ∈ A i,
- for all z₁, z₂ ∈ A j, f z₁ = f z₂ implies z₁ = z₂, and
- for all z ∈ A j, le i z (f z) holds.
2. There exists an object y ∈ A j and a function f : Object → Object such that:
- for all z ∈ (A j).erase y, f z ∈ A i,
- for all z₁, z₂ ∈ (A j).erase y, f z₁ = f z₂ implies z₁ = z₂, and
- for all z ∈ (A j).erase y, le i z (f z) holds.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Envy-freeness up to one object (EF1) under pairwise dominance. -/ def is_ef1_pd {Agent Object : Type*} [DecidableEq Object] (le : Agent → Object → Object → Prop) (A : Agent → Finset Object) : Prop := ∀ (i j : Agent), (∃ (f : Object → Object), (∀ z ∈ A j, f z ∈ A i) ∧ (∀ z₁ ∈ A j, ∀ z₂ ∈ A j, f z₁ = f z₂ → z₁ = z₂) ∧ ∀ z ∈ A j, le i z (f z)) ∨ ∃ y ∈ A j, ∃ (f : Object → Object), (∀ z ∈ (A j).erase y, f z ∈ A i) ∧ (∀ z₁ ∈ (A j).erase y, ∀ z₂ ∈ (A j).erase y, f z₁ = f z₂ → z₁ = z₂) ∧ ∀ z ∈ (A j).erase y, le i z (f z)