BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260723T140945Z
UID:Seminar-dept-357@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20141014T130000
DTEND:20141014T140000
SUMMARY:School Seminar Series
DESCRIPTION:Aris Filos-Ratsikas: Truthful approximations to range voting\n\nWe consider the fundamental mechanism design problem of \n\napproximate social welfare maximization under general cardinal\n\npreferences on a finite number of alternatives and without\n\nmoney. The well-known range voting scheme can be thought of as\n\na non-truthful mechanism for exact social welfare maximization in this\n\nsetting.  With m being the number of alternatives, we exhibit a\n\nrandomized truthful-in-expectation ordinal mechanism with \n\napproximation ratio \Omega(m^{-3/4}). On the other hand, we show \n\nthat for sufficiently many agents, the approximation ratio of any\n\ntruthful-in-expectation ordinal mechanism is  O(m^{-2/3}). We supplement \n\nour results with an upper bound for any truthful mechanism. We get tighter \n\nbounds for the natural special case of $m = 3$, and in that case furthermore\n\nobtain separation results concerning the approximation ratios achievable by \n\nnatural restricted classes of truthful-in-expectation mechanisms. In particular, \n\nwe show that the best cardinal truthful mechanism strictly outperforms all ordinal ones.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=357
LOCATION:Ashton Lecture Theater
END:VEVENT
END:VCALENDAR