"On the Limits of Dictatorial Classification" Speaker: Reshef Meir, The Hebrew University Date: Wednesday, 2 December 2009 Time: 12noon Place: Ross 201 This talk is a continuation of a talk given in March 2009 in the Critical MAS seminar, but it is self-contained. Abstract: In the strategyproof classification setting, a set of labeled examples is partitioned among multiple agents. Given the reported labels, an optimal classification mechanism returns a classifier that minimizes the number of mislabeled examples. However, each agent is interested in the accuracy of the returned classifier on its own examples, and may misreport its labels in order to achieve a better classifier, thus contaminating the dataset. The goal is to design strategyproof mechanisms that correctly label as many examples as possible. In previous work we investigated the foregoing setting under limiting assumptions, or with respect to very restricted classes of classifiers. In this talk, we study the strategyproof classification setting with respect to prominent classes of classifiers---boolean conjunctions and linear separators---and without any assumptions on the input. Our main result is negative, showing that strategyproof mechanisms cannot achieve a constant approximation ratio. This is by constructing a reduction from a voting problem and applying the Gibbard-Satterthwaite theorem. On the positive side, we present a randomized mechanism---Iterative Random Dictator---and demonstrate both that it is strategyproof and that its approximation ratio does not increase with the number of agents. Interestingly, the notion of dictatorship is prominently featured in all our results, helping to establish both upper and lower bounds. This is a joint work with Ariel Procaccia and Jeff Rosenschein.