Equilibria in a Hypercube Spatial Voting Model

We give conditions for equilibria in the following Voronoi game on the discrete hypercube. Two players position themselves in $\{0,1\}^d$ and each receives payoff equal to the measure (under some probability distribution) of their Voronoi cell (the set of all points which are closer to them than to the other player). This game can be thought of as a discrete analogue of the Hotelling--Downs spatial voting model in which the political spectrum is determined by $d$ binary issues rather than a continuous interval. We observe that if an equilibrium does exist then it must involve the two players co-locating at the majority point (ie the point representing majority opinion on each separate issue). Our main result is that a sufficient condition for an equilibrium is that on each issue the majority option is held by at least $\frac{3}{4}$ of voters. The value $\frac{3}{4}$ can be improved slightly in a way that depends on $d$ and with this improvement the result is best possible. We give similar sufficient conditions for the existence of a local equilibrium. We also analyse the situation where the distribution is a mix of two product measures. We show that either there is an equilibrium or the best response to the majority point is its antipode.
Comment: 11 pages