Abstract

Deferred-acceptance heuristic auctions are auctions that have an allocation rule that can be implemented using an adaptive reverse greedy algorithm. Milgrom and Segal (2013) recently introduced these auctions and proved that they satisfy a remarkable list of incentive guarantees: in addition to being dominant-strategy incentive-compatible, they are weakly group-strategyproof, can be implemented by ascending-clock auctions, and admit outcome-equivalent full-information pay-as-bid versions. Forward greedy algorithms— and the VCG mechanism, for that matter— do not generally possess any of these additional incentive properties.

Are there computationally efficient auctions in the deferred-acceptance framework that match the performance of (forward) greedy mechanisms, or even of the best polynomial-time algorithm, or is there an intrinsic trade-off between the strength of the incentive guarantees and the best-possible approximation factor? We study welfare-maximization with single-minded bidders— the original application of greedy algorithms to algorithmic mechanism design— and give novel mechanisms that achieve the best of both worlds: the incentive guarantees of a deferred-acceptance heuristic auction, and approximation guarantees close to the best possible.

Joint work with Vasilis Gkatzelis and Tim Roughgarden