Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences
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 $\ell_1$, $\ell_2$ and $\ell_\infty$, 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 $\ell_2$ (resp. $\ell_1,\ell_{\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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem
In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements…
Towards Foundation Models for Consensus Rank Aggregation
Aggregating a consensus ranking from multiple input rankings is a fundamental problem with applications in recommendation systems, search engines, job recruitment, and elections. Despite decades of research in consensus …
Reinforcement LearningRecommendation SystemsOptimal majority rules and quantitative Condorcet properties of setwise Kemeny voting schemes
The important Kemeny problem, which consists of computing median consensus rankings of an election with respect to the Kemeny voting rule, admits important applications in biology and computational social choice and was …
Space reduction techniques for the $3$-wise Kemeny problem
Kemeny's rule is one of the most studied and well-known voting schemes with various important applications in computational social choice and biology. Recently, Kemeny's rule was generalized via a set-wise approach by Gi…
A new social welfare function with a number of desirable properties
By relaxing the dominating set in three ways (e.g., from "each member beats every non-member" to "each member beats or ties every non-member, with an additional requirement that at least one member beat every non-member"…
Relation