# Subgame Perfect Nash Equilibrium

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.

-
The payoffs should be the amount of money that each player receives. – crf Aug 11 '12 at 0:42
I remember this exact problem from one of the lectures here: academicearth.org/courses/game-theory I am sorry to say I don't remember which of the lectures he mentioned it, and might not have been in the right context. – Arthur Aug 11 '12 at 0:49
what do you mean when you say "I assigned a payoff of [0,100] to paths where the allocation is passed"? – crf Aug 11 '12 at 0:54

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 :-)

-
Thank you, good points. I should have included that players can still vote "yes" for free in equilibrium, regardless of whether utility is discrete or not. That's a very important point now that I think about it. – crf Aug 11 '12 at 5:26
I'm sorry, I forgot an important detail. Please see my updated question, players should vote "no" when they are indifferent. – Kevin Aug 11 '12 at 6:12
@Kevin: That's rather sad. I spent several hours on that answer. I removed my upvote and changed it to a downvote. Please take more care next time. – joriki Aug 11 '12 at 6:15
When player 5 allocates, what do you mean when you say "so there can't be an equilibrium allocating any money to player 6, since player 5 would be better off allocating half the money to player 6"? Why would player 5 be better off by allocating half the money to player 6 when player 6 always votes "yes"? – Kevin Aug 11 '12 at 6:16
@Kevin: Because she can keep the other half for herself :-) – joriki Aug 11 '12 at 6:16

