# Best Strategy in a Non-Cooperative Game of Perfect Information (Pure Strategies only)

Suppose there are two players in this game, and each player has $4$ dollars prior to making his move. Each player has as his strategy space the ability to submit an integer number of these $4$ initial dollars initially available to him (i.e., he can submit $0$ dollars, $1$ dollar, $2$ dollars, $3$ dollars, or $4$ dollars). Now, if the sum of the dollars submitted by both players is greater than or equal to $4$ dollars, then each player earns $5$ dollars, and hence his utility is $5$ dollars, plus whatever remains of his initial $4$ dollars. As an example, if Player $1$ should submit $2$ dollars, and Player $2$ should submit $3$ dollars, then Player $1$'s payoff is $7$ dollars, while Player $2$'s payoff is $6$ dollars. On the other hand, if the sum of the dollars submitted by both players is less than $4$ dollars, then each player earns $0$ dollars in return, and hence his utility is whatever remains of his initial $4$ dollars. As an example, if Player $1$ should submit $1$ dollar, while Player $2$ submits $2$ dollars, then Player $1$'s payoff is $3$ dollars, while Player $2$'s payoff is $2$ dollars.

Given that I do not know what strategy my opponent (say, Player $2$) will take, which strategy ought I (Player $1$) to take so as to maximize my own utility?

Identifying the Nash Equilibria in this game is simple enough: (4,0), (3,1), (2,2), (1,3), and (0,4); however, how can I use this information to make my move, especially considering that none of my actions appear to dominate (weakly or strictly) any of my other actions?

• If I'm playing once only, I'll probably pay $4$, since it has the highest guaranteed payoff ($5$). If I'm starting a sequence of plays of some significant length, I'll probably pay $2$ in hopes of encouraging the $\langle 2,2\rangle$ equilibrium. – Brian M. Scott Sep 16 '15 at 4:07
• Can you explain how playing the game once versus playing the game multiple times have differing strategies? – David Smith Sep 16 '15 at 4:10
• Isn’t it clear from my comment? I may win only $2$ for a few plays, but if the other player isn’t a complete idiot, he should realize that I’m suggesting that we cooperate at $\langle 2,2\rangle$, the equilibrium that is equally advantageous to both of us. – Brian M. Scott Sep 16 '15 at 5:12
• @BrianM.Scott Even if the game is only played once, if Player 2 isn't a complete idiot, after you play $2$ he will see that he ends up with $7$ if he plays $2$, and less than $7$ if he plays anything else. Or am I misunderstanding what "Game of Perfect Information" means? – bof Sep 16 '15 at 5:19
• @bof: You’re misunderstanding the game: the plays are made simultaneously, so neither player knows the other’s play when choosing his own. – Brian M. Scott Sep 16 '15 at 6:03

If the purpose of the game is to maximize own profit instead of having more money than the opponent, then always submitting four dollars will guarantee continuous earning. (assuming the opponent can make any move)

If one assumes the opponent is rational then always submitting two dollars would be the best strategy as the opponent will know this fact as well and will start submitting two dollars (in the long run) after a finite number of turns without maximizing profit.

• This assumes that the two players are in competition, when in fact each player is strictly concerned with maximizing his own payoff, and thus cares nothing for the payoff of the other player. – David Smith Sep 16 '15 at 3:52
• @David: I don’t understand why you accepted this, since it’s based on an incorrect understanding of the game: it is simply not true that either both players earn $5$ or both earn $0$. – Brian M. Scott Sep 16 '15 at 6:04
• @BrianM.Scott I agree that the initial answer is not satisfactory. However, the subsequent EDIT section he later added is basically the same as the initial comment you provided (the one on which I asked for further clarification), so that's why I accepted it. – David Smith Sep 16 '15 at 6:47
• @David: That is certainly your prerogative, but I’ll make one final comment: since the first paragraph is based on a wholly incorrect understanding of the game, the answer as a whole seems to me more than a little misleading. Removing the first paragraph would solve the problem. – Brian M. Scott Sep 16 '15 at 7:20
• The first paragraph is removed. – cr001 Sep 16 '15 at 7:25

