Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches

We study two-party policy competition as a two-player game in which each party selects a policy vector from a compact subset of Rk and voters evaluate policies via inner products with their preference vectors. We model electoral uncertainty by an affine isotone winning-probability function of the total utility difference across all voters, and define payoffs as supporters' expected utility. We prove existence of a pure-strategy Nash equilibrium (PSNE) in both one- and multi-dimensional settings, with a closed-form characterization in one dimension. Although the game is not monotone in general, experiments (see the full version) suggest decentralized gradient-based dynamics typically converge quickly to approximate PSNE. Finally, we give a polynomial-time grid-based algorithm to compute an ε-approximate PSNE.