Tom Weideman
6/25/97



Some time back, there was a raging discussion here about the proper
3-way split at the end of a percentage prize payout tournament with
players of equal playing ability.  I believe it was started because a
Card Player article written by McEvoy on the subject in which he
butchered the math involved was subsequently corrected by Malmuth (in
his usual tact-free manner), who pointed to his work in _Gambling
Theory_.  Silly arguments ensued along the lines of McEvoy being more of
an authority because he plays tournaments and Malmuth doesn't, etc.  I
want to make it clear from the start that it is not the intention of
this post to start this nonsense back up again -- I just want to do my
part to further our knowledge in this area.  I started thinking about
the problem back then, and it has remained on the back burner for some
time since.  Recently I returned to it, and I'd like to share my
preliminary results.  Keep in mind that these results ARE preliminary,
and that much more needs to be done.

I think of this problem as a 3-way gambler's ruin.  We are given the
three bankrolls, and assuming a fair game (the players are assumed to be
of equal ability, otherwise the problem gets even tougher), we want to
know the probabilities of each player finishing in each position.  I
looked through whatever literature I could find, but I saw no mention at
all of a gambler's ruin problem involving more than 2 competitors.  So I
came up with my own method.  Unfortunately, this particular method only
works with 3 players, but (with great effort) it certainly can be
generalized to more players if necessary.

Consider the following triangular diagram:

                              A
                             / \
                            a - b
                           / \ / \
                          c - d - e
                         / \ / \ / \
                        f - g - h - i
                       / \ / \ / \ / \
                      B - j - k - l - C

• In this diagram, the capital letters A, B, and C represent the
different contestants in the tournament.
• Each labelled point represents a possible state of the tournament.
• The three vertices of the large triangle represent a win for its
respective player.
• The sides of the large triangle represent eliminations of the player
whose vertex is across from it.  For example, positions A, a, c, f, and
B represent possible states of the tournament where player C has been
eliminated.
• Each dashed line represents a confrontation between two players.  The
two players involved are those whose side of the big triangle is
parallel to the line.  For example, going along the line from d to h
represents a confrontation between A and C where C was the winner.

Since a vertex of the big triangle means that a player has all of the
chips, and the side opposite the vertex means that player has none of
them, then each successive parallel row represents the various states in
between.  For simplicity, we will refer to each row as being "1 bet",
without specifying it any further.  Each confrontation between two
players is therefore contesting 1 bet.  Thus the example of d-to-h given
above would read "A loses 1 bet to C".  The row a-b has player A with 3
bets, c-d-e two bets, f-g-h-i 1 bet, and B-j-k-l-C 0 bets.  The row i-l
has player C with 3 bets, e-h-k 2 bets, and so on.

Now the question becomes: "Given an initial state of the tournament
(pick a letter in the diagram), what are the probabilities of player A
finishing 1st, 2nd, and 3rd?"  The math is actually pretty easy (though
tedious).  First, a couple rules regarding the use of the triangle:

1) Once an outer edge is reached, it cannot be exited (i.e. there is no
way for someone to return to the tournament once eliminated).
2) Every transition direction exiting from a letter has an equal
probability of every other (with the exception of the zero probabilities
generated from (1) above).  For example, the probability that the state
of the tournament will go from d to a is the same as d to b, c, e, g,
and h (i.e. it is 1/6).  Similarly, the probability of the state of the
tournament going from c to a is the same as c to f (i.e. it is 1/2).

Okay, now for a calculation.  The number of bets in play is 4 (count the
number of rows), so we'll choose the starting point:

A = 2 bets,  B = 1 bet,  C = 1 bet

The point on the diagram for this is d.  Let's start by calculating the
probability of player A being eliminated first.  From here on, the
letters will be variables that equal the probability of this outcome at
the state of the tournament they represent on the diagram.  We thus seek
the value of d.

The probability d is the sum of products of conditional probabilities:

d = (1/6)a + (1/6)b + (1/6)c + (1/6)e + (1/6)g + (1/6)h

Notice that a, b, c, and e are states where another player has been
eliminated, so the probability that A is eliminated first in these
states is zero:

a = b = c = e = 0

Also note that the symmetry of the triangle demands that g = h, leaving
the simple relation:

