Quantifying Incentive Compatibility of Ranking Systems

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Multiagent Systems

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 coincide, 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 quantifying 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 monotonicity 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.