The existence of incentive-compatible, computationallyefficient mechanisms for combinatorial auctions with good approximation ratios is the paradigmatic problem in algorithmic mechanism design. It is believed that, in many cases, good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. In this paper, we prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. Our results are tight, hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits. We show two different techniques to obtain such lower bounds: one for deter-
Stored only when both papers are in the corpus — 48 citations exist upstream.
Imported from OpenAlex (CC0) — nothing here is generated.