*** d = (1/3)g ***

Now we need g, so we repeat the process:

g = (1/6)c + (1/6)d + (1/6)f + (1/6)h + (1/6)j + (1/6)k

States j and k both represent eliminations of A, while c and f are
eliminations of C, so:

c = f = 0, j = k = 1

Plugging in these numbers as well as h = g gives the equation:

g = (1/6)d + (1/6)g + 1/3

*** 5g = d + 2 ***

Now solve the two starred equations simultaneously for d to get:
---------
| d = 1/7 | ( = Probability of A finishing third)
---------

This is NOT Malmuth's result.  For the same starting conditions, he gets
a probability of 1/5.  I believe the source of the problem for Malmuth's
calculation is the assumption that when 1 player busts out, each of the
other players will get half of the busted player's chips.  Of course, he
also assumes that the number of total bets held by each player is large
(i.e. no one is about to be put all-in), but his reasons for this
assumption are poker related (i.e. he wants the number of hands that a
each player has position over the other to even out), and doesn't apply
to my method, which assume equal probabilities of all results (washing
out poker-related edges held by players).

Now to finish off this particular example:

• The probabilities of B and C coming in 3rd are the same of course,
which makes them 3/7 (you get this if you do it the long way too).

• Repeating the process so that it ends at the vertex A gives the
probability that A will win, and it coincidentally comes out to be the
same probability that Malmuth gets: 1/2.  HOWEVER, it is not immediately
clear that there is agreement in all chip distributions.  More work has
to be done in this area to prove or disprove this.  Malmuth makes a good
argument for this being the case (by considering the expectation for the
freeze-out tournament situation), so if my method does not get the same
results each time regarding finishing first, then something is clearly
wrong somewhere.

• Repeating the process so that the course of the tournament eliminates
either B or C first, and then elimnates A gives the expected probability
of 5/14 (this is expected because adding it to 1/2 and 1/7 gives unity).

Recap for player A with A = 2, B = 1, C = 1:
                         1st       2nd       3rd
Malmuth probabilities:  (1/2)     (3/10)    (1/5)
Weideman probabilities: (1/2)     (5/14)    (1/7)

Okay, what does this mean in terms of money?  Well, clearly the correct
payout is more heavily weighted toward the chip leader than Malmuth
claims.  Specifically, for a payout of 50%, 30%, 20%, the payoffs to
player A are:

Malmuth:  (1/2)(50%) + (3/10)(30%) + (1/5)(20%) = 38.00% of prize fund
Weideman: (1/2)(50%) + (5/14)(30%) + (1/7)(20%) = 38.57% of prize fund

This is not a huge difference (only $571 in a $100k purse), but it is
not obvious whether these two methods converge or diverge for other more
complicated cases.

At this point I'd like to describe some problems with my method:

1. I have not yet proven/disproven that my method predicts that the
probability of winning the event is equal to the fraction of the total
number of chips the players holds.  I plan to at least work out the
3,1,1 case to test the conjecture.

2. I've shown a result for stack sizes of 2 bets, 1 bet, and 1 bet, but
I have not proven that the same result occurs for any number of bets in
the same proportions.  I'm still working on this (I haven't even gotten
around to calculating the results for A=4, B=2, C=2 yet).  If in fact
the results DO change for greater numbers of total bets, then one
consequence is that some players gain and others lose as the betting
limits of the tournament go up.

3. I haven't yet developed a simplified method for calculating the
result for three arbitrary stack sizes (even on a computer).  So far I
have to do the algebra in each individual case (and don't be fooled by
the apparent simplicity of this one case -- as the number of total bets
available increases, the amount of tedious labor increases very
rapidly).  Matrix methods are looking promising for solving the general
case, and work is still in progress.

4. Extending the method to a case where the players do not play equally
well is difficult.  Actually, assuming a good mathematical assumption
can be made regarding relative playing ability, each individual case can
be calculated, but the generalization mentioned in #2 seems even more
daunting.

5. Three-way confrontations in a single hand are not considered in my
method.  Incorporating these is particularly difficult, and it is not
clear that they will contribute much to the final answer.  Still, any
departure from possible real scenarios should be mentioned.

Any feedback from you math.weenies out there is appreciated.

Tom Weideman