Answer: Polynomial-time solvable.
Corollary 5.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven any fair division instance with concave and binary valuations, a Nash optimal allocation can be computed in polynomial time. Remark 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\), rational type masses \(\mu\), rational per-capita supplies \(\rho\), and a finite type set \(T\) with \(\Gamma_t\subseteq[m]\) and nondecreasing concave \(f_t:\{0,\ldots,m\}\to\mathbb{Q}_{\ge0}\), choose \(x_{t,B}\ge0\) for \(t\in T\) and \(B\subseteq[m]\) satisfying \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:\,j\in B}x_{t,B}=\rho_j\), and compute an \(\varepsilon\)-optimal allocation maximizing \(\exp(\sum_{t,B}x_{t,B}\log f_t(|B\cap\Gamma_t|))\).
Input consists of \(m\), a finite set \(T\), rational \(\mu_t,\rho_j\geq0\), sets \(\Gamma_t\subseteq[m]\), and table-encoded nondecreasing concave functions \(f_t:\{0,\ldots,m\}\to\mathbb{Q}_{\geq0}\). A continuous allocation is \(x_{t,B}\geq0\) satisfying \(\sum_Bx_{t,B}=\mu_t\) and \(\sum_{t,B:\,j\in B}x_{t,B}=\rho_j\).
Its Nash welfare is \(U(x)=\exp\!\left(\sum_{t,B}x_{t,B}\log f_t(|B\cap\Gamma_t|)\right)\), with \(U(x)=0\) if a positive-mass term has value \(0\). An \(\varepsilon\)-optimal allocation has \(U(x)\geq e^{-\varepsilon}\max_yU(y)\).
Is computing an \(\varepsilon\)-optimal continuous allocation solvable in polynomial time (in the input size and \(\log(1/\varepsilon)\)), or is it NP-hard?
For the discrete problem in which each indivisible good is assigned to one agent and agent \(i\)'s valuation is \(f_i(|S\cap\Gamma_i|)\), with \(f_i\) nondecreasing and concave, a Nash-optimal allocation is computable in polynomial time.
For every positive rational \(\varepsilon\), the problem is polynomial-time solvable in the input size and \(\log(1/\varepsilon)\). A polynomial-size rational allocation can be returned explicitly. The key is a polynomial-size linear formulation that records the mass assigned to each possible cardinality and its item marginals.
1. A polynomial-size formulation.
Write \(J_t=\Gamma_t\), \(n_t=|J_t|\), and \(M=\sum_t\mu_t\). For each \(t\) and \(k\in\{0,\ldots,n_t\}\), introduce:
For \(j\notin J_t\), introduce \(a_{t,j}\), the total mass of type \(t\) containing \(j\).
Consider the rational polytope \(P\) defined by
\[
\sum_{k=0}^{n_t}z_{t,k}=\mu_t,\qquad z_{t,k}\geq0,
\]
\[
0\leq y_{t,k,j}\leq z_{t,k},
\qquad
\sum_{j\in J_t}y_{t,k,j}=kz_{t,k},
\]
\[
0\leq a_{t,j}\leq\mu_t,
\]
and, for every \(j\in[m]\),
\[
\sum_{t:\,j\in J_t}\sum_{k=0}^{n_t}y_{t,k,j}
+
\sum_{t:\,j\notin J_t}a_{t,j}
=\rho_j.
\]
This formulation has \(O(|T|(m+1)^2)\) variables and constraints. Its rational coefficients have polynomial encoding length.
Every feasible allocation induces a point of \(P\): set
\[
z_{t,k}=\sum_{B:\,|B\cap J_t|=k}x_{t,B},
\]
\[
y_{t,k,j}
=\sum_{B:\,|B\cap J_t|=k,\ j\in B}x_{t,B},
\qquad
a_{t,j}=\sum_{B:\,j\in B}x_{t,B}.
\]
The displayed constraints follow directly from the allocation constraints and counting the \(k\) relevant items in each bundle.
We next prove the converse constructively.
2. Every rational point of \(P\) has a polynomial-size allocation representation.
First fix a finite set \(J\), an integer \(k\in\{0,\ldots,|J|\}\), and rational numbers satisfying
\[
z>0,\qquad 0\leq y_j\leq z,\qquad \sum_{j\in J}y_j=kz.
\]
We claim that these are the marginals of a rational distribution of total mass \(z\) on at most \(|J|+1\) subsets of size \(k\).
Choose a set \(S\subseteq J\) of size \(k\) containing every coordinate with \(y_j=z\), and containing only coordinates with \(y_j>0\). Such a choice exists: the sum condition implies that at most \(k\) coordinates equal \(z\), and at least \(k\) coordinates are positive.
Set
\[
\delta=
\min\left(
\{z\}
\cup\{y_j:j\in S\}
\cup\{z-y_j:j\notin S\}
\right).
\]
Every number in this minimum is positive. Assign mass \(\delta\) to \(S\), and replace
\[
z\leftarrow z-\delta,\qquad
y_j\leftarrow y_j-\delta\,\mathbf 1_{\{j\in S\}}.
\]
The residual quantities satisfy the same constraints. Indeed, selected coordinates remain nonnegative and satisfy
\[
y_j-\delta\leq z-\delta;
\]
unselected coordinates satisfy \(y_j\leq z-\delta\) by the definition of \(\delta\). The sum decreases by \(k\delta\).
If the residual mass is positive, at least one previously strict coordinate reaches either zero or the new upper bound. Coordinates already at a bound remain at a bound: a zero coordinate is unselected, and a coordinate equal to \(z\) is selected. Consequently, after at most \(|J|\) such steps, all coordinates are at bounds, and one final step removes the remaining mass. This proves the claim.
Apply this construction separately to every positive \(z_{t,k}\). For each type \(t\), it produces a list of relevant-item subsets, with rational masses summing to \(\mu_t\), realizing all the prescribed \(y_{t,k,j}\).
It remains to incorporate items outside \(J_t\). Represent the list as consecutive half-open intervals partitioning \([0,\mu_t)\), each interval labeled by its relevant-item subset. For every \(j\notin J_t\), include \(j\) precisely on \([0,a_{t,j})\). Cut the partition at every endpoint \(a_{t,j}\). Each resulting interval now specifies one complete bundle; give that bundle mass equal to the interval’s length.
This realizes every required marginal. It also preserves the masses \(z_{t,k}\), because adding items outside \(J_t\) does not change the relevant cardinality.
For each type, the initial list has at most \((n_t+1)^2\) intervals, and adding outside items introduces at most \(m-n_t\) cuts. Thus the allocation has polynomial support.
The construction also has polynomial bit complexity. Its operations are comparisons, additions, and subtractions of rational numbers. A common denominator for the polynomially many input coordinates has polynomial bit length and remains a common denominator throughout.
Therefore \(P\) is an exact formulation, and rational points of \(P\) can be converted into explicit rational allocations in polynomial time.
3. Feasibility and zero welfare.
Rational linear programming decides feasibility of \(P\) in polynomial time and, when feasible, returns a rational feasible point of polynomial encoding length. If \(P\) is infeasible, the original instance is infeasible.
Now define \(P^+\) by adding
\[
z_{t,k}=0
\quad\text{whenever}\quad f_t(k)=0.
\]
A feasible allocation has positive welfare if and only if it induces a point of \(P^+\):
Hence, if \(P\) is feasible but \(P^+\) is infeasible, every feasible allocation has welfare zero. Any allocation constructed from a rational feasible point of \(P\) is then optimal.
If \(M=0\), feasibility requires every \(\rho_j=0\). The zero allocation is optimal and has welfare \(1\), since its logarithmic welfare is the empty sum.
It therefore remains to treat \(M>0\) and nonempty \(P^+\).
4. Approximating the logarithmic objective.
On \(P^+\), define
\[
L(z)=
\sum_{t,k:\,f_t(k)>0}z_{t,k}\log f_t(k).
\]
The formulation and reconstruction preserve this objective exactly. Thus maximizing welfare is equivalent to maximizing \(L\) on \(P^+\).
All variables of \(P^+\) are bounded, so \(P^+\) is compact. The objective \(L\) is a finite linear function there; consequently, a maximizer \(z^*\) exists.
Put
\[
\bar\varepsilon=\min\{\varepsilon,1\},
\qquad
\eta=\frac{\bar\varepsilon}{4\max\{1,M\}}.
\]
For every positive table entry used in the objective, compute a rational approximation \(c_{t,k}\) satisfying
\[
|c_{t,k}-\log f_t(k)|\leq\eta.
\]
Define the rational objective
\[
\widehat L(z)=\sum_{t,k:\,f_t(k)>0}c_{t,k}z_{t,k}.
\]
These logarithm approximations can be computed in polynomial time. For completeness, write a positive rational \(q\) as \(q=2^h r\), with \(1\leq r<2\). The magnitude of \(h\) is bounded by the binary encoding length of \(q\). For \(w=(r-1)/(r+1)\), use
\[
\log r
=
2\sum_{\ell=0}^{N-1}\frac{w^{2\ell+1}}{2\ell+1}
+R_N.
\]
Since \(0\leq w\leq1/3\),
\[
|R_N|
\leq
2\sum_{\ell=N}^{\infty}(1/3)^{2\ell+1}
\leq3^{-2N}.
\]
The same formula approximates \(\log 2\), using \(w=1/3\). Combining the two approximations gives an approximation to
\[
\log q=h\log 2+\log r
\]
with error at most \((|h|+1)3^{-2N}\). A polynomial number of terms therefore suffices, and the rational partial sums have polynomial encoding length.
Solve the rational linear program maximizing \(\widehat L\) on \(P^+\), and let \(\widehat z\) denote the resulting cardinality masses. For every feasible \(z\),
\[
|L(z)-\widehat L(z)|
\leq
\eta\sum_{t,k}z_{t,k}
=\eta M.
\]
Optimality for the approximate objective now gives
\[
L(\widehat z)
\geq \widehat L(\widehat z)-\eta M
\geq \widehat L(z^*)-\eta M
\geq L(z^*)-2\eta M
\geq L(z^*)-\varepsilon.
\]
Reconstruct an allocation \(\widehat x\) from the complete rational LP solution. Because reconstruction preserves \(L\),
\[
U(\widehat x)
=\exp(L(\widehat z))
\geq e^{-\varepsilon}\exp(L(z^*))
=e^{-\varepsilon}\max_x U(x).
\]
5. Complexity and conclusion.
The algorithm uses polynomial-size rational linear programs, logarithm approximations of polynomial encoding length, and a polynomial-time reconstruction producing polynomially many nonzero bundle masses. Since
\[
\log(1/\eta)
=
O\!\left(
1+\log\max\{1,M\}
+\log(1/\bar\varepsilon)
\right),
\]
its running time is polynomial in the input size and \(\max\{0,\log(1/\varepsilon)\}\).
The proof does not require monotonicity or concavity: the same result holds for arbitrary nonnegative rational table-encoded functions of the relevant-item cardinality.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed polynomial-time result. The formulation, reconstruction, treatment of zero values, and approximation guarantee are correct. No major or minor mathematical issues were found.
The variables record exactly the information needed for the item constraints and objective. In particular, the constraint \(\sum_{j\in J_t}y_{t,k,j}=kz_{t,k}\) correctly counts relevant-item incidences, while \(y_{t,k,j}\leq z_{t,k}\) enforces that a bundle contains each item at most once.
Outside-item marginals need no cardinality-indexed constraints because outside items do not affect value, and the problem imposes no further restrictions on bundles.
The formulation has polynomial size and rational coefficients of polynomial encoding length. Every feasible allocation induces a feasible point with the stated cardinality masses.
The required set \(S\) exists: the sum constraint bounds the number of coordinates equal to \(z\) by \(k\), and guarantees at least \(k\) positive coordinates. This also covers \(k=0\), \(k=|J|\), and \(J=\varnothing\).
Every candidate in the minimum defining \(\delta\) is positive. After subtraction:
If positive mass remains, a previously strict coordinate reaches a bound. Existing bound coordinates remain at bounds, so the termination argument and support bound of \(|J|+1\) are correct.
Cutting the interval representation at the outside-item marginal endpoints realizes each \(a_{t,j}\) exactly. These cuts preserve relevant-item subsets and therefore preserve every \(z_{t,k}\) and \(y_{t,k,j}\).
The stated support bound is valid. Zero-mass types require no intervals and cause no difficulty. Repeated complete bundles can have their masses combined.
The bit-complexity justification is also sound: a product of the input coordinate denominators provides a common denominator of polynomial bit length, and the reconstruction uses only polynomially many comparisons, additions, and subtractions.
Although Section 2 emphasizes rational points for algorithmic purposes, its finite decomposition and interval construction also apply to real points. Thus the asserted exactness does not leave a gap concerning real feasible allocations or maximizers.
The constraints defining \(P^+\) exclude exactly the cardinalities that would cause zero welfare when assigned positive mass. Hence feasibility of \(P^+\) is equivalent to existence of a positive-welfare allocation.
If \(P\) is feasible and \(P^+\) is infeasible, every feasible allocation has welfare zero, so the proposed output is optimal.
The case \(M=0\) is correctly separated: feasibility requires all item marginals to vanish, and the zero allocation has welfare \(1\) under the stated empty-sum convention. Reporting infeasibility when \(P\) is empty appropriately handles inputs for which no allocation exists.
On \(P^+\), every coefficient used in \(L\) is finite, and reconstruction preserves \(L\). All variables are bounded by the type masses, so the nonempty polytope \(P^+\) is compact and its linear objective attains a maximum.
Because this case admits positive welfare, allocations with zero welfare cannot improve the optimum. Maximizing \(L\) therefore resolves the original welfare maximization.
The normalization \(q=2^h r\) has the stated range and encoding bounds. The tail estimate is valid: the geometric bound displayed in the proof is at most \(3^{-2N}\). Combining approximations to \(\log r\) and \(\log 2\) gives error at most \((|h|+1)3^{-2N}\), including when \(h\) is negative.
Consequently, polynomially many terms suffice for the required accuracy, and the rational sums have polynomial encoding length.
The uniform objective error is correctly bounded by \(\eta M\). Optimality of the rational approximate objective then yields the stated loss of at most \(2\eta M\), which is indeed at most \(\varepsilon\). Exponentiating gives exactly the required multiplicative guarantee.
The rational linear programming results invoked apply here: the programs have explicitly represented rational data of polynomial length; feasibility can be decided in polynomial time; and the bounded, nonempty optimization program admits a rational optimal solution of polynomial encoding length.
The accuracy dependence is polynomial in \(\max\{0,\log(1/\varepsilon)\}\), with the usual inclusion of the encoding length of supplied rational inputs. Reconstruction produces an explicit allocation with polynomial support.
No step uses monotonicity or concavity, so the stated extension to arbitrary nonnegative rational cardinality tables is justified.
No repair or additional mathematical clarification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.