Abstract
We devise a new auction mechanism for combinatorial auctions, such as the upcoming “incentive auctions” for re-allocating spectrum rights. Our mechanism achieves optimal social welfare subject to computability, and possesses an impressive list of incentive properties.
Introduction
As wireless technology becomes increasingly central to modern life, the management of the radio spectrum has become a high-stakes economic and technical challenge. Governments worldwide are tasked with re-allocating spectrum rights—often moving them from older uses like broadcast television to modern mobile broadband. This process typically involves "combinatorial auctions," where bidders compete for subsets of items that have synergistic values. However, designing these auctions is notoriously difficult due to the competing demands of computational feasibility and strategic integrity.
The Combinatorial Auction Challenge
The primary hurdle in spectrum allocation is the sheer complexity of the radio spectrum itself. Different telecommunications companies require specific "bundles" of frequency bands to operate effectively. The value of a bundle often exceeds the sum of its individual parts, creating a complex optimization problem for the auctioneer.
Two major obstacles define this field:
- Computational Complexity: Finding an allocation that maximizes "social welfare" (the total value derived by all participants) is an NP-hard problem. Even with a modest number of bidders and items, calculating the mathematically perfect outcome is often impossible within a reasonable timeframe.
- Strategic Behavior: In a standard auction, bidders are incentivized to misreport their true valuations to pay less. This "gaming" of the system leads to inefficient outcomes where the spectrum is not allocated to those who can utilize it most effectively.
While existing mechanisms have addressed individual misreporting, they remain highly vulnerable to collusion, where groups of bidders coordinate their actions to manipulate the auction outcome.
From Forward to Reverse Greedy Mechanisms
To solve these issues, this paper introduces a "reverse greedy" mechanism, also known as a deferred-acceptance auction. This represents a fundamental shift from traditional "forward greedy" approaches.
In a standard forward approach, the auctioneer ranks bids from highest to lowest and iteratively accepts the "best" looking bids, removing any conflicting bidders as they go. While computationally fast, this method allows groups to coordinate low bids to win items for significantly less than their true value.
In contrast, the reverse approach starts with the entire pool of bidders and iteratively rejects the bid that appears "least promising." This is typically the bid contributing the least to potential social welfare relative to the conflicts it creates with other bidders. The process continues until the remaining bids are all mutually compatible. By utilizing this deferred-acceptance logic, the authors mathematically prove that the auction becomes "group strategy-proof."
Solving the Collusion Gap
A key insight of this research is that the direction of "greed" matters immensely for game-theoretic security. Rejection-based greed offers much stronger protection against collusion than selection-based greed.
In traditional auctions, a "collusion gap" exists where multiple bidders (like "Sue" and "Tom") can coordinate their bids to displace a middle-man ("Moe"). This allows them to win their respective items while paying far less than they would in a competitive environment. The reverse greedy mechanism eliminates the benefit of such joint misreporting, ensuring that the auction remains fair even when participants attempt to cooperate against the auctioneer.
Conclusion: The Triple Crown of Auction Design
The "reverse greedy" mechanism successfully achieves three critical goals for modern spectrum management:
- Feasibility: It is computationally efficient, capable of handling the complex bundles required for global spectrum rights.
- Individual Incentives: No single agent can gain an advantage by lying about their valuation.
- Group Incentives: No group of agents can benefit from colluding or coordinating their misreporting.
By providing the optimal social welfare possible within the constraints of polynomial-time computation, this framework offers a robust solution for the next generation of government incentive auctions.
Summary updated