Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (aaai25-33482)

Given rational masses over a finite set of complete bidder valuation and behavior types, proportional item capacities, a polyhedral competitor space, and acceptable overcharge \(\kappa\), define the unit-bidder first-order limit of unnormalised welfare for a capacity-scaled residual market with one distinguished competitor \(e\). Compute \(e_\kappa\) in the competitor space whose scaled welfare equals \(\kappa\) plus the minimum scaled welfare, and output its induced \(f\)-VCG price.

A residual society is given by its support: \(\tau\) complete bidder valuation and behavior types with positive binary-rational masses \(q_t\), where \(\sum_t q_t=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m\geq1\) item categories with positive rational capacities \(c_j\).
Each valuation \(v_t\) is an explicit table on all \(d=2^m\) bundles, with nonnegative rational entries, free disposal, and \(v_t(\varnothing)=0\). Each bidder receives at most one bundle; items may remain unsold.
For capacity vector \(b\geq0\), define background welfare \(W(b)=\max\{\sum_{t,S}x_{t,S}v_t(S):x_{t,S}\geq0,\ \sum_Sx_{t,S}\leq q_t,\ \sum_{t,S:j\in S}x_{t,S}\leq b_j\}\). Thus background masses may split among bundles.
The distinguished bidder has a revealed rational valuation \(v\) in a nonempty compact rational polytope \(C\), given by \(r\) inequalities; every vector in \(C\) is a nonnegative free-disposal valuation with empty-bundle value zero. A rational \(\kappa\geq0\) is acceptable: every relevant bidder behavior type accepts an overcharge of exactly \(\kappa\) at every nonempty-bundle bid.
At scale \(N\), background masses and capacities are \(Nq_t\) and \(Nc_j\), while the distinguished bidder receives one whole bundle. For sufficiently large integers \(N\), let \(T_N(e)=\max_{S\subseteq[m]}\{e(S)+N W(c-\mathbf1_S/N)\}\), where \(\mathbf1_S\) is the bundle incidence vector.
Define unit-bidder first-order welfare by \(H(e)=\lim_{N\to\infty}[T_N(e)-N W(c)]\), and bundle-specific background change by \(D(S)=\lim_{N\to\infty}N[W(c-\mathbf1_S/N)-W(c)]\).
Fix lexicographic tie-breaking and let \(S_v\) maximize \(v(S)+D(S)\). The induced limiting \(f\)-VCG price is \(p_e(v)=H(e)-H(v)+v(S_v)\); the competitor changes the price, while the allocation uses the revealed valuation.
Promise that some \(e_\kappa\in C\) satisfies \(H(e_\kappa)=\kappa+\min_{e\in C}H(e)\).

Is exact computation of such an \(e_\kappa\) and its induced price polynomial-time in \(m,\tau,d,r,L\), where \(L\) is the total binary input length, or is this promised problem NP-hard?

