Optimal Candidate Positioning in Multi-Issue Elections

Abstract

We study strategic candidate positioning in multidimensional spatial-voting elections. Voters and candidates are represented as points in ${\mathbb{R}}^d$, and each voter supports the candidate that is closest under a distance induced by an ${\ell }_p$-norm. We prove that computing an optimal location for a new candidate is NP-hard already against a single opponent, whereas for a constant number of issues the problem is tractable: an $O(n^{d+1})$ hyperplane-enumeration algorithm and an $O(n\log n)$ radial-sweep routine for $d=2$ solve the task exactly. We further derive the first approximation guarantees for the general multi-candidate case and show how our geometric approach extends seamlessly to positional-scoring rules such as $k$-approval and Borda. These results clarify the algorithmic landscape of multidimensional spatial elections and provide practically implementable tools for campaign strategy.

18 pages, 3 figures, Ecai 25