Abstract

Deferred-acceptance auctions are mechanisms that are based on backward-greedy algorithms and possess a number of remarkable incentive properties, including implementation as an obviously-strategyproof ascending auction. All existing work on DA auctions considers only binary single-parameter problems, where each bidder either "wins" or "loses." We generalize the DA auction framework to non-binary settings, and apply this generalized framework to obtain approximately welfare-maximizing DA auctions for a number of basic mechanism design problems: multi-unit auctions, problems with polymatroid constraints or multiple knapsack constraints, and the problem of scheduling jobs to minimize their total weighted completion time. Our results require the design of novel backward-greedy algorithms with good approximation guarantees.