University of Cambridge > Talks.cam > Microsoft Research Cambridge, public talks > The Performance of Deferred-Acceptance Heuristic Auctions

The Performance of Deferred-Acceptance Heuristic Auctions

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

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

This talk is part of the Microsoft Research Cambridge, public talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity