Computing Nash Equilibria for District-based Nominations

We study political parties that strategically place their candidates in districts so to maximise the number of their nominees that get elected. In each district, voters rank the nominated candidates and elect the plurality winners. After studying equilibrium existence in restricted instances, we show that deciding the existence of pure Nash equilibria for these games is NP-complete if party size is bounded by a constant and Σ P 2-complete for the general case. For the hardness part of the latter result we reduce from ∃∃!-3sat.