Lemma 2.2 — some optimal allocation gives each vertex agent at most one vertex item
ProvedNSWApxHard.Reduction.lemma_2_2exchange-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 (fewer vertex items than vertex agents). Then there is an allocation of maximum Nash social welfare such that
i.e. every vertex agent holds at most one vertex item.
This is the first normal form of an optimal allocation used in the soundness analysis.
Differences from the source:
- generalization: c_min N vertex items with c_min N < N → any number k < N of vertex items; reason: the proof uses only that there are fewer vertex items than vertex agents (p. 3), 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: Lemma 2.2's sentence does not repeat them.
Preamble
import Mathlib import Definitions.Def_NSWApxHard_Reduction_Instance
Formal statement
namespace NSWApxHard.Reduction
/-- Lemma 2.2 (Lee, p. 2): if there are fewer vertex items than vertex agents (`k < N`), some
optimal allocation of the reduced instance gives each vertex agent at most one vertex item. -/
theorem lemma_2_2 {N : ℕ} (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (k : ℕ) (α : ℝ)
(hG : IsCubic G) (hα₁ : 1 / 3 < α) (hα₂ : α < 1 / 2) (hk : k < N) :
∃ x : Item G k → Agent G,
IsOptimal (redUtil G k α) x ∧ ∀ v : Fin N, vItems x v ≤ 1 := by sorry
end NSWApxHard.Reduction
Source
Lee, APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items, arXiv:1507.01159v1, p. 2, Lemma 2.2 (proof p. 3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.