Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences

DOI10.1016/J.DAM.2022.05.009MaRDI QIDQ2146734zbMATH OpenOpenAlexWikidataFDO

Authors Olivier Spanjaard, Magdaléna Tydrichová, Bruno Escoffier

Publication date 21 June 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.13054

zbMATH Keywords

computational complexityEuclidean preferencesKemeny ranking

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Individual preferences (91B08)

Abstract: The assumption that voters' preferences share some common structure is a standard way to circumvent NP-hardness results in social choice problems. While the Kemeny ranking problem is NP-hard in the general case, it is known to become easy if the preferences are 1-dimensional Euclidean. In this note, we prove that the Kemeny ranking problem remains NP-hard for $k$-dimensional Euclidean preferences with $k!ge!2$ under norms $el{l}_1$, $el{l}_2$ and $el{l}_{i}nfty$, by showing that any weighted tournament (resp. weighted bipartite tournament) with weights of same parity (resp. even weights) is inducible as the weighted majority tournament of a profile of 2-Euclidean preferences under norm $el{l}_2$ (resp. $el{l}_1,el{l}_{infty}$), computable in polynomial time. More generally, this result regarding weighted tournaments implies, essentially, that hardness results relying on the (weighted) majority tournament that hold in the general case (e.g., NP-hardness of Slater ranking) are still true for 2-dimensional Euclidean preferences.

Recommendations

• Computing kemeny rankings from d-Euclidean preferences
• Strategyproof and efficient preference aggregation with Kemeny-based criteria
• On weights and quotas for weighted majority voting games
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• A survey on the linear ordering problem for weighted or unweighted tournaments
• Condorcet choice correspondences for weak tournaments
• Ranking of Weighted Majority Rules
• Two effective total ranking models for preference voting and aggregation
• Publication:3199160
• Consensus among preference rankings: a new weighted correlation coefficient for linear and weak orderings

Cites work

• A characterization of the single-peaked single-crossing domain
• A Polynomial Time Algorithm for Unidimensional Unfolding Representations
• Computing kemeny rankings from d-Euclidean preferences
• Foundations of spatial preferences
• scientific article; zbMATH DE number 3148878 (Why is no real title available?)
• scientific article; zbMATH DE number 4005933 (Why is no real title available?)
• Intermediate Preferences and the Majority Rule
• Recognizing one-dimensional Euclidean preference profiles
• Social choice and individual values
• Social Preference Orderings and Majority Rule
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(4)

• Computing kemeny rankings from d-Euclidean preferences
• Recognizing 1-Euclidean preferences: an alternative approach
• Weighted tournament solutions
• Euclidean preferences in the plane under \(\ell_1,\ell_2\) and \(\ell_\infty\) norms

This page was built for publication: Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2146734)