Answer: Polynomial-time solvable by exact rational linear programming. Optimization takes \(\operatorname{poly}(m,\tau 2^m,L)=\operatorname{poly}(L)\) time under explicit tabulation; decision takes \(\operatorname{poly}(m,\tau 2^m,L+\ell_K)=\operatorname{poly}(L+\ell_K)\), where \(\ell_K\) is the binary encoding length of \(K\).
Theorem 8 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateiBundle(3) with Adjust and myopic best- response proxy agents computes the minimal CE prices in combinatorial resource allocation problems. We have the following key result, that follows from The- orems 3 and 7.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite goods \(G\), types \(T\) with rational masses \(\mu_t\) summing to \(1\), per-type bundle values \(b_t(S)\), and per-capita supplies \(q_g\), take a rational terminal allocation \(x^*_{t,S}\) and price schedule \(p^0_t(S)\) that support a competitive equilibrium. The allocation must satisfy \(\sum_S x^*_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x^*_{t,S}\le q_g\). Find prices \(p_t(S)\) with \(0\le p_t(S)\le p^0_t(S)\) that minimize \(\sum_{t,S}x^*_{t,S}p_t(S)\), subject to every bundle assigned positive mass to type \(t\) maximizing \(b_t(S)-p_t(S)\), and \(x^*\) maximizing auctioneer revenue among feasible mass allocations at those prices.
Let \(G\) be a finite set of goods, with \(m=|G|\). A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts supported types, not possible types.
For every \(t\) and \(S\subseteq G\), explicitly tabulate binary-rational values \(b_t(S)\ge0\), initial prices \(p_t^0(S)\ge0\), and terminal masses \(x^*_{t,S}\ge0\). Values satisfy \(b_t(\varnothing)=0\) and free disposal; \(p_t^0(\varnothing)=0\). Supplies \(q_g\ge0\) are binary rationals. Let \(L\) be the total input bit length.
A feasible mass allocation is any real array \(x\ge0\) satisfying \(\sum_{S\subseteq G}x_{t,S}=\mu_t\) and \(\sum_{t,S:g\in S}x_{t,S}\le q_g\); the empty bundle represents receiving nothing, and each individual receives at most one bundle.
Prices may discriminate between types and bundles. Define \(R_p(x)=\sum_{t,S}x_{t,S}p_t(S)\). An allocation \(x\) and prices \(p\) form a competitive equilibrium when every \(S\) with \(x_{t,S}>0\) maximizes \(b_t(S)-p_t(S)\) over all bundles, and \(R_p(x)\ge R_p(y)\) for every feasible \(y\). Ties are allowed.
The input promises that \((x^*,p^0)\) is a competitive equilibrium. Minimize \(R_p(x^*)\) over prices satisfying \(0\le p_t(S)\le p_t^0(S)\) for every type and bundle, while retaining that equilibrium.
Is this minimum-revenue price-adjustment problem solvable in polynomial time, or is its decision version—whether the minimum is at most an input binary-rational threshold \(K\)—\(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\), including the encoding of \(K\).
For finite agents, iBundle(3) with Adjust and myopic best-response proxy agents computes minimum-revenue competitive-equilibrium prices; this is a correctness guarantee without a polynomial-time bound. [Parkes–Ungar](https://cdn.aaai.org/AAAI/2000/AAAI00-013.pdf)
No result settling exactly the mass problem specified here was identified in the literature search.
The problem is solvable in polynomial time in the explicitly tabulated input length. Both an exact minimum-revenue price vector and the exact minimum revenue can be computed by rational linear programming.
Write \(N=\tau 2^m\). The optimization running time is \(\operatorname{poly}(m,N,L)\), hence \(\operatorname{poly}(L)\) under the specified explicit encoding. If \(\ell_K\) is the binary encoding length of the threshold \(K\), the decision running time is \(\operatorname{poly}(m,N,L+\ell_K)\), hence \(\operatorname{poly}(L+\ell_K)\).
The key is that the seller optimizes over real mass allocations, so its revenue maximization is a linear program. Because \(x^*\) is fixed input data, a dual certificate of its optimality is linear in the unknown prices.
Let \(\mathcal F\) denote the set of feasible mass allocations specified in the question. For fixed prices \(p\), the seller’s optimization problem is
\[ \max_{y\in\mathcal F}\ \sum_{t,S}y_{t,S}p_t(S). \]
Its dual has variables \(a_t\in\mathbb R\) for the type-mass equalities and \(\lambda_g\ge 0\) for the supply inequalities. It is
\[ \min_{a,\lambda}\ \sum_t\mu_t a_t+\sum_g q_g\lambda_g, \]
subject to
\[ a_t+\sum_{g\in S}\lambda_g\ge p_t(S) \qquad\text{for every }t,S. \]
Here and below, every bundle index ranges over all subsets of \(G\).
Lemma. For fixed \(p\), the allocation \(x^*\) maximizes seller revenue if and only if there exist dual-feasible \(a,\lambda\) satisfying
\[ \sum_t\mu_t a_t+\sum_gq_g\lambda_g = \sum_{t,S}x^*_{t,S}p_t(S). \]
Proof. For any feasible \(y\) and dual-feasible \(a,\lambda\),
\[ \begin{aligned} R_p(y) &\le \sum_{t,S}y_{t,S} \left(a_t+\sum_{g\in S}\lambda_g\right)\\ &=\sum_t\mu_t a_t +\sum_g\lambda_g\sum_{t,S:g\in S}y_{t,S}\\ &\le \sum_t\mu_t a_t+\sum_gq_g\lambda_g. \end{aligned} \]
The first inequality uses \(y\ge 0\); the equality uses the type-mass constraints; the last inequality uses feasibility and \(\lambda\ge 0\). Thus the asserted equality certifies \(R_p(y)\le R_p(x^*)\) for every feasible \(y\).
Conversely, the seller’s primal is nonempty because assigning every type its entire mass of the empty bundle is feasible. It is closed and bounded: every coordinate satisfies \(0\le y_{t,S}\le\mu_t\). Its objective therefore has a finite attained maximum. The dual is feasible, for example with \(\lambda=0\) and \(a_t=\max_Sp_t(S)\). Linear programming strong duality supplies an attained dual optimum equal to the primal optimum. If \(x^*\) is optimal, this gives precisely the required equality. These are the hypotheses needed for the standard [LP duality theorem](https://courses.csail.mit.edu/6.854/18/Notes/n12-duality.html). \(\square\)
Define the fixed support
\[ H=\{(t,S):x^*_{t,S}>0\}. \]
It can be computed exactly from the rational input. For every type, this support contains at least one bundle because \(\sum_Sx^*_{t,S}=\mu_t>0\).
Introduce a variable \(u_t\in\mathbb R\). Buyer optimality is equivalent to
\[ u_t+p_t(S)\ge b_t(S) \qquad\text{for every }t,S, \]
together with
\[ u_t+p_t(S)=b_t(S) \qquad\text{for every }(t,S)\in H. \]
Indeed, these constraints say that every bundle’s utility is at most \(u_t\), and every positively allocated bundle attains \(u_t\). Conversely, if every positively allocated bundle maximizes utility, choose \(u_t=\max_S\{b_t(S)-p_t(S)\}\).
The weak inequalities preserve all allowed ties.
Use variables \(p_t(S)\), \(u_t\), \(a_t\), and \(\lambda_g\). Minimize
\[ \sum_{t,S}x^*_{t,S}p_t(S) \]
subject to the following constraints:
\[ 0\le p_t(S)\le p_t^0(S) \qquad\text{for every }t,S. \]
\[
u_t+p_t(S)\ge b_t(S)
\qquad\text{for every }t,S,
\]
with equality whenever \((t,S)\in H\).
\[ \lambda_g\ge 0,\qquad a_t+\sum_{g\in S}\lambda_g\ge p_t(S) \qquad\text{for every }t,S. \]
\[ \sum_t\mu_t a_t+\sum_gq_g\lambda_g = \sum_{t,S}x^*_{t,S}p_t(S). \]
All these constraints are linear with rational coefficients. In particular, the last equality is linear because \(x^*\) is fixed.
To verify exact equivalence:
Consequently, the feasible price vectors of this LP are exactly those in the question, and its objective is exactly the requested revenue.
The equilibrium promise makes the LP feasible: \(p=p^0\) has suitable certificates. Its objective is bounded below by zero. Therefore it has an attained optimum. Rational LP optimization computes an exact rational optimal solution of polynomial encoding length; the relevant bit-complexity and exact-optimality facts are covered in [these LP complexity notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
The LP has
\[ d=N+2\tau+m,\qquad N=\tau2^m, \]
variables and \(O(N+\tau+m)\) constraints, counting each equality as two inequalities if necessary. Its number of nonzero coefficients is \(O((m+1)N+\tau+m)\). Numerical coefficients come directly from the input or are \(0\), \(1\), or \(-1\), with only constantly many repetitions of each input coefficient.
A sparse encoding therefore has bit length
\[ B=O\!\left(L+\bigl((m+1)N+\tau+m\bigr)\log(d+2)\right). \]
Construction and exact rational LP optimization take \(\operatorname{poly}(m,\tau2^m,L)\) bit operations. Because all bundle entries and all supplies are explicitly encoded, \(N+\tau+m=O(L)\). Thus this is polynomial in \(L\), despite its exponential dependence on \(m\) when expressed separately.
For the decision problem, add the single linear inequality
\[ \sum_{t,S}x^*_{t,S}p_t(S)\le K. \]
The resulting LP is feasible exactly when the minimum revenue is at most \(K\). Its encoding grows by \(O(N\log(d+2)+\ell_K)\), giving running time \(\operatorname{poly}(m,\tau2^m,L+\ell_K)\). If the stated \(L\) already includes \(K\), this is simply \(\operatorname{poly}(L)\). Hence the decision problem belongs to \(\mathrm P\); it cannot be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions unless \(\mathrm P=\mathrm{NP}\).
The finite-agent correctness guarantee appears in [Parkes–Ungar, Theorem 8](https://cdn.aaai.org/AAAI/2000/AAAI00-013.pdf). The polynomial bound here follows independently from the specified real-mass feasible set and explicit tabulation.
⟨structured verdict parsed — rendered above⟩
The LP formulation correctly settles the stated mass problem in polynomial time under explicit tabulation. I found one minor encoding-accounting error; it does not affect the algorithm, its correctness, or its polynomial running time.
The seller’s variables are nonnegative real masses, with type-mass equalities and supply upper bounds. The displayed dual therefore correctly uses unrestricted \(a_t\), nonnegative \(\lambda_g\), and constraints \(a_t+\sum_{g\in S}\lambda_g\ge p_t(S)\).
The feasibility of \(x^*\), needed throughout, follows from the equilibrium promise. No integrality assumption is introduced.
Every step of the weak-duality calculation is valid: nonnegative masses justify the first inequality, type-mass equalities justify regrouping, and nonnegative supply multipliers justify the final inequality. Equality with \(R_p(x^*)\) therefore certifies seller optimality.
Conversely, the empty-bundle allocation makes the primal feasible because supplies are nonnegative. The coordinate bounds \(0\le y_{t,S}\le\mu_t\) make its feasible set compact. The stated dual-feasible choice is valid because the bundle set is finite. Thus strong duality and dual attainment apply as claimed. The cited [LP duality notes](https://courses.csail.mit.edu/6.854/18/Notes/n12-duality.html) support the duality result being used.
Each type has a nonempty allocated support because its mass is positive and \(x^*\) is feasible. The inequalities bound every bundle’s utility above by \(u_t\), and the support equalities ensure that every positively allocated bundle attains that bound. Conversely, choosing the maximum utility supplies the required certificate.
This formulation correctly permits ties. It imposes no optimality requirement on unallocated bundles beyond the required upper bound.
The seller certificate is linear because \(x^*\), \(\mu_t\), and \(q_g\) are fixed input coefficients. There is no product of unknown variables.
Both directions of the claimed equivalence follow from the preceding certificates. The objective is exactly the requested revenue. Price bounds also force \(p_t(\varnothing)=0\), as required by the initial empty-bundle price.
The equilibrium promise supplies feasibility at \(p^0\), and nonnegative prices bound the objective below by zero. A feasible finite-dimensional LP with an objective bounded below attains its optimum; unbounded auxiliary variables do not invalidate this fact.
The rational LP theorem invoked is applicable: a rational LP can be optimized exactly in polynomial bit time, and a feasible LP with finite optimum admits a rational optimal solution of polynomial encoding length. The displayed construction satisfies these hypotheses. The cited [LP complexity notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf) discuss polynomial algorithms, solution-size bounds, and exact optimality recovery.
The variable count \(d=N+2\tau+m\), constraint count, and nonzero-coefficient bound are valid. Numerical input coefficients occur only constantly many times in the optimization LP, so its stated sparse encoding bound is sound.
Explicit tabulation gives \(N+\tau+m=O(L)\). Consequently, the claimed optimization time \(\operatorname{poly}(m,\tau2^m,L)\) is polynomial in \(L\). This does not claim polynomial dependence on \(m\) independent of the explicit table size.
Adding \(R_p(x^*)\le K\) is equivalent to asking whether the attained minimum is at most \(K\). This also handles negative thresholds correctly.
Minor issue: The statement that the encoding “grows by \(O(N\log(d+2)+\ell_K)\)” omits the bit lengths of the repeated coefficients \(x^*_{t,S}\). An ordinary sparse encoding stores those rational coefficients again.
A concrete failure occurs with fixed \(m=1\), \(\tau=1\), and terminal masses \(2^{-h}\) and \(1-2^{-h}\). With zero values and initial prices, and supply \(1\), these are valid promised inputs. The added row contains coefficients requiring \(\Omega(h)\) bits under ordinary binary rational encoding, although \(N\), \(d\), and the encoding length of \(K=0\) are constant.
Minimum clarification: Include the total encoding length of the repeated terminal-mass coefficients in the incremental bound, or state the sufficient bound \(O(L+N\log(d+2)+\ell_K)\). The final decision running time remains \(\operatorname{poly}(L+\ell_K)\).
The peripheral attribution to [Parkes–Ungar, Theorem 8](https://cdn.aaai.org/AAAI/2000/AAAI00-013.pdf) matches the cited theorem. The mass-problem proof does not depend on transferring that finite-agent result.
The prover establishes polynomial-time exact optimization and decision for the specified representation. Its qualification concerning NP-hardness unless \(\mathrm P=\mathrm{NP}\) is appropriate.
⟨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.