Answer: Polynomial-time solvable in \(m,\tau,L\), with an exact rational revenue-maximizing vector as output.
Proposition 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf the set of items is structured as a directed acyclic graph D, and each bid is a subtree of D, then winner determination is NP-complete. Faster data structures Bid graph representation (GRA) We use an adja- cency list representation of the bid graph G for efficient insert and delete operations on bids. We do not actu- ally keep track of exclusion counts ej. Instead, a bid j having been deleted corresponds to ej > 0, and a bid j not having been deleted corresponds to ej = 0.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an item DAG \(D=(V,E)\), rational per-capita supplies \(q_v\), and a finite support of buyer types \(t\), each with rational mass \(\mu_t\), price \(p_t\), and a bundle \(S_t\) that is a subtree of \(D\), choose accepted masses \(x_t\) maximizing \(\sum_t p_t x_t\), subject to \(0\le x_t\le\mu_t\) and \(\sum_{t:v\in S_t}x_t\le q_v\) for every \(v\in V\). Each accepted unit of mass receives its type’s whole bundle; determine the revenue-maximizing vector \(x\).
Let \(D=(V,E)\) be an explicitly given item DAG with \(m=|V|\geq1\). Each item has a nonnegative binary-rational per-capita supply \(q_v\).
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a nonnegative binary-rational price \(p_t\) and an explicitly listed nonempty bundle \(S_t\subseteq V\), which is the vertex set of a directed out-tree subgraph of \(D\); it need not be induced or contain all descendants of its root. Different types may request the same bundle.
An allocation chooses real accepted masses \(x_t\). Each accepted unit receives one unit of every item in its whole bundle and pays \(p_t\). Unallocated supplies may be discarded, and any revenue-maximizing allocation is acceptable.
The optimization problem is \(\max\sum_t p_tx_t\), subject to \(0\leq x_t\leq\mu_t\) and \(\sum_{t:v\in S_t}x_t\leq q_v\) for every \(v\in V\). Let \(L\) be the total binary input length.
Is computing an exact revenue-maximizing vector \(x\) polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For indivisible bids and one unit per item, the revenue-threshold decision problem with directed subtree bundles in a DAG is NP-complete. With connected subtree bundles in an item tree, discrete optimization takes \(O(nm)\) time for \(n\) bids ([verified full version](https://cs.uwaterloo.ca/~klarson/teaching/F04-886/papers/bidbranching.aij03.pdf)).
Computing an exact revenue-maximizing vector is polynomial-time solvable in \(m,\tau,L\). This holds even for arbitrary explicitly listed bundles; the directed out-tree restriction is unnecessary.
The conclusion uses the stated model, in which each accepted mass \(x_t\) may take any real value in \([0,\mu_t]\).
Index the items and types, and define the incidence matrix \(A\in\{0,1\}^{m\times\tau}\) by
\(A_{vt}=1\) if \(v\in S_t\), and \(A_{vt}=0\) otherwise.
Let \(q=(q_v)_{v\in V}\), \(\mu=(\mu_t)_{t=1}^{\tau}\), and \(p=(p_t)_{t=1}^{\tau}\). The optimization problem is exactly
\(\max\{p^{\mathsf T}x:Ax\leq q,\ x\leq\mu,\ -x\leq0\}\).
Indeed, \((Ax)_v=\sum_{t:v\in S_t}x_t\) is precisely the consumption of item \(v\). Thus every feasible allocation gives a feasible LP vector with the same revenue, and every feasible LP vector is an allocation permitted by the problem.
This LP has \(\tau\) variables and \(m+2\tau\) inequalities. Its full constraint matrix is obtained by stacking \(A\), \(I_\tau\), and \(-I_\tau\). All matrix entries belong to \(\{-1,0,1\}\), while its right-hand side and objective coefficients are rational numbers supplied in the input.
Even a dense representation has binary length
\(N=O(m\tau+\tau^2+L)\).
The explicitly listed bundles allow construction of \(A\) in polynomial time. In particular, the algorithm creates one variable for each listed type, rather than enumerating possible types or possible bundles. Repeated bundles simply give repeated columns, possibly with different bounds and prices.
Write \(P=\{x\in\mathbb R^\tau:Ax\leq q,\ 0\leq x\leq\mu\}\).
First, \(P\) is nonempty: \(x=0\) satisfies every constraint because all supplies and masses are nonnegative.
Second, \(P\) is closed, being an intersection of finitely many closed halfspaces. It is bounded because \(P\subseteq\prod_{t=1}^{\tau}[0,\mu_t]\). Therefore \(P\) is compact. The continuous objective \(p^{\mathsf T}x\) consequently attains a finite maximum on \(P\).
We apply the standard exact rational linear-programming theorem: given an explicitly represented rational LP with a nonempty bounded feasible region, an exact rational optimal vector can be computed in time polynomial in its binary encoding length. This theorem includes lower-dimensional feasible regions and multiple optimal solutions; an optimal vertex can be returned. See [CMU’s *Advanced Algorithms* notes, Theorem 19.5](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f20/www/notes/cmu850-f20.pdf#page=239).
All hypotheses have now been checked:
Applying that theorem therefore returns an exact optimal vector in time \(\operatorname{poly}(N)\), hence in time \(\operatorname{poly}(m,\tau,L)\). This is an exact computation guarantee, beyond merely approximating the optimal revenue.
An explicit determinant argument also verifies that exact output does not require exponentially many bits.
Choose an optimal vertex \(x^\star\), whose existence follows from the elementary theorem that a linear objective on a nonempty bounded polyhedron has an optimal vertex.
At a vertex, the normals of the tight inequalities span \(\mathbb R^\tau\). To see why, suppose they did not. There would be a nonzero vector \(h\) orthogonal to all tight normals. Every other inequality has positive slack, so, because there are finitely many inequalities, both \(x^\star+\varepsilon h\) and \(x^\star-\varepsilon h\) would remain feasible for sufficiently small \(\varepsilon>0\). This would express \(x^\star\) as the midpoint of two distinct feasible points, contradicting the definition of a vertex.
Consequently, we can select \(\tau\) linearly independent tight inequalities and write
\(Bx^\star=r\),
where \(B\in\{-1,0,1\}^{\tau\times\tau}\) is nonsingular and the entries of \(r\) are selected from the supplies, masses, and zero.
Let \(H\) be the product of the positive denominators of all supplies and masses in their input representations. Then \(Hr\) is integral, and \(H\) has \(O(L)\) bits: the logarithm of a product is the sum of the logarithms of its factors. Each entry of \(Hr\) likewise has \(O(L)\) bits.
Set \(y=Hx^\star\), so that \(By=Hr\). For each coordinate \(t\), let \(B_t\) be obtained by replacing column \(t\) of \(B\) with \(Hr\). Cramer’s rule gives
\(x_t^\star=\dfrac{\det B_t}{H\det B}\).
The determinant expansion has \(\tau!\) terms. Since the entries of \(B\) have absolute value at most one,
\(1\leq|\det B|\leq\tau!\).
Every term in the expansion of \(\det B_t\) contains one entry of \(Hr\) and otherwise entries of absolute value at most one. Therefore
\(|\det B_t|\leq\tau!\max_i|(Hr)_i|\).
Both numerator and denominator in the displayed representation of \(x_t^\star\) thus have
\(O\bigl(L+\tau\log(\tau+1)\bigr)\)
bits. Reducing the fraction cannot increase that bound. Hence the entire optimal vector has polynomial binary length.
The cited discrete problem requires each bid to be either accepted or rejected. Its formulation explicitly imposes binary decision variables; the directed-subtree hardness result concerns that discrete problem. See [Sandholm and Suri, Section 2 and Theorem 6](https://cs.uwaterloo.ca/~klarson/teaching/F04-886/papers/bidbranching.aij03.pdf).
Here the admissible choices are the full intervals \(0\leq x_t\leq\mu_t\). Restricting them to \(x_t\in\{0,\mu_t\}\) would change the problem. An exact optimizer for the continuous problem need not return a vector satisfying that restriction, so the discrete hardness result does not establish hardness of the stated task.
Likewise, no integrality property of the bundle-incidence matrix is needed: fractional accepted masses are valid outputs. The exact rational LP algorithm completely resolves the question.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. Its argument establishes polynomial-time computation of an exact rational revenue-maximizing vector in \(m,\tau,L\). No major or minor mathematical issues were found.
The incidence definition \(A_{vt}=1\) precisely when \(v\in S_t\) correctly gives item consumption as
\((Ax)_v=\sum_{t:v\in S_t}x_t\).
The constraints \(Ax\leq q\), \(x\leq\mu\), and \(-x\leq0\) are exactly the task’s feasibility requirements. The objective \(p^{\mathsf T}x\) is exactly its revenue. Both directions of the claimed correspondence between allocations and LP vectors hold.
The counts of \(\tau\) variables and \(m+2\tau\) inequalities are correct. Stacking \(A,I_\tau,-I_\tau\) produces only entries in \(\{-1,0,1\}\). The dense encoding bound
\(N=O(m\tau+\tau^2+L)\)
correctly includes the constraint matrix and the input rational coefficients.
Construction uses the explicitly listed support, without enumerating possible types. Repeated bundles correctly remain separate variables, allowing different prices and mass bounds.
The out-tree restriction is unnecessary for this formulation and algorithm.
The zero vector is feasible because \(q_v\geq0\) and \(\mu_t>0\).
The feasible set is closed and lies inside the bounded box \(\prod_t[0,\mu_t]\). Consequently, it is compact, and the continuous linear objective attains a finite maximum.
These arguments also cover zero supplies, zero prices, and feasible regions of lower dimension. The normalization \(\sum_t\mu_t=1\) ensures the support is nonempty; no unhandled zero-variable case arises.
The invoked theorem is stated sufficiently precisely: an explicitly represented rational LP with a nonempty bounded feasible region admits polynomial-time computation of an exact rational optimizer.
The cited [CMU notes, Theorem 19.5 and Section 19.4.1](https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15850-f20/www/notes/cmu850-f20.pdf#page=239) support polynomial-time computation of an optimal vertex and explicitly discuss lower-dimensional polytopes and numerical precision.
All required hypotheses are checked in the write-up. Maximization versus the source’s minimization convention is an immediate sign conversion, with no substantive issue.
The deduction from polynomial time in \(N\) to polynomial time in \(m,\tau,L\) is valid. The result concerns an exact vector, not merely an approximate objective value.
The stated optimal-vertex existence theorem applies to the nonempty bounded polyhedron.
The argument that tight constraint normals span \(\mathbb R^\tau\) is valid: a nonzero orthogonal direction preserves tight constraints, and finitely many strictly slack constraints permit sufficiently small perturbations in both directions. This contradicts extremality.
Selecting \(\tau\) independent tight constraints therefore yields a nonsingular integer matrix \(B\) with entries in \(\{-1,0,1\}\).
The denominator-clearing argument is correct. The product \(H\) has \(O(L)\) bits, and each entry of \(Hr\) is integral with \(O(L)\) bits.
Cramer’s rule correctly yields
\(x_t^\star=\det B_t/(H\det B)\).
The determinant bounds
\(1\leq|\det B|\leq\tau!\)
and
\(|\det B_t|\leq\tau!\max_i|(Hr)_i|\)
are valid, including when a numerator is zero.
Thus the claimed per-coordinate bound
\(O(L+\tau\log(\tau+1))\)
and polynomial total output length follow. Fraction reduction cannot increase these bounds.
The cited [Sandholm–Suri paper, Section 2 and Theorem 6](https://cs.uwaterloo.ca/~klarson/teaching/F04-886/papers/bidbranching.aij03.pdf) explicitly uses binary acceptance variables and states hardness for directed subtree bids in a DAG.
The prover correctly distinguishes that model from the task’s continuous intervals. Imposing \(x_t\in\{0,\mu_t\}\) would change the feasible set. Discrete hardness therefore does not invalidate the continuous LP algorithm.
No integrality property is required because fractional masses are permitted.
None. No additional lemma, hypothesis, computation, or clarification is needed to verify the conclusion.
⟨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.