We consider directed graphs over a set of agents, where an edge (i,j) is taken to mean that agent i trusts or supports agent j. Given such a graph, our goal is to select a subset of agents of fixed size that maximizes the sum of indegrees, that is, a subset of most popular or most trusted agents. On the other hand, each agent is only interested in being selected, and may misreport its outgoing edges to this end. This problem formulation captures realistic scenarios where agents choose among themselves, in the context of, e.g., social networks such as Twitter, reputation systems such as Epinions, and Internet search.
We wish to design mechanisms|functions that map graphs to selected subsets (without making payments)|which satisfy two constraints: strategy proofness, i.e., agents cannot benefit from misreporting their outgoing edges; and approximation, that is, the mechanism must always select a subset of agents that is close to optimal in terms of the sum of indegrees. Our first major result is a surprising impossibility: no deterministic strategy proof mechanism can yield a nite approximation ratio for any k 2 f1; : : : ; n????1g, where k is the size of the selected subset and n is the number of agents. Our second major result is a randomized strategy proof mechanism that yields an approximation ratio of four for any value of k, and provides a ratio that approaches one as k grows.