AFTD Auto-Formalizing Theoretical Domains

efx_partial_nat_utility

def

Natural utility in a partial allocation whose last owner label denotes unallocated goods.

Statement

def efx_partial_nat_utility {n m : ℕ} (v : Fin n → Fin m → ℕ) (σ : Fin m → Fin (n+1)) (i : Fin n) : ℕ
Source
Arbitrary source-bundle padding of the OP-7 Pareto-maximal locked-good obstruction, experiments 11497 and 11498.
Verified
01 Nov 2026
Axioms
none listed
Used by 9
  • efx_source_two_envy_graphThe starting envy graph has exactly one edge, from agent 0 to agent 2, and thus three sources.
  • efx_pareto_lock_padded_sanityFor every k the padded starting allocation is partial EFX and has the claimed baseline utilities.
  • efx_nondeg_cycle_sanityAll values are positive, the old allocation with good 12 unallocated is EFX with the stated baselines, and the only envy edges are 0→3 and…
  • efx_source_lift_valuesScale old values by 3, add unequal source locks, and give the new agent two high-valued locks.
  • efx_source_two_full_efxThe explicit complete EFX allocation preserves the other three initial utilities.
  • efx_three_pair_anchor_sanityThe starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
  • efx_anchor_lock_start_sanityAll values are positive, the starting allocation is EFX with the specified utilities, and every tested EFX inequality is strict.
  • efx_partial_natNatural EFX inequalities for a partial allocation whose last owner label denotes unallocated goods.
  • efx_partial_nat_sourceAn agent is a source of the strict-envy graph if no agent strictly envies her bundle.

Lean source view module on GitHub

def efx_partial_nat_utility {n m : ℕ} (v : Fin n → Fin m → ℕ) (σ : Fin m → Fin (n+1)) (i : Fin n) : ℕ := ∑ g : Fin m, if σ g = i.castSucc then v i g else 0
See it in the graphDiscuss this resultChallenge it