BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Performance of Deferred-Acceptance Heuristic Auctions - Paul D
 uetting\, Stanford University
DTSTART:20140317T110000Z
DTEND:20140317T120000Z
UID:TALK51210@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Deferred-acceptance heuristic auctions are auctions that have 
 an allocation rule that can be implemented using an adaptive reverse greed
 y algorithm. Milgrom and Segal (2013) recently introduced these auctions a
 nd 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\, an
 d admit outcome-equivalent full-information pay-as-bid versions. Forward g
 reedy algorithms --- and the VCG mechanism\, for that matter --- do not ge
 nerally possess any of these additional incentive properties.\n\nAre there
  computationally efficient auctions in the deferred-acceptance framework t
 hat match the performance of (forward) greedy mechanisms\, or even of the 
 best polynomial-time algorithm\, or is there an intrinsic trade-off betwee
 n the strength of the incentive guarantees and the best-possible approxima
 tion factor?  We study welfare-maximization with single-minded bidders ---
  the original application of greedy algorithms to algorithmic mechanism de
 sign --- and give novel mechanisms that achieve the best of both worlds: t
 he incentive guarantees of a deferred-acceptance heuristic auction\, and a
 pproximation guarantees close to the best possible.\n\nJoint work with Vas
 ilis Gkatzelis and Tim Roughgarden
LOCATION:Auditorium\, Microsoft Research Ltd\, 21 Station Road\, Cambridge
 \, CB1 2FB
END:VEVENT
END:VCALENDAR