Abstract:
We consider a setting where each member of a set of agents either approves or disapproves of any other agent in the set, and we are supposed to select a subset of k agents for a given value of k. We want the sum of approval scores of the selected agents to be as large as possible, and we want the selection to be strategyproof in the sense that no agent can influence his own chances of being selected by changing his vote. We give a (randomized) strategyproof mechanism without payments for which the expected sum of approval scores is at least 1/4 of the optimum. Surprisingly, no deterministic strategyproof mechanism without payments can guarantee a finite ratio. The latter is also true for randomized mechanisms that satisfy group-strategyproofness, i.e., for which no set of agents can change their votes such that all of them gain.

This talk is about joint work with Noga Alon, Ariel Procaccia, and Moshe Tennenholtz.