AFTD Auto-Formalizing Theoretical Domains

is_ef1_pd

def

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

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)
See it in the graphDiscuss this resultChallenge it