most recent 30 from http://mathoverflow.net 2013-05-19T19:07:50Z http://mathoverflow.net/feeds/question/109264 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109264/optimum-tournament-strategy bobuhito 2012-10-10T00:58:28Z 2012-10-10T09:59:45Z

<p>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.</p> <p>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.)</p> <p>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)?</p> <p>[this is a tangent from http://mathoverflow.net/questions/107390/flipping-coins-on-a-budget]</p>

http://mathoverflow.net/questions/109264/optimum-tournament-strategy/109286#109286 Douglas Zare 2012-10-10T09:59:45Z 2012-10-10T09:59:45Z

<p>I will address the case $N=2$.</p> <p>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$. </p> <p>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. </p> <p>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.</p> <p>In the first game of a best-of-seven series, spend $1/7$ of your energy.</p>