| paper | Combinatorial auctions with decreasing marginal utilities |
| authors | B. Lehmann, D. Lehmann, Noam Nisan |
| venue | SIGECOM 2001 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even for one valuation type and all item supplies equal to \(\tfrac12\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
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\).
A high-multiplicity combinatorial auction with \(\tau\) valuation types carrying masses \(\mu_t\), integral bundles \(S\subseteq X\) assigned to each unit of mass, per-capita item capacities \(b_j\), configuration variables \(x_{t,S}\), and total-welfare objective \(\sum_{t,S}x_{t,S}v_t(S)\).
The mirror covers the allocation results in Theorems 9 and 10. It leaves the structural hierarchy and measure results, the greedy approximation in Theorem 11, false-name bidding in Theorem 12, bounded complementarities in Theorem 13, and other strategic examples unmirrored.
I think this paper supports a serious continuous mirror, with Theorem 10 as the strongest anchor and Theorem 9 as a complementary tractable case.
My lead problem is Continuous High-Multiplicity Capped Welfare. Let \(X=\{1,\ldots,m\}\) be non-identical item types. There is a finite set of valuation types \(t\in T\), with population masses \(\mu_t\) summing to \(1\). A type is a complete valuation description, including its item weights and budget cap. In the anchored restriction,
\[ v_t(S)=\min\left\{B_t,\sum_{j\in S}w_{tj}\right\}, \]
with ordinary additive valuations represented by an unlimited cap. Item \(j\) has available mass \(b_j\), interpreted as \(B_j/N\) copies in a finite market of \(N\) agents.
A solution is a configuration measure \(x_{t,S}\ge 0\): \(x_{t,S}\) is the mass of type-\(t\) agents receiving the integral bundle \(S\). It must satisfy \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:j\in S}x_{t,S}\le b_j\). Its welfare is
\[ W(x)=\sum_{t,S}x_{t,S}v_t(S). \]
The decision question is whether some feasible \(x\) has \(W(x)\ge K\); the optimization version asks for maximum welfare and an attaining mass allocation. Individuals still receive whole bundles. Only the population of identical agents is continuous.
This is a natural high-multiplicity regime for spectrum licences, cloud-resource bundles, or procurement markets: millions of small buyers belong to a few standardized demand classes, while the number \(m\) of non-identical item categories may be substantial. If all data are rational, clearing denominators converts the instance into a finite auction with repeated valuation types, and every finite repeated-type auction normalizes back to such an instance.
The anchor is Theorem 10, proved in this paper by reduction from the exact-sum Knapsack problem. It states that finding an optimal allocation in a combinatorial auction with only two valuations, both additive with budget limits, is NP-hard. The reduction uses item weights \(a_1,\ldots,a_m\) and target \(t\). One bidder has additive value \(v_1(S)=\sum_{i\in S}a_i\); the other has capped value \(v_2(S)=2\min(t,\sum_{i\in S}a_i)\). Writing \(f=\sum_i a_i\), an allocation giving \(S\) to the capped bidder and \(S^c\) to the additive bidder has value \(f+t\) exactly when \(\sum_{i\in S}a_i=t\); allocations with sum below or above \(t\) have strictly smaller value. Thus exact welfare optimization is NP-hard even with two succinctly represented submodular valuations.
The continuous question is whether this item-combinatorial hardness survives when the two valuation profiles are represented by large masses of identical agents and item supplies scale with population. My expectation is provisionally Class B: the reduction’s combinatorics live in the \(m\) non-identical items and the budget cap, not in the identities of the two bidders. The relevant pricing problem for the configuration LP asks for a bundle maximizing \(v_t(S)-\sum_{j\in S}p_j\), and for capped additive valuations this can itself encode a threshold subset problem.
This is not a claim that Theorem 10 already proves the continuous hardness result. Atomless mass can split identical agents across different bundles, so the original two-agent reduction does not automatically embed. That is the main technical test: determine whether repeated capped types retain the subset-sum obstruction or whether mass splitting makes the problem tractable. Either outcome would be a meaningful continuization of the paper’s central allocation result.
The second problem is Continuous Gross-Substitutes Welfare, anchored in Theorem 9, which is stated and justified in the paper using earlier Kelso–Crawford, LP, demand-oracle, and discrete-convexity machinery. The theorem says that an optimal allocation among gross-substitutes valuations can be found in polynomial time when the valuations themselves can be computed in polynomial time.
The continuous version uses the same \(x_{t,S}\) formulation, but restricts every valuation type to gross substitutes. Its exact question is to compute a welfare-maximizing configuration measure. The configuration LP has exponentially many bundle variables but only \(\tau+m\) meaningful constraint families. Its dual assigns a price \(p_j\) to each item and asks, for each type, whether some bundle maximizes
\[ v_t(S)-\sum_{j\in S}p_j. \]
That is precisely the demand/pricing problem used in the paper’s finite algorithm. With \(\tau\) explicitly supplied types, population masses merely weight the dual objective; they do not introduce \(N\) separate bidders. I therefore expect this mirror to be Class A, solvable in time polynomial in \(m\), \(\tau\), and the encoding length, assuming polynomial-time demand computation.
The authors should recognize both questions as their allocation problem rather than as a different outcome-space relaxation: the valuation classes, integral bundles, item capacities, welfare objective, and allocation structure are unchanged. What changes is that the society is supplied as a distribution over repeated valuation types, and the algorithm must exploit that high multiplicity.
The weakest point is the hardness anchor. The paper’s NP-hardness uses two named bidders, whereas a genuine continuum permits a type’s mass to be divided among many bundles. It is therefore possible that the continuous capped-welfare problem becomes a tractable configuration LP, making the result Class A rather than Class B. That does not undermine the mirror; it identifies exactly what the continuization is meant to discover. The follow-up questions are whether capped additive types admit polynomial pricing, whether hardness returns for restricted supply ratios or additional bundle constraints, and how the answer depends on \(m\), \(\tau\), and the number of budget levels.
The strongest negative case is against Theorem 10, not against the whole programme.
Its reduction depends on two genuinely indivisible bidders partitioning one finite set of unique items. In the proposed continuum, the type-\(v_2\) population can split across configurations \(S\), so the condition “some bidder receives a subset whose weight is exactly \(t\)” disappears. A convex combination of subsets can satisfy the aggregate constraints without any individual bundle witnessing the exact-sum solution. If the original item set is kept fixed, only finitely many agents receive anything and the normalized welfare collapses. If supplies are scaled with population, the model becomes a capacitated multi-unit market with item types, not the two-bidder allocation problem used in Theorem 10. Thus the claimed hardness transfer is not established.
That objection does not eliminate the better version of the question. Scaled supplies and repeated capped-additive buyers are a plausible high-multiplicity market, and its configuration LP has the pricing problem
\[ \max_{S\subseteq X}\left\{\min\left(B_t,\sum_{j\in S}w_{tj}\right)-\sum_{j\in S}p_j\right\}, \]
which may itself encode knapsack. The right conclusion is only that Theorem 10 does not directly anchor the proposed continuum; the resulting problem is a new capacitated welfare problem. Since a tractable answer would still be a meaningful Class A result, this is not a decisive objection under the programme’s rules.
Theorem 9 is harder to defeat. For repeated gross-substitutes types, the continuous allocation LP has dual
\[ \min \left\{\sum_t \mu_t z_t+\sum_j b_jp_j: z_t+\sum_{j\in S}p_j\ge v_t(S)\ \text{for every }t,S\right\}. \]
Separation for type \(t\) is exactly the demand problem from Theorem 9:
\[ \max_{S\subseteq X}\left(v_t(S)-\sum_{j\in S}p_j\right). \]
The masses change the objective coefficients but not the pricing problem. With rational data, this yields a genuine high-multiplicity question whose complexity is measured in \(\tau\), \(m\), and encoding length rather than in the expanded number of bidders. Calling it merely a restatement of the finite theorem would conflict with the programme’s explicit high-multiplicity perspective: the compression from \(N\) repeated bidders to \(\tau\) types is precisely the object being studied. The oracle qualification should be made explicit, or one can restrict to finitely represented GS subclasses such as OXS, but neither point defeats the mirror.
So the honest negative case is weak. It can show that Theorem 10’s particular subset-sum reduction does not survive atomization without substantial re-modelling. It cannot defeat the improved capped-welfare question, and it cannot defeat the gross-substitutes mirror at all. A universal claim that no worthwhile continuous mirror exists would have to rely on fixed-supply degeneracy, “the answer is easy,” or “the finite answer is already known”—all of which are either repairable or expressly excluded by the programme.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.