Gambling Solution

Time to solve the gambling puzzle from last time. When I told this problem to Matt, his immediate reaction (which I found rather amusing) was to say "OK....hmm, what would Kory do?................. ah yes, consider a simpler case." That seems to be the right approach, so lets assume that the frungy tournament is best or 3, first team to 2 games wins.

We already know that we should not bet all $400 on Blue in the first game, because then Red might win the first game and suddenly we are out of money. Blue then might go on to win the tournament and we are in trouble. Taking the other extreme strategy of not betting on the first game at all, if Blue wins the game, we have no choice but to bet everything on Blue now (else if Blue wins again we are done). But now if Red wins we are out of money for the final game (which, if we are unlucky, Blue will win).

The next obvious thing is to take the middle ground and bet $200 on Blue in the first game. Now if Blue loses we have $200 left and Red is up 1-0. Since Red winning again is auto-victory for us anyway we might as well bet everything we have left on Blue. If Blue wins now we have $400 and they are tied 1-1. At this point it is simple. OK, instead suppose Blue wins the first game, now we have $600 and Blue is up 1-0. We need only bet $200 on Blue this next game, so that if they win we end with $800, so now if they lose we have $400 left and the teams are 1-1 again. Good, this is a full solution, it is also nice to see that it is 100%, rather than just a probabilistic solution.

A few things to notice about that solution. First of all, we never ended with any excess money, in all strategies we came out with exactly $800. Another thing is that the result was "path independent", that is, no matter if Blue won first or Red won first if the game got to being tied at 1-1 it did not matter how we got there, we had exactly $400. Both of these facts are general about the full solution (assuming it is a 100% solution, that is).

First of all, the "no excess money" result. Let us begin by supposing that we have a full strategy for how to bet in the games as the tournament progresses. Note that every game is a bet on a coin flip, therefore no matter what your planned strategy is you will have an expectation of $400 after each game. The side bet is an even chance split of $800 and $0, so it has an expectation of $400. Thus, at the end of the week, no matter your strategy, you have an expected final amount of money equal to $800. If there is any possible path through the game tree that ends with more than $800, there is also a path through the game tree with less than $800, so no solution that works 100% of the time can ever end with excess money.

Now for the "path independent" result. Suppose we have a betting strategy for the whole week. Further suppose there was a node in the game tree (for example, Red is up 3-1 on Blue) that depending on how you got there you will have different amounts of money (so for one path you have $x, and for the other you have $y). Assuming x>y then if we get there with $x, we can simply throw away $(x-y) to leave ourselves with $y and still have a planned out strategy for the rest of the game. This strategy will apparently have had excess money, which we know is impossible.

Alright, we are almost ready to make the full solution. The final step is that if your strategy knows how much money it has at each step, you know how much you need to bet. So if you know you have $400 now and if Blue wins you need to have $600, but if Red wins you need to have $200, the it is time to bet $200 on Blue. We will describe a strategy as a chart of the amount of money we need at each step in the game tree. Consider the tree for the three game case as follows (This is going to format like crap, but it will be readable):

AAA BBB
CCC DDD

OK, AAA represents the amount of money we start with (so, 400), BBB is the amount of money we have if Red is up 1-0, CCC is the amount of money we have if Blue is up 1-0 and DDD is the amount of money we have if the game is tied 1-1. So, my notation is that if Red wins we move a step right, if Blue wins we take a step down.

We know that if Blue wins two games we must have exactly 800, and if Red wins we must have exactly 0 (no excess money), so we can add those values in:

AAA BBB 0
CCC DDD 0
800 800

Now, we know that DDD must be exactly 400, there is no other amount of money it can be that will be consistent with this. But then we know that CCC is 600, and BBB is 200. Finally we get that AAA is 400, which is really just a consistency check.

You can now easily see the general answer, but lets just go through it anyway, for the full 7 game case we have:

AAA BBB CCC DDD 0
EEE FFF GGG HHH 0
KKK LLL NNN PPP 0
QQQ RRR SSS TTT 0
800 800 800 800

Great, we can now see that TTT is 400, PPP is 200, HHH is 100 and DDD is 50. Also we get that SSS is 600, RRR is 700 and QQQ is 750. Sort of a neat symmetry here:

AAA BBB CCC 050 0
EEE FFF GGG 100 0
KKK LLL NNN 200 0
750 700 600 400 0
800 800 800 800

Its simple enough to continue filling this all in now:

400 275 150 050 0
525 400 250 100 0
650 550 400 200 0
750 700 600 400 0
800 800 800 800

So, apparently the correct solution begins with placing a $125 bet on Blue in the first game.