Core-competitive Auctions

Gagan Goel, Mohammad Reza Khani, Renato Paes Leme

TL;DR

This paper introduces the concept of "core-competitive auctions" to address the low revenue problem of VCG auctions in settings with complementary goods. They design incentive-compatible auctions that achieve a significant fraction of the revenue from "core outcomes" (a notion of competitive pricing) for the Text-and-Image ad auction setting, achieving O(ln ln k) and O(√ln k) approximation ratios for randomized and deterministic auctions, respectively.

What Problem Does This Paper Address?

The celebrated Vickrey-Clarke-Groves (VCG) auction mechanism is known for its desirable property of achieving efficient outcomes in an incentive-compatible way. However, a major drawback is its often very low, even zero, revenue, especially when the items being sold have complementary relationships. Complementarities arise in many real-world scenarios like spectrum auctions, procurement, and online advertising, where the value of one item increases with the presence of another. In such cases, VCG can fail to generate significant revenue even if buyers have high valuations.

Researchers have explored "core-selecting auctions" which guarantee competitive pricing (a "core outcome") even with complements. However, these often sacrifice incentive compatibility. This paper tackles the fundamental question: can we design an auction that is both incentive-compatible and achieves revenue comparable to a competitive outcome, even if not perfectly competitive? They define "core-competitive auctions" as incentive-compatible auctions whose revenue is at least a certain fraction (1/α) of the minimum revenue achievable by a core outcome. They focus on the Text-and-Image ad auction scenario as a case study for complementary goods.

Methods

The paper introduces the formal definition of "core-competitive auctions" based on a "core-revenue benchmark," which is the minimum revenue among all possible core outcomes. They then propose and analyze two mechanisms for the Text-and-Image setting:

  1. Deterministic Mechanism: This mechanism allocates either a single image ad or a set of text ads based on a comparison of bidder valuations and a derived threshold. The allocation rule and pricing are designed to ensure incentive compatibility and achieve a specific revenue guarantee relative to the core-revenue benchmark.
  2. Randomized Mechanism: This mechanism builds upon the deterministic one by introducing randomness in the allocation decision. By optimizing the revenue extraction through a probabilistic threshold, it achieves a better approximation ratio for the core-revenue benchmark.

Both mechanisms are analyzed using concepts from cooperative game theory (core outcomes) and mechanism design (incentive compatibility, individual rationality). They also establish lower bounds to show the tightness of their achieved approximation factors.

Datasets

Not discussed in the paper. The paper focuses on theoretical mechanism design and analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Core-Revenue Benchmark": Defining a specific revenue target (the minimum revenue from a core outcome) provides a concrete goal for designing revenue-maximizing, yet incentive-compatible, auctions in challenging settings.
  • Complementarities as the Revenue Hurdle: The paper clearly articulates how complementarities are the root cause of VCG's revenue deficiency and why standard auction designs struggle.
  • Balancing Incentive Compatibility and Revenue: The core-competitive framework offers a way to relax the strict requirements of perfect core outcomes or perfect incentive compatibility to achieve a practical balance, leading to significantly better revenue than VCG in complementary settings.
  • Text-and-Image Setting as a Representative Case: This specific ad auction scenario effectively captures the essence of complementary goods and serves as a good testbed for developing and evaluating new auction mechanisms.
  • Tightness of Bounds: Demonstrating both upper bounds (achieved by their mechanisms) and lower bounds (impossibility results) is crucial for establishing the optimality of their findings within the defined model.

Key Results

  • Deterministic Auction: The paper presents a deterministic mechanism for the Text-and-Image setting that is O(√ln k)-core-competitive. This means its revenue is at least a factor of 1/O(√ln k) of the core-revenue benchmark.
  • Randomized Auction: A randomized mechanism is designed that achieves a better O(ln ln k)-core-competitive factor.
  • Lower Bounds: The authors prove that these factors are tight, meaning no deterministic mechanism can achieve better than O(√ln k) and no randomized mechanism can achieve better than Ω(ln ln k) core-competitive factor for this setting under certain assumptions.

Limitations and Future Work

  • Specific Setting: The results are derived for the Text-and-Image ad auction setting. Generalizing these findings to other types of complementary goods or more complex auction environments is a natural next step.
  • Assumptions: The analysis relies on specific assumptions about bidder valuations and the environment (e.g., single-parameter agents, downward-closed feasible sets). Relaxing these assumptions could lead to more broadly applicable results.
  • Practical Implementation: While the mechanisms are theoretically sound, their practical implementation might involve further considerations regarding computational complexity and bidder behavior in real-world scenarios.
  • Other Benchmarks: The paper compares the core-revenue benchmark to others like envy-free and Micali-Valiant benchmarks. Further exploration of how core-competitiveness relates to other revenue objectives could be valuable.
  • More Complex Complementarities: Investigating mechanisms for settings with more intricate forms of complementarities beyond the Text-and-Image model would be a significant extension.

Summary updated

Abstract

One of the major drawbacks of the celebrated VCG auction is its low (or zero) revenue even when the agents have high value for the goods and a competitive outcome would have generated a significant revenue. A competitive outcome is one for which it is impossible for the seller and a subset of buyers to 'block' the auction by defecting and negotiating an outcome with higher payoffs for themselves. This corresponds to the well-known concept of core in cooperative game theory. In particular, VCG revenue is known to be not competitive when the goods being sold have complementarities. Complementary goods are present in many application domains including spectrum, procurement, and ad auctions. The absence of good revenue from VCG auction poses a real hurdle when trying to design auctions for these settings. Given the importance of these application domains, researchers have looked for alternate auction designs. One important research direction that has come from this line of thinking is that of the design of core-selecting auctions (See Ausubel and Milgrom, Day and Milgrom, Day and Cramton, Ausubel and Baranov). Core-selecting auctions are combinatorial auctions whose outcome implements competitive prices even when the goods are complements. While these auction designs have been implemented in practice in various scenarios and are known for having good revenue properties, they lack the desired incentive-compatibility property of the VCG auction. A bottleneck here is an impossibility result showing that there is no auction that simultaneously achieves competitive prices (a core outcome) and incentive-compatibility. In this paper we try to overcome the above impossibility result by asking the following natural question: is it possible to design an incentive-compatible auction whose revenue is comparable (even if less) to a competitive outcome? Towards this, we define a notion of core-competitive auctions. We say that an incentive-compatible auction is α-core-competitive if its revenue is at least 1/α fraction of the minimum revenue of a core-outcome. We study one of the most commonly occurring setting in Internet advertisement with complementary goods, namely that of the Text-and-Image setting. In this setting, there is an ad slot which can be filled with either a single image ad or k text ads. We design an O(ln ln k) core-competitive randomized auction and an O(√ln k) competitive deterministic auction for the Text-and-Image setting. We also show that both factors are tight.
BibTeX
@inproceedings{goel2015core,
  author = {Gagan Goel and Mohammad Reza Khani and Renato Paes Leme},
  title = {{Core-competitive Auctions}},
  booktitle = {EC},
  year = {2015},
  url = {https://openreview.net/forum?id=9vaMbPuY6cp},
}
Figure