Mechanisms for multi-unit auctions (d4-conf-sigecom-2007-0007)

Given finitely many complete \(k\)-minded valuation types \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), and rational per-capita supply \(\rho\), compute an optimal or \((1-\varepsilon)\)-approximate mass allocation \(x_{\theta,q}\ge0\) satisfying \(\sum_q x_{\theta,q}=\mu_\theta\) and \(\sum_{\theta,q}q\,x_{\theta,q}\le\rho\), where each recipient receives an integral bundle \(q\). Determine the exact complexity, finite-\(N\) rounding guarantees, and whether the discrete hardness behind Proposition 4.3 survives.

A society is given by its support: the list of the \(\tau\) types with positive binary-rational masses \(\mu_\theta\), summing to \(1\); \(\tau\) counts supplied types, not possible types.
Let \(m\ge1\) be a binary-encoded integer bounding each recipient’s bundle. Each type supplies its complete valuation through at most \(k\) bids \((q_{\theta j},p_{\theta j})\), with integral \(1\le q_{\theta j}\le m\) and nonnegative binary-rational \(p_{\theta j}\): \(v_\theta(q)=\max(\{0\}\cup\{p_{\theta j}:q_{\theta j}\le q\})\) for \(q\in\{0,\ldots,m\}\).
Given binary-rational supply \(0\le\rho\le m\), a mass allocation has \(x_{\theta,q}\ge0\), \(\sum_{q=0}^m x_{\theta,q}=\mu_\theta\), and \(\sum_{\theta,q}q x_{\theta,q}\le\rho\); its welfare is \(W(x)=\sum_{\theta,q}v_\theta(q)x_{\theta,q}\). Types may be split among integral bundle sizes. Let \(\mathrm{OPT}_\mu=\max_x W(x)\).
For finite-population rounding, take an integer \(N\ge1\) with \(N\mu_\theta\) integral for every type; integer counts \(a_{\theta,q}\ge0\) must satisfy \(\sum_q a_{\theta,q}=N\mu_\theta\) and \(\sum_{\theta,q}q a_{\theta,q}\le\lfloor N\rho\rfloor\), with welfare measured per capita.
State running times in \(m,\tau,k,L\), where \(L\) is the total binary input length, distinguishing polynomial dependence on \(m\) from polynomial dependence on \(\log m\); include \(\varepsilon^{-1}\) and \(N\) when applicable.

Is exact mass-welfare maximization in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For rational \(0<\varepsilon<1\), what is the complexity of obtaining welfare at least \((1-\varepsilon)\mathrm{OPT}_\mu\), and what worst-case per-capita welfare loss can be guaranteed when rounding an optimal mass allocation to the finite population defined above?

