Answer: \(\mathrm{P}\): the decision problem is solvable in time polynomial in \(m,\tau,L\), and an optimal rational manipulation and internal allocation can be constructed.
Theorem 2 (Optimal Collusion) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 2 com- putes the optimal manipulation for the colluder coalition C.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a maximum demand \(K\), a finite support \(\Theta\) of rational diminishing-marginal valuation schedules, a population distribution \(\mu\), a designated coalition subdistribution \(\nu\leq\mu\), and supply \(\rho\) units per capita, choose a mass flow \(\pi_{\theta,b}\) assigning coalition agents of true type \(\theta\) to nonincreasing rational bid schedules \(b\), with noncoalition mass reporting truthfully. Allocate the top \(\rho\) mass of reported marginal units, splitting cutoff ties symmetrically, and find a flow maximizing coalition true utility \(\sum_{\theta,b,k}\alpha_{\theta b k}(v_\theta(k)-pk)\), where \(p\) is the limiting VCG cutoff price and \(\alpha_{\theta b k}\) is coalition mass receiving \(k\) units.
A society is given by its support: \(\tau\) types with positive masses \(\mu_\theta\), each encoded as a binary rational; \(\tau\) counts listed types, not possible types. Normalize \(\sum_\theta\mu_\theta=1\). Each type has an explicitly listed valuation schedule \(v_\theta(0),\ldots,v_\theta(K)\), with \(v_\theta(0)=0\) and positive, nonincreasing rational marginal values. Set \(m=K\geq1\).
The input also gives rational coalition masses \(0\leq\nu_\theta\leq\mu_\theta\), with \(\sum_\theta\nu_\theta>0\), rational supply \(0<\rho\leq K\), and a rational utility threshold \(T\). Let \(L\) be the total input bit length.
A manipulation is a finitely supported nonnegative rational flow \(\pi_{\theta,b}\), with \(\sum_b\pi_{\theta,b}=\nu_\theta\), over rational marginal bid schedules \(b_1\geq\cdots\geq b_K\geq0\). Noncoalition mass reports its true marginals.
Each reported marginal contributes its reporting mass to the marginal-bid distribution. Let \(D_{>}(x)\) be its mass strictly above \(x\), and define the unit price \(p=\inf\{x\geq0:D_{>}(x)\leq\rho\}\).
Allocate all marginal mass above \(p\), and the fraction \(f\) of mass at \(p\) needed to allocate exactly \(\rho\). For an agent with a block of equal cutoff bids, award the whole block to fraction \(f\) of such agents and none of it to the remainder; this preserves prefixes and treats identical reports symmetrically.
Let \(Q\) be the coalition's awarded unit mass; its total auction payment is \(pQ\). Coalition members may freely transfer items and money internally. Their final rational masses \(\beta_{\theta,k}\geq0\), for \(0\leq k\leq K\), satisfy \(\sum_k\beta_{\theta,k}=\nu_\theta\) and \(\sum_{\theta,k}k\beta_{\theta,k}=Q\); total true utility is \(U=\sum_{\theta,k}\beta_{\theta,k}v_\theta(k)-pQ\).
Is deciding whether some manipulation and internal allocation attain \(U\geq T\) in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite bidders with diminishing marginal valuations and unrestricted internal item and monetary transfers, optimal collusion under VCG is computable in polynomial time ([Bachrach](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/mu.pdf)).
No result settling this exact distributional problem was identified in the literature search.
The decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). Moreover, an optimal manipulation and internal allocation can be constructed with polynomial support and polynomial bit length.
The proof uses two facts: for any feasible coalition quantity, mixing an all-high report with an all-zero report minimizes its payment; and optimal internal allocation is a fractional greedy allocation of true marginal values.
Write the true marginal values as
\[ a_{\theta,j}=v_\theta(j)-v_\theta(j-1),\qquad 1\leq j\leq K. \]
By hypothesis, these are positive and nonincreasing in \(j\). Define the coalition and noncoalition unit capacities by
\[ c=\sum_\theta\nu_\theta,\qquad C=Kc,\qquad N=K(1-c). \]
Thus \(C>0\) and \(C+N=K\).
Let the noncoalition’s marginal mass strictly above a price \(x\) be
\[ A(x)=\sum_{\theta,j:\,a_{\theta,j}>x}(\mu_\theta-\nu_\theta). \]
In particular, \(A(0)=N\). Define the finite price set
\[ \mathcal P=\{0\}\cup \{a_{\theta,j}:\mu_\theta-\nu_\theta>0,\ 1\leq j\leq K\}. \]
It has at most \(\tau K+1\) elements.
Every coalition quantity must belong to the interval
\[ \mathcal I=[q_-,q_+],\qquad q_-=\max\{0,\rho-N\},\qquad q_+=\min\{C,\rho\}. \]
Indeed, the coalition receives at most \(C\) units and at most the supply \(\rho\), while the noncoalition receives at most \(N\) units. The interval is nonempty: \(\rho\leq C+N\) implies \(\rho-N\leq C\).
For \(R\in[0,N]\), define
\[ g(R)=\inf\{x\geq0:A(x)\leq R\}. \]
Since \(A\) is a finite step function whose positive breakpoints belong to \(\mathcal P\), this infimum is attained and belongs to \(\mathcal P\). More explicitly, if the distinct noncoalition marginal values are \(w_1>\cdots>w_r>0\), with respective masses \(d_1,\ldots,d_r\), then, for \(R<N\),
\[ g(R)=w_i \quad\text{where}\quad \sum_{\ell<i}d_\ell\leq R< \sum_{\ell\leq i}d_\ell. \]
Also, \(g(N)=0\). When \(N=0\), the only possible argument is \(R=0\), and \(g(0)=0\).
Lemma. For every rational \(Q\in\mathcal I\), the minimum attainable price among manipulations awarding the coalition quantity \(Q\) is \(g(\rho-Q)\). It is attained by a manipulation using at most two reports per coalition type.
Proof. First consider any manipulation awarding quantity \(Q\), with price \(p\). The noncoalition receives \(R=\rho-Q\) units. All its marginal mass strictly above \(p\) is allocated, so
\[ A(p)\leq R. \]
Consequently, \(p\) belongs to the set defining \(g(R)\), and hence
\[ g(\rho-Q)\leq p. \]
For attainment, choose a rational \(H\) strictly above every true marginal value, and put \(\lambda=Q/C\). For every type \(\theta\), assign reporting mass \(\lambda\nu_\theta\) to the schedule \((H,\ldots,H)\), and reporting mass \((1-\lambda)\nu_\theta\) to \((0,\ldots,0)\).
These are admissible schedules, and their reporting masses sum to \(\nu_\theta\). Their total marginal mass at \(H\) is
\[ K\sum_\theta\lambda\nu_\theta=\lambda C=Q. \]
For every \(0\leq x<H\), the resulting total marginal mass strictly above \(x\) is therefore
\[ D_{>}(x)=Q+A(x). \]
Because \(Q\leq\rho\), some \(x<H\) satisfies \(D_{>}(x)\leq\rho\). The resulting auction price is exactly \(g(\rho-Q)\), and all marginal mass at \(H\) wins.
If this price is positive, all zero bids lose, so the coalition receives exactly \(Q\). If the price is zero, then \(A(0)=N\leq\rho-Q\). Since \(Q\in\mathcal I\) also gives \(\rho-Q\leq N\), equality holds. Thus the high bids and positive noncoalition bids already account for exactly the supply, and no zero-bid coalition mass needs allocation.
The construction consequently awards exactly \(Q\) at price \(g(\rho-Q)\). All reports and masses are rational. \(\square\)
This proof respects the specified cutoff rule: coalition reports either win their entire block above the cutoff or receive no cutoff units.
Let \(W(Q)\) denote the maximum coalition true value obtainable from quantity \(Q\):
\[ W(Q)= \max_\beta\sum_{\theta,k}\beta_{\theta,k}v_\theta(k), \]
subject to the internal allocation constraints in the question.
We now give an explicit formula for \(W\).
List all pairs \((\theta,j)\) with \(\nu_\theta>0\), sorted by nonincreasing marginal value. Resolve ties so that earlier marginal indices precede later indices within each type. Write their values and capacities as
\[ a_1\geq\cdots\geq a_n,\qquad d_i=\nu_{\theta_i}, \]
where \(n\leq\tau K\). Define
\[ c_0=0,\qquad c_i=\sum_{\ell=1}^i d_\ell. \]
Then \(c_n=C\). For \(Q\in[c_{i-1},c_i]\),
\[ W(Q)=\sum_{\ell<i}a_\ell d_\ell +a_i(Q-c_{i-1}). \]
Proof. For any internal allocation, let
\[ x_{\theta,j}=\sum_{k=j}^K\beta_{\theta,k}. \]
These variables satisfy
\[ \nu_\theta\geq x_{\theta,1}\geq\cdots\geq x_{\theta,K}\geq0, \]
and
\[ \sum_{\theta,j}x_{\theta,j}=Q,\qquad \sum_{\theta,k}\beta_{\theta,k}v_\theta(k) =\sum_{\theta,j}a_{\theta,j}x_{\theta,j}. \]
Temporarily retain only the bounds \(0\leq x_\ell\leq d_\ell\) and the total-quantity constraint. For \(Q\in[c_{i-1},c_i]\), any such vector satisfies
\[ \sum_\ell a_\ell x_\ell = a_iQ+ \sum_{\ell<i}(a_\ell-a_i)x_\ell+ \sum_{\ell>i}(a_\ell-a_i)x_\ell \leq \sum_{\ell<i}a_\ell d_\ell+a_i(Q-c_{i-1}). \]
Here the first sum is bounded using \(x_\ell\leq d_\ell\), and the last sum is nonpositive.
Equality is attained by filling every position before \(i\), partially filling position \(i\), and leaving later positions empty. The ordering ensures that, within each type, earlier marginals are filled before later ones. Hence this vector also satisfies the required monotonicity constraints.
It determines an admissible allocation through
\[ \beta_{\theta,0}=\nu_\theta-x_{\theta,1}, \]
\[ \beta_{\theta,k}=x_{\theta,k}-x_{\theta,k+1} \quad(1\leq k<K),\qquad \beta_{\theta,K}=x_{\theta,K}. \]
These masses are nonnegative, have the prescribed type totals, and award quantity \(Q\). For rational \(Q\), they are rational. \(\square\)
Thus \(W\) is continuous and piecewise linear, with at most \(\tau K\) pieces.
Combining this result with the preceding lemma, the best attainable utility for a prescribed rational quantity \(Q\in\mathcal I\) is
\[ W(Q)-Q\,g(\rho-Q). \]
The minimum-price function can jump at cutoff boundaries. The following algorithm handles those boundaries using closed intervals.
For each \(s\in\mathcal P\), define
\[ u_s=\min\{C,\rho-A(s)\},\qquad J_s=[q_-,u_s]. \]
Skip \(s\) if \(u_s<q_-\). Otherwise compute
\[ M_s=\max_{Q\in J_s}\bigl(W(Q)-sQ\bigr). \]
Because \(W(Q)-sQ\) is piecewise linear, this maximum occurs at an endpoint of \(J_s\) or at a breakpoint \(c_i\) belonging to \(J_s\). Therefore it suffices to evaluate
\[ \{q_-,u_s\}\cup\{c_i:q_-\leq c_i\leq u_s\}. \]
Let \(M\) be the largest value obtained over all prices and quantities considered. At least one interval is nonempty: at the largest noncoalition marginal value, \(A(s)=0\); if there is no noncoalition mass, the interval for \(s=0\) is nonempty.
Theorem. \(M\) is the optimal attainable coalition utility.
Proof: upper bound. Consider any manipulation and internal allocation, with quantity \(Q\), price \(p\), and utility \(U\). Put
\[ s=g(\rho-Q). \]
The minimum-price lemma gives \(s\in\mathcal P\) and \(s\leq p\). Also,
\[ A(s)\leq\rho-Q, \]
so \(Q\leq\rho-A(s)\). Together with \(Q\in\mathcal I\), this implies \(Q\in J_s\). Consequently,
\[ U\leq W(Q)-pQ \leq W(Q)-sQ \leq M_s \leq M. \]
Proof: attainment. Choose a candidate pair \((s,Q)\) attaining \(M\). Both coordinates are rational. Since \(Q\in J_s\),
\[ A(s)\leq\rho-Q, \]
and therefore \(g(\rho-Q)\leq s\). Use the two-report construction from Section 2 and the greedy internal allocation from Section 3. Their utility is
\[ W(Q)-Q\,g(\rho-Q) \geq W(Q)-sQ =M. \]
The upper bound just proved applies to this constructed manipulation as well, so its utility equals \(M\). \(\square\)
In these subproblems, \(s\) serves as a price upper bound. At a cutoff endpoint, the constructed manipulation may clear at a lower price; this improves its utility and makes the closed-interval optimization valid.
There are at most \(\tau K+1\) candidate prices and at most \(\tau K+2\) candidate quantities per price. The algorithm sorts the explicitly listed marginal values, computes rational cumulative masses and values, and evaluates the displayed formulas.
All computed numbers have polynomial bit length. They are formed from polynomially many additions, subtractions, multiplications, and divisions of input rationals and the integer \(K\). Thus exact rational comparisons and arithmetic take time polynomial in \(K,\tau,L\).
The maximizing quantity also yields a polynomial-size witness:
Finally, answer yes precisely when \(M\geq T\). Since \(m=K\), this is a polynomial-time decision algorithm in the parameters requested.
⟨structured verdict parsed — rendered above⟩
The proof resolves the stated decision problem. The minimum-price construction, greedy internal allocation, and finite optimization are correct, including at cutoff boundaries. No major or minor issues were found.
The definitions \(c=\sum_\theta\nu_\theta\), \(C=Kc\), and \(N=K(1-c)\) correctly give coalition and noncoalition unit capacities. The assumptions imply \(C>0\) and \(C+N=K\).
Every attainable coalition quantity satisfies
\[
\max\{0,\rho-N\}\leq Q\leq\min\{C,\rho\}.
\]
These inequalities follow from the supply constraint and the two groups’ capacities. The claimed nonemptiness follows from \(\rho\leq C+N\), together with nonnegativity of the capacities.
The function \(A\) correctly counts noncoalition marginal mass strictly above its argument. Because true marginals are positive, \(A(0)=N\).
The stated formula for \(g\) correctly handles strict inequalities. At \(x=w_i\), the mass strictly above \(x\) is \(\sum_{\ell<i}d_\ell\); immediately below \(w_i\), that mass includes \(d_i\). Therefore
\[
\sum_{\ell<i}d_\ell\leq R<\sum_{\ell\leq i}d_\ell
\]
gives \(g(R)=w_i\).
In particular, when \(R\) equals a cumulative mass, the formula selects the next lower breakpoint. This endpoint convention is important and is correct.
The cases \(R=N\) and \(N=0\) are explicitly and correctly handled. Thus the infimum is attained, belongs to \(\mathcal P\), and satisfies \(A(g(R))\leq R\).
The lower bound is valid: allocating all noncoalition marginal mass above the actual price gives \(A(p)\leq\rho-Q\), hence \(g(\rho-Q)\leq p\).
The construction is admissible. Since \(Q\in\mathcal I\subseteq[0,C]\), the mixing coefficient \(\lambda=Q/C\) lies in \([0,1]\). Both constant schedules are nonnegative and nonincreasing, and the reporting masses have the required type totals.
The high-report marginal mass is exactly
\[
K\sum_\theta\lambda\nu_\theta=Q.
\]
For \(0\leq x<H\), the identity \(D_{>}(x)=Q+A(x)\) is correct. Since \(H\) exceeds all true marginals, the defining price threshold is reached below \(H\), and the resulting price is exactly \(g(\rho-Q)\). All high reports therefore win their entire blocks.
The zero-price case is correctly checked. The condition \(g(\rho-Q)=0\) gives \(N\leq\rho-Q\), while feasibility gives \(\rho-Q\leq N\). Consequently, high coalition bids and positive noncoalition bids already fill the supply exactly. No coalition zero bids receive units.
The construction therefore attains exactly \(Q\), including \(Q=0\), \(Q=C\), and the case with no noncoalition mass. It also respects the specified block allocation rule.
The transformation
\[
x_{\theta,j}=\sum_{k=j}^K\beta_{\theta,k}
\]
correctly produces the monotonicity constraints, total quantity, and marginal-value objective.
The displayed upper-bound calculation is valid. For positions before \(i\), the coefficients \(a_\ell-a_i\) are nonnegative, so the capacity bounds apply in the stated direction. For positions after \(i\), those coefficients are nonpositive, so their contributions are at most zero.
The greedy vector attains this bound. Nonincreasing true marginals, together with the stated tie ordering, ensure that an earlier marginal of any type precedes its later marginals. Thus the vector satisfies every within-type monotonicity constraint.
The inverse formulas for \(\beta\) are correct: they give nonnegative masses, telescope to the prescribed type totals, and preserve total quantity and value. Rational \(Q\) yields rational allocation masses.
The formula covers both \(Q=0\) and \(Q=C\), and neighboring pieces agree at their common endpoints. Hence the claimed continuous piecewise-linear description of \(W\) is justified.
Each nonempty interval \(J_s\) lies within \(\mathcal I\): its upper endpoint is at most \(C\) and at most \(\rho\), since \(A(s)\geq0\). It imposes precisely the additional condition \(A(s)\leq\rho-Q\).
The finite candidate list is sufficient. On each linear piece, \(W(Q)-sQ\) attains its maximum at a piece endpoint; the listed interval endpoints and included breakpoints cover all such possibilities. Singleton intervals are also covered.
The upper-bound argument applies to every admissible manipulation and internal allocation. Each inequality has the correct direction, particularly \(W(Q)-pQ\leq W(Q)-sQ\), which uses \(Q\geq0\).
The attainment argument is also valid. Its constructed utility is at least \(M\), and the previously established universal upper bound makes it at most \(M\). Thus it equals \(M\). Allowing the construction to clear below the candidate price \(s\) causes no gap.
All enumerated quantities are rational. The proof therefore establishes an attained optimum within the required rational domain, rather than merely a supremum over real quantities.
The numbers of candidate prices and quantities are polynomial in \(\tau K\). The schedules are explicitly listed, so sorting their marginals and evaluating the formulas require polynomially many operations.
The bit-length claim is valid for the specific formulas used: cumulative rational sums, weighted values, candidate endpoints, and the single mixing ratio \(Q/C\) have polynomial bit length. The construction permits a polynomial-bit rational \(H\) above all true marginals.
At most two reporting schedules per coalition type are needed. The internal allocation has at most \(\tau(K+1)\) listed masses, each of polynomial bit length. Thus both optimization and witness construction meet the requested polynomial bounds.
No additional lemma, clarification, or repair is needed. The final comparison \(M\geq T\) correctly decides the problem.
⟨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.