Soundness observation, p. 2 — in any optimal allocation vertex items go to vertex agents and i(e) goes to a(e)
ProvedNSWApxHard.Reduction.optimal_observationexchange-argumentnash-social-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1soundness
Let be a 3-regular graph on vertices, let , and consider the reduced instance with vertex items. In every allocation of maximum Nash social welfare,
- each vertex item is assigned to some vertex agent , and
- each edge item is assigned to the corresponding edge agent .
This normal form is the first step of the soundness analysis; Lemmas 2.2–2.4 build on it.
Differences from the source:
- generalization: c_min N vertex items → any number k of vertex items; reason: the observation does not depend on the number of vertex items, and k = c_min N is the page's case.
- reading: the section's standing assumptions (G 3-regular, "Let α be a constant in (1/3, 1/2)", p. 2) → explicit hypotheses; reason: the sentence relies on them without repeating them.
- encoding: a 3-regular graph with N vertices → a graph on Fin N, N = 0 allowed; reason: for N = 0 there are no items and the claim is empty, so no instance of the page changes.
Preamble
import Mathlib import Definitions.Def_NSWApxHard_Reduction_Instance
Formal statement
namespace NSWApxHard.Reduction
/-- Observation (Lee, p. 2): in any optimal allocation of the reduced instance, each vertex item
is assigned to some vertex agent, and each edge item `i(e)` to the edge agent `a(e)`. -/
theorem optimal_observation {N : ℕ} (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (k : ℕ)
(α : ℝ) (hG : IsCubic G) (hα₁ : 1 / 3 < α) (hα₂ : α < 1 / 2)
(x : Item G k → Agent G) (hx : IsOptimal (redUtil G k α) x) :
(∀ j : Fin k, ∃ v : Fin N, x (Sum.inl j) = Sum.inl v) ∧
∀ e : Edge G, x (Sum.inr (Sum.inl e)) = Sum.inr e := by sorry
end NSWApxHard.Reduction
Source
Lee, APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items, arXiv:1507.01159v1, p. 2, §2, Soundness (first observation)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.