Lemma 2.4 — if every vertex cover has ≥ c_max N vertices, the optimal NSW is at most (2(1+α)/3)^{γ/2.5}(1+α)^{β/2.5}
ProvedNSWApxHard.Reduction.lemma_2_4nash-social-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1soundnessvertex-cover
Let be a 3-regular graph on vertices, let , and consider the reduced instance with vertex items. Let be a real number such that every vertex cover of has at least vertices. Then every allocation satisfies
With , , and the right-hand side is the paper's .
This is the soundness half of the reduction. Since for , the bound is a constant factor below the completeness value whenever .
Differences from the source:
- generalization: c_min N vertex items and covers of size at least c_max N → any number k < N of vertex items and any real lower bound K′ on the size of every vertex cover; reason: k = c_min N, K′ = c_max N give the page's statement.
- generalization: "for some universal constant γ > 0" → the explicit γN = (K′ − k)/3; reason: this is the γ := (c_max − c_min)/3 fixed in the proof (p. 5); it is positive when K′ > k, so the statement implies the page's existential one.
- encoding: "the optimal Nash social welfare is at most" → every allocation has Nash social welfare at most the bound; reason: there are finitely many allocations, so the optimum is attained and both say the same.
- encoding: (2(1+α)/3)^{γ/2.5}(1+α)^{β/2.5} → exponents ((K′ − k)/3)/(2.5N) and (3k − 1.5N)/(2.5N); reason: γN = (c_max − c_min)N/3, βN = 3k − 1.5N and n = 2.5N, the same numbers.
- reading: the section's standing assumptions (G 3-regular, "Let α be a constant in (1/3, 1/2)", p. 2) and c_min N < N (p. 3) → explicit hypotheses; reason: Lemma 2.4's sentence does not repeat them.
Preamble
import Mathlib import Definitions.Def_NSWApxHard_Reduction_Instance
Formal statement
namespace NSWApxHard.Reduction
/-- Lemma 2.4 (Lee, p. 4): if every vertex cover of the 3-regular graph `G` has at least `K'`
vertices (the paper's `c_max N`) and there are `k < N` vertex items (the paper's `c_min N`), then
every allocation of the reduced instance has Nash social welfare at most
`(2(1+α)/3)^{γ/2.5} (1 + α)^{β/2.5}`, where `γ N = (K' - k)/3` and `β N = 3k - 1.5N`. -/
theorem lemma_2_4 {N : ℕ} (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (k : ℕ) (α K' : ℝ)
(hG : IsCubic G) (hα₁ : 1 / 3 < α) (hα₂ : α < 1 / 2) (hk : k < N)
(hK' : ∀ C : Finset (Fin N), G.IsVertexCover ↑C → K' ≤ (C.card : ℝ))
(x : Item G k → Agent G) :
nsw (redUtil G k α) x ≤
(2 * (1 + α) / 3) ^ (((K' - k) / 3) / (5 * N / 2)) *
(1 + α) ^ ((3 * (k : ℝ) - 3 * N / 2) / (5 * N / 2)) := by sorry
end NSWApxHard.Reduction
Source
Lee, APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items, arXiv:1507.01159v1, p. 4, Lemma 2.4 (proof pp. 4–5, γ := (c_max − c_min)/3 on p. 5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.