Here is the prompt:
You choose to put 1-100 marbles in a bag. Your opponent also has the same option. Then we pick one marble from the bag. If your marble gets picked from the bag you get the amount of marbles you did not put in as your payout. So if you put in 20 marbles and your marble gets picked you get 80. What is the optimal number of marbles to put in?
I understand the basics of game theory and Nash equilibria but I don't know how to reason about a question like this where the opponent has so many options. Here is what I have so far:
If the opponent picks $k$ marbles then I should pick $j$ marbles to maximize my payout, where the payout is given by
$$\frac{j}{j + k} (100 - j)$$ using the definition of expected value. However, clearly the value of $j$ that optimizes this function varies with respect to $k$, the number of marbles the opponent picks. I am guessing I need to use the value of $k$ that the opponent would pick if they were to maximize their own payout, but I don't know how to find that. Any direction would be appreciated, thanks.
You want to find the best response function - in other words, if Player 2 plays $k$, then what is the optimal $j$ for Player 1 to play, which will be a function of $k$.
To make things easier, start with the continuous version of the problem first i.e. Player 1 can choose any real number in $[1,100]$ and the expected payoff is $U_1(j,k) = \frac{j}{j+k}(100-j)$. Using calculus, we see that the $BR_1(k) = \sqrt{k^2 + 100k} - k$. Since the game is symmetrical, $BR_2(j) = \sqrt{j^2 + 100j} - j$. Solving these simultaneously gives us $j = k = 100/3$.
In the integer version of the game, the solution will be close to this, but because there are jumps in utility, it's best to check a few potential equilibria, namely both $(33,33)$ and $(34,34)$.
Starting with $(33,33)$, you should check whether $33$ is the best response to $33$. If Player 2 plays $33$, then your payoff for playing different values is: \begin{array}{|c|c|}\hline &32&33&34\\\hline 33& 2176/65 \approx 33.477 &33.5& 2244/67 \approx 33.493\\\hline \end{array} We can safely say that no other value will beat the $33.5$ payoff (you can test every value or look at a graph of $\frac{j}{j+33}(100-j)$ for $1\le j \le 100$), so $(33,33)$ is a NE. Similarly,
\begin{array}{|c|c|}\hline &32&33&34&35\\\hline 34 & 1088/33 \approx 32.970& 33 &33& 2275/69 \approx 32.971\\\hline \end{array} So this time it turns out that $BR_1(34) = \{33,34\}$, so $(34,34)$ is another NE!