Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods

Piotr Krysta, Orestis Telelis, Carmine Ventre

Introduction

Combinatorial auctions (CAs) represent a fundamental challenge at the intersection of computer science and economics. In these auctions, bidders compete for bundles of items, where the value of a bundle may be greater than (or less than) the sum of its individual components. While standard CAs are notoriously difficult to optimize—finding a welfare-maximizing allocation is NP-hard and resistant to approximation—real-world scenarios often present structural constraints that can be exploited.

This research, published in the Journal of Artificial Intelligence Research (2015), focuses on multi-unit CAs where the number of distinct types of goods ($m$) is small, even if the total number of units is large. A classic example is a spectrum auction involving a few geographic regions but hundreds of identical licenses within each. The paper provides the first deterministic, truthful, and near-optimal mechanisms for this setting.

The Mechanism Design Challenge

Designing an effective auction requires balancing three competing objectives:

  1. Computational Efficiency: The allocation algorithm must run in polynomial time relative to the number of bidders and items.
  2. Social Welfare Maximization: The goal is to maximize the sum of all bidders' valuations.
  3. Truthfulness (Incentive Compatibility): The mechanism must ensure that bidders are incentivized to report their true valuations, typically achieved through a payment rule that makes truth-telling a dominant strategy.

The authors utilize Maximal-in-Range (MiR) mechanisms to achieve these goals. An MiR algorithm restricts its search to a pre-defined subset (or "range") of all possible allocations and selects the optimal one within that range. When combined with Vickrey-Clarke-Groves (VCG) payments, MiR mechanisms are guaranteed to be truthful.

Algorithmic Approaches for Diverse Bidder Preferences

The paper categorizes bidders based on their valuation functions and provides tailored solutions for each:

Submodular Bidders

For bidders with submodular valuations—those experiencing diminishing marginal returns as they acquire more units—the authors developed a Polynomial Time Approximation Scheme (PTAS). This mechanism approximates the optimal social welfare within a factor of $(1+\epsilon)$ without violating any supply constraints. This is achieved by extending the Dobzinski-Nisan method, which involves rounding allocations so that bidders receive items in specific, pre-defined bundle sizes.

Multi-minded Bidders

Multi-minded bidders have specific "atomic" bundles they desire (e.g., "I want exactly 10 units of A and 5 of B"). For this group, the authors provide a Fully Polynomial Time Approximation Scheme (FPTAS). To achieve this level of efficiency, the mechanism slightly relaxes supply constraints, potentially "overselling" inventory by a factor of $(1+\epsilon)$. The authors prove that this relaxation is necessary; without it, the problem remains strongly NP-hard even for $m \ge 2$.

General Bidders

For bidders with unrestricted preferences, the paper offers a truthful $(m+1)$-approximation mechanism. While less precise than the schemes for submodular or multi-minded bidders, it provides a robust baseline for general settings where $m$ is small.

Theoretical Limits and Hardness

A significant portion of the work is dedicated to establishing the "best-possible" nature of these results. Through complexity analysis, the authors demonstrate that their approximation schemes sit at the boundary of mathematical possibility. For instance, the hardness proofs show that an FPTAS for multi-minded bidders without supply violation would imply $P=NP$. The efficiency of these algorithms depends exponentially on the number of distinct goods; if $m$ is large, these "polynomial" algorithms become practically unusable.

Conclusion and Future Directions

This research provides a comprehensive toolkit for managing multi-unit auctions with a constant number of distinct goods. By leveraging the "power of few," the authors transform intractable global optimization problems into manageable tasks through sophisticated dynamic programming and range restriction.

However, gaps remain. There is still a discrepancy between the $(m+1)$-approximation provided for general bidders and the known lower bound of 2 for a single good. Closing this gap for a constant $m > 1$ and further exploring the communication complexity of these mechanisms remain important open problems for the field.

Summary updated

BibTeX
@article{krysta2015mechanisms,
  author = {Piotr Krysta and Orestis Telelis and Carmine Ventre},
  title = {{Mechanisms for Multi-unit Combinatorial Auctions with a Few Distinct Goods}},
  journal = {J. Artif. Intell. Res.},
  year = {2015},
  doi = {10.1613/jair.4587},
}
Figure