How hard is dominant-strategy mechanism design for combinatorial auctions?

DSIC is a stronger requirement than truthfulness

A mechanism in a combinatorial auction outputs both an allocation of m items among n bidders and prices. Truthfulness means each bidder is best off following the prescribed strategy assuming other bidders also follow theirs, an ex-post Nash equilibrium. DSIC is stricter: each bidder is best off playing truthfully no matter how the other bidders behave, whether rationally, adversarially, or nonsensically.

That distinction matters because the paper's main results concern deterministic DSIC mechanisms, while its two-bidder results also cover universally DSIC, a randomized analogue. The paper separates these settings deliberately: randomization can enable more powerful mechanisms, so deterministic and randomized hardness are not interchangeable.

The communication budget sets the approximation floor

The paper defines DSIC_GEN(m, γ), DSIC_XOS(m, γ), and DSIC_GS(m, γ) as the best approximation ratio attainable by a deterministic, individually rational, no-negative-transfers DSIC mechanism using at most 2^γ communication over m items, for general monotone, XOS, and gross substitutes valuations respectively. The parameter γ ranges from log m to m.

The main theorems state DSIC_GS(m, γ) = Ω((m/γ)^(1/7)), DSIC_XOS(m, γ) = Ω((m/γ)^(1/5)), and DSIC_GEN(m, γ) = Ω(m/γ), all for γ in [log m, m]. A single unified proof yields all three. Because the general lower bound matches the deterministic DSIC O(m/γ)-approximation of QiuW24, the general case is tight: DSIC_GEN(m, γ) = Θ(m/γ).

Gross substitutes hardness answers a prior open question

For GS valuations, polynomial-communication welfare maximization is possible, and VCG turns that into a polynomial-communication deterministic truthful mechanism. The new lower bound shows this does not carry over to deterministic DSIC mechanisms: no good approximation is possible in polynomial communication. This answers an open question of DobzinskiRV22.

The paper notes that its GS construction only uses convolutions of weighted matroid rank valuations, so the lower bound also holds for Rado valuations, a strict subclass of GS. That makes the impossibility stronger, not weaker: it applies even to a narrower valuation class than GS.

How a DSIC mechanism becomes a simultaneous algorithm

The proof retains the outer framework of DRV22: a good deterministic DSIC mechanism is converted into a good simultaneous algorithm on a hard distribution, and a communication lower bound for the simultaneous problem then yields a lower bound for the DSIC mechanism. The obstruction is contingent strategies: if Alice moves first and can send message X or Y, Bob may choose a continuation favorable after X and unfavorable after Y, which can make a valuation prescribed to send Y prefer X and violate DSIC.

The paper's first change separates the scale of the underlying valuation from the value of a special outcome. For GS and XOS valuations the special outcome is receiving a high-value item; for general valuations it is receiving the entire set of items. Its value is large enough to affect each bidder's incentives but small relative to total welfare. This lets the proof work with all bidders at the same underlying valuation scale, avoiding the common-scale averaging loss in DRV22.

The remaining barrier is quantitative. In the earlier 0-1 construction, guaranteeing any positive utility already certifies full value, which is false for GS and XOS valuations, where a bidder may get positive utility while recovering only a small fraction of full value. The paper uses amplification: each bidder has exponentially many candidate clauses, and amplification doubles the coefficients of a sparse collection of clauses, so a short first message is unlikely to rule out the hidden special coordinate having been doubled. A second contingent-strategy argument upgrades normal continuation utility into a high utility guarantee, and the protocol then performs a randomized allocation that places special sets correctly with good probability.

Two-bidder results split hardness from possibility

The many-bidder hard instances do not generalize to few bidders, so the paper proves separate two-bidder results. On the hardness side, any IR, NNT, universally DSIC mechanism attaining a 0.9999-approximation for two weighted matroid rank valuations uses exponential communication. Weighted matroid rank valuations are GS, so they admit deterministic welfare-maximizing algorithms and truthful mechanisms; the hardness is specific to universally DSIC mechanisms.

On the possibility side, there is a polynomial-communication (1+√5)/2 ≈ 1.618-approximation for two submodular bidders using a universally DSIC mechanism. Before this work it was not known whether even a polynomial-communication universally truthful mechanism could beat a 2-approximation for two submodular valuations, nor whether a polynomial-communication universally DSIC mechanism could beat a 2-approximation for two weighted matroid rank valuations. The paper also gives a polynomial-communication simultaneous algorithm beating 3/4 for two matroid rank valuations, with a (41−√6)/50 ≈ 0.771-approximation.

Mixing two mechanisms beats a one-half approximation

The two-submodular DSIC mechanism mixes two procedures that perform well on different profiles. One is random allocation, which gives a 1/2-approximation in the worst case. The other is the extended parallel second-price auction (EP2A) from FF20, which asks each bidder for the marginal value of each item; the higher bidder gains the right to purchase the item at the lower bidder's value, and both bidders purchase their favorite available set at the given prices. FF20 prove EP2A is DSIC for subadditive valuations.

When the instance is close to modular, EP2A sets nearly correct prices and items go to the correct bidder. The bad case is when the instance is far from modular: reported marginal values may far exceed the value bidders can actually extract, leaving many items unallocated. That is exactly the case where random allocation is expected to beat 1/2. Randomly allocating a portion of the items and running EP2A on the rest balances the two extremes. Submodularity is necessary here because EP2A must remain DSIC after contracting the original valuations, and submodularity is preserved under contraction while subadditivity is not.

Where these bounds do and do not transfer

The many-bidder lower bounds are stated for γ in [log m, m] and for deterministic, IR, NNT DSIC mechanisms. The two-bidder lower bound holds for universally DSIC mechanisms, so it is not a statement about all truthful mechanisms. The positive two-bidder results are polynomial-communication constructions for two submodular bidders and for two matroid rank valuations, not for arbitrary numbers of bidders.

The paper also flags what remains open. It is still open whether a polynomial-communication truthful mechanism can beat a 1/2-approximation for XOS valuations with two bidders, whether a polynomial-communication deterministic DSIC mechanism can beat 1/2 for weighted matroid rank valuations, and whether a polynomial-communication deterministic truthful mechanism can beat 1/2 for submodular valuations. For submodular, XOS, and subadditive valuations, the optimal approximation for deterministic truthful mechanisms that are MIR, value-query implementable, or computationally efficient is Θ̃((m/γ)^(1/2)), while simultaneous algorithms for subadditive valuations attain O(m^(1/3)); if the correct DSIC answer were also Θ̃((m/γ)^(1/2)), new techniques would be needed for a tight lower bound.

The tight general case is the anchor result

Among the paper's results, the general-valuation bound is the one that is fully pinned down: DSIC_GEN(m, γ) = Θ(m/γ) for γ in [log m, m], matching the deterministic DSIC O(m/γ)-approximation of QiuW24. The GS and XOS bounds are lower bounds only, with exponents 1/7 and 1/5 respectively, and the paper explicitly notes that better KSSHD hard instances could plausibly improve them.

For readers deciding how much to trust each number, the practical split is therefore between the tight general case and the looser GS and XOS cases, and between the many-bidder deterministic setting and the two-bidder universally DSIC setting. The GS result is the sharpest conceptual shift: it shows that the VCG route to polynomial-communication deterministic truthfulness for GS does not extend to deterministic DSIC approximation, even though GS welfare maximization itself is tractable in polynomial communication.

Sources used in this answer