Abstract
We consider auctions in which greedy algorithms, paired with first-price or critical-price payment rules, are used to resolve multi-parameter combinatorial allocation problems. We study the price of anarchy for social welfare in such auctions. We show for a variety of equilibrium concepts, including Bayes-Nash equilibrium and correlated equilibrium, the resulting price of anarchy bound is close to the approximation factor of the underlying greedy algorithm.
Introduction
In algorithmic mechanism design, a fundamental tension exists between computational efficiency and incentive compatibility. The Vickrey-Clarke-Groves (VCG) mechanism is the theoretical gold standard, as it ensures truthfulness is a dominant strategy. However, VCG requires solving the underlying allocation problem optimally—a task that is NP-hard for most complex combinatorial auctions, such as assigning $m$ items to $n$ bidders with diverse preferences.
To maintain computational tractability, researchers often employ greedy approximation algorithms. While these algorithms provide a guaranteed approximation factor $c$ relative to the optimal social welfare, they are typically not truthful. Consequently, bidders are incentivized to manipulate their bids strategically. This paper investigates the resulting "Price of Anarchy" (PoA)—the ratio between the optimal social welfare and the welfare achieved at equilibrium—when greedy allocation rules are paired with simple payment mechanisms.
The Greedy Mechanism Framework
The authors bridge the gap between approximation and incentives by identifying a critical property of greedy algorithms: Strongly Loser-Independence (SLI).
Strongly Loser-Independence
An allocation algorithm satisfies SLI if the final outcome remains unchanged even if "losing" bidders (those who did not receive their desired sets) alter their bids, provided their new bids remain below the threshold required to win. The authors demonstrate that most standard greedy allocation rules naturally satisfy this property. SLI is vital because it prevents strategic agents from using "sacrificial" bids on items they do not value simply to disrupt the greedy ordering and secure other items.
Payment Rules
The study focuses on two primary payment structures:
- First-Price Rules: Bidders pay exactly the amount they bid.
- Critical-Price Rules: Bidders pay the minimum amount they could have bid to remain a winner, generalizing the concept of second-price auctions to combinatorial settings.
Theoretical Analysis: The Smoothness Framework
To bound the PoA, the authors utilize a "smoothness" analysis. This framework involves proving that for any optimal allocation, there exists a specific bid a player could make that guarantees them a fraction of their contribution to the optimal welfare, regardless of the strategies chosen by other players. By aggregating these guarantees across all players, the authors derive robust bounds on the social welfare at equilibrium.
Applications and Results
The framework is applied to several classic combinatorial problems, including General Combinatorial Auctions, the Unsplittable Flow Problem (UFP), Convex Bundle Auctions, and Job Scheduling. The results show that the PoA is remarkably close to the algorithm's original approximation factor $c$.
Key Efficiency Bounds
- First-Price Mechanisms: For Pure Nash Equilibria, the PoA is exactly $c$. In the more complex Bayes-Nash Equilibrium (where bidders have incomplete information), the PoA is at most $c + O(c^2/e^c)$.
- Critical-Price Mechanisms: Assuming agents do not overbid (the "no-overbidding" assumption), the PoA is at most $c + 1$.
- Correlated Types: In scenarios where bidder values are dependent, the PoA remains bounded by $4c$ for non-adaptive greedy algorithms.
The authors also provide lower bounds, demonstrating that the small additive constants (like the $+1$ in critical-price settings) are necessary and represent a fundamental limit of these mechanisms rather than an artifact of the proof technique.
Discussion and Limitations
While the paper establishes strong welfare guarantees, it notes several open challenges. First, while the PoA is low if an equilibrium exists, greedy first-price auctions do not always guarantee the existence of a Pure Nash Equilibrium. Second, the current definition of "greedy" focuses on player-allocation pairs and does not yet encompass algorithms that award items based on marginal gains, which are common in submodular optimization. Finally, extending the $4c$ bound for correlated types to adaptive greedy algorithms remains a subject for future research.
By decoupling computation from incentives, this work shows that "natural" greedy algorithms—already favored for their speed—can be transformed into robust auctions where strategic behavior does not significantly degrade system efficiency.
Summary updated