Abstract
Designing auctions for multiple items with complex interdependencies is a fundamental challenge in mechanism design. This paper introduces the Combinatorial Ascending Auction (CASA), a mechanism that provides a "rank-guarantee" for revenue. By ensuring the seller earns at least the $(|M|+1)$-th highest valuation for bundles in a menu $M$, CASA achieves near-optimal results with minimal bidder rationality and remains robust even when the seller lacks information regarding bidders' valuation distributions.
Introduction
Combinatorial auctions, such as those used for FCC spectrum licenses or digital advertising slots, are notoriously difficult to design. Bidders often have complex preferences where items act as complements (valuable only as a set) or substitutes (only one is needed).
Traditional auction theory, notably the Myerson model, often proves inadequate in these settings because it typically assumes single-item environments, hyper-rational bidders (Bayesian Nash Equilibrium), and known statistical "priors" for valuations. While the Vickrey-Clarke-Groves (VCG) mechanism is theoretically efficient, it frequently yields zero revenue and is vulnerable to strategic manipulation. CASA seeks a middle ground: an auction that is simple to play, robust to uncertainty, and guaranteed to perform well under realistic conditions.
The Combinatorial Ascending Auction (CASA)
The CASA mechanism is defined by a straightforward set of rules designed to facilitate competition over bundles:
- The Menu ($M$): The auctioneer defines a specific set of bundles that bidders are permitted to bid on.
- Bidding Process: Bidders take turns raising prices on any assortment of bundles from the menu. These bids are binding commitments.
- The "Pay-as-Bid" Rule: Unlike complex personalized pricing schemes, CASA uses the current leading prices to determine winners.
- Allocation: The auction concludes when prices stabilize. The auctioneer then selects the combination of non-overlapping bundles that maximizes total revenue.
The Rank-Guarantee and Menu Design
The core theoretical innovation of this work is the Rank-Guarantee. A $k$-th rank guarantee ensures that the auction's revenue is at least as high as the $k$-th highest valuation for each bundle. The authors prove that CASA achieves a $(|M|+1)$-th rank guarantee, provided bidders avoid "obviously dominated" strategies—meaning they do not quit if a bundle they value more than the current price is available.
There is a fundamental trade-off between menu size and the revenue guarantee: a larger menu allows for more efficient allocations but weakens the revenue guarantee as $|M|$ increases. However, the authors identify specific preference structures where the menu can be significantly reduced without sacrificing efficiency.
As shown in Table 1, if items are substitutes, the menu can be limited to individual items. If they are complements, a "grand bundle" may suffice. These simplifications allow CASA to maintain strong revenue guarantees while remaining computationally and strategically manageable.
Key Results and Asymptotic Optimality
The paper establishes several critical properties of the CASA mechanism:
- Revenue Bound: Revenue is guaranteed to be $\ge$ the $(|M|+1)$-th highest valuation for any valuation profile.
- Thick Market Performance: In markets where the number of bidders $N$ is much larger than the menu size $|M|$, CASA is asymptotically optimal. The revenue loss scales at a rate of $O(|M|^2/N)$, meaning it extracts nearly the full surplus as competition increases.
- Strategic Robustness: The mechanism's performance holds even if bidders are acting somewhat irrationally or colluding in small groups, as long as a sufficient residual of rational, competing bidders exists.
- Distributional Robustness: As a "prior-free" auction, the seller does not need to know the bidders' valuation distributions; the competition between "losers" naturally drives the price toward the rank-guarantee.
Limitations and Future Directions
While CASA offers a robust framework, it faces challenges in "thin" markets with few bidders, where the rank-guarantee may be too low to be effective. Additionally, while CASA simplifies the decision of whether to bid, it does not fully solve the strategic complexity of which specific bundles a bidder should target to maximize their individual profit. Future research may explore the use of AI bidding proxies to help human bidders navigate these tactical complexities, potentially leading to hybrid models of human intent and algorithmic execution.
Summary updated