Edit: as joriki points out, this solution is no good in the case where utility is continuous. He provides a solution for the continuous case. I am taking $\epsilon$ here to be the smallest discrete unit of money (don't know if we're going dollars or cents, doesn't matter).

Go through this extremely carefully as I definitely may have made a mistake somewhere.

Okay, I'm going to introduce some notation here. The $u_i$ is the utility to the $i$-th player of a given action profile. An action profile is a vector of all the actions that all the other players take, so like, $\langle(100/7, 100/7, 100/7, 100/7, 100/7, 100/7, 100/7),yes,yes,yes,yes,yes,yes\rangle$ is the action profile where player 1 proposes that they split the money equally and players 2 through 7 all vote yes. That's super ugly though, so instead I'll write this: $p_j^i$ is the amount that player $i$ receives from the $j$-th player's allocation, and $u_i(p_j^i,pass)$ is the i-th player's utility from any action profile where player $j$ offers $p_j^i$ and it passes, and $u_i(p_j^i,fail)$ is player $i$'s same utility from that offer when it fails.

Now before looking at how specific players behave, let's think about how players should behave in general. In any given stage of the game, utility is determined by whether the proposal passes or fails. So at any given stage of the game, player $i$ is choosing what action to pick subject to this: $$u_i(p_j^i,pass)=a \\ u_i(p_j^i,fail)=b$$

($i,j$ are not necessarily distinct). If player $i$ is a voter, they should vote yes when $a>b$ and they should vote no when $b>a$.

Note that the allocating player $j$ faces this in every stage:

$$u_j(p_j^j,pass)=p_j^j \\ u_i(p_j^i,fail)=-1$$

So player $j$ always wants the motion to pass, since the lowest $p_j^j$ can ever be is 0. Thus player $j$ always maximizes $p_j^j$ subject to the constraint that the motion passes.

Okay let's look at the specifics, by backward induction.

In the last stage P7 gets 100. That was easy.

In the second to last stage, when P6 is allocating, we have $$u_7(p_6^7,pass)=p_6 \\ u_7 (p_6^7 ,fail)=100$$ $$u_6(p_6^6,pass)=p_6 ^6 \\ u_6 (p_6^6 ,fail)=-1$$

As we established, P6 wants the motion to pass (because the offerer always wants their motion to pass), so he offers 100, and so in equilibrium in this subgame $u_6=0$ and $u_7=100$.

Now we examine the stage where P5 is allocating. We have $$u_7(p_5 ^7,pass)=p_5^7 \\ u_7(p_5^7,fail)=100 \\ u_6(p_5 ^6,pass)=p_5^6 \\ u_6(p_5^6,fail)=0$$

I didn't write P5's utility because as we already established, the offerer always wants the motion to pass. Player 7 strongly prefers to vote yes unless $p_5^7=100$, in which case he is indifferent. Player 6 prefers to vote yes as long as $p_5^6>0$. Player 5 can get a pass by offering player 6 anything whatsoever, and so player 5 offers player 6 a pittance—say $\epsilon$—and we have $u_7=0,u_6=\epsilon,u_5=100-\epsilon$.

When player 4 is allocating we have $$u_7(p_4 ^7,pass)=p_4^7 \\ u_7(p_4^7,fail)=0 \\ u_6(p_4 ^6,pass)=p_4^6 \\ u_6(p_4^6,fail)=\epsilon \\ u_5(p_4^5,pass)=p_4^5 \\ u_5(p_4^5,fail)=100-\epsilon$$

Player 6 will vote yes as long as $p_4^6>\epsilon$ and player 7 will vote yes as long as $p_4^7>0$. Player 5 is a lost cause as far as player 4 is concerned, but that's fine. Player 4 offers player 6 $2\epsilon$ and player 7 $\epsilon$ and we have $u_7=\epsilon,u_6=2\epsilon,u_5=0,u_4=100-3\epsilon$.

When player 3 is allocating we have $$u_7(p_3 ^7,pass)=p_3^7 \\ u_7(p_3^7,fail)=\epsilon \\ u_6(p_3 ^6,pass)=p_3^6 \\ u_6(p_3^6,fail)=2\epsilon \\ u_5(p_3^5,pass)=p_3^5 \\ u_5(p_4^5,fail)=0 \\ u_4(p_3^4,pass)=p_3^4 \\ u_4(p_3^4,fail)=100-3\epsilon \\$$

As we keep going through these iterations it starts to become clear that what we're really looking for is the offerer's cheapest way to buy a pass. Player 3 needs to buy two votes, which he can do by offering player 5 $\epsilon$ and player 7 $2\epsilon$, and so we have the outcome $u_7=2\epsilon,u_6=0,u_5=\epsilon,u_4=0,u_3=100-3\epsilon$

And again, with P2 allocating, $$u_7(p_2 ^7,pass)=p_2^7 \\ u_7(p_2^7,fail)=2\epsilon \\ u_6(p_2 ^6,pass)=p_2^6 \\ u_6(p_2^6,fail)=0 \\ u_5(p_2^5,pass)=p_2^5 \\ u_5(p_2^5,fail)=\epsilon \\ u_4(p_2^4,pass)=p_2^4 \\ u_4(p_2^4,fail)=0 \\ u_3(p_2^3,pass)=p_2^3 \\ u_3(p_2^3,fail)=100-3\epsilon$$

Player 2 needs to buy 3 votes, which are most cheaply bought by offering players 4 and 6 $\epsilon$ each and player 5 $2\epsilon$ and so we have $u_7=0,u_6=\epsilon,u_5=2\epsilon,u_4=\epsilon,u_3=0,u_2=100-4\epsilon$

Finally we reach the first stage, where Player 1 allocates. We have,

$$u_7(p_1 ^7,pass)=p_2^7 \\ u_7(p_1^7,fail)=0 \\ u_6(p_2 ^6,pass)=p_1^6 \\ u_6(p_1^6,fail)=\epsilon \\ u_5(p_1^5,pass)=p_1^5 \\ u_5(p_1^5,fail)=2\epsilon \\ u_4(p_1^4,pass)=p_1^4 \\ u_4(p_1^4,fail)=\epsilon \\ u_3(p_1^3,pass)=p_1^3 \\ u_3(p_1^3,fail)=0 \\ u_2(p_1^2,pass)=p_1^2 \\u_2(p_1^2,fail)=100-4\epsilon$$

Player 1 needs to buy 3 votes, which are most cheaply bought by offering $\epsilon$ to each of players 7 and 3, and then offering $2\epsilon$ to either of players 4 or 6. And so our final outcome is: $u_7=\epsilon,u_6=0\text{ (or }2\epsilon),u_5=0,u_4=2\epsilon \text{ (or }0), u_3=\epsilon, u_2=0, u_1=100-4\epsilon$, with players 3, 4 (or 6) and 7 voting to accept the offer.

-
This is OK as a practical solution, but I don't think it addresses the formal question about the subgame perfect Nash equilibrium, and in particular about the treatment of indifference. – joriki Aug 11 '12 at 4:48