My homework question is summarized below:
There are 7 players (say P1,P2,…,P7) trying to split 100 dollars. The game starts with P1 proposing an allocation of the 100 dollars to each player, that is, P1 assigns a dollar amount [0, 100] to each player, including himself. Then the remaining players P2..P7 all vote "Yes" or "No" to P1's allocation, simultaneously. If half or more vote "Yes", then the allocation is passed and everyone's payoff is the dollar amount they were allocated. If less than half vote "Yes", then the current player allocating (P1 in the first round of this game) receives a payoff of -1 and is removed from the subsequent rounds of the game. The game then continues onto the next round but with P2 attempting the next allocation for players P2…P7. The game continues until either the proposed allocation is passed (half or more vote "Yes"), or until P7 is the only player left in the game, in which he receives all 100 dollars.
Using the solution concept of subgame perfect Nash equilibrium, what happens?
I'm not quite sure how to start this question since I am not given an Extensive form game, and if I tried to make one myself, I wouldn't know the payoffs. Also the size of this Extensive form game (around $2^0 + 2^1 + … + 2^5$ nodes) is quite impractical to solve.
My attempt is below and admittedly it is lacking. I'm fairly positive I'm taking the wrong approach.
I tried starting from the very last round of the game and working upwards. The way I made the games was to consider a Px allocating and I would draw the extensive form game of players Px+1 .. P7 voting "yes" or "no". To make these games work for any allocation, I assigned a payoff of [0,100] to paths where the allocation is passed.
I first considered the case where P6 is allocating and P7 is voting and made the extensive form game of this. I found subgame perfect nash equilibrium and the proposal to fail. Next I made an extensive form game when P5 allocates and P6 and P7 votes. Some payoffs were found by using the result of the previous game. The proposal passes this time. But now I couldn't find the subgame perfect Nash equilibrium when P4 allocates and P5, P6, P7 vote because I didn't know which payoffs were better for some players (because I was allocating [0,100] to paths where proposals passed. To be more specific, there were paths where one strategy would lead to a payoff of [0,100] that P4 allocated and the other would lead to [0,100] that P5 allocated).
The whole point of me making these games was to hopefully find some pattern to each player's actions, but the case when P4 allocates stopped that plan. The only pattern I figured out was P7 always votes "No" when there are 2 or less voters.
Besides this, I don't know how to proceed. Any help at all is appreciated.
EDIT: I forgot an important part of the question. The question states: focus on subgame perfect Nash equilibria when players vote "no" when they are indifferent between voting for or against it. I apologize for my carelessness.
Best Answer
Below the line is an answer to the original question, which was interesting because of subtle issues of indifference. The question has now been edited to include the prescription that indifferent players vote "no".
In that case there is no equilibrium in the continuous version of the game: At the last stage, player $7$ always votes "no", so the payoff is $(-1,100)$. At the penultimate stage, player $6$ always votes "yes", so the payoff is $(100,0,0)$. At the stage before that, there is no equilibrium, since offering something to player $6$ or $7$ is strictly dominated by offering half as much, and offering nothing to either of them is strictly dominated by offering something to one of them.
In the discrete case, the analysis is the same for the last two stages. Player $4$ must offer $1$ to either player $6$ or player $7$, with payoff $(99,0,1,0)$ or $(99,0,0,1)$. Player $3$ must offer $1$ to the two players who would otherwise get nothing, with payoff $(98,0,1,0,1)$ or $(98,0,1,1,0)$. Player $2$ must offer $1$ to the two players who would otherwise get nothing and $2$ to one of the players who would otherwise get $1$, with payoffs $(96,0,1,2,1,0)$, $(96,0,1,0,1,2)$, $(96,0,1,2,0,1)$ or $(96,0,1,0,2,1)$. Finally, player $1$ must offer $1$ to the players who would otherwise get $0$ and $2$ to one of the players who would otherwise get $1$, with payoffs $(96,0,1,2,0,0,1)$, $(96,0,1,0,0,2,1)$, $(96,0,1,2,1,0,0)$, $(96,0,1,0,1,2,0)$, $(96,0,1,2,0,1,0)$, $(96,0,1,0,0,1,2)$ or $(96,0,1,0,1,0,2)$. In all cases, the payoffs for players $1$ through $3$ are $96$, $0$ and $1$, respectively, and the remaining $3$ are divided in various ways among players $4$ through $7$.
In both versions, continuous and discrete, the question "Using the solution concept of subgame perfect Nash equilibrium, what happens?" doesn't make sense, since there is no unique subgame perfect Nash equilbrium in either.
This is a great question; it's interesting and quite relevant to understanding the underlying concepts, and you put considerable effort into describing what you've tried; I wonder why it hasn't received more upvotes.
crf's solution is the "right" solution in practical terms, since one would always offer otherwise indifferent players a small incentive to make sure they don't take an adverse decision; but I understood the question to be more formally about how to treat indifference in finding a (weak) subgame perfect Nash equilibrium. The answer to that is somewhat different, namely that the only subgame perfect Nash equilibrium outcome of the continuous version of this game is where player $1$ assigns herself all the money, without any infinitesimal bribes subtracted, whereas the discrete version (where the proposals have to be integer dollar amounts) has a plethora of subgame perfect Nash equilibria, in which various players are bribed with various small amounts of money if they threaten to vote "no" otherwise.
The reason lies in how the solution concept of a subgame perfect Nash equilibrium treats credible and non-credible threats and promises (let's call them announcements). An announcement is not credible if the player would be worse off by actually carrying it out. Whereas a plain Nash equilibrium allows strategies involving non-credible announcements, a subgame perfect Nash equilibrium doesn't. However, it still allows announcements about what you'll do when you're indifferent; that is, if in a subgame a player is indifferent between two options, either of the two options can be part of a strategy in a subgame perfect Nash equilibrium.
In the continuous version of the present game, none of the solutions found by crf are equilibria, since for any given $\epsilon\gt0$ player $1$ could always choose a smaller $\epsilon$ and get a higher payoff. So the question is whether there's a subgame perfect Nash equilibrium where player $1$ gets all the money. The crucial point here is that the condition for a (weak) Nash equilibrium (subgame perfect or not) is only that the players can't profit from switching strategies. Whether strategies are in equilibrium is not affected by whether one player switching their strategy would make it profitable for another player to also switch their strategy.
In the present case, if player $1$ allocates all the money to herself and everyone else's strategy is to always vote "yes", then no player can profit from switching strategies, so this is a (weak) subgame perfect Nash equilibrium. The fact that players threatening to vote "no" would make it profitable for player $1$ to offer them something doesn't matter; it's not profitable, given the given strategies, for player $1$ to switch strategies.
Here's the analysis in detail. At the last stage, with two players left, the equilibrium strategy profiles are: player $6$ makes any allocation and player $7$ votes "no" no matter what player $6$ does; or player $6$ allocates all the money to player $7$ and player $7$ votes yes if and only if player $6$ allocates all the money to her. The payoffs are $(-1,100)$ in the first case and $(0,100)$ in the second.
At the penultimate stage, with three players left, subgame perfection eliminates non-credible threats by player $6$ to vote "no" to any proposal allocating her any money (since she'd get at most $0$ if the proposal fails), so there can't be an equilibrium allocating any money to player $6$, since player $5$ would be better off allocating half as much to player $6$. Thus in equilibrium player $5$ must allocate all the money to herself. Of course player $7$ votes "no", but player $6$ can't profit from voting "no", so player $6$ voting "yes" yields an equilibrium. (This is independent of which of the two equilibria for the last stage we select; for $(0,100)$ player $6$ is indifferent and for $(-1,100)$ she even profits from voting "yes".) The strategy of player $6$ in case player $5$ offers her something can be anything since it doesn't affect the outcome, so there's a continuum of equilibrium strategy profiles, but they all have the same payoff, $(100,0,0)$.
The analysis proceeds analogously at all stages. With player $4$ proposing, player $5$ will always vote "no", and there can't be an equilibrium where player $4$ offers anything to player $6$ or $7$ because she could offer half as much instead (non-credible threats to vote "no" in that case being eliminated by subgame perfection); so the only equilibrium is that player $4$ allocates all to herself, player $5$ votes "no" and players $6$ and $7$ vote "yes"; again the strategies of players $6$ and $7$ if player $4$ offers them something are arbitrary and don't affect the outcome, which is always $(100,0,0,0)$.
At the next stage, with player $3$ proposing, player $4$ votes "no", and any of the four subsets of players $5$ through $7$ with at least two players voting "yes" yields an equilibrium (as always, the strategies in case player $3$ offers them something being arbitrary). The payoff is $(100,0,0,0,0)$, and the analysis continues, with more different strategy profiles in equilibrium at each stage since there are more majority subsets at each stage, but the payoff is always the same: $(100,0,0,0,0,0)$ at the second stage and $(100,0,0,0,0,0,0)$ at the first.
In the discrete version, this is still a subgame perfect Nash equilibrium, but now there are also ones similar to crf's result.
Again, at the last stage, there are two equilibrium payoffs, $(0,100)$ and $(-1,100)$. At the penultimate stage, in the $(-1,100)$ case player $6$ will always vote "yes" to any proposal, so the only equilibrium payoff is $(100,0,0)$, whereas in the $(0,100)$ case player $1$ is indifferent between $(100,0,0)$ and $(0,100)$ and can therefore threaten to vote "no" when offered $0$, but can't threaten to vote "no" when offered $1$, so in this case there's an additional equilibrium with payoffs $(99,1,0)$.
With player $4$ proposing, in the $(100,0,0)$ case there are additional equilibria with payoffs $(99,0,1,0)$, $(99,0,0,1)$ and $(98,0,1,1)$, where in each case the players offered $1$ threaten to vote "no" if offered $0$. In the $(99,1,0)$ case, there are additional equilibria with payoffs $(98,0,1,1)$, $(98,0,2,0)$ and $(97,0,2,1)$. In summary, the possible equilibrium payoffs at this stage are $(100-x-y,x,y)$, with $0\le x\le2$ and $0\le y\le1$.
At the next stage, with player $3$ proposing, there is for the first time a choice of majorities, and player $3$ can pick the cheapest majority to bribe. The equilbrium payoffs are:
$$ \begin{array}{c|c} \text{stage }4&\text{stage }3\\\hline (100,0,0,0)&(100,0,0,0,0),(99,0,0,0,1),(99,0,1,0),(99,1,0,0),\\&(98,0,1,1),(98,1,0,1),(98,1,1,0)\\\hline (99,0,0,1)&(99,0,0,0,1),(98,0,0,1,1),(98,0,1,0,1),(97,0,1,1,1)\\\hline (99,0,1,0)&(99,0,0,1,0),(98,0,0,1,1),(98,0,1,1,0),(97,0,1,1,1)\\\hline (98,0,1,1)&(98,0,0,1,1),(97,0,0,1,2),(97,0,0,2,1),(97,0,1,1,1),\\&(96,0,1,2,1),(96,0,1,1,2)\\\hline (98,0,2,0)&(98,0,0,2,0),(97,0,1,2,0),(97,0,0,2,1),(97,0,1,2,1)\\\hline (97,0,2,1)&(97,0,0,2,1),(96,0,1,2,1),(96,0,0,2,2),(96,0,1,2,2)\\ \end{array} $$
I'll leave the boring details of the first two stages to you :-)