BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Algorithms as Mechanisms: The Price of Anarchy of Relax and Round 
 - Paul Dütting (LSE)
DTSTART:20141118T140000Z
DTEND:20141118T150000Z
UID:TALK56146@talks.cam.ac.uk
CONTACT:Felix Fischer
DESCRIPTION:Many algorithms\, that are originally designed without explici
 tly considering incentive properties\, are later combined with simple pric
 ing rules and used as mechanisms. The resulting mechanisms are often natur
 al and simple to understand. But how good are these algorithms as mechanis
 ms? Truthful reporting of valuations is typically not a dominant strategy 
 (certainly not with a pay-your-bid\, first-price rule\, but it is likely n
 ot a good strategy even with a critical value\, or second-price style rule
  either). Our goal is to\nshow that a wide class of approximation algorith
 ms yields this way mechanisms with low Price of Anarchy.\n\nThe seminal re
 sult of Lucier and Borodin [SODA'10] shows that combining a greedy algorit
 hm that is an alpha-approximation algorithm with a pay-your-bid payment ru
 le yields a mechanism whose Price of Anarchy is O(alpha). In this paper we
  significantly extend the class of algorithms for which such a result is a
 vailable by showing that this close connection between approximation ratio
  on the one hand and Price of Anarchy on the other also holds for the desi
 gn principle of relaxation and rounding provided that the relaxation is sm
 ooth and the rounding is oblivious.\n\nWe demonstrate the far-reaching con
 sequences of our result by showing its implications for sparse packing int
 eger programs\, such as multi-unit auctions and generalized matching\, for
  the maximum traveling salesman problem\, for combinatorial auctions\, and
  for single source unsplittable flow problems. In all these problems our a
 pproach leads to novel simple\, near-optimal mechanisms whose Price of Ana
 rchy either matches or beats the performance guarantees of known mechanism
 s.\n\nJoint work with Thomas Kesselheim and Eva Tardos
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR