# Nash equilibrium question

(Hotelling’s voting model) Consider a population of voters uniformly distributed along the ideological spectrum from left (x = 0) to right (x = 1). There are two candidates i = 1,2 for a single ofﬁce and they choose their ideological positions $x_i$ $\in$ [0,1] simultaneously. Voters observe the choices of the candidates and then each voter votes for the candidate whose position is closest to the voter’s ideological position. If the candidates choose $x_1$ = .3 and $x_2$ = .6, for instance, then any voter to the left of 0.45 votes for candidate 1 and anyone to the right of 0.45 votes for candidate 2. Therefore, candidate 1 gets 45% of votes and 2 gets 55% so the winner is candidate 2. If both candidates choose the same position, the votes are split equally, and the winner is chosen by ﬂipping a fair coin. Suppose that the candidates care only about their chance of winning, and are not at all interested in ideology

Suppose there are three candidates. Show that in any pure strategy Nash equilibrium: (i) there is a player who wins for sure, (ii) the winner’s position is the most left or the most right among the three candidates, (iii) if the winner is in the most left, then the positions of both losers are strictly to the right of 1/2, and the position of the winner must be strictly between 0 and 1/2. (iv) For any x $\in$ (0,1/2), construct a pure strategy Nash equilibrium in which the winner’s position is x .

Sorry, since it's game theory, I wasn't sure where to post this, but it is very brainteaser-ish to me and I thought the math people might be able to take a stab at it

-
We can't do much with it if you leave out the most important parts of the question. What are the rules of the game? – Robert Israel Oct 16 '11 at 21:22
I just realized that. I've been staring at this so long I forgot others didn't know the rules – candlewick Oct 16 '11 at 21:22
@candlewick: do you know how to calculate best responses? – Ilya Oct 16 '11 at 21:46

Better late than never.

(i) Suppose the winner does not win for sure (was determined by coin flip). Then there must either be one (1) other candidate who got the same number of votes (but lost the coin flip), or (2) two other candidates. If (1), then the candidate who did not have the same number of votes as the winners can strictly improve by taking the same position, which gives 1/3 of the votes (chances increase from probability 0 to 1/3). If (2) then all candidates are on the same point, so an $\epsilon$ deviation to the left or right will give at least $50%-\epsilon>1/3$ of the votes, hence winning the election for sure.

(ii) If the winner were in the middle, the outer candidates have a profitable deviation to move closer to the middle candidate, until only an $\epsilon$ is left, which is not sufficient to win.

(iii) Suppose that also another candidate is in the left half including 1/2 (but right to the winner, see ii). This is not an equilibrium, because the most right candidate could then win by moving left to 1/2 (or to $1/2+\epsilon$ if one is at 1/2) and getting the majority of votes.

(iv) This is one of the cases where it matters whether parties care about the number of votes or chances of winning. Nice, took me a while.

The winner's position is $x\in(0,1/2)$. Proposed equilibrium positions: $$[1]~(x, 1-x, 1-x) \text{ if } x>1/4,$$ $$[2]~ (x,x+\frac{2(1-x)}{3},x+\frac{2(1-x)}{3}) \text{ if }x<1/4.$$ For this to be an equilibrium, the other two candidates must not have a profitable deviation. Both losers have the same amount of votes (same position) and lose. Deviating an $\epsilon$ to the right still loses the election, because $x>x-\epsilon$. Using [1], deviating to the left exactly between winner and remaining candidate gives $\frac{1-2x}{2}-x<0\Leftrightarrow x>1/4$. Hence, it would be profitable to deviate for $x<1/4$ using [1] ($(x,1-x,1-x)$). However, using [2] ($(x,x+\frac{2(1-x)}{3},x+\frac{2(1-x)}{3})$) for the case $x<1/4$ shows that the middle deviation is not profitable (receives only $x/3$ of votes and loses). Deviating left to the winner gives less than $x$ with [1], so now the rightmost candidate wins the election. With [2], the deviation left to the winner is profitable only if $x-\epsilon-\frac{1-x}{3}>0\Leftrightarrow x>(1+\epsilon)/4$, but we use this candidate only for $x<1/4$, so we are fine.

Finally, there is no profitable deviation for the winner: going to the left means losing votes to the losers, going to the right might increase the number of votes, but this is not profitable since he already wins for sure at the proposed positions. Note for $x=1/4$ we can use either [1] or [2] and candidates will be indifferent between deviating and staying, which sustains the equilibrium.

-