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

Question

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?

Answer 1

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.

Answer 2

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.