Combinatorial auctions with decreasing marginal utilities (d4-conf-sigecom-2001-0031)

Given \(X=\{1,\ldots,m\}\), a finite set \(T\) of complete valuation types, rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), rational item supplies \(b_j\ge 0\), and capped-additive valuations \(v_t(S)=\min\{B_t,\sum_{j\in S}w_{tj}\}\), compute the maximum welfare over configuration masses \(x_{t,S}\ge 0\) satisfying \(\sum_{S\subseteq X}x_{t,S}=\mu_t\) and \(\sum_{t\in T,\;S\ni j}x_{t,S}\le b_j\), where \(W(x)=\sum_{t\in T,S\subseteq X}x_{t,S}v_t(S)\); equivalently, decide whether some feasible \(x\) has \(W(x)\ge K\).

Definitions. Let \(X=\{1,\ldots,m\}\). Each type \(t\in T\) has rational mass \(\mu_t\), budget \(B_t\), and item weights \(w_{tj}\), with \(v_t(S)=\min\{B_t,\sum_{j\in S}w_{tj}\}\). Given rational supplies \(b_j\) and threshold \(K\), choose \(x_{t,S}\ge0\) such that \(\sum_{S\subseteq X}x_{t,S}=\mu_t\) and \(\sum_{t,S\ni j}x_{t,S}\le b_j\). Its welfare is \(W(x)=\sum_{t,S}x_{t,S}v_t(S)\).

Target. Is deciding whether a feasible \(x\) with \(W(x)\ge K\) exists solvable in polynomial time, or is it NP-hard?

Nearest known results. In the discrete indivisible-item setting, welfare maximization is NP-hard even for two budget-additive valuations. This problem instead permits divisible masses of each valuation type and rational item supplies.

The decision problem is \(\mathrm{NP}\)-hard, even with a single valuation type of mass \(1\) and every item supply equal to \(\tfrac12\).

Reduction. We reduce from the standard \(\mathrm{NP}\)-complete problem Partition: given positive integers \(a_1,\ldots,a_m\), encoded in binary, decide whether some subset has sum exactly half their total. Its \(\mathrm{NP}\)-completeness is a classical result of [Karp](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Write \(A=\sum_{j=1}^m a_j\). Construct an instance with one type \(t\), setting

\(\mu_t=1,\qquad w_{tj}=a_j,\qquad B_t=A/2,\qquad b_j=1/2,\qquad K=A/2.\)

These parameters have polynomial encoding length and are computable in polynomial time. Suppress the type index, and write \(B=A/2\), \(a(S)=\sum_{j\in S}a_j\), and \(x_S=x_{t,S}\).

A partition gives a feasible allocation reaching the threshold. Suppose \(S\subseteq X\) satisfies \(a(S)=B\). Its complement also satisfies \(a(X\setminus S)=B\). Assign mass \(\tfrac12\) to each of these two bundles and zero to all other bundles.

The total assigned mass is \(1\). Every item belongs to exactly one of the two bundles, so its consumption is exactly \(\tfrac12\), meeting its supply constraint. Both bundles have value \(B\), hence welfare is \(B=K\).

An allocation reaching the threshold gives a partition. Conversely, suppose a feasible allocation satisfies \(W(x)\ge B\). Since every bundle has value at most \(B\) and \(\sum_S x_S=1\), we have

\(W(x)=\sum_S x_S\min\{B,a(S)\}\le B.\)

Thus \(W(x)=B\). Consequently,

\(\sum_S x_S\bigl(B-\min\{B,a(S)\}\bigr)=0.\)

Every summand is nonnegative. Therefore every bundle with \(x_S>0\) satisfies \(a(S)\ge B\).

On the other hand, the supply constraints and positivity of the weights give

\(\sum_S x_Sa(S)=\sum_{j=1}^m a_j\sum_{S\ni j}x_S\le \sum_{j=1}^m a_j/2=B.\)

Because all positive-mass bundles have weight at least \(B\), their average weight is at least \(B\). The preceding inequality forces that average to equal \(B\). Explicitly,

\(\sum_{S:x_S>0}x_S\bigl(a(S)-B\bigr)=0.\)

Again, every summand is nonnegative, so every positive-mass bundle has weight exactly \(B\). At least one such bundle exists because the total mass is \(1\). It supplies the required partition.

Conclusion. The constructed instance reaches its welfare threshold if and only if the original Partition instance is a yes-instance. This proves \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions, and rules out a polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\). Fractional masses do not remove this obstruction: attaining the threshold forces exact equality in the weight of every bundle used.

⟨structured verdict parsed — rendered above⟩

The proof is correct and fully resolves the target: the decision problem is \(\mathrm{NP}\)-hard, even with one valuation type of mass \(1\) and all supplies equal to \(\tfrac12\). No substantive or minor gaps were found.

• Source problem and applicability. The prover precisely states the version of Partition used: positive integers encoded in binary, with a subset required to have exactly half the total sum. Its classical \(\mathrm{NP}\)-completeness is the appropriate hardness premise; the cited reference is [Karp’s *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). The reduction uses precisely these inputs and imposes no additional promise.

• Construction and encoding size. All constructed parameters satisfy the target’s rational-input requirements. The sum \(A\) has polynomial bit length in the source input size, and division by \(2\) introduces only a constant-size denominator. There are only \(m\) weights and \(m\) supplies to specify. Thus both construction time and output encoding length are polynomial. The exponentially many possible bundles need not be explicitly listed in the instance.

• Forward implication. If \(a(S)=B\), then \(a(X\setminus S)=A-B=B\). Assigning mass \(\tfrac12\) to each bundle gives total mass \(1\). Each item occurs in exactly one bundle, so each supply constraint holds with equality. Both bundle values are \(B\), giving welfare exactly \(K=B\). Every claimed equality is valid.

• Welfare saturation in the reverse implication. Since each bundle value is at most \(B\), nonnegative masses totaling \(1\) imply \(W(x)\le B\). Hence the assumed \(W(x)\ge B\) forces equality. The displayed deficit sum is therefore zero. It is a finite sum of nonnegative terms, so every positive-mass bundle satisfies \(\min\{B,a(S)\}=B\), equivalently \(a(S)\ge B\).

• The supply-based weight bound. The exchange of summations is valid because both index sets are finite. Multiplying each supply constraint by the positive integer \(a_j\) preserves its direction. Summing yields the claimed bound \(\sum_S x_Sa(S)\le A/2=B\). This correctly bounds uncapped bundle weight, rather than just capped welfare.

• Exact equality and extraction. All positive-mass bundles have weight at least \(B\), and their masses total \(1\), so their weighted average is at least \(B\). Combined with the preceding upper bound, this gives equality. The second displayed zero sum consequently consists entirely of nonnegative terms; each positive-mass bundle must have weight exactly \(B\). Such a bundle exists because the total mass is \(1\). This establishes the required Partition witness without any assumption that allocation masses are integral or rational.

• Edge cases and conclusion. Odd \(A\) causes no difficulty: the constructed half-integral budget and threshold are permitted, while the reverse implication would still require an integer subset sum equal to \(A/2\). Single-item instances are also covered. The equivalence proves a polynomial-time many-one reduction to the exact decision problem asked. Neither membership in \(\mathrm{NP}\) nor strong \(\mathrm{NP}\)-hardness is needed or claimed.

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