Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.13841 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909743480569856 |
|---|---|
| author | Cleveland, Colin de Keijzer, Bart Polukarov, Maria |
| author_facet | Cleveland, Colin de Keijzer, Bart Polukarov, Maria |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Candidate Positioning in Multi-Issue Elections Cleveland, Colin de Keijzer, Bart Polukarov, Maria Computer Science and Game Theory 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. |
| title | Optimal Candidate Positioning in Multi-Issue Elections |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2508.13841 |