MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
7

1

Consider a symmetric N-player game in which all players partition one total unit of energy among individual games. The probability of winning each game is simply proportional to the spent energy (player #1 wins with probability $\frac{E_1}{E_1+E_2+...+E_N}$). The winner is the first player to win G games.

Before each game, players know both "how much energy each person has left" and "how many games each person has won" to choose the energy to spend in the next game. (I'm additionally interested in game theory if these are not both known, but that's a bonus.)

A full game-tree solution for all cases would be nice, but maybe too much to ask for...instead, how much energy should be spent on the first game if N=2 and G=4 (World Series)?

[this is a tangent from http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget]

flag

1 Answer

4

I will address the case $N=2$.

The best strategy is the boring one of distributing your energy evenly. This can be proved inductively in the number of games left. If the players need $a$ and $b$ games to win, respectively, then we say the number of games left is $a+b-1$.

It is trivial for $1$ game left, and a simple calculation with $2$ games left, where one side needs to win both games and the other side needs to win either.

Suppose it is true for $g-1$ games, and let there be $g$ games left. Suppose your opponent distributes his/her energy evenly. Consider the strategy of using $x/g + \delta$ energy on the next game. By induction, regardless of the result, the correct strategy for the last $g-1$ games is to distribute your energy evenly. Choosing $x/g + \delta$ energy for the first game and $x/g - \delta/(g-1)$ equity for the remaining games is equivalent to choosing $x/g + \delta$ energy for the last game and $x/g - \delta/(g-1)$ for the first $g-1$ games. But by induction, after the first game where you use the equity $x/g - \delta/(g-1)$, your equity is less than or equal to the choice of distributing your energy evenly among the last $g-1$. Thus, for any $x/g + \delta$, the equity of that choice is less than or equal to the choice of $x/g + \delta(\frac{-1}{g-1})^n$. By the continuity of winning chances and using $|\frac{-1}{g-1}| \lt 1$, the equity using $x/g+\delta$ on the first choice is at most the equity of using $x/g$. So, by induction, it is optimal to distribute your energy equally.

In the first game of a best-of-seven series, spend $1/7$ of your energy.

link|flag
Great proof! I now see that this is different from "flipping coins on a budget" because the win probability is less sensitive to spent energy (and I now think my question would have been more dynamic if the win probability were proportional to the square of the spent energy, instead of the linear energy, which might be more realistic in more-skilled competitions like track sprinting, instead of baseball). Would you guess N>2 also has a boring evenly-distributed solution? – bobuhito Oct 11 at 0:13
I think with $N \gt 2$ there is the possibility of collusion, and the analysis is more complicated. – Douglas Zare Oct 11 at 0:17
This would seem to show that distributing energy evenly is a Nash equilibrium. But if your opponent does not play evenly, how do you see that this is still the best strategy? – Granger Oct 11 at 0:46
For $N=2$, you only need to see that your opponent is worse off to know that you are better off. Even distribution is not the optimal strategy against an opponent who plays unevenly, but you still win (or at asymmetric scores, you do better than par) when you play evenly. For example, suppose you need to win both remaining games, you have $1$ energy, and your opponent has $3/2$. Suppose your opponent uses $1$ energy in the next game, and $1/2$ in the final game (if necessary). $1/2-1/2$ wins $1/6=16.7\%$, better than the par of $4/25 = 16.0\%$. The exploitive strategy would be $3-\sqrt6$... – Douglas Zare Oct 11 at 1:16
... in the first round and $\sqrt{6}-2$ in the second round, which wins $16.8\%$. – Douglas Zare Oct 11 at 1:18

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.