Source-linked AI summary
APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items
Euiwoong Lee
TL;DR
The paper studies maximizing Nash social welfare when indivisible items are allocated to agents with additive utilities. It proves constant-factor inapproximability, complementing a known constant-factor approximation, with the hardness threshold reported as µ ≈ 1.00008.
Problem
The paper studies how to allocate indivisible items among agents with additive utilities to maximize the geometric mean of their utilities.
Source: §1 · p. 1Method
The paper constructs a reduction from Vertex Cover to an instance of Nash social welfare maximization.
Source: §2 · pp. 2, 5Results
µ ≈ 1.00008: it is NP-hard to approximate Nash social welfare within this factor.
Source: §2 · p. 5Takeaways & Limitations
The result establishes APX-hardness for Nash social welfare maximization, complementing the known constant-factor approximation.
Source: §1 · p. 1The gap between the hardness threshold 1.00008 and the 2.889 approximation guarantee remains open.
Source: §2 · p. 5
Abstract
from arXiv · showhide
We study the problem of allocating a set of indivisible items to agents with additive utilities to maximize the Nash social welfare. Cole and Gkatzelis recently proved that this problem admits a constant factor approximation. We complement their result by showing that this problem is APX-hard.
1 Introduction
The paper studies allocating indivisible items with additive utilities to maximize Nash social welfare, the geometric mean of agents’ utilities. It proves constant-factor inapproximability, complementing a previously known constant-factor approximation.
1 Introduction
- The objective is to allocate indivisible items among agents with additive utilities to maximize the geometric mean of their utilities.The paper calls this objective Nash social welfare.Source: §1 · p. 1
- Nash social welfare balances efficiency, represented by the arithmetic mean, and fairness, represented by maximizing the minimum agent utility.The latter objective is also known as the Santa Clause problem.Source: §1 · p. 1
- Cole and Gkatzelis gave the first constant-factor approximation, with a 2e^(1/e) ≈ 2.889 approximation guarantee.Source: §1 · p. 1
- The paper proves that approximating Nash social welfare within some constant factor µ > 1 is NP-hard.This suggests that constant-factor approximation is the best one can hope for.Source: §1 · p. 1
2 APX-Hardness
The section proves APX-hardness for maximizing Nash social welfare through a reduction from Vertex Cover on 3-regular graphs. The construction converts a gap in Vertex Cover into a gap in the optimal social welfare of the allocation instance.
2 APX-Hardness
- The reduction starts from the 3-regular Vertex Cover gap: distinguish a cover of size at most cminN, cmin≈0.5103, from instances where every cover has size at least cmaxN, cmax≈0.5155.This gap is NP-hard to approximate within factor ≈1.01.Source: §2 · pp. 1–2
- Each graph vertex and edge has a corresponding agent; vertex items give utility 1 to vertex agents, edge items give utility 1 − α to their edge agent, and shared items benefit incident agents.Each shared item gives utility 1/3 to its incident vertex agent and α to its incident edge agent, and 0 to all other agents.Source: §2 · p. 2
- For a graph with a vertex cover C of size cminN, the completeness allocation gives each vertex agent utility 1 and each edge agent utility either 1 or 1 + α.It gives 3(1 − cmin)N edge agents one shared item and 3(cmin − 0.5)N two; β := 3(cmin − 0.5) ≈ 0.03.Source: §2 · p. 2
- The soundness argument uses an optimal allocation with at most one vertex item per vertex agent and a rule governing who receives each shared item.These structural properties constrain the utilities of vertex and edge agents used in the soundness bound.Source: §2 · pp. 2–3
- For soundness, if every cover has size at least cmaxN, the reduction shows the optimal Nash social welfare is bounded above by a quantity involving γ, where γ≈0.0017.The proof derives this bound by showing at least γN vertex agents receive only two shared items.Source: §2 · pp. 4–5
- Using completeness and soundness properties of the reduction, it is NP-hard to approximate Nash social welfare within factor µ ≈ 1.00008, and closing the gap from 1.00008 to 2.889 remains open.Source: §2 · p. 5