Computer Science Theory Seminar

Vasilis GkatzelisDrexel University
Deferred-acceptance auctions: worst-case approximation guarantees

Monday, September 18, 2017 - 4:00pm
Gates 122

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.