Fair Division of Indivisible Goods for a Class of Concave Valuations

The strongest honest positive case is a single-anchor mirror of Theorem 1. The paper has no numbered hardness theorem of its own—the APX-hardness remark is attributed to Lee (2017)—so I would not manufacture a hardness anchor.

My lead problem is CASC Mass-NSW with integral bundles.

There is an atomless population of total mass \(1\), partitioned into finitely many complete types \(T\), with type masses \(\mu_t\), \(\sum_t\mu_t=1\). A type includes the entire valuation profile: for every good \(j\), nonincreasing marginal utilities \(u_{t,j,1}\ge u_{t,j,2}\ge\cdots\), and a cap \(c_t\). For an integral bundle \(B=(b_1,\ldots,b_m)\), its utility is

\[ \bar u_t(B)=\min\left(c_t,\sum_{j=1}^m\sum_{\ell=1}^{b_j}u_{t,j,\ell}\right). \]

Good \(j\) has \(q_j\) copies per unit population mass. The \(q_j\) may be rational: in a finite realization with \(N\) agents, there are \(Nq_j\) copies. Every individual still receives an integral bundle; only the mass of individuals receiving each bundle is fractional.

An allocation is a finite-support collection \(x_{t,B}\ge 0\) satisfying

\[ \sum_B x_{t,B}=\mu_t \quad\text{and}\quad \sum_{t,B}b_jx_{t,B}=q_j \]

for every type \(t\) and good \(j\). Its continuous Nash social welfare is

\[ \operatorname{NSW}_\infty(x) = \exp\left(\sum_{t,B}x_{t,B}\log \bar u_t(B)\right), \]

with value \(0\) if a positive-mass set receives zero utility.

Given a fixed \(\gamma\in(0,1]\), the problem is to output such an allocation \(x\) satisfying

\[ \operatorname{NSW}_\infty(x^\star) \le (1+\gamma/4)e^{e^{-1/(1+\gamma)}} \operatorname{NSW}_\infty(x), \]

where \(x^\star\) is an optimal continuous allocation. In addition, \(x\) should be \(1/(2+\gamma)\)-EF1: whenever \(x_{t,B}>0\) and \(x_{t',B'}>0\), there must be a copy \(g\) in \(B'\) such that

\[ \bar u_t(B) \ge \frac{1}{2+\gamma}\bar u_t(B'\setminus\{g\}). \]

For uncapped valuations, the output should also be \((1+\gamma/4)\)-approximately Pareto-optimal: there must be no feasible reassignment that improves every individual’s utility by a factor of at least \(1+\gamma/4\).

The anchor is Theorem 1, proved in this paper. It states that for finitely many agents with CASC valuations and indivisible goods with multiple copies, a polynomial-time algorithm produces an allocation whose NSW is within factor \((1+\gamma/4)e^{e^{-1/(1+\gamma)}}\) of optimum, while simultaneously giving \(1/(2+\gamma)\)-EF1 and \((1+\gamma/4)\)-approximate Pareto optimality for uncapped valuations. As \(\gamma\to0\), the NSW factor tends to \(e^{1/e}\approx1.445\).

This is a genuine high-multiplicity mirror, not merely a fractional-goods reformulation. If \(\mu_t\), \(q_j\), and \(x_{t,B}\) are rational, choose \(N\) clearing all denominators. Then create \(N\mu_t\) agents of type \(t\), \(Nq_j\) copies of good \(j\), and assign \(Nx_{t,B}\) agents to bundle \(B\). Conversely, every finite allocation induces such a mass allocation. Thus the continuous instance is the compressed representation of arbitrarily many interchangeable agents, while goods remain indivisible at the individual level.

A convincing regime would be a large public or corporate allocation market: hundreds of thousands of residents or employees, many copies of laptops, training places, childcare slots, food packages, or other indivisible benefits, and perhaps only dozens of complete need/eligibility profiles. The type records all marginal values and the saturation threshold, so this is not assuming away idiosyncratic costs; it is assuming that genuinely identical agents are grouped, exactly as high multiplicity requires. The per-capita supply \(q_j\) is the natural co-modification when the population is normalized.

The paper’s Theorem 6 makes this scenario especially recognizable to the authors. It proves, for uncapped valuations in a \(\delta\)-large market where each individual copy has utility at most a \(\delta\)-fraction of average total utility, the stronger bound

\[ \frac{\operatorname{NSW}(x^\star)} {\operatorname{NSW}(x^{\mathrm{alg}})} \le \frac{1+4\varepsilon}{1-\delta}. \]

That theorem is not my second anchor, because its \(\delta\)-large promise is stated for the finite copy list rather than directly for type-compressed input. But it supplies unusually strong evidence that a large-population version of this problem is within the paper’s intended subject matter.

I would expect the stated approximation problem to be a Class A candidate. After taking logarithms, the objective is linear in the mass variables \(x_{t,B}\), and the supply and type-mass constraints are linear. The resulting formulation is a configuration LP over integral bundles. Its central question is whether pricing over CASC bundles can be solved or approximated efficiently using the concavity of the marginal utilities, column generation, or related continuous-optimization machinery. That is precisely the sort of computational question the ChoCo programme is meant to expose.

The weakest point is algorithmic compression. Theorem 1 itself runs in the number of named agents and does not prove that its price/MBB process can be compressed to \((\mu,q)\). The configuration space may be exponential, and caps can make pricing resemble a knapsack problem. So I would not claim that the continuous algorithm is already supplied by the paper. The claim is narrower: this is a natural, technically faithful continuous-population problem whose main difficulty is exactly whether the paper’s finite-agent algorithm survives high-multiplicity compression. Exact NSW optimization may retain hardness from indivisible goods, but the constant-factor/fair allocation question is a credible Class A target rather than a cosmetic restatement.