Answer: Polynomial-time solvable in \(m,\tau,L\), using at most \(\tau+1\) rational linear programs.
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateThe primal has an integer solution if and only if the final restricted primal has an integer solution.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) goods, a finite set \(T\) of bidder types with bundle \(x_t\in\{0,1\}^m\setminus\{0\}\), value \(v_t\in\mathbb{Q}_{\ge 0}\), and rational mass \(\mu_t\ge 0\) summing to \(1\), together with per-capita supply \(b\in\mathbb{Q}_{\ge 0}^m\), decide whether there exist served masses \(\alpha_t\in[0,\mu_t]\) and a uniform per-item price \(\lambda\ge 0\) such that \(\alpha\) maximizes \(\sum_{t\in T}\alpha_t v_t\) subject to \(\sum_{t\in T}\alpha_t x_t\le b\), every served type demands its bundle at price \(p(x)=\lambda|x|\), every unserved type demands the empty bundle, and the allocation maximizes seller revenue at those prices.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\ge1\) goods. Type \(t\) has a nonempty bundle \(x_t\in\{0,1\}^m\setminus\{0\}\) and value \(v_t\in\mathbb Q_{\ge0}\). Per-capita supply is \(b\in\mathbb Q_{\ge0}^m\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Each member of type \(t\) may receive only \(x_t\) or \(\varnothing\), with respective values \(v_t\) and \(0\), and has quasi-linear utility. The seller has no value for retained goods.
Define \(F=\{\beta\in\mathbb R^\tau:0\le\beta_t\le\mu_t,\ \sum_t\beta_tx_t\le b\}\). Served masses are divisible and need not be realizable as lotteries over indivisible allocations.
A uniform price is \(p(x)=\lambda|x|\), with \(\lambda\in\mathbb R_{\ge0}\) and \(p(\varnothing)=0\). Demand ties permit either bundle.
A supporting allocation is \(\alpha\in F\) satisfying \(\alpha\in\arg\max_{\beta\in F}\sum_t\beta_tv_t\), \(\alpha_t>0\Rightarrow v_t\ge\lambda|x_t|\), and \(\alpha_t<\mu_t\Rightarrow v_t\le\lambda|x_t|\).
It must also satisfy \(\alpha\in\arg\max_{\beta\in F}\lambda\sum_t\beta_t|x_t|\); this seller comparison includes every feasible allocation, irrespective of buyer demand.
Is deciding whether a supporting allocation and uniform price exist solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite single-minded auctions, the feature-space welfare LP has an integer optimal solution exactly when the terminal demand-restricted LP does; this is an integrality correspondence, not a complexity classification ([Lahaie 2011](https://ojs.aaai.org/index.php/AAAI/article/download/7876/7735)).
No result settling this exact continuous uniform-price decision problem was located in the literature search.
The decision problem is polynomial-time solvable in \(m,\tau,L\). In fact, at most \(\tau+1\) rational linear programs suffice.
Write \(k_t=|x_t|\) and \(r_t=v_t/k_t\). The nonempty-bundle hypothesis ensures \(1\le k_t\le m\), so every \(r_t\) is well defined. For an allocation \(\beta\), define
\(Q(\beta)=\sum_t k_t\beta_t,\qquad W(\beta)=\sum_t v_t\beta_t.\)
We prove the classification directly for the given continuous feasible set \(F\).
Welfare optimality follows from the other conditions. Fix \(\lambda\ge0\), and suppose \(\alpha\in F\) satisfies both buyer-demand implications and the seller’s optimality condition. Put \(d_t=v_t-\lambda k_t\). The demand implications give:
Consequently, for every \(\beta\in F\),
\(\sum_t d_t\alpha_t\ge\sum_t d_t\beta_t.\)
Indeed, each coordinate of \(\alpha\) maximizes its corresponding linear term over \([0,\mu_t]\). Seller optimality also gives \(\lambda Q(\alpha)\ge\lambda Q(\beta)\). Adding these inequalities yields
\(W(\alpha)=\sum_t d_t\alpha_t+\lambda Q(\alpha)\ge\sum_t d_t\beta_t+\lambda Q(\beta)=W(\beta).\)
Thus the welfare condition requires no additional optimization test. This argument includes \(\lambda=0\).
Only finitely many prices need to be tested. Define the candidate set
\(C=\{0\}\cup\{r_t:r_t>0\}.\)
We claim that if a supporting allocation exists at any real price \(\lambda\ge0\), the same allocation is supported at some \(c\in C\).
Given a supporting pair \((\alpha,\lambda)\), choose
\(c=\max\bigl(\{0\}\cup\{r_t:r_t\le\lambda\}\bigr).\)
Then \(0\le c\le\lambda\), and there is no type ratio in \((c,\lambda]\).
If \(r_t>c\), this absence of intermediate ratios implies \(r_t>\lambda\), so the original demand conditions force \(\alpha_t=\mu_t\). If \(r_t<c\), then \(r_t<\lambda\), so they force \(\alpha_t=0\). Types with \(r_t=c\) are indifferent at price \(c\). Hence \(\alpha\) satisfies the buyer-demand conditions at \(c\).
If \(c>0\), then \(\lambda>0\). The original seller condition implies that \(\alpha\) maximizes \(Q\) over \(F\), because multiplication by the positive scalar \(\lambda\) preserves maximizers. It therefore also maximizes \(cQ\). If \(c=0\), every feasible allocation maximizes the seller’s identically zero objective. The welfare argument above now proves that \((\alpha,c)\) is supporting.
This proves the candidate-price reduction, including prices above every type ratio and cases with zero-valued types.
The algorithm tests each candidate exactly. At price zero, all positive-valued types must be fully served. Zero-valued types may be unserved. Therefore price zero works exactly when
\(\sum_{t:v_t>0}\mu_t x_t\le b.\)
Necessity follows because every supporting allocation includes these masses, and all bundle coordinates are nonnegative. For sufficiency, serve precisely these masses and serve none of the zero-valued types. This allocation is feasible, satisfies demand, and satisfies seller optimality; the preceding argument supplies welfare optimality.
For positive prices, first compute
\(Q^\star=\max_{\beta\in F}Q(\beta).\)
This rational LP is feasible because \(0\in F\), and its optimum is attained because \(F\) is closed and bounded.
For each positive \(c\in C\), define
\(F_c=\{\beta\in F:\ \beta_t=\mu_t\text{ when }r_t>c,\ \beta_t=0\text{ when }r_t<c\}.\)
These are exactly the feasible allocations satisfying buyer demand at price \(c\). Types with \(r_t=c\) retain their full interval of allowed served masses.
If \(F_c\) is empty, reject that candidate. Otherwise compute
\(Q_c^\star=\max_{\beta\in F_c}Q(\beta).\)
Accept that candidate exactly when \(Q_c^\star=Q^\star\). All comparisons are exact rational comparisons.
To verify correctness, suppose a candidate is accepted. An optimizer \(\alpha\in F_c\) satisfies buyer demand and maximizes \(Q\) over all of \(F\). Since \(c>0\), it satisfies the seller’s required comparison against every feasible allocation. The welfare argument then makes \((\alpha,c)\) supporting.
Conversely, if any supporting pair exists, the candidate-price reduction produces a supporting pair at some \(c\in C\). If \(c=0\), the zero-price test succeeds. If \(c>0\), its allocation belongs to \(F_c\) and has quantity \(Q^\star\), forcing \(Q_c^\star=Q^\star\). Thus the algorithm accepts exactly the yes-instances.
The running time is polynomial in the stated input parameters. There are at most \(\tau\) positive candidate prices. Including the unrestricted quantity optimization, the algorithm solves at most \(\tau+1\) LPs.
Each LP has \(\tau\) variables and \(m+2\tau\) inequalities: \(m\) supply inequalities and two bounds per variable. Forced coordinates are implemented by setting their lower and upper bounds equal. All coefficients are rational; the objective coefficients \(k_t\) are integers of at most \(O(\log(m+1))\) bits.
Using a dense matrix encoding, each LP has encoding length bounded by
\(B=O\bigl(L+\tau(m+\tau)+\tau\log(m+1)\bigr).\)
The standard polynomial-time theorem for rational linear programming decides feasibility and returns exact optimal values and rational optimizers in time polynomial in the dimensions and encoding length. Its hypotheses hold here: the data are rational, and every feasible optimization problem is bounded. Exact optimal values have polynomial bit length, so equality testing is also polynomial.
If \(\mathsf{LP}(n,q,B)\) denotes such an exact LP running-time bound, the total running time is
\(O\bigl((\tau+1)\mathsf{LP}(\tau,m+2\tau,B)+\operatorname{poly}(m,\tau,L)\bigr)=\operatorname{poly}(m,\tau,L).\)
All computations use the \(\tau\) listed support types.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned decision problem. The argument is correct and rigorous: existence of a supporting allocation and uniform price is decidable in polynomial time in \(m,\tau,L\). No major or minor issues were found.
Since every bundle is nonempty, \(1\le k_t\le m\), so \(r_t=v_t/k_t\) is well defined and nonnegative. The feasible set \(F\) is nonempty because it contains the zero allocation, and it is compact because its constraints are closed and each coordinate lies in \([0,\mu_t]\). These observations justify the optimization problems used below.
The demand implications correctly force \(\alpha_t=\mu_t\) when \(d_t=v_t-\lambda k_t>0\), and \(\alpha_t=0\) when \(d_t<0\). When \(d_t=0\), every permitted coordinate value maximizes \(d_t\alpha_t\).
Consequently, the coordinatewise inequality against every \(\beta_t\in[0,\mu_t]\) is valid. Summing gives the stated inequality against every \(\beta\in F\). Adding seller optimality yields welfare optimality exactly as written.
The proof does not assume that coordinatewise maximization produces a feasible allocation: feasibility of \(\alpha\) is already a hypothesis. It also correctly includes \(\lambda=0\), where the seller objective vanishes.
The maximum defining \(c\) exists because its defining set is finite and contains zero. Its value belongs to \(C\): any nonzero selected ratio is positive.
By maximality, there is no type ratio in \((c,\lambda]\). Thus \(r_t>c\) implies \(r_t>\lambda\), forcing full service under the original demand conditions. Likewise, \(r_t<c\) implies \(r_t<\lambda\), forcing zero service. Types with \(r_t=c\) satisfy both demand implications at the new price.
For \(c>0\), both prices are positive, so seller optimality at \(\lambda\) implies maximization of \(Q\), and hence seller optimality at \(c\). For \(c=0\), seller optimality is automatic. The established welfare implication therefore completes the reduction.
This argument covers prices above all ratios, prices equal to a ratio, and zero-valued types.
At zero price, every positive-valued type must be fully served. Since bundle coordinates and served masses are nonnegative, feasibility necessarily implies
\[
\sum_{t:v_t>0}\mu_t x_t\le b.
\]
Conversely, that inequality makes the proposed allocation feasible. Serving all positive-valued types and none of the zero-valued types satisfies demand and seller optimality, so the earlier implication supplies welfare optimality.
This also handles the case where every value is zero.
The forced coordinates defining \(F_c\) are precisely the demand requirements at positive price \(c\). Equal-ratio types correctly retain their full permitted intervals.
Both \(F\) and every nonempty \(F_c\) are compact, so their quantity optima are attained. Since \(F_c\subseteq F\), equality \(Q_c^\star=Q^\star\) holds exactly when a demand-compatible allocation maximizes quantity over all feasible allocations. For positive \(c\), this is exactly the seller condition.
The acceptance and rejection arguments therefore establish both directions of correctness. In particular, the unrestricted computation of \(Q^\star\) respects the task’s requirement that seller comparisons include allocations irrespective of buyer demand.
There are at most \(\tau\) distinct positive candidates and one unrestricted quantity LP. Infeasibility detection and optimization can be handled by the same LP procedure, so the stated bound of at most \(\tau+1\) LPs is valid.
The variable and inequality counts are correct. Implementing forced coordinates through equal lower and upper bounds preserves these counts. The encoding-length bound is a valid upper bound, including dense constraint storage and the objective coefficients.
The rational LP theorem is stated sufficiently precisely for its use here. All coefficients are rational, feasible instances are bounded, and exact rational optimal values and optimizers have polynomial encoding length. Forming ratios, comparing them, performing the zero-price test, and comparing optimal values also require only polynomial-time rational arithmetic.
No repair or additional 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.