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
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.
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]