The Performance of Deferred-Acceptance Heuristic Auctions

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

• Paul Duetting, Stanford University
• Monday 17 March 2014, 11:00-12:00
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.