A conjecture about the subgame perfect equilibria of a model of sequential location

Martin J. Osborne

The conjecture described on this page arose during joint work with Amoz Kats in the mid-1980s. It remains unproved and uncontradicted.

I conjecture that the extensive game described here has a unique subgame perfect equilibrium outcome. The game is of interest for two reasons. First, the character of the conjectured equilibrium, when the game is interpreted as a model of electoral competition, is related to claim of Maurice Duverger, sometimes referred to as "Duverger's law", that states that plurality rule favors a “two-party system” (Political Parties, 1954, p.217). Second, despite the simplicity of the game and the conjectured equilibrium, no simple proof or counterexample appears to exist.

Each of the players 1,..., n chooses a member of the set [0, 1] ⋃ {OUT}. Members of [0, 1] may be interepreted as political positions; I refer to a player who chooses a position (rather than OUT) as a candidate. 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. There is a continuum of citizens, each of whom has a favorite position. The distribution of these favorite positions is F, which is nonatomic and has support [0, 1]. Thus the fraction of citizens with favorite postions at most x is F(x). Each citizen votes for a candidate whose position is closest to her favorite position. Assume that if two or more candidates choose the same position, the votes for the position are divided equally among the candidates choosing the position. To be more precise, suppose that the positions chosen by candidates are y₁, y₂, ..., y_k with y₁ < y₂ < ... < y_k, and for i = 1, ..., k denote the number of candidates who choose y_i by n_i. Then each of the n₁ candidates choosing y₁ obtains the fraction F((y₁ + y₂)/2)/n₁ of the votes, each of the n_k candidates choosing y_k obtains the fraction 1 − F((y_k−1 + y_k)/2)/n_k of the votes, and for j = 2, ..., k − 1 each of the n_j candidates choosing y_j obtains the fraction [F((y_j+1 + y_j)/2) − F((y_j + y_j−1)/2)]/n_j.

Each player obtains the payoff 0 if she chooses OUT, the payoff 1/r if she is among the r players who receive the maximal fraction of votes, and the payoff −1 otherwise.

By making exhaustive analyses, this conjecture may be proved for n = 2, 3, and 4. However, no proof or counterexample for an arbitrary value of n is known. In fact, no proof even that the outcome described is a subgame perfect equilibrium outcome for an arbitrary value of n is known. 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.

One property of any equilibrium is immediate: every player who chooses a position (rather than OUT) obtains the same fraction of the votes, because a player who obtains a smaller fraction of the votes than another player can increase her payoff by deviating to OUT.

It seems natural to try to prove the conjecture by induction. Consider the claim that the equilibrium I 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 the median of F, which I denote 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 optimally enter in such a way that player 2 loses. For n = 4 here is the argument: 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 argue 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.

For a slight variant of the model, an easy argument characterizes the (different) unique subgame perfect equilibrium. Suppose that if two or more candidates obtain the same fraction of the votes then the one who entered first wins outright, obtaining the payoff 1, and the remaining candidates obtain the payoff −1. Then in any equilibrium at most one player chooses to become a 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 median of F). I claim that no player chooses a position such that, given the previous players' actions, she loses if no more players become candidates. This claim is true for player n. Now suppose that it is true for all players from i on. Then i − 1 will not choose a position that, given the previous players' positions, causes her to lose, because by the previous steps, no subsequent player will enter unless she wins (outright), in which case i − 1 will lose. Thus the claim is true for all i. 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 choose OUT.

In his Masters thesis at Erasmus University (Duverger's (f)law: counterproof to the Osborne conjecture, 2015), Jan-Pieter de Vries claims to describe a (12-player) counterexample to the conjecture. However, his argument is incomplete, and my collaborative work with him, Jurjen J. A. Kamphorst (his advisor), and Jeffrey S. Rosenthal has failed to either confirm or disconfirm that his work describes a subgame perfect equilibrium of the game.