Recognising Multidimensional Euclidean Preferences

Dominik PetersAAAI 2017 · DOI

Abstract

In social choice theory, the spatial model of voting assumes that voters and candidates can be represented as points in a $d$-dimensional Euclidean space. While identifying such embeddings in one dimension is computationally efficient, the complexity for higher dimensions has long remained an open question. This paper proves that recognizing $d$-dimensional Euclidean preferences is $\exists\mathbb{R}$-complete for any fixed $d \ge 2$. This result implies that the problem is not only NP-hard but also potentially requires exponential space to represent solutions, posing significant challenges for practical applications in multidimensional unfolding.

Introduction

The spatial model of preferences is a cornerstone of political science and economics. In this model, a voter prefers candidate $A$ over candidate $B$ if $A$ is closer to the voter's ideal point in some $d$-dimensional space. This "multidimensional unfolding" allows researchers to uncover the latent structure of political competition. For $d=1$, preferences are "single-peaked," and recognition is a well-solved problem. However, as this research demonstrates, the transition from one to two dimensions introduces a massive jump in computational complexity.

The Complexity of Spatial Choice

The core finding of this work is that recognizing $d$-Euclidean preferences is complete for the Existential Theory of the Reals ($\exists\mathbb{R}$). This complexity class characterizes problems that involve solving systems of polynomial inequalities over real numbers. $\exists\mathbb{R}$ lies between NP and PSPACE; thus, $\exists\mathbb{R}$-completeness implies NP-hardness and suggests that the problem may not even be in NP.

The proof relies on a reduction from $d$-REALISABILITY, a known hard problem concerning whether a combinatorial description of hyperplane intersections can be realized in Euclidean space.

The Reduction Strategy

The reduction transforms an instance of hyperplane realization into a preference recognition problem. By carefully placing "witness" points and candidates, the author forces any valid Euclidean embedding to mirror the structure of the hyperplane arrangement.

A visualization of the reduction from hyperplane arrangements to spatial preferences, showing points $a_i, b_i$ and hyperplanes $h_j$ within concentric rings.

As shown in the figure above, the construction uses concentric rings and specific point placements ($a_i, b_i$) to constrain the geometry. This ensures that the only way to satisfy the preference rankings is to recreate the specific hyperplane intersections of the original $d$-REALISABILITY instance.

Representation and Forbidden Patterns

A significant consequence of $\exists\mathbb{R}$-completeness is the "bit complexity" trap. The paper proves that some Euclidean preference profiles require coordinates with an exponential number of bits ($2^{\Omega(n+m)}$) to be represented accurately. This means that even if a solution exists, it might be too large to write down in polynomial time.

Geometric construction illustrating the constraints on point $p_i$ relative to circles and tangent lines in the embedding.

Furthermore, the research shows that unlike many other preference structures, $d$-Euclidean preferences cannot be identified by a finite list of "forbidden" sub-patterns. This lack of local characterization means that one must consider the entire profile globally to determine its Euclidean-ness.

Key Results and Metrics

The study also explores variations of the problem:

  • Dichotomous Preferences: Even when voters only provide "approve/disapprove" labels, the recognition problem remains $\exists\mathbb{R}$-complete.
  • Alternative Metrics: Interestingly, the difficulty is specific to the $L_2$ (Euclidean) metric. If one uses the $L_1$ (Manhattan) or $L_\infty$ (Chebyshev) metrics, the problem becomes significantly easier, falling back into NP.

Conclusion

The theoretical results are bolstered by experimental evidence. Using the state-of-the-art nlsat solver on real-world data from PrefLib, the author found that non-trivial profiles could not be resolved within reasonable time limits. This highlights the practical infeasibility of exact recognition for large datasets. Future work should focus on approximation heuristics or the use of alternative metrics that offer better computational tractability while still capturing the multidimensional nature of human preferences.

Summary updated

BibTeX
@inproceedings{peters2017recognising,
  author = {Dominik Peters},
  title = {{Recognising Multidimensional Euclidean Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10616},
}
Figure