Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.10290 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915790577467392 |
|---|---|
| author | Cleveland, Colin de Keijzer, Bart Polukarov, Maria |
| author_facet | Cleveland, Colin de Keijzer, Bart Polukarov, Maria |
| contents | We study the computational complexity of strategic behaviour in primary elections. Unlike direct voting systems, primaries introduce a multi-stage process in which voters first influence intra-party nominees before a general election determines the final winner. While previous work has evaluated primaries via welfare distortion, we instead examine their game-theoretic properties. We formalise a model of primaries under first-past-the-post with fixed tie-breaking and analyse voters' strategic behaviour. We show that determining whether a pure Nash equilibrium exists is $Σ_2^{\mathbf P}$-complete, computing a best response is NP-complete, and deciding the existence of subgame-perfect equilibria in sequential primaries is PSPACE-complete. These results reveal that primaries fundamentally increase the computational difficulty of strategic reasoning, situating them as a rich source of complexity-theoretic challenges within computational social choice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10290 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Strategic Behavior in Primary Elections Cleveland, Colin de Keijzer, Bart Polukarov, Maria Computer Science and Game Theory Computational Complexity F.1.3 We study the computational complexity of strategic behaviour in primary elections. Unlike direct voting systems, primaries introduce a multi-stage process in which voters first influence intra-party nominees before a general election determines the final winner. While previous work has evaluated primaries via welfare distortion, we instead examine their game-theoretic properties. We formalise a model of primaries under first-past-the-post with fixed tie-breaking and analyse voters' strategic behaviour. We show that determining whether a pure Nash equilibrium exists is $Σ_2^{\mathbf P}$-complete, computing a best response is NP-complete, and deciding the existence of subgame-perfect equilibria in sequential primaries is PSPACE-complete. These results reveal that primaries fundamentally increase the computational difficulty of strategic reasoning, situating them as a rich source of complexity-theoretic challenges within computational social choice. |
| title | The Complexity of Strategic Behavior in Primary Elections |
| topic | Computer Science and Game Theory Computational Complexity F.1.3 |
| url | https://arxiv.org/abs/2602.10290 |