Computer Science Theory Seminar
Deferred-acceptance auctions are mechanisms whose allocation rule needs to use an adaptive reverse greedy algorithm. Economists recently introduced these auctions and proved that they satisfy remarkable incentive guarantees that make them very practical. However, we have a very limited understanding of the extent to which such reverse greedy algorithms can provide desirable worst-case approximation guarantees. Computer scientists have analyzed several forward greedy algorithms in the past, but we show that reverse greedy algorithms are much more complicated (e.g., they do not even guarantee maximality). In this talk we first study the limitations of this class of algorithms, and then we design new approximation algorithms from this class, which induce novel deferred-acceptance auctions.