×

zbMATH — the first resource for mathematics

Axiomatic foundations for ranking systems. (English) Zbl 1183.68613
Summary: 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. In this paper we present an extensive axiomatic study of ranking systems. In particular, we consider two fundamental axioms: Transitivity, and Ranked Independence of Irrelevant Alternatives. Surprisingly, we find that there is no general social ranking rule that satisfies both requirements. Furthermore, we show that our impossibility result holds under various restrictions on the class of ranking problems considered. However, when transitivity is weakened, an interesting possibility result is obtained. In addition, we show a complete axiomatization of approval voting using ranked IIA.

MSC:
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: Link