5
$\begingroup$

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.

  • 0
    Yes! it's exactly that!2011-12-20

1 Answers 1

4

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.$

  • 0
    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.2013-12-07