For finite bidders, a competitor with welfare equal to minimum welfare plus \(\kappa\) can be computed using polynomially many winner-determination oracle calls and additional polynomial time; this is an oracle-relative guarantee. [Balcan, Prasad, and Sandholm](https://sid-prasad.github.io/papers/aaai-25.pdf).
No result settling this precisely specified first-order mass problem was located.

Exact polynomial-time computation

The promised problem is polynomial-time solvable in \(m,\tau,d,r,L\). The proof gives an exact rational algorithm using at most \(2d+2\) linear-programming calls.

1. The background dual and its optimal face

Write \(p(S)=\sum_{j\in S}p_j\). Define the background dual feasible polyhedron
\[ Q=\left\{(\alpha,p)\in\mathbb R_{\geq0}^{\tau+m}: \alpha_t+p(S)\geq v_t(S)\text{ for every }t,S\right\}. \]
For every nonnegative capacity vector \(b\), linear-programming duality gives
\[ W(b)=\min_{(\alpha,p)\in Q} \left(\sum_t q_t\alpha_t+\sum_j b_jp_j\right). \]

The hypotheses for duality hold: the primal is feasible by taking all allocations zero, and it is bounded because \(0\leq x_{t,S}\leq q_t\). The dual is feasible, for example with \(p=0\) and \(\alpha_t=\max_S v_t(S)\).

Let \(w=W(c)\), and define
\[ F=\left\{(\alpha,p)\in Q: \sum_tq_t\alpha_t+\sum_jc_jp_j=w\right\}. \]
This is a nonempty compact optimal face. Indeed, nonnegativity and the strict positivity of every \(q_t,c_j\) imply
\[ 0\leq\alpha_t\leq \frac{w}{q_t}, \qquad 0\leq p_j\leq\frac{w}{c_j}. \]

We will prove that
\[ \boxed{D(S)=-\max_{(\alpha,p)\in F}p(S).} \]

2. Exact first-order background changes

Fix a bundle \(S\), and put
\[ M_S=\max_{(\alpha,p)\in F}p(S). \]
The maximum exists by compactness.

Let \(V\) be the set of vertices of \(Q\). This set is finite: each vertex is uniquely specified by a choice of linearly independent tight constraints from the finite defining system.

For sufficiently small \(\varepsilon>0\), every coordinate of \(c-\varepsilon\mathbf1_S\) is positive. Consequently, the dual objective at this capacity vector has compact sublevel sets within \(Q\): all variables are nonnegative and all objective coefficients are strictly positive. Its optimal face is therefore compact and contains a vertex of \(Q\). Hence
\[ W(c-\varepsilon\mathbf1_S) = \min_{u=(\alpha^u,p^u)\in V} \left(\sum_tq_t\alpha_t^u+\sum_jc_jp_j^u-\varepsilon p^u(S)\right). \]

Let \(V_0\) consist of the vertices optimal at \(c\). Because \(F\) is a compact face of \(Q\), its vertices belong to \(V_0\), and maximizing \(p(S)\) over \(F\) attains its maximum at such a vertex. Thus
\[ \min_{u\in V_0} \left(w-\varepsilon p^u(S)\right)=w-\varepsilon M_S. \]

For each \(u\in V\setminus V_0\), define its strictly positive objective gap
\[ \gamma_u=\sum_tq_t\alpha_t^u+\sum_jc_jp_j^u-w>0. \]
Its perturbed objective exceeds \(w-\varepsilon M_S\) by
\[ \gamma_u-\varepsilon\bigl(p^u(S)-M_S\bigr). \]
If \(p^u(S)\leq M_S\), this expression is positive for every positive \(\varepsilon\). Otherwise, it is positive whenever
\[ \varepsilon<\frac{\gamma_u}{p^u(S)-M_S}. \]
There are only finitely many vertices, so all these conditions hold simultaneously for sufficiently small positive \(\varepsilon\). Therefore,
\[ W(c-\varepsilon\mathbf1_S)=w-\varepsilon M_S \]
throughout a sufficiently small interval.

Taking \(\varepsilon=1/N\) proves that the defining limit exists and that
\[ D(S)=-M_S. \]
In particular, \(D(\varnothing)=0\).

This proof uses vertices only to establish the limit; the algorithm does not enumerate them.

3. Computing every background change and \(H\)

First compute \(w\) by solving the given background welfare LP. For each bundle \(S\), compute \(D(S)\) using the rational LP
\[ \begin{aligned} \text{maximize}\quad &\sum_{j\in S}p_j\\ \text{subject to}\quad &(\alpha,p)\in Q,\\ &\sum_tq_t\alpha_t+\sum_jc_jp_j=w. \end{aligned} \]
Negate the resulting optimum.

Each of these LPs is feasible and bounded because its feasible set is \(F\).

There are finitely many bundles, so the small-perturbation identities from Section 2 hold simultaneously for all bundles once \(N\) is sufficiently large. For every valuation \(e\), it follows that
\[ \begin{aligned} T_N(e)-Nw &=\max_S\left\{e(S)+N\bigl[W(c-\mathbf1_S/N)-w\bigr]\right\}\\ &=\max_S\{e(S)+D(S)\}. \end{aligned} \]
Thus the unit-bidder limit also exists, with
\[ \boxed{H(e)=\max_S\{e(S)+D(S)\}.} \]

4. Finding a competitor at the promised level

Represent the given polytope as \(C=\{e:Ae\leq a\}\). Compute its minimum first-order welfare by the epigraph LP
\[ \begin{aligned} \text{minimize}\quad &h\\ \text{subject to}\quad &Ae\leq a,\\ &e(S)+D(S)\leq h\qquad\text{for every bundle }S. \end{aligned} \]
Its optimum is exactly
\[ h_{\min}=\min_{e\in C}H(e). \]
Indeed, for each fixed \(e\), the smallest feasible \(h\) is \(H(e)\). The minimum exists because \(C\) is nonempty and compact and \(H\) is continuous.

Set \(z=h_{\min}+\kappa\). For each bundle \(T\), solve the linear feasibility problem
\[ \begin{aligned} &Ae\leq a,\\ &e(S)+D(S)\leq z\qquad\text{for every bundle }S,\\ &e(T)+D(T)=z. \end{aligned} \]

Every feasible solution to any of these systems satisfies \(H(e)=z\): the inequalities give \(H(e)\leq z\), while the equality gives \(H(e)\geq z\).

Conversely, if \(e\in C\) satisfies \(H(e)=z\), at least one bundle \(T\) attains the finite maximum defining \(H(e)\). That \(e\) satisfies the corresponding feasibility system. Consequently,
\[ \{e\in C:H(e)=z\} = \bigcup_T \left\{e\in C: e(S)+D(S)\leq z\ \text{for all }S,\ e(T)+D(T)=z\right\}. \]
The promise ensures that this union is nonempty. Solving at most \(d\) feasibility LPs therefore produces an exact rational \(e_\kappa\).

5. Computing the allocation and price

Scan all bundles and select the prescribed lexicographic maximizer
\[ S_v\in\arg\max_S\{v(S)+D(S)\}. \]
All comparisons are between exact rational numbers.

Since \(H(v)=v(S_v)+D(S_v)\), the required price is
\[ \begin{aligned} p_{e_\kappa}(v) &=H(e_\kappa)-H(v)+v(S_v)\\ &=\boxed{h_{\min}+\kappa-D(S_v)}. \end{aligned} \]
In particular, all competitors at the promised welfare level induce the same price.

6. Binary complexity

The background primal has \(\tau d\) variables and \(\tau+m\) resource constraints. Each LP computing \(D(S)\) has \(\tau+m\) variables and at most \(\tau d+\tau+m+2\) inequalities when its equality is encoded as two inequalities. The minimum-welfare LP has \(d+1\) variables and \(r+d\) inequalities. Each target-level feasibility LP has \(d\) variables and \(r+d+2\) inequalities.

We use the standard rational linear-programming theorem: feasibility and bounded optimization can be solved exactly in time polynomial in the binary description length, with polynomial-length rational outputs. The rational encoding bounds and polynomial-time LP algorithms are presented in [Goemans’s linear-programming notes, Sections 11–13](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).

All initial LP coefficients have polynomial encoding length in the given input. The computed value \(w\), then the values \(D(S)\), and finally \(h_{\min}\) have polynomial encoding length by that theorem. Consequently, every subsequent LP also has polynomial description length. All stated feasibility and boundedness hypotheses have been verified above.

The algorithm makes one background optimization call, at most \(d\) derivative calls, one minimum-welfare call, and at most \(d\) target-level feasibility calls. Its remaining work consists of constructing these systems and performing polynomially many rational operations.

Enumerating the \(d=2^m\) bundles is permitted by the requested complexity bound and by their explicit representation in the input. Thus this is an exact polynomial-time algorithm for the specified promised problem.

⟨structured verdict parsed — rendered above⟩

Verdict: proved. The output establishes an exact polynomial-time algorithm for the specified promised problem. No major or minor mathematical issues were found.

• Background dual and optimal face.

The dual is correctly derived: the type-mass constraints produce the nonnegative variables \(\alpha_t\), and the capacity constraints produce the nonnegative variables \(p_j\). Its bundle constraints are exactly \(\alpha_t+p(S)\geq v_t(S)\).

The stated strong-duality hypotheses hold. The primal is nonempty and bounded, and the displayed dual feasible point is valid. Consequently, the dual optimum is attained and equals \(W(b)\).

The optimal face \(F\) is nonempty and closed. Its coordinate bounds follow from nonnegativity and strict positivity of every objective coefficient \(q_t,c_j\). Thus compactness is correctly established, including when \(w=0\).

• First-order background change.

The vertex argument is valid. A polyhedron given by finitely many inequalities has finitely many vertices, since each vertex is determined by a full-rank collection of tight constraints.

For sufficiently small positive \(\varepsilon\), all perturbed capacity coefficients remain strictly positive. Together with \(q_t>0\), this gives compact nonempty objective sublevel sets and an attained optimum. The compact optimal face has a vertex, and a vertex of that face is a vertex of \(Q\). Therefore, minimizing over \(V\) is justified.

Maximizing \(p(S)\) over the compact face \(F\) attains its maximum at a vertex belonging to \(V_0\). The comparison with every nonoptimal vertex is computed correctly:
\[ \gamma_u-\varepsilon\bigl(p^u(S)-M_S\bigr). \]
The two sign cases are exhaustive. Finiteness of \(V\) gives a common positive interval on which no nonoptimal vertex wins. Hence the claimed local identity and limit
\[ D(S)=-M_S \]
follow. This also correctly covers the empty bundle. No enumeration of vertices or computation of the perturbation threshold is required by the algorithm.

• Computation of \(D\) and existence of \(H\).

Each derivative LP optimizes exactly over \(F\), so its negated optimum is the established value \(D(S)\).

There are finitely many bundles. The bundle-specific perturbation intervals can therefore be made simultaneous. Their thresholds depend only on the background problem, so the displayed identity for \(T_N(e)-Nw\) holds for every fixed valuation \(e\) once \(N\) is sufficiently large. The conclusion
\[ H(e)=\max_S\{e(S)+D(S)\} \]
is justified.

• Minimum welfare and the promised competitor.

The epigraph LP correctly computes \(\min_{e\in C}H(e)\). It is feasible, its objective is bounded below, and its optimum is attained because \(C\) is nonempty and compact and \(H\) is continuous. Unboundedness of the epigraph in the upward \(h\) direction does not obstruct bounded optimization.

The target-level systems are correct in both directions. Their inequalities impose \(H(e)\leq z\), and their selected equality imposes \(H(e)\geq z\). Conversely, any valuation satisfying \(H(e)=z\) has an attaining bundle because the maximum is finite.

Thus the union identity is exact. The promise guarantees feasibility of at least one system, and rational LP feasibility produces an exact rational competitor. The argument also covers \(\kappa=0\), lower-dimensional \(C\), and an attaining empty bundle.

• Allocation and price.

Scanning the explicit bundle table implements the prescribed lexicographic tie-breaking using exact rational comparisons. The selected bundle satisfies
\[ H(v)=v(S_v)+D(S_v). \]
Substitution into the task’s price definition gives exactly
\[ p_{e_\kappa}(v)=h_{\min}+\kappa-D(S_v). \]
The sign is correct, and independence from the particular competitor at this welfare level follows.

• Exact binary complexity.

The invoked theorem is appropriate: rational LP feasibility and finite optimization admit polynomial-time exact algorithms with polynomial-length rational witnesses and optimal outputs. The prover verifies the required feasibility and bounded-objective conditions; individual target systems may be infeasible, which the feasibility algorithm handles.

The cited notes discuss rational input encoding, polynomial-size vertex representations, polynomial-time LP algorithms, and recovery of exact optima in Sections 11–13. [Goemans’s linear-programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).

The stated LP dimensions and constraint counts are correct under the indicated conventions. Polynomial encoding length is preserved through the successive computations of \(w\), \(D(S)\), and \(h_{\min}\). Constructing \(z\), finding the competitor, and calculating its price preserve this bound.

The call count is at most \(2d+2\). Enumerating all bundles is permitted because the requested running time is polynomial in \(d\), and valuations are explicitly represented on those bundles. This establishes polynomial time for the specified representation.

Repair feedback: None required. The proof resolves both exact competitor computation and its induced price.

⟨structured verdict parsed — rendered above⟩