A conjecture about the subgame perfect equilibria of a model of sequential location
author
history
The conjecture described on this page arose during joint work with Amoz Kats in the mid-1980s. It remains unproved and uncontradicted.
conjecture
The simple extensive game described here appears to have a unique subgame perfect equilibrium outcome. The game is of interest for two reasons. First, the character of the conjectured equilibrium is related to "Duverger's Law" when the game is interpreted as modeling the location decisions of political candidates. Second, despite the simplicity of the structure of the conjectured equilibrium, a proof appears to require a rather "deep" argument. We present the conjecture in the hope that someone will provide a proof.
Each of the players 1, ..., n chooses a member of the set [0,1] ⋃ {OUT} (i.e. either chooses a "position" or opts out). The choices are made sequentially (starting with player 1), and every player is perfectly informed at all times. The outcome of the game is determined as follows. After all players have chosen their actions, each player who has chosen a position receives votes from a continuum of citizens; the player who receives the most votes wins. The distribution of citizens' ideal points is nonatomic, with support [0,1]. A player who chooses the same position y as k − 1 other players obtains the fraction 1/k of the votes of all the citizens whose ideal points are closer to y than to any other chosen position. (In particular, voting is "sincere".) Each player obtains the payoff 0 if she chooses OUT, the payoff 1/k if she is among the k players who receive the maximal fraction of votes, and -1 otherwise. (That is, each player wants to enter the competition only if she has some chance of winning.)
In every subgame perfect equilibrium clearly every player who enters (chooses a position) obtains the same fraction of votes (if a player loses outright, then she could have done better by not entering). Denote the median of F by m.
- Conjecture
- The game has a unique subgame perfect equilibrium outcome, in which players 1 and n choose the position m and all other players choose OUT.
This conjecture is consistent with the "Duverger's law", which states in part that plurality rule elections foster a two-party system (Duverger (1954, 217)).
By making exhaustive analyses, we can prove this conjecture for n = 2, 3, and 4. A proof for an arbitrary value of n, however, eludes us. (We are unable even to show for arbitrary n that the outcome describe is a subgame perfect equilibrium outcome. Detailed arguments for n = 2 and n = 3 are available in the solution to Exercise 196.4 in my book An introduction to game theory, which may be found on the website for the book. Alternative arguments for n = 2 and n = 3, together with a limited argument for n = 4, are available on this page.)
It is natural to try a proof by induction. Consider the claim that the equilibrium we have described is a (but not necessarily the only) subgame perfect equilibrium. Suppose that every game with fewer than n players has a subgame perfect equilibrium in which the only players to enter are the first and the last, who do so at m. Now consider the game with n players. If player 1 enters at m and player 2 does not enter, then by the inductive step no player except n enters, and n's position is m. It remains to show that if player 1 enters at m then player 2 does not enter. That is, wherever player 2 enters, the subsequent players will optimally enter in such a way that player 2 loses. For n = 4 the argument is the following: if player 2's position is m then wherever player 3 enters, player 4 can enter and win, causing player 2 to lose; if player 2's position is different from m then there is a position for player 3 with the property that player 4 cannot enter and win (or tie), and if player 4 does not enter then player 3 wins outright, causing player 2 to lose. To show for an arbitrary value of n that player 2 does not enter seems to require a detailed analysis of the (potentially very complicated) behavior of the remaining players in the ensuing subgame in the event that player 2 does enter.
A slight variant of the model leads to an easy argument characterizing the (different) unique subgame perfect equilibrium. Suppose that if two candidates obtain the same fraction of the votes then the one who entered first wins outright. Then clearly in any equilibrium there is at most one candidate. The following inductive argument (due to Jeffrey S. Rosenthal and Phil Morenz) shows that this candidate is player 1, who chooses the position m. The claim is that no player chooses a position such that she loses in the event that no more players enter. Certainly this claim is true for player n. Now suppose that it is true for all players from i on. Then i − 1 will not put herself into a losing position, since by the previous steps, no subsequent player will enter unless she wins (outright), in which case i − 1 will lose. Now, if player 1 enters at m, it follows that no subsequent player will enter; if she enters at y < m then player 2 is assured of victory if she enters at 1 − y − ε for ε small enough (since no single subsequent player can enter and win), so player 2 does indeed enter, and hence player 1 loses. Thus the game has a unique subgame perfect equilibrium outcome, in which player 1 enters at m and all other players opt out.