Valuation Compressions in VCG-Based Combinatorial Auctions

Paul Dütting, Monika Henzinger, Martin StarnbergerACM Trans. Economics and Comput 2018 · OpenReview

TL;DR

This paper investigates the efficiency of the Vickrey-Clarke-Groves (VCG) mechanism in combinatorial auctions when bidders are restricted to simpler bidding strategies. They show that while these restrictions can make VCG computation feasible, they can also lead to significant welfare losses, especially as bidding languages become more expressive, and provide new bounds on this loss.

What Problem Does This Paper Address?

In combinatorial auctions, the VCG mechanism is theoretically optimal for maximizing social welfare and incentivizing truthful bidding. However, a major practical hurdle is that computing VCG allocations and payments can be computationally intractable for many realistic bidder valuation models (e.g., subadditive, submodular). This paper addresses this gap by studying what happens when bidders are forced to use simpler, more computationally tractable bidding languages. The core question is: how much social welfare do we lose when we restrict bidders to these simpler languages, and how does this loss change as the bidding language becomes more expressive?

Methods

The authors analyze the "Price of Anarchy" (PoA), which measures the ratio of optimal social welfare to the worst-case welfare achieved at equilibrium. They introduce a new concept called "relaxed smoothness" for mechanisms, which is a generalization of existing smoothness notions. This allows them to derive upper bounds on the PoA for various equilibrium concepts, including correlated and coarse correlated equilibria, and for learning outcomes (minimizing regret). They also establish lower bounds on the PoA by constructing specific examples of valuations and bids. A key technique involves analyzing the "outcome closure" property of mechanisms, which relates the set of equilibria in simpler bidding spaces to those in more complex ones.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The trade-off between tractability and efficiency: Restricting bidders to simpler bidding languages (like additive bids) makes VCG computation feasible, but it doesn't guarantee optimal welfare. The paper quantifies this loss.
  • Expressiveness matters: The welfare loss (Price of Anarchy) generally increases as the bidding language becomes more expressive. This is a counter-intuitive finding: more expressive languages, while potentially more descriptive, can lead to worse outcomes in equilibrium.
  • New bounds for non-additive bids: The paper provides novel upper and lower bounds for non-additive bidding languages (like OXS and fractionally subadditive), extending previous results from additive bids.
  • Relaxed Smoothness: A new technical tool is introduced to analyze the efficiency of mechanisms under various equilibrium concepts, offering more flexibility than prior smoothness definitions.
  • Hardness of finding equilibria: For additive bids, deciding whether a pure Nash equilibrium exists for VCG is shown to be NP-hard, highlighting the complexity even in simpler settings.

Key Results

  • Upper Bounds: An upper bound of 4 on the Price of Anarchy is shown for additive bids with respect to correlated and coarse correlated equilibria. For non-additive bids, bounds of $O(\log m)$ and $2$ are established for subadditive and $\beta$-fractionally subadditive valuations, respectively.
  • Lower Bounds: A lower bound of 2.4 is proven for pure Nash equilibria with subadditive valuations restricted to OXS bids, demonstrating a strict increase in welfare loss compared to additive bids. A general lower bound of 2 is also established for pure Nash equilibria with non-additive bids.
  • Hardness: Deciding the existence of a pure Nash equilibrium for VCG with subadditive valuations and additive bids is NP-hard.

Limitations and Future Work

  • Open Questions: The paper identifies several open questions, including whether mixed Nash equilibria can be computed efficiently for additive bids, and whether the welfare loss for non-additive bids (like OXS) is strictly greater than for additive bids.
  • Specific Bidding Spaces: While the paper analyzes general classes of valuations and bidding languages, further work could explore the precise boundaries of welfare loss for specific, commonly used bidding formats.
  • Incomplete Information: The paper primarily focuses on complete information settings, with an appendix touching on incomplete information. Extending the analysis of welfare loss under incomplete information remains an area for future research.

Summary updated

Abstract

The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions, the truthful direct-revelation mechanism that maximizes social welfare is the Vickrey-Clarke-Groves mechanism. For many valuation spaces, computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency.
BibTeX
@article{dutting2018valuation,
  author = {Paul Dütting and Monika Henzinger and Martin Starnberger},
  title = {{Valuation Compressions in VCG-Based Combinatorial Auctions}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2018},
  url = {https://openreview.net/forum?id=uWMhigxKql},
}
Figure