Answer: An exact optimal allocation is computable in \(\operatorname{poly}(m,\tau,L)\) time.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet a single-minded type $d_{i} = \langle s_{i} , v_{i} \rangle$, $s_{i} \subseteq G$, $v_{i} \in {\bf R}_{+}$ be given for each bidder $i \in P$. Let $\mid G \mid = k$ and $\mid P \mid = n$. If $k$ and $n$ grow in a polynomially related way, the problem of finding an allocation $a$ that maximizes $\sum_{i = 1}^{n} d_{i}(a)$ is NP-hard. Moreover, the existence of a polynomial time algorithm guaranteed to find an allocation whose value is at least $k^{- 1 / 2 + \epsilon}$ times the value of the optimal solution would imply that NP = ZPP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given goods \(G\), supported bidder types \(t=(S_t,v_t)\) with rational masses \(\mu_t\) summing to \(1\), and rational per-capita supplies \(q_g\), choose served masses \(x_t\) to maximize \(\sum_t v_t x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:g\in S_t}x_t\le q_g\) for each \(g\in G\). Can an optimal allocation be computed in time polynomial in \(|G|\), the support size, and the input bit length?
Let \(G\) be a finite set of \(m\) goods. A society is given by its support: a list of \(\tau\) distinct types \(t=(S_t,v_t)\), with \(S_t\subseteq G\), \(v_t\in\mathbb{Q}_{\geq0}\), and positive binary rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each bidder of type \(t\) values a bundle containing \(S_t\) at \(v_t\), and any other bundle at zero. Serving mass \(x_t\) gives each served bidder its entire requested bundle and consumes mass \(x_t\) of each good in \(S_t\); the served mass may be divided arbitrarily.
The input also gives binary rational per-capita supplies \(q_g\geq0\). Goods may remain unused, and requested bundles may be empty. Let \(L\) be the total binary input length, including the explicitly listed bundles.
An allocation is a vector \(x\in\mathbb{R}^{\tau}\) satisfying \(0\leq x_t\leq\mu_t\) and \(\sum_{t:g\in S_t}x_t\leq q_g\) for every \(g\in G\); its welfare is \(\sum_t v_t x_t\).
Can an exact optimal allocation be computed in time polynomial in \(m,\tau,L\), or is this optimization problem NP-hard?
For finitely many single-minded bidders and one indivisible unit of each good, exact welfare maximization is NP-hard even when the numbers of goods and bidders grow polynomially in relation to one another. The supplied discrete result does not establish the complexity of this mass formulation.
An exact optimal allocation can be computed in time polynomial in \(m,\tau,L\). The mass formulation is a rational linear program with explicitly listed variables and constraints.
Index the listed types by \(t\in\{1,\ldots,\tau\}\). Define the incidence matrix \(A\in\{0,1\}^{m\times\tau}\) by \(A_{gt}=1\) if \(g\in S_t\), and \(A_{gt}=0\) otherwise.
Consider the linear program
\(\displaystyle \max\left\{\sum_{t=1}^{\tau}v_tx_t:\ Ax\leq q,\quad 0\leq x\leq\mu\right\}.\)
Its feasible vectors are exactly the allocations in the question: the coordinate bounds specify how much mass of each type can be served, and row \(g\) of \(Ax\leq q\) specifies the consumption of good \(g\). Its objective is exactly the stated welfare. Thus this formulation introduces no relaxation.
There are \(\tau\) variables and \(m+2\tau\) inequalities. All coefficients are rational. Constructing \(A\) from the explicitly listed bundles takes polynomial time, and the entire linear program has binary encoding length polynomial in \(m,\tau,L\). In particular, there is no enumeration of unlisted types or of all subsets of goods.
The feasible region \(P\) is nonempty because \(x=0\) is feasible. It is closed and bounded because \(P\subseteq\prod_{t=1}^{\tau}[0,\mu_t]\). Consequently, the continuous welfare function attains a finite maximum on \(P\).
Empty bundles give zero columns in \(A\); zero supplies may force some coordinates to vanish. Both cases are covered by this same formulation.
We use the standard rational linear-programming theorem: given an explicitly encoded rational linear program, a deterministic algorithm can identify infeasibility or unboundedness, or return an exact rational optimal solution, using a number of bit operations polynomial in the program’s binary encoding length. Exact polynomial-time algorithms based on the ellipsoid method are discussed in [Gleixner and Steffy, *Linear Programming using Limited-Precision Oracles*, Section 1.3](https://optimization-online.org/wp-content/uploads/2019/12/7507.pdf).
All hypotheses hold here: the coefficients are rational and explicitly encoded, the program has polynomial encoding length, and its feasible region is nonempty with a finite optimum. Applying this theorem therefore returns an exact optimal allocation in time polynomial in \(m,\tau,L\).
For completeness, the exact allocation also admits a polynomial-size rational representation. A linear functional on a nonempty bounded polyhedron attains its maximum at a vertex; let \(x^\star\) be such an optimal vertex.
At a vertex, the active constraint normals span \(\mathbb{R}^{\tau}\). Indeed, otherwise there would be a nonzero direction orthogonal to all active normals. Sufficiently small movements in both directions would preserve the active equalities and all inactive inequalities, contradicting extremality.
Select \(\tau\) linearly independent active constraints. They give \(Bx^\star=b\), where \(B\) is an invertible integer matrix whose entries belong to \(\{-1,0,1\}\). Let \(D\) be the product of the denominators of all supplies and masses. Then \(Db\) is integral, and \(\log_2D=O(L)\).
Cramer’s rule gives, for every coordinate,
\(\displaystyle x_t^\star=\frac{\det B_t(Db)}{D\det B},\)
where \(B_t(Db)\) replaces column \(t\) of \(B\) by \(Db\). Hadamard’s inequality gives \(\lvert\det B\rvert\leq\tau^{\tau/2}\). Moreover, \(0\leq x_t^\star\leq\mu_t\leq1\), so the numerator’s absolute value is at most \(D\lvert\det B\rvert\). Each coordinate consequently needs only \(O(L+\tau\log(\tau+1))\) bits.
Divisibility changes the feasible set substantially. For example, take three goods and three types requesting the three different pairs of goods. Give each type mass \(1/3\) and value \(1\), and each good supply \(1/3\).
Serving mass \(1/6\) of every type is feasible and has welfare \(1/2\). Summing the three supply inequalities yields \(2(x_1+x_2+x_3)\leq1\), proving that this allocation is optimal.
In the corresponding discrete instance with one bidder requesting each pair and one unit of each good, at most one bidder can be served. Its welfare, normalized by the number of bidders, is \(1/3\).
Thus replacing indivisible bidders by divisible masses need not preserve the optimum. The supplied discrete hardness result does not contradict the polynomial-time algorithm above.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The formulation is exact, the rational LP theorem applies, and the claimed polynomial bound concerns bit operations and exact output. No major or minor mathematical issues were found.
The displayed Cramer formula is correct:
\(x_t^\star=\det B_t(Db)/(D\det B)\).
Hadamard’s bound \(\lvert\det B\rvert\leq\tau^{\tau/2}\) follows from the entry bound. Because \(0\leq x_t^\star\leq1\), the numerator has absolute value at most \(D\lvert\det B\rvert\). Hence the stated per-coordinate bit bound \(O(L+\tau\log(\tau+1))\) is valid. This establishes polynomial output size; the algorithmic guarantee comes from the separately invoked LP theorem.
No repair or additional clarification is required. The supplied write-up establishes polynomial-time exact optimization for the stated mass formulation.
⟨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.