Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is my first post in Math section. I've been redirected here from StackOverflow, users from there suggested me to ask here.

This could appear a little bit complex at first sight but afterall there's nothing special.

We are in a poker touranment, there are 'n' players, each one has a stack of chips. There are only 'p' places to be paid at the end of the tournament.

We want to apply a math formula to convert the actual players' stacks into money. So we call 'equity' the probability of each player to finish the tournament in each paid place.

I'll hypothesize there are 4 players (P1,P2,P3,P4) and 3 paid places:

Equity on 1st place is:

$eq1_1 = ($P1_stack / $total_chips);
$eq2_1 = ($P2_stack / $total_chips);
$eq3_1 = ($P3_stack / $total_chips);
$eq4_1 = ($P4_stack / $total_chips);

Equity on 2nd place:

To calculate the equity of each player on 2nd place we have to hypothesize that each one of the remanent players has won the first prize, subtract his(the winner's) stack from the total chips, divide the player 2 chips by the remanent chips, and multiply this number by the probability(equity on 1st prize of the player who won the 1st prize). I know, brains' explosions have been reported here.

//-if P2 wins the tornament
$eq1_2 = $eq2_1*($P1_stack/($total_chips-$P2_stack));
//-if P3 wins the tornament
$eq1_2 = $eq1_2 + $eq3_1*($P1_stack/($total_chips-$P3_stack));
//-if P4 wins the tornament
$eq1_2 = $eq1_2 + $eq4_1*($P1_stack/($total_chips-$P4_stack));

if there would have been more players the cycle should have continued.

Equity on 3rd place

If your brain hasn't exploded yet, it will after you'll read this :p To calculate P1 equity on 3rd place we have to: 1) Subtract the winner AND the second winner stacks from the total chips. 2) Subtract P1 stack from the number we got. (Remainingstack) 3) Calculate the equity of the second winner on second place after a winner has been hypothesized. 4) Multiply the number we got (3)(P1_stack/ Remainingstack)Equity of the winner on 1st place.

I've written a working code so far but it works only if there are 3 paid placed. I'd like to modify it to get a more elegant and versatile way to get equity even if the paid places are more than 3.

This is my code: http://codepad.org/Q62l2wfv

I'm not an expert coder but maybe by doing it with a recursive call it should be faster and equity on 4th, 5th, 6th place can be calculated with no difficulties.

share|improve this question
1  
Yes, it sounds exactly like a recursive call. But first, let me see if I've got this straight. What you're doing appears to be equivalent to the following procedure: Pick a random chip. Whoever it belongs to gets first place, and their chips are discarded. Repeat to pick second place, third place, and so on. Then the equity of player $i$ on $j$th place is the probability that player $i$ gets $j$th place after this procedure. Right? –  Rahul Dec 20 '11 at 13:51
    
Yes! it's exactly that! –  Tom Dwan Dec 20 '11 at 13:56
add comment

1 Answer

up vote 4 down vote accepted

Okay, let's represent the stacks by a (given) vector $s = [s_1, s_2, \ldots, s_n]$, and the equity by an (unknown) $n\times n$ matrix $$E = \begin{bmatrix} e_{11} & e_{12} & \ldots & e_{1n} \\ e_{21} & e_{22} & \ldots & e_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ e_{n1} & e_{n2} & \ldots & e_{nn} \end{bmatrix}$$ representing the probability that player $i$ gets place $j$. This matrix is a function of $s$, let's say $E = f(s)$. Note that I'm filling up all $n$ places; if you have fewer, just ignore the later columns.

Suppose player $i$ were to get first place. If this happens, you remove him from the game, find the places of the other players, and then shift them all down by one to put player $i$ back in 1st place. So:

  • Remove player $i$ from the stacks, giving $s\setminus s_i = [s_1, s_2 \ldots, s_{i-1}, s_{i+1}, \ldots, s_n]$.
  • Do a recursive call on $s\setminus s_i$, yielding the matrix $E'_i = f(s\setminus s_i)$ representing the equity of everyone else if player $i$ did not exist.
  • $E'_i$ is an $(n-1)\times(n-1)$ matrix. Add a column of zeros at the beginning (everyone else has probability zero of being in first place), and insert a row $[1, 0, \ldots, 0]$ at the $i$th position (the only place player $i$ can have is first). This new $n\times n$ matrix is the equity of all players, conditional on player $i$ getting first place. Call this matrix $E_i$.

Of course, player $i$ only gets first place with probability $$p_i = \frac{s_i}{\sum s_j}.$$ So the actual value of $E$, taking into account all the players' probability of winning, is simply $$E = \sum p_i E_i.$$

share|improve this answer
    
I am re-reading your answer two years later. It's really one of the greatest anwer I've ever had in this website. I don't know if you're familiar with some coding languages, however I've created a PHP version of your "model"; however it's too slow for my purpouses. Could you recomend some other languages to make it faster? Or, in alternative, is it possible to simplify your "model"? Thanks in advance. –  Tom Dwan Dec 7 '13 at 11:14
    
I coded it up in Mathematica to see if the result simplifies at all. It doesn't. If you have $s=\{a,b,c,d\}$, here's what the first row of $E$ looks like. The first element is $\frac a{a+b+c+d}$ obviously, the second element is $\frac b{a+b+c+d}\cdot\frac a{a+c+d} + \frac c{a+b+c+d}\cdot\frac a{a+b+d} + \frac d{a+b+c+d}\cdot\frac a{a+b+c}$ (either $b$ wins and $a$ comes second, or $c$ wins and $a$ comes second, or $d$ wins and $a$ comes second), the third element is $\frac b{a+b+c+d}\cdot\frac c{a+c+d}\cdot\frac a{a+d} + \cdots$ with five other terms... –  Rahul Dec 7 '13 at 18:53
    
My algorithm has a cost of $T(n) = nT(n-1) + O(n^3)$, which seems to be superpolynomial, so it will get pretty expensive if $n$ is large. I don't have any ideas for a faster approximate algorithm. You could try reimplementing in C/C++ and see if that's fast enough for you, or you could start a bounty on this question asking for an asymptotically faster algorithm. –  Rahul Dec 7 '13 at 19:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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