§2, p. 2 — the reduced instance has n = N + M = 2.5N agents and m = c_min N + M + 3N items
ProvedNSWApxHard.Reduction.instance_sizenash-social-welfarep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1reduction
Let be a 3-regular graph on vertices, so that it has edges, and build the reduced instance with vertex items. Then the numbers of agents and of items satisfy
With this is the paper's .
The count fixes the exponent in every welfare computation of the reduction and shows the instance has polynomial size.
Formalization Note The identities are stated doubled, and , in the natural numbers.
Differences from the source:
- generalization: c_min N vertex items → any number k of vertex items; reason: the count holds for every k, and k = c_min N gives the page's identity.
- encoding: n = 2.5N, m = (4.5 + c_min)N → 2n = 5N, 2m = 2k + 9N in ℕ; reason: same identities without fractions.
- encoding: a 3-regular graph with N vertices → a graph on Fin N, N = 0 allowed; reason: for N = 0 both sides are 0, so no instance of the page changes.
Preamble
import Mathlib import Definitions.Def_NSWApxHard_Reduction_Instance
Formal statement
namespace NSWApxHard.Reduction
/-- Lee, p. 2: for a 3-regular graph on `N` vertices with `k` vertex items, the reduced instance
has `n = N + M = 2.5N` agents and `m = k + M + 3N = k + 4.5N` items. -/
theorem instance_size {N : ℕ} (G : SimpleGraph (Fin N)) [DecidableRel G.Adj] (k : ℕ)
(hG : IsCubic G) :
2 * Fintype.card (Agent G) = 5 * N ∧ 2 * Fintype.card (Item G k) = 2 * k + 9 * N := by sorry
end NSWApxHard.Reduction
Source
Lee, APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items, arXiv:1507.01159v1, p. 2, §2 (sentence after the reduction)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.