Answer: Polynomial-time solvable; an exact optimum \(x^\star\) can be computed in time polynomial in \(m,\tau,B,L\), and hence satisfies \(W(x^\star)\geq\mathrm{OPT}-3C\varepsilon\).
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateiBundle terminates with an allocation that is within minfjGj; jI jg of the optimal solution, for myopic best-response agent bidding strategies. The auction is optimal as the bid increment approaches zero because the error-term goes to zero. However, iBundle requires price discrimination, and this can be hard to enforce. For example, the auctioneer must prevent agents entering the auction under multiple pseudonyms, and also prevent the transfer of items in an after-market.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of bidder types \(T\), rational masses \(\mu_t\), explicit package menus \(\mathcal B_t\subseteq 2^{[m]}\), package values \(v_{t,S}\), and per-capita supplies \(q_j\), compute an allocation \(x_{t,S}\geq 0\) maximizing \(\sum_{t\in T}\sum_{S\in\mathcal B_t}v_{t,S}x_{t,S}\), subject to \(\sum_{S\in\mathcal B_t}x_{t,S}\leq\mu_t\) for each type and \(\sum_{t,S:j\in S}x_{t,S}\leq q_j\) for each resource class. Each unit of assigned mass receives the whole package \(S\).
A society is given by its support: the list of the \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) resource classes with binary-rational per-capita supplies \(q_j\geq0\). Each type has an explicit menu \(\mathcal B_t\subseteq2^{[m]}\setminus\{\varnothing\}\) and nonnegative binary-rational values \(v_{t,S}\), with \(v_{t,S}\leq v_{t,R}\) whenever listed packages satisfy \(S\subseteq R\). Receiving nothing has value zero; surplus resources may be discarded.
An allocation assigns disjoint portions of each type to whole packages: \(x_{t,S}\geq0\), \(\sum_{S\in\mathcal B_t}x_{t,S}\leq\mu_t\), and \(\sum_{t\in T}\sum_{S\in\mathcal B_t:j\in S}x_{t,S}\leq q_j\). Mass may be split between packages, but each assigned individual receives one whole package.
Write \(W(x)=\sum_{t\in T}\sum_{S\in\mathcal B_t}v_{t,S}x_{t,S}\), let \(\mathrm{OPT}\) be its maximum over feasible allocations, and set \(C=\min\{1,\sum_{j=1}^m q_j\}\). The input also includes a positive binary-rational tolerance \(\varepsilon\); let \(B=\sum_t|\mathcal B_t|\) and let \(L\) be the total input bit length, including \(\varepsilon\).
Can a feasible allocation satisfying \(W(x)\geq\mathrm{OPT}-3C\varepsilon\) be computed in polynomial time in \(m,\tau,B,L\), or is achieving this additive guarantee NP-hard?
For discrete societies with \(n\) agents and \(M\) indivisible items, iBundle terminates under myopic best-response bidding with welfare loss at most \(3\min\{M,n\}\varepsilon\); this is an additive approximation guarantee, not a polynomial-time guarantee. Exact winner determination is reported NP-hard, and iBundle uses exact winner determination in each round. [Parkes and Ungar](https://cdn.aaai.org/AAAI/2000/AAAI00-012.pdf).
No result settling this precise continuous approximation question was verified.
The requested allocation is computable in polynomial time. In fact, an exactly optimal allocation is computable in polynomial time in \(m,\tau,B,L\).
The essential hypotheses are that menus are explicitly listed and type masses may be split between packages.
Let \(I=\{(t,S):t\in T,\ S\in\mathcal B_t\}\), so \(|I|=B\). Introduce one real variable \(x_{t,S}\) for each member of \(I\). Consider the linear program
\[ \max \sum_{(t,S)\in I}v_{t,S}x_{t,S} \]
subject to
\[ \sum_{S\in\mathcal B_t}x_{t,S}\leq\mu_t \qquad(t\in T), \]
\[ \sum_{\substack{(t,S)\in I\\j\in S}}x_{t,S}\leq q_j \qquad(j\in[m]), \]
and
\[ x_{t,S}\geq0 \qquad((t,S)\in I). \]
These are precisely the feasibility constraints in the question, and the objective is precisely \(W(x)\). Consequently, the linear program’s optimal value equals \(\mathrm{OPT}\).
To verify compatibility with whole-package assignments, fix a type \(t\), order its packages, and represent its mass by the interval \([0,\mu_t)\). Partition an initial portion of this interval into consecutive, disjoint intervals of lengths \(x_{t,S}\). Give every individual in the interval associated with \(S\) the entire package \(S\), and give the remaining individuals nothing. The type constraint ensures these intervals fit. Resource \(j\) is consumed in total mass exactly equal to the left-hand side of its resource constraint.
Thus every feasible vector represents an allowed allocation; no additional integrality constraint is required.
If \(B=0\), the empty allocation is optimal. Assume henceforth that \(B>0\).
The zero vector is feasible because all supplies and masses are nonnegative. Moreover, every feasible coordinate satisfies
\[ 0\leq x_{t,S}\leq\mu_t\leq1. \]
The feasible region is therefore nonempty, closed, and bounded. Since the objective is continuous, it attains a finite maximum.
We use the standard polynomial-time theorem for rational linear programming: given explicitly encoded rational constraints and a rational linear objective, a nonempty feasible region with a finite optimum admits an exact rational optimal solution computable in time polynomial in the program’s binary encoding length. This is the classical polynomial-time solvability result established through the ellipsoid method. [Khachiyan, *A polynomial algorithm in linear programming*](https://www.mathnet.ru/eng/dan42319).
All its hypotheses hold here:
Because each menu is explicit, all package-incidence coefficients can be constructed in polynomial time. Even a dense encoding has length bounded by
\[ O\bigl((\tau+m+B)(B+1)+L\bigr). \]
Applying the rational linear-programming theorem therefore returns an exact rational optimal allocation \(x^\star\) in time polynomial in \(m,\tau,B,L\). The theorem also guarantees a polynomial-size binary representation of the output.
The monotonicity assumption on listed package values is compatible with this formulation but is not needed for the algorithm.
By exact optimality,
\[ W(x^\star)=\mathrm{OPT}. \]
Since \(q_j\geq0\), we have \(C=\min\{1,\sum_jq_j\}\geq0\). Together with \(\varepsilon>0\), this gives
\[ W(x^\star)=\mathrm{OPT}\geq\mathrm{OPT}-3C\varepsilon. \]
This includes \(C=0\). The algorithm need not use \(\varepsilon\); its encoding is already included in \(L\).
Parkes and Ungar’s winner-determination problem assigns bundles to individual agents while respecting XOR bids and preventing any indivisible item from being assigned twice. Their paper reports that problem as NP-hard. [Parkes and Ungar, *Iterative Combinatorial Auctions: Theory and Practice*](https://cdn.aaai.org/AAAI/2000/AAAI00-012.pdf).
Here, arbitrary splitting of each type’s mass is expressly permitted. The linear program above consequently describes the actual allocation problem exactly. Discrete winner-determination hardness therefore does not establish hardness for this continuous model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly establishes polynomial-time computation of an exact optimum, which implies the requested additive guarantee. No major or minor mathematical issues were found.
The index set \(I\) contains exactly one variable for every explicitly listed type–package pair, so there are \(B\) variables.
The type constraints, resource constraints, nonnegativity constraints, and objective coincide with those in USER_TASK. Thus the feasible sets and optimal values agree exactly. The LP does not introduce unlisted packages.
The interval construction is valid under the task’s express permission to split type mass arbitrarily. For each type, nonnegative interval lengths sum to at most \(\mu_t\); hence the intervals fit and are disjoint. Every assigned individual receives one entire listed package. The resulting resource consumption is exactly the corresponding constraint sum. No integrality condition is missing.
The treatment of \(B=0\) is correct: there are no assignable packages, and the empty allocation has optimal welfare zero.
For \(B>0\), the zero vector is feasible. Nonnegativity and the type constraint imply \(x_{t,S}\leq\mu_t\), while positive normalized masses imply \(\mu_t\leq1\). Consequently the feasible set is bounded. It is closed because it is defined by finitely many non-strict linear inequalities.
The continuous objective therefore attains a finite maximum on this nonempty compact set. Empty individual menus, zero supplies, and zero values cause no difficulty.
The prover states the rational linear programming theorem precisely enough for this application: explicitly encoded rational data, nonempty feasibility, and a finite optimum permit computation of an exact rational optimal solution in polynomial binary time. This is a valid standard theorem; the attribution to Khachiyan’s polynomial-time LP result is appropriate. [Khachiyan’s paper](https://www.mathnet.ru/eng/dan42319).
Every required hypothesis is verified in the output:
The stated dense encoding bound
\(O((\tau+m+B)(B+1)+L)\)
is valid: matrix coefficients have constant encoding size, and the supplied rational coefficients contribute at most their input encoding length, with structural overhead covered by the displayed bound.
Explicit package lists permit construction of all incidence coefficients in polynomial time. The resulting LP encoding is polynomial in the requested parameters. The exact rational output has polynomial binary length; allocation coordinates are allowed to be real, so rational output satisfies the task’s domain requirements.
Exact optimality gives \(W(x^\star)=\mathrm{OPT}\). Since \(C\geq0\) and \(\varepsilon>0\), the claimed inequality follows with the correct sign and constant.
The case \(C=0\) is included: the required guarantee then demands exact optimality, which the algorithm supplies. Ignoring \(\varepsilon\) is legitimate because the algorithm establishes the stronger exact guarantee.
The cited paper does describe exclusive-or bids, prohibits assigning an indivisible item twice, and reports NP-hard winner determination. The prover accurately summarizes those statements. [Parkes and Ungar](https://cdn.aaai.org/AAAI/2000/AAAI00-012.pdf).
The conclusion is appropriately limited: that discrete hardness result does not establish hardness for the stated continuous model. The exact LP equivalence independently settles the continuous question.
Required clarification or repair: none.
⟨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.