AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_values

def

The four rows of the positive natural valuation matrix are (3,3,12,2,15,1,1,1,16,16,1,1,3), (3,14,1,3,3,12,16,1,1,1,1,16,3), (2,2,32,6,2,28,2,32,2,2,19,15,2), and (1,16,1,3,3,12,14,1,3,16,1,1,1).

Statement

def efx_min_cycle_values : Fin 4 → Fin 13 → ℕ
Source
Minimum-cardinality champion-cycle swap obstruction for OP-7, experiments 11442–11449; comparison with arXiv:2002.05119 Section 3.1.
Verified
01 Nov 2026
Axioms
none listed
Used by 8
  • efx_min_cycle_minimum_cardinalityThe three listed sets are inclusion-minimal envied sets with the stated champions, while every subset of at most two goods in the two…
  • efx_min_cycle_sanityEvery value is positive; each agent values all old bundles equally, values each good of her own old bundle at least as much as good 12,…
  • efx_min_cycle_valueNatural additive value of a set in the explicit matrix.
  • efx_min_cycle_full_efxThe instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1) that strictly improves all four original utilities; it…
  • efx_min_cycle_two_cycle_classificationEvery inclusion-minimal two-cycle is the pair of agents 0 and 1, with target-0 set {0,1,12} and target-1 set either {3,4,12} or {4,5,12}.…
  • efx_min_cycle_all_standard_moves_failFor each of the two two-cycle choices, the upper-half swap and either single-good lower-half repair all fail EFX despite preserving every…
  • efx_nondeg_cycle_valuesThe nondegenerate perturbation of the minimum-cardinality champion-cycle matrix.
  • efx_min_cycle_no_selfNo source self-champions, even when champion sets are allowed to be arbitrary inclusion-minimal envied subsets.

Lean source view module on GitHub

def efx_min_cycle_values : Fin 4 → Fin 13 → ℕ := ![![3,3,12,2,15,1,1,1,16,16,1,1,3], ![3,14,1,3,3,12,16,1,1,1,1,16,3], ![2,2,32,6,2,28,2,32,2,2,19,15,2], ![1,16,1,3,3,12,14,1,3,16,1,1,1]]
See it in the graphDiscuss this resultChallenge it