Stelios Stylianou

A two-player voting game in Euclidean space

Suppose we fix a finite collection S of points in R^d, which we regard as the locations of voters (in a d-dimensional political spectrum). Two players (candidates), Alice and Bob, are playing the following game. Alice goes first and chooses any point A in R^d. Bob can then choose any point B in R^d, knowing what A is. A voter V positioned at x will vote for Alice if d(x,A) < d(x,B), and will vote for Bob if d(x,A) > d(x,B), where d denotes Euclidean distance. If x is equidistant from A and B, then V will not vote for anyone. The candidate with the greatest number of votes wins. If they both get the same number of votes, then (by convention) Alice is declared the winner.

When d=1, it is easy to see that Alice can always win this game by choosing A to be the median of S. This observation was first made by Hotelling in the 1920s; he referred to this model (in one dimension) as the Median Voter Model. When d > 1 however, the game is sometimes an Alice win and sometimes a Bob win, depending on the structure of S. We completely characterize the sets S for which Alice wins in dimensions > 1, showing that the game is usually won by Bob, unless S has a specific structure. We will then briefly talk about an algorithm that can be used to identify the (unique) winning point for Alice, if the game is an Alice win, and if time permits we will discuss a related result saying that Alice can always get at least |S|/(d+1) votes, for an arbitrary finite set S.

Based on joint work with (subsets of) David Ellis and Robert Johnson.