Deferred-Acceptance Auctions: Performance and Generalizations
Deferred-acceptance auctions are mechanisms whose allocation rule can be implemented using an adaptive reverse greedy algorithm. These auctions were introduced by Milgrom and Segal, who proved that they satisfy remarkable incentive guarantees that previously studied mechanisms do not possess. We first provide an overview of social welfare approximation bounds regarding the performance of deferred-acceptance auctions in the presence of single-minded bidders. Then, we generalize the definition of deferred-acceptance auctions beyond single-minded bidder settings and provide examples of generalized deferred-acceptance auctions.