AFTD Auto-Formalizing Theoretical Domains

is_nel_pd

def

An allocation A : Agent → Finset Object satisfies NEL under pairwise dominance with respect to item preferences le : Agent → Object → Object → Prop if whenever agent i receives strictly fewer objects than agent j, for every object y in A j there is an injection from (A j).erase y into A i mapping each object z to an object weakly preferred to z by agent i according to le i.

Statement

def is_nel_pd {Agent Object : Type*} [DecidableEq Object] (le : Agent → Object → Object → Prop) (A : Agent → Finset Object) : Prop
Defined in
arXiv:2611.09685 Section 3.1
Verified
09 Nov 2026
Axioms
none listed
Used by 5
  • 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…
  • is_nel_ruleGiven types Agent and Object with decidable equality on Object, an allocation rule f : (Agent → LinearOrder Object) → Agent → Finset…
  • 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…
  • round_robin_five_item_spe_not_nelFor two agents with identical item values 16, 8, 4, 2 and 1 and the round-robin order 0,1,0,1,0, there is a subgame-perfect continuation…

Read back from the Lean

For any types Agent and Object with decidable equality on Object, a ternary relation le : Agent → Object → Object → Prop, and an allocation A : Agent → Finset Object, is_nel_pd le A asserts that for all agents i and j, if (A i).card < (A j).card, then for every object y ∈ A j, there exists a function f : Object → Object such that: 1. for all z ∈ (A j).erase y, f z ∈ A i (i.e., f maps A j \ {y} into A i); 2. for all z₁, z₂ ∈ (A j).erase y, if f z₁ = f z₂ then z₁ = z₂ (i.e., f is injective on A j \ {y}); and 3. 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

/-- No envy toward larger bundles up to any object (NEL) under pairwise dominance. -/
def is_nel_pd {Agent Object : Type*} [DecidableEq Object] (le : Agent → Object → Object → Prop) (A : Agent → Finset Object) : Prop := ∀ (i j : Agent), (A i).card < (A j).card → ∀ 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