For discrete multi-unit auctions, no polynomial-time maximal-in-range algorithm—one optimizing over a valuation-independent allocation range—guarantees a ratio strictly exceeding \(1-1/n\) for \(n\) bidders unless \(\mathrm{P}=\mathrm{NP}\). Unrestricted discrete welfare maximization is \(\mathrm{NP}\)-hard already for single-minded bids, but admits an FPTAS for \(k\)-minded bids. [Source](https://arxiv.org/pdf/1401.3834)
No result settling precisely the mass-allocation formulation above was identified in the literature search.

1. Results

Exact mass-welfare maximization is in \(\mathrm{P}\), with running time polynomial in \(\tau,k,L\) and \(\log(m+1)\). There is no need for polynomial dependence on \(m\).

Consequently, welfare at least \((1-\varepsilon)\mathrm{OPT}_\mu\) can be obtained by computing an exact optimum, with no dependence on \(\varepsilon^{-1}\) beyond reading the approximation parameter.

Define the maximum value of one recipient by
\[ \]
\(P_{\max}:=\max_\theta v_\theta(m)\), taking \(P_{\max}=0\) if all bids have zero value. One can compute an optimal mass allocation and round it to feasible finite-population counts with per-capita welfare \(W_N\) satisfying

\(0\le \mathrm{OPT}_\mu-W_N\le P_{\max}/N.\)

If \(P_{\max}>0\), the upper inequality can be made strict. The coefficient \(1\) is sharp as a supremum. Without bounding bid values, there is no absolute loss bound depending only on \(m,\tau,k,N\).

The proofs follow.

2. Only bid thresholds are needed

For each type \(\theta\), sort its distinct bid quantities, combine bids at equal quantities by taking their maximum price, and compute the running maximum price. Retain only quantities at which this running maximum strictly increases. Include quantity \(0\), with value \(0\), and call the resulting set \(B_\theta\).

Then \(|B_\theta|\le k+1\). For every quantity \(q\in\{0,\ldots,m\}\), there is a quantity \(b\in B_\theta\) such that

\(b\le q\quad\text{and}\quad v_\theta(b)=v_\theta(q).\)

Indeed, if \(v_\theta(q)=0\), take \(b=0\). Otherwise, take the smallest bid threshold at which the value \(v_\theta(q)\) is attained; this threshold is a retained strict increase.

Moving all mass at \(q\) to such a \(b\) preserves welfare and weakly decreases resource consumption. Thus the original problem is exactly equivalent to its restriction to the sets \(B_\theta\).

In particular, it has an exact rational linear-programming formulation with at most \(\tau(k+1)\) variables, \(\tau\) type-mass equalities, and one supply inequality. These variables describe the actual mass allocations, so this is an exact formulation rather than a relaxation.

The next section gives a direct algorithm and the structure needed for rounding.

3. An exact algorithm with at most one split type

3.1 Concavifying one type

Fix a type and consider its retained points \((b,v_\theta(b))\), ordered by quantity. Their values strictly increase after the initial point \((0,0)\).

Construct a polygonal chain by processing these points in order. Whenever three consecutive chain points \(A,B,C\) satisfy

\(\dfrac{v(B)-v(A)}{q(B)-q(A)} \le \dfrac{v(C)-v(B)}{q(C)-q(B)},\)

delete \(B\), repeating until the chain’s slopes strictly decrease.

The displayed inequality says exactly that \(B\) lies on or below the chord from \(A\) to \(C\). Replacing the two segments through \(B\) by that chord therefore raises or preserves the chain everywhere between \(A\) and \(C\). Inductively, the final chain lies above every retained point. Its decreasing slopes make it concave.

Write its vertices as

\((b_{\theta,0},u_{\theta,0}),\ldots,(b_{\theta,r_\theta},u_{\theta,r_\theta}),\)

where \((b_{\theta,0},u_{\theta,0})=(0,0)\). Let \(h_\theta\) be the resulting piecewise-linear function. A type with no positive bids has only the initial vertex.

For any allocation supported on \(B_\theta\), define its mean quantity by

\(z_\theta:=\mu_\theta^{-1}\sum_{q\in B_\theta}q x_{\theta,q}.\)

Because \(h_\theta(q)\ge v_\theta(q)\) at every retained quantity, and \(h_\theta\) is concave, finite Jensen’s inequality gives

\(\sum_{q\in B_\theta}v_\theta(q)x_{\theta,q} \le \sum_{q\in B_\theta}h_\theta(q)x_{\theta,q} \le \mu_\theta h_\theta(z_\theta).\)

Conversely, every point on a chain segment is attained by splitting the type’s mass between that segment’s two endpoint quantities. Thus \(\mu_\theta h_\theta(z_\theta)\) is exactly the best welfare attainable at mean quantity \(z_\theta\).

3.2 Sorting marginal segments

For each chain segment \(i\), define its resource capacity and welfare slope by

\(c_{\theta,i}:=\mu_\theta(b_{\theta,i}-b_{\theta,i-1}),\)

\(s_{\theta,i}:= \dfrac{u_{\theta,i}-u_{\theta,i-1}} {b_{\theta,i}-b_{\theta,i-1}}.\)

All slopes are positive, and within each type they strictly decrease. Consider the continuous knapsack problem

\(\max\sum_{\theta,i}s_{\theta,i}y_{\theta,i}\)

subject to

\(0\le y_{\theta,i}\le c_{\theta,i}, \qquad \sum_{\theta,i}y_{\theta,i}\le\rho.\)

This is an upper bound on mass welfare: for each type, fill its segments consecutively up to total resource use \(\mu_\theta z_\theta\); the resulting segment welfare equals \(\mu_\theta h_\theta(z_\theta)\), which bounds that type’s original welfare.

Solve this knapsack problem by sorting all segments by nonincreasing slope, breaking ties arbitrarily, and filling them until supply is exhausted.

Here is an explicit optimality proof. If every segment is filled, the solution attains the upper bound \(\sum_{\theta,i}s_{\theta,i}c_{\theta,i}\). Otherwise choose a cutoff slope \(\lambda\ge0\) such that filled segments have slope at least \(\lambda\), unfilled segments have slope at most \(\lambda\), and any partially filled segment has slope exactly \(\lambda\). At a boundary between segments, either adjacent slope is a valid choice.

For every feasible \(y\),

\(\sum_{\theta,i}s_{\theta,i}y_{\theta,i} \le \lambda\rho+ \sum_{\theta,i}\max\{s_{\theta,i}-\lambda,0\}c_{\theta,i}.\)

This follows by writing \(s_{\theta,i}=\lambda+(s_{\theta,i}-\lambda)\), using the supply constraint for the first term, and the segment bounds for the second. The greedy solution attains this bound: its total resource use is \(\rho\), and it fills every segment whose slope exceeds \(\lambda\).

Because slopes strictly decrease within each type, the global ordering always fills that type’s segments in their chain order. Hence the greedy solution corresponds to a feasible mass allocation and attains the upper bound on original mass welfare. It is therefore exactly optimal.

3.3 Structure and running time

The greedy procedure partially fills at most one segment. Every other type receives a single chain-vertex quantity.

Consequently, there is an optimal allocation in which every type is concentrated at one quantity, except possibly one type split between two integral quantities. Its support has at most \(\tau+1\) entries.

Let \(B\) be the total number of supplied bids, so \(B\le\tau k\). Sorting bids, constructing the chains, sorting their segments, and scanning them takes

\(O((B+\tau)\log(B+\tau+1))\)

arithmetic and comparison operations.

All calculations can use exact rational arithmetic with bit lengths \(O(L)\). To verify this, segment slopes use differences of input prices and quantities; cumulative resource use is a sum of terms \(\mu_\theta d_\theta\), with integral \(0\le d_\theta\le m\). A common denominator is the product of the input mass denominators and the supply denominator, whose total bit length is \(O(L)\). The single partial segment introduces only an additional integral quantity difference. Welfare calculations likewise admit common denominators of bit length \(O(L)\).

Thus a valid bit-time bound is

\(O((\tau(k+1))\log(\tau(k+1)+1)\operatorname{poly}(L)).\)

In particular, dependence on the bundle bound is polynomial in \(\log(m+1)\), not in \(m\). The output is the compact list of nonzero allocation entries.

4. Approximation complexity

All valuations are nonnegative, so \(\mathrm{OPT}_\mu\ge0\). The exact algorithm therefore returns welfare satisfying

\(\mathrm{OPT}_\mu\ge(1-\varepsilon)\mathrm{OPT}_\mu.\)

If \(E\) is the binary encoding length of \(\varepsilon\), the approximation task has running time

\(O(E)+O((\tau(k+1))\log(\tau(k+1)+1)\operatorname{poly}(L)).\)

This is stronger than an FPTAS: the algorithm is exact, and its running time has no dependence on \(\varepsilon^{-1}\) beyond reading its encoding.

The discrete hardness and mechanism restrictions in the [cited multi-unit-auction paper](https://arxiv.org/pdf/1401.3834) do not transfer to this formulation. Here, a positive mass of one type may be split among different integral bundle sizes, which is precisely what permits the concavification above.

5. Finite-population rounding and sharpness

5.1 Rounding the sparse optimum

Choose the optimal allocation constructed above. Every unsplit type can be implemented exactly: assign all \(N\mu_\theta\) recipients its chosen quantity.

Suppose the exceptional type \(\theta^\ast\) is split between quantities \(a<b\), and let \(x_b\) be its mass receiving \(b\). Put

\(n_\ast:=N\mu_{\theta^\ast},\qquad t:=Nx_b,\qquad r:=t-\lfloor t\rfloor.\)

Assign \(\lfloor t\rfloor\) recipients quantity \(b\), and the remaining \(n_\ast-\lfloor t\rfloor\) recipients quantity \(a\). These counts are nonnegative integers and preserve the type’s population exactly.

Before rounding, this type consumes

\(a n_\ast+(b-a)t\)

items. After rounding, it consumes

\(a n_\ast+(b-a)\lfloor t\rfloor,\)

which is smaller by \(r(b-a)\). Thus total consumption after rounding is an integer no greater than \(N\rho\), and consequently is at most \(\lfloor N\rho\rfloor\).

The exact per-capita welfare loss is

\(\mathrm{OPT}_\mu-W_N = \dfrac{r}{N}\bigl(v_{\theta^\ast}(b)-v_{\theta^\ast}(a)\bigr).\)

Monotonicity and nonnegativity imply

\(0\le v_{\theta^\ast}(b)-v_{\theta^\ast}(a)\le P_{\max}.\)

Since \(0\le r<1\), this proves

\(0\le\mathrm{OPT}_\mu-W_N<P_{\max}/N\)

when \(P_{\max}>0\). If there is no split, or \(P_{\max}=0\), the loss is zero.

Let \(\mathrm{OPT}_N\) denote the best feasible finite-population per-capita welfare. Dividing any feasible integer counts by \(N\) gives a feasible mass allocation. Hence

\(W_N\le\mathrm{OPT}_N\le\mathrm{OPT}_\mu,\)

so the same bound also controls the mass-to-finite optimum gap.

5.2 Sharpness and absence of a uniform relative guarantee

Fix any \(N\). Take one type of mass \(1\), bundle bound \(m=1\), and one bid \((1,P)\), where \(P>0\). Choose a positive binary-rational supply \(\rho<1/N\).

The mass optimum assigns mass \(\rho\) quantity \(1\), giving

\(\mathrm{OPT}_\mu=\rho P>0.\)

But \(\lfloor N\rho\rfloor=0\), so every finite-population allocation has welfare zero.

Binary-rational supplies can approach \(1/N\) from below. Therefore the loss approaches \(P/N=P_{\max}/N\). This proves sharpness as a supremum, even for \(\tau=k=m=1\).

The same example shows that no positive uniform multiplicative ratio relative to \(\mathrm{OPT}_\mu\) is possible for finite-population rounding. Also, allowing \(P\) to grow shows why an absolute loss bound must depend on valuation magnitude.

5.3 Rounding complexity

After the sparse optimum is available, rounding uses \(O(\tau)\) exact arithmetic operations on numbers of bit length \(O(L+\log(N+1))\). Compact integer counts therefore take polynomial time in \(\tau,k,L,\log(m+1),\log(N+1)\).

If the output must list each of the \(N\) recipients individually, writing that expanded output requires at least \(\Omega(N)\) time.

⟨structured verdict parsed — rendered above⟩

The prover resolves all three requested questions. The exact algorithm, polynomial bit complexity, and finite-population rounding bound are correct. No substantive or minor mathematical gaps were found.

• Reduction to retained bid thresholds.

Combining equal quantities, taking running maxima, and retaining only strict increases preserves the valuation information needed for optimization. For every integral quantity \(q\), the stated choice of \(b\le q\) satisfies \(v_\theta(b)=v_\theta(q)\), including the zero-value case.

Moving mass from \(q\) to \(b\) preserves each type’s total mass and welfare while weakly decreasing consumption. Conversely, every allocation supported on the retained quantities is allowed in the original formulation. Thus the equivalence is exact.

The variable bound \(\tau(k+1)\) is valid. The resulting linear program describes mass allocations directly; it does not impose an integrality requirement that would recreate the discrete auction problem.

• Construction of the concave chains.

The deletion criterion is correct: for quantities \(q(A)<q(B)<q(C)\), the displayed comparison of adjacent slopes is equivalent to \(B\) lying on or below the chord joining \(A\) and \(C\).

Replacing the two adjacent segments by that chord weakly raises their values throughout the affected interval. Repeated deletion therefore preserves domination of every processed retained point. The final strictly decreasing slopes establish concavity.

Positive slopes follow because retained values strictly increase with quantity. Removing intermediate vertices preserves this property. A type with no positive bids contributes only the point \((0,0)\), as stated.

• Interpretation of the concave envelope.

Each mass \(\mu_\theta\) is positive, so the definition of \(z_\theta\) is valid. The normalized allocation weights \(x_{\theta,q}/\mu_\theta\) are nonnegative and sum to one. Their quantities lie in the chain’s domain. These are exactly the hypotheses needed for the finite Jensen inequality used in the proof.

Both inequalities are justified: the first uses pointwise domination at retained quantities; the second uses concavity.

The converse attainability claim is also justified as written. A point on a chain segment is a convex combination of its two vertices, which are permitted integral bundle quantities with their actual valuation values. Consequently, the chain value is the attainable maximum welfare at each feasible mean quantity.

• Continuous-knapsack optimality.

The capacities \(c_{\theta,i}\) correctly convert quantity increments into resource consumption for a type of mass \(\mu_\theta\). The slopes \(s_{\theta,i}\) convert those resource increments into welfare increments.

Filling each type’s segments consecutively represents its concave-chain welfare. Hence the unrestricted segment knapsack is an upper bound on mass welfare.

The cutoff inequality is valid: the supply constraint bounds the term with coefficient \(\lambda\ge0\); positive residual coefficients are bounded using segment capacities; negative residual terms can be discarded in an upper bound.

When not all segments are filled, greedy consumes exactly \(\rho\) and attains the stated bound. When all segments are filled, the separate capacity bound establishes optimality. This also covers zero supply, supply equal to total capacity, excess supply, and an empty segment collection.

Strictly decreasing slopes within each type ensure that global sorting respects that type’s segment order, regardless of ties between different types. The greedy upper bound is therefore attained by a feasible mass allocation.

• Sparse optimal allocation.

Sequential greedy filling leaves at most one partially filled segment. Every type without such a segment ends at a chain vertex and can be assigned one bundle quantity. The exceptional type uses the two endpoints of its partial segment.

Thus the claimed support bound of \(\tau+1\) is correct. The rounding argument appropriately chooses this constructed optimum; it does not assume every optimal allocation has this support structure.

• Exact running time and bit complexity.

There are at most \(B\le\tau k\) supplied bids and at most \(B\) positive chain segments. The stated sorting, chain-construction, and scanning operation bound is valid.

The rational-size argument is sound. Differences and ratios of input numbers have bit length \(O(L)\). Products of the relevant input denominators have total bit length \(O(L)\). Cumulative resource quantities introduce only bounded integer factors and sums, and the partial segment introduces one additional quantity difference. Welfare calculations likewise remain within polynomial bit complexity.

The resulting bit-time bound is polynomial in \(\tau,k,L\) and \(\log(m+1)\). It requires no enumeration of all \(m+1\) bundle quantities. The compact output representation is explicitly specified.

• Approximation guarantee.

Since welfare is nonnegative, an exact optimum satisfies the requested multiplicative guarantee for every rational \(0<\varepsilon<1\), including when the optimum is zero.

The separate accounting for the encoding length \(E\) of \(\varepsilon\) is correct. There is no numerical dependence on \(\varepsilon^{-1}\).

• Finite-population feasibility and loss.

Unsplit types are implemented exactly because \(N\mu_\theta\) is integral. For the exceptional type, \(0\le t\le n_\ast\), so both rounded counts are nonnegative integers with the correct total.

The consumption decrease is exactly \(r(b-a)\). Total rounded consumption is an integer bounded by \(N\rho\), hence by \(\lfloor N\rho\rfloor\).

The welfare-loss calculation is correct:
\(\mathrm{OPT}_\mu-W_N=r(v_{\theta^\ast}(b)-v_{\theta^\ast}(a))/N\).
Monotonicity, nonnegativity, and \(r<1\) give the asserted strict bound when \(P_{\max}>0\). The no-split and zero-value cases have zero loss.

Dividing feasible finite counts by \(N\) establishes \(\mathrm{OPT}_N\le\mathrm{OPT}_\mu\), so the same bound controls the optimum gap.

• Sharpness and rounding complexity.

The one-type, one-unit example satisfies the input restrictions when its price and supply are binary rationals. For \(0<\rho<1/N\), finite supply is zero while mass welfare is \(\rho P\). Binary-rational supplies approaching \(1/N\) from below establish sharpness as a supremum.

The same example verifies both the absence of a positive uniform multiplicative rounding guarantee and the need for valuation magnitude in an absolute loss bound.

Compact rounding has polynomial dependence on \(\log(N+1)\), while explicitly listing all recipients requires at least \(\Omega(N)\) output time. These distinctions meet the task’s requirements.

No additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