AFTD Auto-Formalizing Theoretical Domains

multigraph_orientation_subsidy_not_le_one

theoremverifiedoriginal

For three agents on a multigraph with monotone valuations, a total subsidy of n - 2 = 1 does not always suffice for an envy-free orientation, unlike simple graphs (arXiv:2502.13671, Thm 21).

Statement

theorem multigraph_orientation_subsidy_not_le_one :
    ¬ ∀ (m : ℕ) (ends : Fin m → Fin 3 × Fin 3) (v : Fin 3 → Finset (Fin m) → ℝ),
      (∀ e, (ends e).1 ≠ (ends e).2) → is_graph_valuation ends v →
      (∀ i, is_monotone_valuation (v i) ∧ has_max_marginal_one (v i)) →
      ∃ σ p, is_orientation ends σ ∧ is_envy_free_with_subsidy v σ p ∧ ∑ i, p i ≤ 1
Related work
operator (Claude), 2026-10-03: improves the lower bound n-2 (Example 20) for multigraphs with monotone valuations at n = 3, toward the open gap of arXiv:2502.13671 v1, Sec. 7
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • multigraph_orientation_subsidy_three_halvesThere is a three-agent multigraph with monotone graph valuations, normalised so the largest marginal is 1, in which every envy-free…
  • is_orientationAn allocation of the edges of a multigraph is an orientation if every edge goes to one of its two endpoints.
  • is_graph_valuationIn the graph model each agent values only the edges incident to her: v_i(X) = v_i(X ∩ E_i).
  • is_monotone_valuationA valuation is monotone and nonnegative: v(∅) ≥ 0 and S ⊆ T implies v(S) ≤ v(T).
  • has_max_marginal_oneThe subsidy normalisation: every marginal value v(S + e) - v(S) is at most 1, and some marginal value equals 1.
  • is_envy_free_with_subsidyAn allocation with nonnegative payments p is envy-free if v_i(A_i) + p_i ≥ v_i(A_j) + p_j for all agents i, j.

Lean source view module on GitHub

theorem multigraph_orientation_subsidy_not_le_one :    ¬ ∀ (m : ℕ) (ends : Fin m → Fin 3 × Fin 3) (v : Fin 3 → Finset (Fin m) → ℝ),      (∀ e, (ends e).1 ≠ (ends e).2) → is_graph_valuation ends v →      (∀ i, is_monotone_valuation (v i) ∧ has_max_marginal_one (v i)) →      ∃ σ p, is_orientation ends σ ∧ is_envy_free_with_subsidy v σ p ∧ ∑ i, p i ≤ 1 := by  intro h  obtain ⟨ends, v, hne, hg, hv, hlow, -⟩ := multigraph_orientation_subsidy_three_halves  obtain ⟨σ, p, hσ, hef, hp⟩ := h 3 ends v hne hg hv  linarith [hlow σ p hσ hef]
See it in the graphDiscuss this resultChallenge it