Price of Anarchy for Greedy Auctions

Brendan Lucier, Allan Borodin

TL;DR

This paper demonstrates that "greedy" approximation algorithms—which are computationally efficient but not naturally truthful—can be converted into auctions with a Price of Anarchy (PoA) that nearly matches the algorithm's original approximation factor. By pairing greedy rules with first-price or critical-price payments, the authors prove that strategic behavior doesn't significantly degrade social welfare across a wide range of equilibrium concepts.

What Problem Does This Paper Address?

In the world of algorithmic mechanism design, there is a fundamental tension between computational efficiency and incentive compatibility.

The gold standard for auctions is the VCG (Vickrey-Clarke-Groves) mechanism, which makes "telling the truth" the dominant strategy for every participant. However, VCG requires solving the underlying allocation problem perfectly. For complex tasks like combinatorial auctions (assigning $m$ items to $n$ bidders with complex preferences), finding the optimal allocation is NP-hard.

Researchers often turn to greedy algorithms because they are fast and provide good approximations (a factor of $c$). The catch? Greedy algorithms are rarely truthful. If you use a greedy rule, bidders will strategically manipulate their bids. This paper asks: If we accept that bidders will be strategic, how much social welfare do we lose at equilibrium? This loss is known as the Price of Anarchy (PoA).

Methods

The authors bridge the gap by identifying a specific property of greedy algorithms they call Strongly Loser-Independence (SLI).

  1. Strongly Loser-Independence: An algorithm is SLI if changing "losing" bids (bids for sets an agent didn't win) doesn't change the final outcome, provided those bids remain "losers." The authors prove that almost all standard greedy allocation rules satisfy this property.
  2. Mechanism Construction: They analyze two simple payment rules:
  3. First-Price: Bidders pay exactly what they bid.
  4. Critical-Price: Bidders pay the minimum amount they could have bid and still won (a generalization of second-price auctions).
  5. Smoothness Framework: They utilize a "smoothness" style analysis to bound the PoA. This involves showing that for any optimal allocation, there exists a bid an agent could make that guarantees them a certain utility, regardless of what others do.

Datasets

As a theoretical computer science paper, no empirical datasets were used. Instead, the authors evaluate their framework against several classic combinatorial allocation problems:

  • General Combinatorial Auctions: Assigning non-intersecting sets of items.
  • Unsplittable Flow Problem (UFP): Routing demands through a graph with edge capacities.
  • Convex Bundle Auctions: Allocating non-overlapping shapes in a 2D plane.
  • Job Scheduling: Assigning tasks to machines with specific time windows.

Key Insights and Ideas

  • Decoupling Computation from Incentives: The biggest "aha moment" is that you don't need to design a mechanism to be "truthful" (DSIC) to get good results. You can pick a "natural" greedy algorithm that engineers already use for its speed and approximation, add a simple pricing rule, and the game-theoretic outcome will be robust.
  • The Power of SLI: The SLI property is the "secret sauce." It prevents a strategic bidder from using "sacrificial" bids on items they don't want just to manipulate the greedy ordering and steal the items they do want.
  • Robustness Across Equilibria: The bounds aren't just for simple Nash Equilibria; they hold for Bayes-Nash Equilibria (where bidders have uncertain information about others) and even Coarse Correlated Equilibria (which arise from simple learning dynamics).

Key Results

The paper provides tight bounds showing that the PoA is very close to the algorithm's approximation factor $c$:

  • First-Price Mechanisms: The Bayes-Nash PoA is at most $c + O(c^2/e^c)$. In the simpler case of Pure Nash Equilibria, the PoA is exactly $c$.
  • Critical-Price Mechanisms: Under the assumption that agents don't overbid (a standard assumption in second-price settings), the PoA is at most $c + 1$.
  • Correlated Types: Even if bidders' values are not independent (e.g., they all value an item more if a certain market trend occurs), the PoA remains bounded by $4c$ for non-adaptive greedy algorithms.
  • Lower Bounds: The authors provide clever counter-examples showing that the small "extra" terms (like the $+1$ in critical-price) are actually necessary and not just a weakness of the proof.

Limitations and Future Work

  • Existence of Pure Nash: The authors admit that while the PoA is low if an equilibrium exists, greedy first-price auctions are not guaranteed to have a Pure Nash Equilibrium (they provide a specific 3-agent example where none exists).
  • Submodular Valuations: The current definition of "greedy" focuses on player-allocation pairs. It doesn't yet cover algorithms that award items one-by-one based on marginal gain (common in submodular optimization).
  • Adaptive Greedy with Correlated Types: The $4c$ bound for correlated types currently only applies to non-adaptive greedy algorithms. Extending this to adaptive versions remains an open challenge.

Summary updated

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.
BibTeX
@inproceedings{lucier2010price,
  author = {Brendan Lucier and Allan Borodin},
  title = {{Price of Anarchy for Greedy Auctions}},
  booktitle = {SODA},
  year = {2010},
  url = {https://openreview.net/forum?id=AFVubBtiioe},
}

Loading related content...

Figure