Incentive-Compatible Classification

We investigate the possibility of an incentive-compatible (IC, a.k.a. strategy-proof) mechanism for the classification of agents in a network according to their reviews of each other. In the α -classification problem we are interested in selecting the top α fraction of users. We give upper bounds (impossibilities) and lower bounds (mechanisms) on the worst-case coincidence between the classification of an IC mechanism and the ideal α -classification. We prove bounds which depend on α and on the maximal number of reviews given by a single agent, Delta . Our results show that it is harder to find a good mechanism when α is smaller and Delta is larger. In particular, if Delta is unbounded, then the best mechanism is trivial (that is, it does not take into account the reviews). On the other hand, when Delta is sublinear in the number of agents, we give a simple, natural mechanism, with a coincidence ratio of α .