Stelios Stylianou

Four-player equilibria on the discrete hypercube.

We consider a four-player game on the discrete hypercube $Q_n = \{0,1\}^n$, where each of the four players has chosen a single vertex of the hypercube (and these vertices need not be distinct). Such a position is called a {\em profile}. Imagine there is a voter at every vertex, and each voter gives their vote to whichever player is closest to them, in terms of Hamming distance. (If multiple players are tied for this smallest distance, the vote is divided equally between them.) The {\em score} of a player is the total number of votes they get. This has a natural interpretation in terms of voting theory: imagine there are $n$ binary issues and that voters are uniformly distributed in their positions on these issues, and view the players as political candidates competing for vote share. An interesting question, from the perspective of voting theory, is to determine whether a Nash equilibrium can occur, that is, whether there exists a situation where no candidate has an incentive to alter their position in order to get more votes. Motivated by this, we say that a profile is an {\em equilibrium} if no player can strictly increase their score by moving to a different vertex, while the other players maintain their original positions. A profile is said to be {\em balanced} if, in each of the $n$ coordinates, two players have chosen 0, and two players have chosen 1. We prove that a four-player profile is an equilibrium if and only if it is balanced, proving a conjecture of Day and Johnson. We will also discuss a generalisation of this problem where there are $k \neq 4$ players. The main question of interest is to determine, for each fixed $k$, whether there exist $k$-player equilibria for infinitely many $n$. We will explain why every two-player profile is an equilibrium, and mention examples of three-player equilibria. The above question remains open for every $k>4$.