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

arXiv: https://arxiv.org/abs/2106.13054 · HTML: https://mlsanity.com/paper/2106.13054/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 22 references that are in the map.
- First posted on arXiv 24 Jun 2021.

## Builds on (most cited first, 1 of 1)

- [Recognising Multidimensional Euclidean Preferences](https://mlsanity.com/paper/1602.08109/) (2016)

## Built on by (most cited first, 1 of 1)

- [Diversity of Structured Domains via k-Kemeny Scores](https://mlsanity.com/paper/2509.15812/) (2025)

## Abstract (arXiv)

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!≥!2 under norms ℓ1, ℓ2 and ℓ_∞, 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 ℓ2 (resp. ℓ1,ℓ∞), 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.