The [0,1] Game: Part 5
Jerrod Ankenman
Bill Chen/Jerrod Ankenman
Part 5: The full infinite pot game and Game #5
This is part 5 in a many-part investigation of what we will refer to as
the [0,1] game, which can in some ways be thought of as analogous to
poker and is actually interesting in its own right.
Recap to this point: In Parts 1 and 2, we analyzed a very simple [0,1]
game where the pot is infinite, but only one or two bets are allowed. We
found intuitively what the optimal strategy and value of the game were.
Then we created a method using indifference equations to solve the same
problems and introduced notation to help us solve more difficult
problems in a little harder way, and got the same answers. In Part 3, we
generalized to the case where unlimited bets were allowed. We discovered
that a single ratio governs all the raising after the first bet, and we
found its value and called it "r". We also solved the game with infinite
bets and found its value. In Part 4 we increased the complexity of our
game by studying the case where check-raising is allowed. We solved the
two-bet check-raise allowed game.
In this part: We solve the most complex game we've considered thus far
-- check-raising allowed, and infinite bets allowed.
In Part 4 we solved game #2, but added check-raising. In Part 5, we will
solve game #3, but with the addition of check-raising. In order to solve
this game, we'll have to use some more advanced mathematical techniques
than we have used previously. Up to this point, everything we've done
should be understandable by anyone who has taken college-level algebra.
However, to solve Game #5, we'll need to use some more advanced
algebraic techniques.
Warning: Some of the math in this part is outside the range of what you
would do in a college algebra class. We promise we won't do that much of
this, but it was necessary in this case to solve this game (the last
step in our progression).
Game #5: infinite pot, infinite bets allowed. Check-raise is allowed.
As we begin, as usual, we'll draw our line graph. Since check-raising is
now allowed, both sides have values of x_n and y_n for all positive
integer values of n. Note that each successive range of x_n dictates a
different initial strategy - ie, from x3 to x4, X bets and then
reraises, but from x4 to x5, X check-raises, and reraises again if given
the opportunity. This will be important to how we structure the
indifference equations at y_n, much later.
x4 x3 x2 x1
|--|--|----|----|----|----|----|----|----|----|
0 y5 y4 y3 y2 y1 1
There are, of course, an infinite number of points between 0 and y5 that
are not pictured. We'll include them, though.
Our first step is to write indifference equations. Previously, we've
just worked from right to left, writing indifference equations for each
point, regardless of whether it be an x_n or a y_n. However, due to the
complexity of solving these equations, we're going to solve for Y's
strategy first, and then solve for X's strategy after that. The reason
we solve for Y's strategy first is (as you will see) that when solving
Y's strategy, X's strategy is not required. So we can solve for all the
Y points, and then use those Y point values to solve for X's points.
(all the results for the next section are for X taking the more
aggressive action - ie, the one that will lead to the most bets in the
pot.)
At x1, Y wants to make X indifferent between betting and checking:
Y's hand
[0,y2] -1 (if x bets, y raises and wins 2, if x checks, y bets and wins
1)
[y1,1] +1 (x bets and wins 1 vs x checks and y checks)
so our indifference equation is:
y2 = 1 - y1 [1]
At x2:
Y's hand
[0,y3] -1 (if x bets, y raises and wins 2, but if x cr, y wins 3)
[y2,y1] +1 (if x bets, y calls and x wins 1, but if x cr x wins 2)
[y1,1] -1 (if x bets, x wins 1 vs 0 when both check)
y3 + (1-y1) = y1 - y2 [2]
At x3:
Y's hand
[0,y4] -1
[y3,y2] +1
[y2,y1] -1
[y1,1] +1
y4 + (y1 - y2) = (y3 - y2) + (1 - y1) [3]
At x4:
Y's hand
[0,y5] -1
[y4,y3] +1
[y3,y2] -1
[y2,y1] +1
[y1,1] -1
y5 + (y3 - y2) + (1 - y1) = (y3 - y4) + (y1 - y2) [4]
You can probably see the pattern here.
For x_n, x loses a bet when y is from 0 to y_n, then alternates winning
and losing bets for decreasing n down to y_0, which is 1.
Now, let's do a little bit of math:
y4 + (y1 - y2) = (y3 - y2) + (1 - y1) [3]
y5 + (y3 - y2) + (1 - y1) = (y3 - y4) + (y1 - y2) [4]
Switching sides on [3]:
(y3 - y2) + (1 - y1) = y4 + (y1 - y2) [3a]
y5 + (y3 - y2) + (1 - y1) = (y3 - y4) + (y1 - y2) [4]
(y3 - y2) + (1 - y1) = y4 + (y1 - y2) [3a]
Subtracting [3a] from [4]:
y5 = -2y4 + y3
You can probably see intuitively that this is going to be the result of
subtracting the equation for x_k from the equation for x_(k+1).
So generalizing, we end up with the following equation that describes
the relationships between each consecutive set of 3 y_n values:
y_(n+2) + 2y_(n+1) - y_n = 0 [*]
This is called a second-order homogenous difference equation.
We can prove that all equations of this form (y_(n+2) + a*y_(n+1) +
b*y_n = 0) have a solution that looks like this:
y_n = a*p^n + b*q^n
where a and b are constants and p and q are the roots of the
"characteristic equation" of the difference equation.
(Well, okay, math majors, this is only true if the characteristic
equation has two real roots, and it does this time so hush.)
The characteristic equation is x^2 + ax + b = 0. This, of course, is the
familiar quadratic equation you learned to solve in high school.
So let's work this out now:
The characteristic equation for our difference equation:
y_(n+2) + 2y_(n+1) + y_n = 0
is
x^2 + 2x - 1 = 0
Breaking out our trusty quadratic formula, we find that the roots of
this equation are:
(-2 +/- sqrt(8))/2 or -1 +/ sqrt(2)).
so
q = -1 - sqrt(2)
p = sqrt(2) - 1 = our old friend r
Back to our formula:
y_n = a*r^n + b*(-sqrt(2) - 1)^n
Now, we know that as y->infinity, y_n converges to 0, because Y won't be
willing to put in many bets with any hands that aren't extremely close
to 0. The expression on the right, however, won't converge to 0 for any
b except b=0.
So now we know that y_n = a*r^n.
Let's go back and solve for a:
y2 = 1 - y1
a*r^2 = 1 - ar
a*r^2 + ar - 1 = 0
Now remember, r^2 = 1 - 2r, so:
a - 2ar + ar - 1 =
a - ar = 1
a = 1/1-r
Now we've got a formula for y_n:
y_n = (1/(1-r))*r^n
and we've got Y's strategy done.
What does this mean exactly? It means that y's optimal strategy is to
first of all bet a certain fraction of hands (it turns out to be
1/sqrt(2). Then he should be willing to put in an additional bet with r
times the number of hands he was willing to put in the previous bet. So
if he was willing to put in 1 bet with 1/(sqrt(2)) hands, he is willing
to put in 2 bets with r/sqrt(2) hands, and 3 bets with r^2/sqrt(2)
hands.
All right, now we'll solve for the slightly tricker strategy for X:
at y1:
X's hand
[y1,1] -1
[x1,y1] 1
[x2,x3] 2
[x4,x5] 2
[...]
[x_2n,x_(2n+1)] 2
X is going to win 2 bets on every interval that X check-raises on.
So the indifference equation here will be:
1-y1 = (x1-y1) + 2(x2 - x3) + 2(x4-x5) [....]
ok, now y2:
X's hand
[y2,x1] -1
[x2,y2] 1
[x3,x3] 2
[x5,x6] 2
[...]
[x_(2n+1),x_2n] 2
Now X is going to win two extra bets on every interval that X bets first
on.
The indifference equation here will be:
x1-y2 = (x2-y2) + 2(x3 - x4) + 2(x5-x6) [....]
Let's do one more, but you can probably already see the pattern forming:
at y3:
X's hand
[y3,x2] -1
[x3,y3] 1
[x4,x5] 2
[x6,x7] 2
[...]
[x_(2n),x_(2n+1)] 2
x2 - y3 = y3 - x3 + 2(x4-x5) + 2(x6-x7) [.....]
And more generally, at y_n:
X's hand
[y_n,x_(n-1)] -1
[x_n,y_n] 1
[x_(n+1),x_(n+2)] 2
[x_(n+3),x_(n+4)] 2
etc...
So our general indifference equation here is:
x_(k-1) - y_k = y_k - x_k + 2(x_(k+2) - x_(k+3)) + 2(x_(k+4) - x_(k+5))
[...]
Now let's write the above, but for k+1 instead of k:
x_k - y_(k+1) = y_(k+1) - x_(k+1) + 2(x_(k+3) - x_(k+4)) + 2(x_(k+5) -
x_(k+6)) [...]
See how the alternating signs on the higher ks look like they'll cancel
out?
Let's add these equations to each other:
x_(k-1) - y_k + x_k - y_(k+1) = y_k - x_k + y_(k+1) + 2x_(k+2)
all the 2*x_(k+3) cancel each other out.
Gathering like terms and changing the indexes to a more convenient form:
x_k + 2x_(k+1) - x_(k+2) = 2y_(k+2) + 2y_(k+1)
Now, let's use our formula for y_n:
x_k + 2x_(k+1) - x_(k+2) = 2(1/(1-r))r^(k+2) + 2(1/(1-r))r^(k+1)
(r/(1-r)) = 1/sqrt(2)
x_k + 2x_(k+1) - x_(k+2) = sqrt(2)*r^(k+1) + sqrt(2)*r^k
x_k + 2x_(k+1) - x_(k+2) = sqrt(2)*r^k*(r + 1)
x_k + 2x_(k+1) - x_(k+2) = sqrt(2)*r^k*(sqrt(2))
x_k + 2x_(k+1) - x_(k+2) = 2r^k [**]
Now this is like our other difference equation, except that instead of
all the x_n terms adding up to zero, they equal a constant. It's called
a non-homogenous difference equation. This adds an extra step to our
solving process.
Our solution now will the sum of the "general solution" which is the
solution to the homogenous form of our equation summed with a
"particular solution" which is some value that actually satisfies the
equation for some known value.
x_n = a*s^n + b*t^n + ParticularSolution
so, let's solve our difference equation, the same way we did before:
1 + 2s - s^2 = 0
s = (-2 +/- sqrt(8))/-2 = 1 +/- sqrt(2)
s = 1 - sqrt(2) = -r
t = 1 + sqrt(2)
Using similar logic as before, we know that our 1 + sqrt(2) coefficient
will be 0, since we know that x_n, too, converges to 0.
So now we've got:
x_n = a*(-r)^n + ParticularSolution
Now, we're going to guess at the form of a particular solution.
We'll conjecture that b_n = b*r^n
Let's plug this into our non-homogenous equation [**]:
br^n + 2br^(n+1) - br^(n+2) = 2r^n
Dividing by r^n:
b + 2br - br^2 = 2
b(1 + 2r - r^2) = 2
b = 2 / (1 + 2r - (1 - 2r))
b = 2 / 4r = 1/2r
OK, so that solves for b.
Now we've got:
x_n = a*(-r)^n + 1/2r*r^n
Now let's solve for a. We know that x_0 is going to be 1.
1 = a*(-r)^0 + 1/2r*(r^0)
1 = a + 1/2r
a = 1-(1/2r)
a = (2r-1)/2r
So we have a general solution for x_n now:
x_n = ((2r-1)/2r)*(-r)^n + (1/2r)*r^n
x_n = r^(n-1) * ((2r-1)/2)*(-1)^n + (1/2))
x_n = r^(n-1) * ((2r-1)*(-1)^n + 1)/2
So now we have optimal strategies for X and Y.
y_n = (1/(1-r))*r^n
x_n = r^(n-1) * ((2r-1)*(-1)^n + 1)/2
What ends up happening here is that Y's strategy is basically
exponential in nature: each cutoff point is derived from the previous
cutoff point by a factor of r. X's strategy, on the other hand,
oscillates in its relationship to Y's strategy.
For example, y1 is at 1/sqrt(2). y2 is at r/sqrt(2), or 1 - 1/sqrt(2).
The distance between these two is:
1/sqrt(2) - (1 - 1/sqrt(2)) = (2 - sqrt(2))/sqrt(2) = sqrt(2) - 1 = r
Now, x1 is located at (1-2r+1)/2 = 1-r
If you measure the distance from y1 to x1, it's 1/sqrt(2) - (1-r) = (3 -
2sqrt(2))/sqrt(2)
If you divide that distance by the distance from y1 to x1, r, you get
that x1 is (r/sqrt(2)) of the way from y1 to y2.
But for x2, because of that (-1)^n term, you get a different result. In
this case, x2 is (1/sqrt(2)) of the way from y2 to y3, and this pattern
continues for larger n.
In fact, the absolute distance between x_n and y_n and x_(n+1) and
y_(n+1) is the same when n is odd. This reflects the idea that X can't
check-raise as much (relatively) as he bets out, because if he does,
then Y can exploit him by moving y1 closer to x1. Instead, for each
interval [y_n,y_n+1], x bets more than he check-raises. The other thing
that is interesting about this is that it means X checks exactly half
the time. Some 8.6% (3sqrt(2) - 2)/2) of the time he check-raises, the
rest of the time check-calls.
We'll calculate the value of this game in Part 6. In Parts 7 and beyond,
we'll take this methodology and extend it to finite pot cases.
Next: The value of the full infinite pot game
jacksup
installment.
Just a few (I hope simple) questions about Part 5, by far the most
complicated segment to this point.
> Game #5: infinite pot, infinite bets allowed. Check-raise is allowed.
>
> As we begin, as usual, we'll draw our line graph. Since check-raising is
> now allowed, both sides have values of x_n and y_n for all positive
> integer values of n. Note that each successive range of x_n dictates a
> different initial strategy - ie, from x3 to x4, X bets and then
> reraises, but from x4 to x5, X check-raises, and reraises again if given
> the opportunity. This will be important to how we structure the
> indifference equations at y_n, much later.
Would it matter if you hadn't structured x's initial strategy this
way? Might a strategy where all of x's check-raising hands are left of
x's betting hands also be optimal? I guess the question is, how did
you determine that you had an optimal strategy for x with these
alternating betting/check-raising ranges?
> x_n = a*(-r)^n + ParticularSolution
>
> Now, we're going to guess at the form of a particular solution.
> We'll conjecture that b_n = b*r^n
Do we ever show that this conjecture is right? I know it worked when
you plugged in the specific value of n, but do we know this is the
general form of b_n?
And finally...
> Now we've got:
>
> x_n = a*(-r)^n + 1/2r*r^n
>
> Now let's solve for a. We know that x_0 is going to be 1.
How do we know this? How do you define where x puts in the 0th bet?
Couldn't x_0 be infinity?
Great job on this, Jerrod and Bill. As always, I look forward to the
next part.
Matt
Bill chen
mattm...@hotmail.com (jacksup) wrote in message news:<473b8d61.03012...@posting.google.com>...
> I love this series of posts and always look forward to the next
> installment.
>
> Just a few (I hope simple) questions about Part 5, by far the most
> complicated segment to this point.
>
> > Game #5: infinite pot, infinite bets allowed. Check-raise is allowed.
> >
> > As we begin, as usual, we'll draw our line graph. Since check-raising is
> > now allowed, both sides have values of x_n and y_n for all positive
> > integer values of n. Note that each successive range of x_n dictates a
> > different initial strategy - ie, from x3 to x4, X bets and then
> > reraises, but from x4 to x5, X check-raises, and reraises again if given
> > the opportunity. This will be important to how we structure the
> > indifference equations at y_n, much later.
>
> Would it matter if you hadn't structured x's initial strategy this
> way? Might a strategy where all of x's check-raising hands are left of
> x's betting hands also be optimal? I guess the question is, how did
> you determine that you had an optimal strategy for x with these
> alternating betting/check-raising ranges?
Well it's that you show that your strategy is optimal after you solve
for the equations by showing that neither side can improve his
strategy to get higher EV.
You can solve the equations with a different parametrization but then
you will find that "something" goes wrong and the strategies you
generated are not optimal, or in some cases doesn't make sense as you
get negative threshold values or the order of the values doesn't
satisfy --we actually do this later when we play the [0,1] uniform
distribution against the weaker [0,1] x^2 distribution (which is
essentially drawing two cards and taking the maximum).
In the solution we obtain, we must make sure x_n is between y_n and
y_(n+1). Not only has Y made X indifferent between putting in n and
n-1 bets, but we can show that it would be worse for X to put in n-2
or fewer or n+1 or more.
>
> > x_n = a*(-r)^n + ParticularSolution
> >
> > Now, we're going to guess at the form of a particular solution.
> > We'll conjecture that b_n = b*r^n
>
> Do we ever show that this conjecture is right? I know it worked when
> you plugged in the specific value of n, but do we know this is the
> general form of b_n?
See, b_n doesn't need a general form. What we ultimately want is the
solution for x_n in the following inhomogenous equation:
x_k + 2x_(k+1) - x_(k+2) = 2r^k [**]
We know the general form of the homogenous equation solution:
a_k + 2a_(k+1) - a_(k+2) = 0
So to get the *general* form of the imhomogenous equation, all we need
to do is to add a particular solution b_n to the genral form of a_n.
See the way to look at it is that if x_n is a general solution to the
inhomogenoues equation, then x_n-b_n must be a solution to the
homogenous equation, and thus is covered by the general form of the
homogenous solution a_n.
>
> And finally...
>
> > Now we've got:
> >
> > x_n = a*(-r)^n + 1/2r*r^n
> >
> > Now let's solve for a. We know that x_0 is going to be 1.
>
> How do we know this? How do you define where x puts in the 0th bet?
> Couldn't x_0 be infinity?
Well, by clever detective work, we see that the first indifference
equation was:
>1-y1 = (x1-y1) + 2(x2 - x3) + 2(x4-x5) [....]
Notice the 1 at the beginning of the equation. So then Jerrod goes on
to say:
>So our general indifference equation here is:
>x_(k-1) - y_k = y_k - x_k + 2(x_(k+2) - x_(k+3)) + 2(x_(k+4) -
x_(k+5))
[...]
Now plug in k=1.
We see that he should have added: "where x_0 is defined to be 1." So
at the key point you quote, he could then say "remember that we
defined x_0 as 1."
>
> Great job on this, Jerrod and Bill. As always, I look forward to the
> next part.
>
> Matt
Thanks,
Bill