Quantifying Incentive Compatibility of Ranking Systems

Abstract

Reasoning about agent preferences on a set of alternatives, and the aggregation of such preferences into some social ranking is a fundamental issue in reasoning about multi-agent systems. When the set of agents and the set of alternatives co-incide, we get the ranking systems setting. A famous type of ranking systems are page ranking systems in the context of search engines. Such ranking systems do not exist in empty space, and therefore agents ’ incentives should be carefully considered. In this paper we define three measures for quan-tifying the incentive compatibility of ranking systems. We apply these measures to several known ranking systems, such as PageRank, and prove tight bounds on the level of incentive compatibility under two basic properties: strong monotonic-ity and non-imposition. We also introduce two novel non-imposing ranking systems, one general, and the other for the case of systems with three participants. A full axiomatization is provided for the latter.