AFTD Auto-Formalizing Theoretical Domains

propm_orientation_exists_of_le_five

theoremverifiedoriginal

Every loopless multigraph on at most five agents with nonnegative additive valuations admits a PROPm orientation (with the PROPm slack taken over relevant items).

Statement

theorem propm_orientation_exists_of_le_five {m n : ℕ} (hn : n ≤ 5)
    (ends : Fin m → Fin n × Fin n) (hloop : ∀ e, (ends e).1 ≠ (ends e).2)
    (u : Fin n → Fin m → ℝ) (hu : ∀ i e, 0 ≤ u i e) :
    ∃ σ, is_orientation ends σ ∧ is_propm_orientation ends u σ
Related work
operator (Claude), 2026-10-03: partial answer to arXiv:2602.18098 v2, Sec. 6 (do PROPm orientations always exist?): yes when the underlying simple graph has an orientation of out-degree at most 2, in particular for at most five agents; proof by cut-and-choose with EFX splits
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • cyclic_two_orientationThe orientation of the complete graph on n vertices with arcs i -> i+1 and i -> i+2 (mod n).
  • is_orientationAn allocation of the edges of a multigraph is an orientation if every edge goes to one of its two endpoints.
  • is_propm_orientationAn orientation is PROPm if every agent's value for her bundle plus her PROPm slack d_i is at least her proportional share.
  • propm_cyclic_two_orientationFor n at most 5, the cyclic orientation i -> i+1, i+2 of the complete graph covers every pair and has out-degree at most two.
  • propm_orientation_of_out_degree_twoIf the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive…

Lean source view module on GitHub

/-- Every loopless multigraph on at most five agents with nonnegative additive valuations admits a PROPm orientation. -/theorem propm_orientation_exists_of_le_five {m n : ℕ} (hn : n ≤ 5)    (ends : Fin m → Fin n × Fin n) (hloop : ∀ e, (ends e).1 ≠ (ends e).2)    (u : Fin n → Fin m → ℝ) (hu : ∀ i e, 0 ≤ u i e) :    ∃ σ, is_orientation ends σ ∧ is_propm_orientation ends u σ := by  obtain ⟨hcov, hdeg⟩ := propm_cyclic_two_orientation n hn  exact propm_orientation_of_out_degree_two ends hloop u hu    ⟨cyclic_two_orientation n, fun e => hcov _ _ (hloop e), hdeg⟩
See it in the graphDiscuss this resultChallenge it