On the Weighted Top-Difference Distance: Axioms, Aggregation, and Approximation

Andrea Aveni, Ludovico Crippa and Giulio Principi

Papers from arXiv.org

Abstract: We study a family of distance functions on rankings that allow for asymmetric treatments of alternatives and consider the distinct relevance of the top and bottom positions for ordered lists. We provide a full axiomatic characterization of our distance. In doing so, we retrieve new characterizations of existing axioms and show how to effectively weaken them for our purposes. This analysis highlights the generality of our distance as it embeds many (semi)metrics previously proposed in the literature. Subsequently, we show that, notwithstanding its level of generality, our distance is still readily applicable. We apply it to preference aggregation, studying the features of the associated median voting rule. It is shown how the derived preference function satisfies many desirable features in the context of voting rules, ranging from fairness to majority and Pareto-related properties. We show how to compute consensus rankings exactly, and provide generalized Diaconis-Graham inequalities that can be leveraged to obtain approximation algorithms. Finally, we propose some truncation ideas for our distances inspired by Lu and Boutilier (2010). These can be leveraged to devise a Polynomial-Time-Approximation Scheme for the corresponding rank aggregation problem.

Date: 2024-03, Revised 2024-03
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2403.15198 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2403.15198

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().