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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