BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Optimization and Incentives Seminar
SUMMARY:Algorithms as Mechanisms: The Price of Anarchy of
Relax and Round - Paul DÃ¼tting (LSE)
DTSTART;TZID=Europe/London:20141118T140000
DTEND;TZID=Europe/London:20141118T150000
UID:TALK56146AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/56146
DESCRIPTION:Many algorithms\, that are originally designed wit
hout explicitly considering incentive properties\,
are later combined with simple pricing rules and
used as mechanisms. The resulting mechanisms are o
ften natural and simple to understand. But how goo
d are these algorithms as mechanisms? Truthful rep
orting of valuations is typically not a dominant s
trategy (certainly not with a pay-your-bid\, first
-price rule\, but it is likely not a good strategy
even with a critical value\, or second-price styl
e rule either). Our goal is to\nshow that a wide c
lass of approximation algorithms yields this way m
echanisms with low Price of Anarchy.\n\nThe semina
l result of Lucier and Borodin [SODA'10] shows tha
t combining a greedy algorithm that is an alpha-ap
proximation algorithm with a pay-your-bid payment
rule yields a mechanism whose Price of Anarchy is
O(alpha). In this paper we significantly extend th
e class of algorithms for which such a result is a
vailable by showing that this close connection bet
ween approximation ratio on the one hand and Price
of Anarchy on the other also holds for the design
principle of relaxation and rounding provided tha
t the relaxation is smooth and the rounding is obl
ivious.\n\nWe demonstrate the far-reaching consequ
ences of our result by showing its implications fo
r sparse packing integer programs\, such as multi-
unit auctions and generalized matching\, for the m
aximum traveling salesman problem\, for combinator
ial auctions\, and for single source unsplittable
flow problems. In all these problems our approach
leads to novel simple\, near-optimal mechanisms wh
ose Price of Anarchy either matches or beats the p
erformance guarantees of known mechanisms.\n\nJoin
t work with Thomas Kesselheim and Eva Tardos
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberfor
ce Road\, Cambridge
CONTACT:Felix Fischer
END:VEVENT
END:VCALENDAR