Answer: Polynomial-time solvable.
Theorem 2 — class: other
Given τ valuation types \(t\) with rational masses \(\mu_t\) summing to \(1\), \(m\) goods with rational per-capita capacities \(q_j\), explicit XOR bids with free disposal, and report-independent nested ranges \(\mathcal{B}_1\subseteq\cdots\subseteq\mathcal{B}_K=2^G\) represented by GROWRANGE item-partition refinements, compute at each stage \(\ell\) an exact rational welfare-maximizing assignment of type mass to integral bundles in \(\mathcal{B}_\ell\), respecting type masses and capacities; also compute the optimum after deleting each type’s mass.
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Let \(G\) contain \(m\geq1\) goods, with binary-rational per-capita capacities \(q_j\geq0\). Each type has an explicit finite XOR bid list \(D_t\) of pairs \((A,b)\), where \(\varnothing\neq A\subseteq G\) and \(b\in\mathbb Q_{\geq0}\); its free-disposal valuation is \(v_t(S)=\max(\{0\}\cup\{b:(A,b)\in D_t,\ A\subseteq S\})\), so \(v_t(\varnothing)=0\).
The input includes \(K\geq1\) report-independent partitions \(P_1,\ldots,P_K\) into nonempty parts; each successive partition refines its predecessor by splitting parts, and \(P_K\) consists of singletons. Define \(\mathcal B_\ell=\{\bigcup_{C\in H}C:H\subseteq P_\ell\}\), including the empty bundle.
At stage \(\ell\), an assignment consists of nonnegative rational masses \(x_{t,S}\) for \(S\in\mathcal B_\ell\), satisfying \(\sum_Sx_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni j}x_{t,S}\leq q_j\). Mass may split among integral bundles; welfare is \(\sum_t\sum_Sv_t(S)x_{t,S}\).
Compute a welfare-maximizing assignment and its value at every stage, and the optimum value after deleting each type's entire mass. Deletion leaves other masses, capacities and partitions unchanged, without renormalization. Any maximizing assignment is acceptable; represent it by its nonzero entries. Let \(L\) be the total binary input length, including all bids and partitions.
Is this exact continuous optimization problem solvable in time polynomial in \(m,\tau,K,L\), or is it \(\mathrm{NP}\)-hard?
For finite agents, report-independent staged maximal-in-range VCG is strategyproof under an independent stage-based interruption and eventually implements an efficient allocation; this is an incentive and eventual-efficiency result, without a polynomial runtime guarantee ([Parkes–Schoenebeck](https://schoeneb.people.si.umich.edu/papers/GrowRange.pdf)).
For the related model of combinatorial exchanges with independent partially acceptable bids, surplus maximization is polynomial-time solvable; that model does not impose the type-mass XOR constraints and staged partition ranges above ([Solving Combinatorial Exchanges](https://www.cs.cmu.edu/~sandholm/www/partialBids.aaai02WS.pdf)). No result settling this exact continuous problem was identified in the search.
Result. The problem is polynomial-time solvable, including exact maximizing assignments at every stage and all whole-type deletion values. The essential fact is that each type needs only polynomially many candidate bundles.
1. Partition closures. Let \(T\) denote the support of types, and let \(B=\sum_{t\in T}|D_t|\) be the total number of listed bids.
For a stage \(\ell\) and a set \(A\subseteq G\), define its partition closure by
\(\displaystyle \operatorname{cl}_{\ell}(A)=\bigcup_{\substack{C\in P_\ell\\C\cap A\neq\varnothing}}C.\)
This closure belongs to \(\mathcal B_\ell\) and contains \(A\). Moreover, if \(S\in\mathcal B_\ell\) contains \(A\), then \(\operatorname{cl}_\ell(A)\subseteq S\): every partition part intersecting \(A\) must be included in \(S\).
For each type, define the candidate family
\(\displaystyle F_{t,\ell}=\{\varnothing\}\cup\{\operatorname{cl}_\ell(A):(A,b)\in D_t\},\)
removing duplicates. Thus \(|F_{t,\ell}|\leq 1+|D_t|\).
Lemma. For every \(S\in\mathcal B_\ell\), there exists \(R\in F_{t,\ell}\) such that \(R\subseteq S\) and \(v_t(R)=v_t(S)\).
Proof. If \(v_t(S)=0\), take \(R=\varnothing\). Otherwise, finiteness of the bid list implies that some \((A,b)\in D_t\) satisfies \(A\subseteq S\) and \(b=v_t(S)\). Take \(R=\operatorname{cl}_\ell(A)\). The closure property gives \(A\subseteq R\subseteq S\). Consequently, the bid on \(A\) gives \(v_t(R)\geq b\), while free-disposal monotonicity gives \(v_t(R)\leq v_t(S)=b\). Hence equality holds. \(\square\)
2. Restricting to candidates preserves welfare. Fix a stage and a set \(I\subseteq T\) of remaining types. Consider any feasible assignment \(x\) for these types.
For every \(t\in I\) and \(S\in\mathcal B_\ell\), choose a bundle \(R_{t,S}\) supplied by the lemma, and define
\(\displaystyle y_{t,R}=\sum_{\substack{S\in\mathcal B_\ell\\R_{t,S}=R}}x_{t,S}\qquad(R\in F_{t,\ell}).\)
The transformation preserves each type’s total assigned mass. For every good \(j\), it also satisfies
\(\displaystyle \sum_{t\in I}\sum_{\substack{R\in F_{t,\ell}\\j\in R}}y_{t,R} =\sum_{t\in I}\sum_{S\in\mathcal B_\ell}\mathbf 1_{\{j\in R_{t,S}\}}x_{t,S} \leq\sum_{t\in I}\sum_{S\in\mathcal B_\ell}\mathbf 1_{\{j\in S\}}x_{t,S} \leq q_j.\)
The first inequality follows from \(R_{t,S}\subseteq S\). Welfare is unchanged because
\(\displaystyle \sum_{t\in I}\sum_{R\in F_{t,\ell}}v_t(R)y_{t,R} =\sum_{t\in I}\sum_{S\in\mathcal B_\ell}v_t(R_{t,S})x_{t,S} =\sum_{t\in I}\sum_{S\in\mathcal B_\ell}v_t(S)x_{t,S}.\)
Conversely, every feasible assignment using candidate bundles is an allowed stage assignment. Thus restricting each type to \(F_{t,\ell}\) preserves the optimum exactly.
3. The explicit linear program. Compute the actual valuation of every candidate:
\(\displaystyle c_{t,R}=\max\bigl(\{0\}\cup\{b:(A,b)\in D_t,\ A\subseteq R\}\bigr).\)
Using the actual valuation matters: the closure of one listed bid may contain another bid with a larger value.
For stage \(\ell\) and remaining types \(I\), solve the following rational linear program:
\(\displaystyle \max\ \sum_{t\in I}\sum_{R\in F_{t,\ell}}c_{t,R}y_{t,R},\)
subject to
\(\displaystyle \sum_{R\in F_{t,\ell}}y_{t,R}=\mu_t\qquad(t\in I),\)
\(\displaystyle \sum_{t\in I}\sum_{\substack{R\in F_{t,\ell}\\j\in R}}y_{t,R}\leq q_j\qquad(j\in G),\)
and \(y_{t,R}\geq0\).
This program is feasible: assign all remaining mass to the empty bundle. It is bounded, since every variable satisfies \(0\leq y_{t,R}\leq\mu_t\). Its feasible set is therefore compact.
It has at most \(B+\tau\) variables and at most \(\tau+m\) equality and capacity constraints. All constraint coefficients are zero or one. Every objective coefficient is zero or a bid value already present in the input.
The standard rational linear-programming theorem supplies an exact rational optimum in time polynomial in the program’s binary encoding length. It applies here because the program is explicit, rational, feasible, and bounded; it does not require a full-dimensional feasible region. See [MIT’s linear-programming algorithm notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
By Section 2, the resulting rational assignment is feasible for the original problem and dominates every original feasible assignment. It is consequently an exact maximizing assignment for that stage.
4. Construction cost and output size. Represent bundles by their membership vectors on \(G\). Each closure is computable by scanning the partition. Each candidate valuation is computable by testing containment against the type’s explicit bid list.
Across all stages, these operations require at most a polynomial number of scans and rational comparisons; for example, candidate valuation evaluation uses at most \(O(KmB^2)\) elementary containment work. Comparisons of bid values have polynomial bit complexity. Constructing the constraint matrices also takes polynomial time in \(m,\tau,K,L\).
For completeness, exact optimal assignments have polynomial binary descriptions independently of any numerical approximation argument. Introduce one nonnegative slack variable for each capacity constraint. The resulting equality system has \(r=|I|+m\) rows and a zero-one coefficient matrix. Its rows are independent: the slack columns isolate the capacity rows, and each type’s empty-bundle column then isolates its mass row.
At a vertex, positive-variable columns must be linearly independent. Otherwise, a nonzero dependence permits sufficiently small perturbations in both directions while preserving equality constraints and nonnegativity, contradicting extremality. Thus a vertex has at most \(r\) positive variables, including slacks.
For a basis matrix \(M\), its basic coordinates solve \(Mz=h\), where \(h\) contains the remaining masses and unchanged capacities. Choose a common denominator \(Q\) for the entries of \(h\). The bit length of \(Q\) is at most the total denominator encoding length in the input. Cramer’s rule gives
\(\displaystyle z_i=\frac{\det M_i(Qh)}{Q\det M}.\)
Hadamard’s inequality bounds the zero-one determinant by \(|\det M|\leq r^{r/2}\), and bounds the numerator determinant by \(r^{r/2}\max_k|(Qh)_k|\). Hence every vertex coordinate has bit length polynomial in \(r\) and \(L\).
An optimal vertex can also be found in polynomial time: after computing the optimum value, successively maximize each coordinate over the current optimal face and fix its attained value. After at most \(B+\tau\) additional LPs the face is a singleton, hence a vertex. Each intermediate face has vertices among the original vertices, so the newly fixed values retain the polynomial bit bounds just proved.
Consequently, one may return at most \(m+|I|\) nonzero assignment entries. Each entry consists of a type, an \(m\)-bit bundle, and a rational mass of polynomial bit length. The exact welfare value likewise has polynomial bit length.
5. All stages and whole-type deletions. For every stage \(\ell\), solve the program with \(I=T\), and output its maximizing assignment and value.
For every deleted type \(u\in T\), solve the same stage program with \(I=T\setminus\{u\}\). The other masses remain \(\mu_t\); the capacities, partitions, and candidate families for surviving types remain unchanged. This implements deletion without renormalization. If no types remain, the value is zero.
There are \(K(\tau+1)\) such optimization problems, each of polynomial encoding length. Their total exact running time and output length are therefore polynomial in \(m,\tau,K,L\).
The refinement condition is compatible with this algorithm but is not needed for tractability: the proof works separately for every supplied partition.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The candidate-bundle reduction preserves welfare and feasibility, and the resulting explicit rational linear programs yield exact solutions in polynomial time. I found no major or minor issues.
The closure definition is valid for every supplied partition. Since a permitted bundle is a union of whole partition parts, any permitted bundle containing \(A\) must contain every part intersecting \(A\). Thus the claimed inclusion \(\operatorname{cl}_{\ell}(A)\subseteq S\) is correct.
The candidate family contains the empty bundle and at most one closure per listed bid, so its stated size bound holds, including when a type has an empty bid list.
The lemma correctly handles both valuation cases:
No assumption about positive bids, unique maximizing bids, or distinct closures is needed.
The transformation is well-defined because the stage bundle family is finite. Aggregating masses over the chosen candidate bundles preserves nonnegativity, rationality, and each remaining type’s total mass.
The capacity calculation is correct: replacing a bundle by a subset cannot increase consumption of any good. The welfare calculation is also correct because the lemma gives equal valuations for each replaced bundle.
The converse inclusion is immediate from the candidates belonging to the permitted stage range. Consequently, the restricted and original problems have exactly the same achievable optimum. This argument applies to every subset \(I\) of surviving types without changing their masses.
The objective coefficients are correctly computed as actual candidate valuations. The prover explicitly avoids the possible error of treating a closure’s generating bid value as its valuation.
The LP has at most \(B+\tau\) variables and at most \(\tau+m\) mass and capacity constraints, apart from nonnegativity constraints. Its coefficients and right-hand sides are rational and have polynomial encoding length.
Feasibility follows from assigning every surviving type’s mass to the empty bundle. Each assignment variable is bounded by its type’s mass, so the feasible region is closed and bounded and the optimum is attained.
The invoked theorem—exact rational linear programming is solvable in time polynomial in the explicit binary encoding length—is applicable. Equalities and a lower-dimensional feasible region do not invalidate it. The cited [MIT linear-programming notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time algorithms, lower-dimensional feasibility, and recovery of optimal vertices.
Thus the LP solution supplies an exact maximizing assignment for the original stage problem.
Partition closures, bundle containment tests, duplicate removal, and comparisons of rational bid values all admit polynomial-time execution on the explicit input.
The stated containment-work bound \(O(KmB^2)\) is valid for evaluating nonempty candidates against their types’ bids. Empty candidates have valuation zero directly. Constructing the matrices and representing bundles by \(m\)-bit membership vectors also takes polynomial time.
The slack-variable argument is correct. Slack columns isolate the capacity rows, and each type’s empty-bundle column isolates its mass row, establishing full row rank.
The perturbation argument correctly shows that a vertex has at most \(r=|I|+m\) positive coordinates, including slacks. The use of a nonsingular basis matrix and Cramer’s rule is valid.
The common-denominator bound is sound. Hadamard’s inequality gives the stated bounds for both the basis determinant and the determinant with one column replaced by \(Qh\). These imply polynomial bit length for every vertex coordinate, including when capacities are large or some are zero.
Successively maximizing and fixing assignment coordinates over the optimal face is also valid. Each step selects a face, whose vertices remain vertices of the original polytope. Fixing every assignment coordinate leaves a singleton, hence an optimal vertex. The fixed values retain polynomial bit length, so the additional LPs remain polynomial in size.
The resulting assignment has at most \(m+|I|\) nonzero entries. Its welfare value has polynomial bit length as well.
Solving independently for every supplied stage satisfies the requested stagewise outputs. Solving with \(I=T\setminus\{u\}\) implements whole-type deletion exactly: surviving masses and capacities remain unchanged, with no renormalization.
The count \(K(\tau+1)\) is correct for the full society and each deletion at each stage. A polynomial number of polynomial-time computations gives polynomial total runtime and output length.
The argument covers empty bid lists, zero bids, zero capacities, coinciding closures, repeated partitions, and deletion of the sole type. The explicit zero-value treatment when no types remain is correct. The observation that refinement is unnecessary for this algorithm is also justified.
No additional clarification or repair is required.
⟨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.