Approximating optimal combinatorial auctions for complements using restricted welfare maximization
Pingzhong Tang and Tuomas Sandholm
The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. We introduce a new form of ``reserve pricing" into CAs: excluding allocations that do not satisfy predefined requirements. We show that Levin's optimal revenue can be 2-approximated by using ``monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types. Finally, we show that the optimal revenue can be 6-approximated even if the ``reserve pricing" is required to be symmetric across bidders.