# If the game is truly perfect-information.

If you're both rational, you keep \$4, she sees that she can choose between having \$4 and \$5, and she chooses \$5, giving you \$5 more, so you get \$9. That's the best you can do.

Unfortunately, real humans do not behave rationally in all circumstances. In fact, in this game, usually Player 2 will expect Player 1 to pony up \$2 of the needed \$4, will maybe tolerate if they only pay \$1, but will effectively punish by keeping the \$4 if they see the other spend \$0. # Closed ballots When there are multiple Nash equilibria, you can sometimes eliminate some of them by saying "well, these other Nash equilibria make us both better off", and that eliminates some choices. Unfortunately, you don't have any opportunity to do that here, but if you do, call the rest of the Nash equilibria the "Pareto equilibria." If multiple Pareto equilibria persist then the players will have to coordinate, otherwise sometimes they will have a suboptimal result. The absolute simplest coordination that you can do in symmetric games is to assume a symmetric strategy, which in your case results in them both choosing to donate \$2 to the pile. Unfortunately not all games are symmetric.

If we can't analyze the game like that, then we generally look at it this way: The Pareto equilibria are a set of two-player choices, $P = \{(A_1, B_1), (A_2, B_2), \dots\}$ and define a subset of options $A = \{A_1,\dots\},\;B=\{B_1,\dots\}.$ Player Alice chooses a strategy which is a probability distribution among her options A in order to make all of Bob's options indifferent to Bob, and Bob chooses a distribution among B to do the same to Alice. The combination of these two is therefore an equilibrium which has a certain stability to it.

Let Bob have a payoff matrix $\mathbf B$ and Alice's probability vector be $\vec a$ and Bob's $\vec b$. Then Bob's expected payoff can be written as $\vec b ~\cdot~ \mathbf B~ \vec a.$ Define the ones vector $\vec 1 = [1;\;1;\;\dots]$, which helps for things like normalization and such. The goal is therefore for Alice to choose $\vec a$ such that $\vec 1 \cdot \vec a = 1$ and also $$\mathbf B ~\vec a = u ~\vec 1.$$Dividing through by $u$ we see that she can simply choose $\vec a/u = \mathbf B^{-1}~\vec 1$ and then determine $u$ by normalization. The only bad things that can happen here are that the equation might not be solvable and potentially the inverse might give us some $a_i$ outside of the interval $[0, 1];$ I am not sure what to do precisely in these situations (maybe the restriction to Pareto equilibria saves us from ever running into them?) but a decent idea would be to take the most-negative one and eliminate its pairs from the set $P$ and then recalculate. However, this does not matter because in your case, we have:$$\mathbf B = \begin{bmatrix} 4&4&4&4&9\\ 3&3&3&8&8\\ 2&2&7&7&7\\ 1&6&6&6&6\\ 5&5&5&5&5\end{bmatrix}$$Notice that the sums along all of the rows are the same, 25. So actually the vector $\vec a / u$ which does this is $\vec 1$. If Alice chooses to do all of her options with probability $1/5$ then Bob has no way to improve or worsen his strategy, so he's free to choose his own strategy with whatever probabilities he wants.

If they cannot collaborate, and they do not implicitly collaborate by both choosing \$2 via the symmetry of the system, then this recipe says that they choose each of their options with probability$1/5$and each have an expected payoff of \$5.

• If the players move at the same time (closed ballots) then it's not a "Game of Perfect Information" as stated in the title of the question. – bof Sep 16 '15 at 5:05
• Ah, yes. I hadn't remembered that in my answer above. – CR Drost Sep 16 '15 at 5:20
• By a game of perfect information, I mean that each player is perfectly aware of the structure of the game, as well as all of the payoffs associated with each action profile. – David Smith Sep 16 '15 at 6:57
• @DavidSmith: I updated this with one general algorithm for correctly, symmetrically choosing a randomized strategy in situations of multiple Nash equilibria, if it helps. – CR Drost Sep 16 '15 at 15:04