AFTD Auto-Formalizing Theoretical Domains

propm_orientation_of_out_degree_two

theoremverifiedoriginal

If the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive valuations there is a PROPm orientation (with the PROPm slack taken over relevant items).

Statement

theorem propm_orientation_of_out_degree_two {m n : ℕ} (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)
    (hT : has_out_degree_two_orientation ends) :
    ∃ σ, 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 15
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
  • edges_betweenThe parallel class of edges joining agents i and j.
  • has_out_degree_two_orientationThe simple graph underlying the multigraph has an orientation in which every vertex has out-degree at most two.
  • incident_edgesThe relevant items E_i of agent i in a multigraph: the edges incident to i.
  • 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.
  • orientation_maximin_valueThe PROPm slack d_i: the maximum over other agents j of agent i's least value for a relevant edge held by j.
  • orientation_prop_shareThe proportional share of agent i in a multigraph orientation instance: half her value for her incident edges (each edge is relevant to…
  • propm_cut_chooseCut and choose on one set of items: the cutter keeps K, the chooser gets the rest; the chooser gets at least half, and the cutter misses…
  • propm_edges_between_symmParallel classes are symmetric: the edges between i and j are the edges between j and i.
  • propm_mem_betweenUnder an orientation, an edge incident to i that is held by another agent j lies in the parallel class of i and j.
  • propm_sum_incidentIn a loopless multigraph, a sum over the edges incident to i splits into sums over the parallel classes at i.
  • propm_sum_ite_memSumming an indicator of K over a superset B gives the sum over K.
  • relevant_min_valueAgent i's value for the least valuable of her relevant edges held by agent j, or 0 if j holds none.
Used by 1

Lean source view module on GitHub

/-- If the simple graph underlying a loopless multigraph has an orientation with every out-degree at most two, then for nonnegative additive valuations there is a PROPm orientation. -/theorem propm_orientation_of_out_degree_two {m n : ℕ} (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)    (hT : has_out_degree_two_orientation ends) :    ∃ σ, is_orientation ends σ ∧ is_propm_orientation ends u σ := by  classical  obtain ⟨T, hTe, hTd⟩ := hT  -- `cut a b`: agent `a` cuts the parallel class `{a, b}`, agent `b` chooses.  set cut : Fin n → Fin n → Prop := fun a b => T a b = true ∧ (T b a = true → a < b) with hcut  have asymm : ∀ a b, cut a b → cut b a → False := by    rintro a b ⟨h1, h2⟩ ⟨h3, h4⟩    exact absurd (h2 h3) (not_lt.mpr (h4 h1).le)  have cut_ne : ∀ a b, cut a b → a ≠ b := fun a b h hab => by    subst hab; exact asymm a a h h  have total : ∀ a b, a ≠ b → (T a b = true ∨ T b a = true) → cut a b ∨ cut b a := by    intro a b hab h    by_cases h1 : T a b = true <;> by_cases h2 : T b a = true    · rcases lt_or_gt_of_ne hab with hl | hl      · exact Or.inl ⟨h1, fun _ => hl⟩      · exact Or.inr ⟨h2, fun _ => hl⟩    · exact Or.inl ⟨h1, fun h => absurd h h2⟩    · exact Or.inr ⟨h2, fun h => absurd h h1⟩    · simp_all  choose K hKsub hKc hKh using    fun i j => propm_cut_choose (edges_between ends i j) (u i) (u j) (hu i)  obtain ⟨σ, hσ⟩ : ∃ σ : Fin m → Fin n, ∀ e, σ e =      if cut (ends e).1 (ends e).2 then        (if e ∈ K (ends e).1 (ends e).2 then (ends e).1 else (ends e).2)      else (if e ∈ K (ends e).2 (ends e).1 then (ends e).2 else (ends e).1) :=    ⟨_, fun _ => rfl⟩  have horient : is_orientation ends σ := by    intro e; rw [hσ e]; split_ifs <;> simp  -- On the class `{i, j}` cut by `i`, agent `i` keeps exactly `K i j`.  have key : ∀ i j e, cut i j → e ∈ edges_between ends i j →      σ e = if e ∈ K i j then i else j := by    intro i j e hc he    simp only [edges_between, Finset.mem_filter, Finset.mem_univ, true_and] at he    rcases he with h | h    · rw [hσ e, h]; exact if_pos hc    · rw [hσ e, h]; exact if_neg (fun h' => asymm _ _ hc h')  refine ⟨σ, horient, fun i => ?_⟩  set d := orientation_maximin_value ends u σ i with hd  have hd0 : 0 ≤ d := (Finset.le_fold_max 0).mpr (Or.inl le_rfl)  have hdj : ∀ j, j ≠ i → relevant_min_value ends u σ i j ≤ d := fun j hj =>    (Finset.le_fold_max _).mpr (Or.inr ⟨j, Finset.mem_erase.mpr ⟨hj, Finset.mem_univ _⟩, le_rfl⟩)  have hval : additive_valuation (u i) (bundle_of σ i) =      ∑ e ∈ incident_edges ends i, (if σ e = i then u i e else 0) := by    rw [← Finset.sum_filter]    unfold additive_valuation    congr 1    ext e    simp only [bundle_of, incident_edges, Finset.mem_filter, Finset.mem_univ, true_and]    constructor    · intro h; refine ⟨?_, h⟩; rcases horient e with h' | h' <;> rw [h] at h' <;> simp [h']    · exact fun h => h.2  -- Per parallel class `{i, j}`: `v_i(class) - 2 v_i(π_i ∩ class) ≤ [i cuts] · d_i`.  have hpair : ∀ j, ∑ e ∈ edges_between ends i j, (u i e - 2 * if σ e = i then u i e else 0) ≤      if cut i j then d else 0 := by    intro j    set B := edges_between ends i j with hB    rw [Finset.sum_sub_distrib, ← Finset.mul_sum]    by_cases hc : cut i j    · rw [if_pos hc]      have hij := cut_ne _ _ hc      have hs : ∑ e ∈ B, (if σ e = i then u i e else 0) = ∑ e ∈ K i j, u i e := by        rw [← propm_sum_ite_mem B (K i j) (hKsub i j)]        refine Finset.sum_congr rfl fun e he => ?_        rw [key i j e hc he]        by_cases hk : e ∈ K i j <;> simp [hk, Ne.symm hij]      rw [hs]      by_cases hR : (bundle_of σ j ∩ incident_edges ends i).Nonempty      · obtain ⟨g, hgR, hgeq⟩ := Finset.exists_mem_eq_inf' hR (u i)        have hrm : relevant_min_value ends u σ i j = u i g := by          rw [relevant_min_value, dif_pos hR, hgeq]        rw [Finset.mem_inter] at hgR        have hgj : σ g = j := by simpa [bundle_of] using hgR.1        have hgB : g ∈ B := propm_mem_between ends σ horient hgR.2 hgj hij        have hgK : g ∉ K i j := by          intro hk; rw [key i j g hc hgB, if_pos hk] at hgj; exact hij hgj        have h1 := hKc i j g (Finset.mem_sdiff.mpr ⟨hgB, hgK⟩)        have h2 := hdj j (Ne.symm hij)        linarith      · have hsub : B ⊆ K i j := by          intro g hgB          by_contra hgK          apply hR          refine ⟨g, Finset.mem_inter.mpr ⟨?_, ?_⟩⟩          · simp only [bundle_of, Finset.mem_filter, Finset.mem_univ, true_and]            rw [key i j g hc hgB, if_neg hgK]          · simp only [hB, edges_between, Finset.mem_filter, Finset.mem_univ, true_and] at hgB            simp only [incident_edges, Finset.mem_filter, Finset.mem_univ, true_and]            rcases hgB with h | h <;> rw [h] <;> simp        have hBK : B = K i j := Finset.Subset.antisymm hsub (hKsub i j)        have hnn : 0 ≤ ∑ e ∈ K i j, u i e := Finset.sum_nonneg fun e _ => hu i e        rw [hBK]; linarith    · rw [if_neg hc]      by_cases hc' : cut j i      · have hij := cut_ne _ _ hc'        have hBji : B = edges_between ends j i := propm_edges_between_symm ends i j        have hs : ∑ e ∈ B, (if σ e = i then u i e else 0) =            ∑ e ∈ B, u i e - ∑ e ∈ K j i, u i e := by          rw [← propm_sum_ite_mem B (K j i) (hBji ▸ hKsub j i), ← Finset.sum_sub_distrib]          refine Finset.sum_congr rfl fun e he => ?_          rw [key j i e hc' (hBji ▸ he)]          by_cases hk : e ∈ K j i <;> simp [hk, hij]        have h1 := hKh j i        rw [← hBji] at h1        have h2 := Finset.sum_sdiff (f := u i) (hBji ▸ hKsub j i : K j i ⊆ B)        rw [hs]; linarith      · have hempty : ∀ e ∈ B, False := by          intro e he          simp only [hB, edges_between, Finset.mem_filter, Finset.mem_univ, true_and] at he          rcases he with h | h          · have := total _ _ (hloop e) (hTe e)            rw [h] at this; rcases this with h' | h'            · exact hc h'            · exact hc' h'          · have := total _ _ (hloop e) (hTe e)            rw [h] at this; rcases this with h' | h'            · exact hc' h'            · exact hc h'        rw [Finset.sum_eq_zero fun e he => (hempty e he).elim,          Finset.sum_eq_zero fun e he => (hempty e he).elim]        norm_num  have hsum : ∑ e ∈ incident_edges ends i, (u i e - 2 * if σ e = i then u i e else 0) ≤ 2 * d := by    rw [propm_sum_incident ends hloop i]    calc ∑ j, ∑ e ∈ edges_between ends i j, (u i e - 2 * if σ e = i then u i e else 0)        ≤ ∑ j, (if cut i j then d else 0) := Finset.sum_le_sum fun j _ => hpair j      _ = ((Finset.univ.filter fun j => cut i j).card : ℝ) * d := by        rw [← Finset.sum_filter, Finset.sum_const, nsmul_eq_mul]      _ ≤ 2 * d := by        have hcard : (Finset.univ.filter fun j => cut i j).card ≤ 2 :=          (Finset.card_le_card fun j hj => by            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hj ⊢            exact hj.1).trans (hTd i)        have : ((Finset.univ.filter fun j => cut i j).card : ℝ) ≤ 2 := by exact_mod_cast hcard        nlinarith  rw [Finset.sum_sub_distrib, ← Finset.mul_sum, ← hval] at hsum  unfold orientation_prop_share  unfold additive_valuation at hsum ⊢  linarith
See it in the graphDiscuss this resultChallenge it