d4-conf-aaai-2010-0149 (d4-conf-aaai-2010-0149)

Given population scale \(N\), a finite report domain of single-minded bidder types \(t=(x_t,v_t)\), rational type masses \(\mu_t\), a kernel and penalty parameter \(\lambda\), and per-capita item supplies scaled to \(N\), determine the maximum unilateral incentive regret of the paper’s one-run kernel auction with price-based payments. A report from type \(t\) to \(t'\) changes the distribution by \(\mu' = \mu + \frac{1}{N}(e_{t'}-e_t)\); decide whether the maximum regret is at most \(\eta\), and return a maximizing report or a certificate.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. The explicitly listed report domain \(D\) may also contain zero-mass types; write \(d=|D|\).
There are \(m\) item categories. Each report \(s\in D\) specifies a nonempty bundle \(x_s\in\{0,1\}^m\) and a nonnegative rational value \(v_s\); its single-minded valuation is \(V_s(y)=v_s\mathbf{1}\{y\ge x_s\}\). Input masses satisfy \(\sum_s\mu_s=1\). Input also includes a binary-encoded integer \(N\ge1\), positive rational per-capita supplies \(c\), positive rational \(\lambda\), rational \(\eta\ge0\), and a rational supply tolerance \(0<\delta<1\).
The kernel is supplied through its rational positive-semidefinite Gram matrix \(K_{su}=k(x_s,x_u)\), consistent with a centered feature map \(\phi(0)=0\). Identical bundles have identical kernel rows. Let \(X\) have columns \(x_s\).
For any report distribution \(\nu\), put \(n=N\nu\) and \(F(n)=\{b\in\mathbb{R}_{\ge0}^d:b\le n,\ Xb\le Nc\}\). Fractional mass allocations are permitted. The auction selects the lexicographically smallest optimal pair \((a,b)\) of \(\max_{0\le a\le n,\ b\in F(n)} v^\top a-\frac{1}{2\lambda}(a-b)^\top K(a-b)\), in the listed report order, and computes bundle prices \(p=K(a-b)/\lambda\).
The delivered mass is \(a\). Restrict inputs to those for which this selected allocation satisfies \(Xa\le Nc+\delta\mathbf{1}\) at the truthful distribution and every unilateral report distribution considered below; this is the explicit approximate-feasibility promise.
A tagged bidder reporting \(s\), where \(n_s\ge1\), receives \(x_s\) with probability \(z_s=a_s/n_s\) and nothing otherwise. Its expected price-based payment is \(r_s(\nu)=\max_{b'\in F(n-e_s)}p^\top b'-p^\top(a-z_se_s)\), using the prices from this run, without recomputing them after removal. Here \(e_s\) is the coordinate unit vector.
For a true type \(t\) with \(N\mu_t\ge1\), reporting \(s\in D\) produces \(\nu^{t\to s}=\mu+(e_s-e_t)/N\). Define \(U_t(s)=z_s(\nu^{t\to s})V_t(x_s)-r_s(\nu^{t\to s})\) and \(R=\max_{t:N\mu_t\ge1,\ s\in D}[U_t(s)-U_t(t)]\); assume at least one such true type exists.
Is deciding whether \(R\le\eta\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Measure running times in \(m,\tau,d\) and the total binary input length \(L\), including the encodings of \(N,\lambda,\delta\).
For discrete bidders, the price-based auction has the conditional additive incentive-regret bound \(2(n-1)\kappa^2/\lambda\), where \(k(x,x)\le\kappa^2\), under the assumed efficient allocation and supporting-price conditions; this is not a polynomial-time computation theorem. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/7642/7503).
The literature search located no result addressing exactly the fractional-mass regret problem defined here.

Conclusion. The decision problem is in \(\mathrm{P}\). In fact, the exact rational value of \(R\) can be computed in time polynomial in \(m,\tau,d,L\). The proof accounts for singular Gram matrices, lexicographic tie-breaking, and binary-encoded \(N\).

1. Each auction run is an exactly solvable convex quadratic program

Extend the mass vector to all of \(D\) by assigning zero mass to unrepresented reports. Fix a nonnegative rational vector \(n\) arising from the truthful distribution or a permitted deviation. Define

\[ \]
\(P_n=\{(a,b)\in\mathbb{R}^{2d}:0\le a\le n,\ 0\le b\le n,\ Xb\le Nc\}\).

This polytope is nonempty because it contains \((0,0)\), and it is bounded because both vectors lie between \(0\) and \(n\). Write the auction objective as

\(f(a,b)=v^\top a-\dfrac{1}{2\lambda}(a-b)^\top K(a-b)\).

Minimizing \(-f\) over \(P_n\) is a rational convex quadratic program. Indeed, its quadratic form evaluated on any direction \((h_a,h_b)\) is

\(\dfrac{1}{\lambda}(h_a-h_b)^\top K(h_a-h_b)\ge0\),

using \(K\succeq0\) and \(\lambda>0\).

We use the exact polynomial-time convex quadratic programming theorem: for a rational positive-semidefinite quadratic objective and rational linear constraints, a nonempty bounded feasible polyhedron admits an exact rational optimizer computable in time polynomial in the binary input length. This theorem allows a singular quadratic matrix and does not require the feasible set to have interior. See [Kozlov, Tarasov, and Khachiyan, *The polynomial solvability of convex quadratic programming*](https://www.mathnet.ru/eng/zvmmf5189). Rational data can be converted to integer data by clearing denominators, with polynomial growth in encoding length.

Consequently, we can compute one exact optimizer \((a^0,b^0)\) of polynomial encoding length. This alone does not implement the prescribed tie-breaking; the next step does.

2. The entire optimal set has a rational polyhedral description

Set \(q^0=a^0-b^0\). We claim that the set of auction optimizers is exactly

\(\Omega_n=\{(a,b)\in P_n:K(a-b)=Kq^0,\ v^\top a=v^\top a^0\}\).

To prove necessity, let \((a,b)\) be any optimizer and put \(q=a-b\). Convexity of \(P_n\) makes the midpoint feasible. Direct expansion gives

\(f\left(\dfrac{a+a^0}{2},\dfrac{b+b^0}{2}\right)=\dfrac{f(a,b)+f(a^0,b^0)}{2}+\dfrac{1}{8\lambda}(q-q^0)^\top K(q-q^0)\).

Both endpoint objectives equal the maximum. The midpoint cannot have a larger objective, while the last term is nonnegative. Therefore

\((q-q^0)^\top K(q-q^0)=0\).

For a real symmetric positive-semidefinite matrix, \(h^\top Kh=0\) implies \(Kh=0\): diagonalizing \(K\), every component along an eigenvector with positive eigenvalue must vanish. Thus \(K(q-q^0)=0\).

It follows that the quadratic penalties agree, since

\(q^\top Kq=(q^0)^\top Kq^0+2(q^0)^\top K(q-q^0)+(q-q^0)^\top K(q-q^0)=(q^0)^\top Kq^0\).

Equality of the optimal objectives now implies \(v^\top a=v^\top a^0\). This proves necessity.

Conversely, if a feasible pair satisfies both displayed linear equalities, then \(K(q-q^0)=0\), so its quadratic penalty agrees with that of the known optimizer. Its linear objective also agrees. It is therefore optimal, proving the claim.

In particular, \(\Omega_n\) is a nonempty bounded rational polytope with a polynomial-length description. All its points produce the same price vector, although their delivered allocations may differ.

3. Lexicographic selection is polynomial-time

List the \(2d\) coordinates in the auction’s prescribed lexicographic order as \(y_1,\ldots,y_{2d}\). Starting with \(\Omega_n\), minimize \(y_1\) by exact linear programming and retain the equality fixing it to its minimum. Then minimize \(y_2\) over the retained set, and continue.

At every stage, the remaining set is a nonempty face of the preceding polytope. After all coordinates have been fixed, exactly one point remains. By construction, this is the lexicographically smallest auction optimizer.

We must also control the encoding lengths of the coordinate minima. Each retained set is a face of the original \(\Omega_n\); its vertices are therefore vertices of \(\Omega_n\). Each coordinate minimum is attained at such a vertex.

For completeness, vertices of a rational polytope have polynomial encoding length in its explicit description. Clear denominators in each constraint. If the resulting integer coefficients have at most \(B\) bits, a vertex in \(2d\) dimensions is determined by \(2d\) independent binding equations. Cramer’s rule expresses every coordinate as a ratio of determinants. Each determinant has magnitude at most

\((2d)!\,2^{2dB}\),

so its encoding length is \(O(dB+d\log d)\). This argument also covers lower-dimensional polytopes, using their binding equality constraints.

Here \(B\) is polynomial in the original input length and dimensions. Hence every coordinate minimum introduced during lexicographic selection has a uniform polynomial encoding bound. There is no repeated growth beyond this bound.

Thus one auction run, including its exact selected pair and prices, requires one convex quadratic program, at most \(2d\) linear programs, and polynomial-time rational arithmetic.

4. Each payment and utility is exactly computable

Suppose the tagged report is \(s\), with \(n_s\ge1\). From the selected allocation compute

\(z_s=\dfrac{a_s}{n_s}\), \(\qquad p=\dfrac{K(a-b)}{\lambda}\).

These are exact rational quantities of polynomial encoding length.

The removal vector \(n-e_s\) is nonnegative. Therefore the payment optimization

\(H_s(n,p)=\max\{p^\top b':0\le b'\le n-e_s,\ Xb'\le Nc\}\)

is a rational linear program with a nonempty bounded feasible set. Exact polynomial-time linear programming computes its optimal value. The required payment is then

\(r_s=H_s(n,p)-p^\top(a-z_se_s)\).

This uses the price vector from the original run, exactly as specified in the task.

For a true type \(t\), determine whether \(x_s\ge x_t\) by inspecting the \(m\) coordinates. Its utility is consequently the exactly computable rational number

\(U_t(s)=z_s v_t\mathbf{1}\{x_s\ge x_t\}-r_s\).

5. Enumerating deviations and deciding the threshold

Let

\(T=\{t\in D:N\mu_t\ge1\}\).

Membership is decidable by exact rational comparison. Every member has positive mass, so \(|T|\le\tau\). By hypothesis, \(T\) is nonempty.

First compute the selected truthful allocation at \(n^0=N\mu\), and compute \(U_t(t)\) for each \(t\in T\).

For every \((t,s)\in T\times D\), form

\(n^{t\to s}=N\mu+e_s-e_t\).

This vector is nonnegative: when \(s\ne t\), the only decreased coordinate is \(t\), whose truthful count is at least \(1\); when \(s=t\), the vector is unchanged. Moreover, its tagged coordinate satisfies \(n^{t\to s}_s\ge1\). Hence every run and payment computation above applies.

Compute \(U_t(s)\) using that run, and then take the finite maximum

\(R=\max_{t\in T,\ s\in D}\bigl(U_t(s)-U_t(t)\bigr)\).

There are at most \(\tau d\) pairs. One exact rational comparison of the resulting \(R\) with \(\eta\) decides the question, including equality.

All constructed numerical data have polynomial encoding length. In particular, forming \(N\mu\), \(Nc\), or dividing by \(\lambda\) depends polynomially on their binary encodings; the algorithm never expands the population into \(N\) individual bidders. The total number of optimization calls is polynomial: at most \(1+\tau d\) quadratic programs and \(2d(1+\tau d)+\tau+\tau d\) linear programs.

The approximate-feasibility promise is not needed by this algorithm. On promised inputs, the computed allocations satisfy it, but it does not change the optimization problems being solved. No precision parameter depending on the numerical value of \(\delta\) is required.

Thus the promised decision problem belongs to \(\mathrm{P}\). An \(\mathrm{NP}\)-hardness result under polynomial-time many-one reductions would therefore imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s conclusion is correct: the promised decision problem is in \(\mathrm{P}\), and the argument establishes polynomial-time computation of the exact rational regret \(R\). I found no major or minor mathematical issues.

• The auction optimization is formulated correctly.

The polytope \(P_n\) reproduces exactly the constraints on \(a\) and \(b\) in the task. For every nonnegative \(n\), it contains \((0,0)\), is closed, and is bounded. Thus the continuous objective attains its optimum.

The Hessian of the minimized objective \(-f\) has directional quadratic form
\[ \frac{1}{\lambda}(h_a-h_b)^\top K(h_a-h_b). \]
This is nonnegative because \(K\) is symmetric positive semidefinite and \(\lambda>0\). All coefficients and constraints are rational. Singular matrices and zero coordinates of \(n\) do not invalidate this formulation.

• The exact quadratic-programming theorem applies as stated.

The cited theorem supplies exact polynomial-time optimization, rather than merely an approximation guarantee. The original paper treats integer symmetric positive-semidefinite quadratic objectives under linear inequalities, explicitly includes exact recovery of an optimizer, and imposes neither positive definiteness nor an interior-point hypothesis. These features support the prover’s invocation. [Kozlov–Tarasov–Khachiyan, original paper](https://www.mathnet.ru/php/getFT.phtml?jrnid=zvmmf&option_lang=eng&paperid=5189&what=fullt).

Clearing denominators preserves the feasible set and, when the objective is multiplied by a positive common denominator, preserves its minimizers and convexity. The common denominators have polynomial binary length. Consequently, the theorem applies to the rational program constructed here and yields an exact optimizer of polynomial encoding length.

• The characterization of the complete optimal set is correct.

The midpoint identity has the correct sign and coefficient:
\[ f\left(\frac{a+a^0}{2},\frac{b+b^0}{2}\right) = \frac{f(a,b)+f(a^0,b^0)}{2} + \frac{1}{8\lambda}(q-q^0)^\top K(q-q^0). \]
If both endpoints are optimal, their feasible midpoint cannot improve the maximum. Positive semidefiniteness therefore forces the final quadratic term to vanish.

The implication from \(h^\top Kh=0\) to \(Kh=0\) is valid for a symmetric positive-semidefinite matrix, including singular matrices. The prover supplies an adequate spectral justification.

Once \(K(q-q^0)=0\), the displayed expansion correctly establishes equality of the quadratic penalties. Equality of optimal objective values then forces equality of \(v^\top a\).

Conversely, the two stated linear equalities guarantee equality of both objective terms with those of the known optimizer. Thus \(\Omega_n\) is exactly the optimal set. Its rational description has polynomial length, and the assertion that every optimizer produces the same prices follows directly from \(Kq=Kq^0\).

• The lexicographic procedure implements the required selection.

Successively minimizing each prescribed coordinate and fixing its minimum is the definition of lexicographic minimization over this compact optimal set. Each stage remains nonempty and bounded. After all \(2d\) coordinates are fixed, there is exactly one point.

The encoding argument also holds. Each successive minimizing set is a face of the preceding polytope and hence a face of \(\Omega_n\). Its vertices are vertices of \(\Omega_n\), so every coordinate minimum is attained at an original vertex.

At a vertex, \(2d\) independent binding constraints determine the coordinates, including when the polytope is lower dimensional. With integer coefficients and right-hand sides bounded in magnitude by \(2^B\), the determinant bound
\[ (2d)!\,2^{2dB} \]
is valid for both denominator and numerator determinants. Its binary length is \(O(dB+d\log d)\). Accordingly, the sequential equalities have uniformly polynomial encoding length; the procedure does not suffer uncontrolled growth across stages.

• Payments and utilities match the task exactly.

Whenever \(n_s\ge1\), the denominator defining \(z_s=a_s/n_s\) is positive. Moreover, \(0\le a_s\le n_s\) ensures \(0\le z_s\le1\).

The removal vector \(n-e_s\) is nonnegative. The payment linear program therefore contains the zero allocation and is bounded by its coordinate upper bounds. Its coefficients are rational with polynomial encoding length, so exact polynomial-time linear programming applies. No sign restriction on \(p\) is required.

The formula for \(r_s\) uses the prices from the original auction run, as required, and does not recompute prices after removal. The containment test \(x_s\ge x_t\) correctly evaluates the single-minded valuation, including its zero case. Thus the utility computation agrees with the specified \(U_t(s)\).

• All eligible types and deviations are covered.

Membership in \(T\) is checked exactly. Since \(N\mu_t\ge1\) implies positive mass, \(|T|\le\tau\), and the task guarantees that \(T\) is nonempty.

For \(s\ne t\), only coordinate \(t\) decreases, and its initial count is at least one. Coordinate \(s\) increases by one, so the tagged report has count at least one. For \(s=t\), the distribution remains truthful and the same count condition holds. Hence every enumerated auction and payment satisfies the required domain restrictions.

The truthful utilities are computed using the truthful distribution, which is precisely the distribution defining \(U_t(t)\). The finite maximum therefore equals the task’s \(R\). Reports \(s=t\) also ensure that the maximum includes zero regret. Exact comparison with \(\eta\) handles equality correctly.

• The complexity accounting and treatment of the promise are sound.

The stated bounds of at most \(1+\tau d\) quadratic programs and
\[ 2d(1+\tau d)+\tau+\tau d \]
linear programs correctly count the described operations.

Multiplication by binary-encoded \(N\), scaling by \(\lambda\), matrix products, and rational utility calculations preserve polynomial encoding length. The algorithm never enumerates individual bidders.

The approximate-feasibility promise concerns the selected outputs and introduces no additional optimization constraint. Computing the specified quantities without using \(\delta\) is therefore legitimate on promised inputs. Neither verification of that promise nor the discrete incentive-regret bound is needed to establish the claimed algorithm.

The output resolves the assigned question. No additional clarification or mathematical repair is needed.

⟨structured verdict parsed — rendered above⟩