Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization

Pingzhong Tang, Tuomas SandholmIJCAI 2011 · OpenReview

Abstract

While the Vickrey-Clarke-Groves (VCG) mechanism is the gold standard for maximizing social welfare in combinatorial auctions (CAs), designing revenue-maximizing (optimal) CAs remains a significant challenge. For auctions involving complements—where items are more valuable as a bundle than individually—designing an optimal mechanism is NP-hard. This paper introduces a novel approach to bridge the gap between welfare and revenue: "Restricted Welfare Maximization." By "poking holes" in the allocation space based on bidder bids and applying a welfare-maximizing rule to the remaining set, we achieve a 2-approximation of the optimal revenue for complements. This mechanism is more efficient, requires less information about bidder distributions, and is easier to implement than existing theoretical benchmarks. We also provide a generalization of Myerson’s Lemma to this environment and demonstrate a 6-approximation when reserve prices must be symmetric.

Introduction

In auction theory, the tension between social welfare and seller revenue is a central theme. The VCG mechanism effectively maximizes social welfare by ensuring items are allocated to those who value them most, but it often fails to generate significant revenue. Conversely, while Roger Myerson (1981) solved the revenue-maximization problem for single items, the problem becomes exponentially more complex in Combinatorial Auctions (CAs), particularly when items are complements.

Levin (1997) derived an optimal CA for complements in settings where each agent's private type is one-dimensional. However, Levin's mechanism is notoriously difficult to implement: it requires the auctioneer to possess perfect knowledge of the probability distributions of all bidders' valuations and can result in significant economic inefficiency. This research seeks a middle ground—a mechanism that retains the intuitive structure of welfare maximization while guaranteeing a high fraction of optimal revenue.

The "Hole-Poking" Paradigm

The core innovation of this paper is the concept of Restricted Welfare Maximization. Rather than abandoning the welfare-maximizing framework, the authors propose modifying the set of allowable outcomes. This is described as "poking holes" in the allocation space.

The Mechanism Design

The process follows four primary steps:

  1. Monopoly Reserve Prices: The auctioneer calculates "monopoly reserve prices" for each bidder based on their type distributions. These act as thresholds for participation.
  2. Restricting the Allocation Space: The auctioneer identifies specific allocations that would result in "negative" expected revenue (based on virtual valuations). These specific allocations are deleted from the set of possible outcomes.
  3. Welfare Maximization: The auction then proceeds using a standard welfare-maximizing allocation rule, but it is restricted to the remaining "legal" allocations.
  4. Levin’s Payment Rule: To maintain incentive compatibility, the authors employ a payment rule that generalizes second-price logic to this restricted space, ensuring that bidders are motivated to report their true valuations.

Theoretical Contributions: Generalizing Myerson

A significant theoretical hurdle in this research was linking the allocation rule to expected revenue in a non-single-parameter environment. The authors provide a key lemma of independent interest: they prove that the expected revenue from any truthful, allocation-monotonic mechanism equals the expected virtual valuation. This generalizes Myerson’s Lemma from the standard single-parameter environment to this more complex setting involving complements. This mathematical bridge is what allows the authors to prove formal approximation bounds against the theoretical optimum.

Key Results and Performance

The proposed mechanism, denoted as $SW_{MR}$ (Social Welfare with Monopoly Reserves), offers several advantages over the previous state-of-the-art:

  • Revenue Guarantees: The authors prove that $SW_{MR}$ with bidder-specific reserve prices captures at least 50% (a 2-approximation) of the maximum possible revenue.
  • Symmetric Constraints: In many real-world scenarios, legal or fairness requirements mandate "anonymous" pricing. The paper shows that even if the seller is restricted to symmetric reserve prices across all bidders, the mechanism still achieves a 6-approximation of the optimal revenue.
  • Efficiency and Simplicity: Unlike Levin’s optimal auction, which may withhold items to maximize profit, the restricted welfare approach is inherently more efficient because it prioritizes welfare among the allowed outcomes. Furthermore, it is "information parsimonious"; instead of needing full probability distributions for every possible bundle, the auctioneer only needs to announce a small set of reserve prices.
  • Truthfulness: The mechanism maintains Dominant Strategy Price Truthfulness, ensuring that bidders have no incentive to misrepresent their valuations regardless of the actions of others.

Conclusion and Future Work

This paper introduces a practical framework for increasing revenue in complex auction environments without sacrificing the structural benefits of welfare-maximizing mechanisms. While the current results are limited to one-dimensional type spaces—where a bidder's preferences are scaled by a single private variable—the "hole-poking" paradigm suggests a promising path for more complex, multi-dimensional environments.

Future research may explore the tightness of the 2-approximation bound and investigate whether similar restricted welfare rules can be applied to broader classes of item constraints and bidder preferences. By focusing on restricting the allocation space rather than redesigning the objective function, this approach offers a robust and verifiable alternative to traditional optimal mechanism design.

Summary updated

Abstract

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. (This does not fall inside the well-studied "single-parameter environment".) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space--based on the bids--and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. 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, and is always more efficient. Finally, we show that the optimal revenue can be 6- approximated even if the "reserve pricing" is required to be symmetric across bidders.
BibTeX
@inproceedings{tang2011approximating,
  author = {Pingzhong Tang and Tuomas Sandholm},
  title = {{Approximating Optimal Combinatorial Auctions for Complements Using Restricted Welfare Maximization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=HyV9I4fdbS},
}
Figure