Price of Anarchy for Greedy Auctions - Lucier, Brendan; Borodin, Allan (Symposium on Discrete Algorithms (SODA) 2010, 2010)
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.