Exploring how marginal chip value changes with stack size

[WRX]

[ QUOTE ]
What is ICM?

[/ QUOTE ]

"Independent Chip Model." It's commonly used, and you'll find lots of discussion about it around here. You could call it a lottery ticket model. Give each player a number of tickets equal to the number of chips he has. Draw one ticket at random to determine first place. Then throw out all the tickets of the first-place winner, and draw one from the remaining tickets to determine second place. Etc. You can see that with a lot of places to be decided, and varying stack sizes, this gets complicated fast.

[pzhon]

[ QUOTE ]

What is ICM?


[/ QUOTE ]
Shuffle the players' chips. Rank the players by their highest chips. Equivalently, remove the chips from the table one at a time, eliminating a player when his last chip is removed.

Independent Chip Model calculators:
http://www.chillin411.com/icmcalc.php
http://sharnett.bol.ucla.edu/ICM/ICM.html (not as convenient, but it has some explanations)

You can write the formulas for n players by summing over the possible first place finishers, removing their chips, and applying the ICM to the reduced tournament on n-1 players. This doesn't seem to simplify. Does anyone know what the probabilities are of finishing last in a tournament where the stack sizes are 1, 2, ..., 100?

[ QUOTE ]

Is it random walk (brownian motion) on a simplex with absorbing boundaries? I saw Tom Ferguson wrote an exact solution for n=3 players. What else is known?

[/ QUOTE ]
The Brownian motion model is different. It's simple to analyze with 3 players because conformal transformations in two dimensions are understood and preserve Brownian paths, and the Riemann maps from the triangle to the disc are even known explicitly. Conformal transformations in higher dimensions are much more rigid, and there isn't much hope to extend the solution to more players without adding ideas.

[WRX]

[ QUOTE ]
I skimmed and did not carefully read, but let me make a couple of points.

(1) The derivative you mention is a particlar directional derivative, but you could consider any direction (or consider all partial derivatives).

(2) But you cannot generally use derivatives, since F may have discontuities.

Just consider the case where 3 (or more) players (on one table) each have the strategy of going all in on every hand. (Or suppose the blinds/antes had doubled every nanosecond so that now everyone is all in on every hand.) Then clearly, treating x_1,...,x_r,...,x_n (n at least 3) as real variables, each F_r will have a discontinuity wherever two variables are equal, chopping the n-simplex into n! pieces.

[/ QUOTE ]

Since one can't win or lose fractions of a chip, doesn't every situation present discontinuities?

It strikes me that since one can't come up with a mathematical formula for any real-world F_r (as opposed to a radical simplification like the ICM), one isn't going to be able to obtain a derivative anyway. And that we're not so much interested in the derivative at any one point as we are in knowing delta F_r/delta x_r between two given values of x_r.

But I'm stumbling in the dark.

[pzhon]

[ QUOTE ]
This leaves open the interesting possibility that the general statement of the ICM might reduce to a relatively simple formula, through the application of higher mathematics. Does anyone know if this has been attempted? Or if it's been shown to be impossible?

[/ QUOTE ]
I've tried and failed so far, but some simplifications could be possible.

One way of ruling out some levels of complexity is to work out examples exactly. Some of the denominators are huge, so any simplification would still have to be able to produce huge denominators, too.

[ QUOTE ]
[ QUOTE ]
Does anyone have a good (ICM) approximation? I found one which is computable, but which does not preserve the property that the matrix of finishing probabilities has the property that each row and column sum to 1.

[/ QUOTE ]

Is this approximation available anywhere?

[/ QUOTE ]
No, at least not from me. Others could have developed it independently, as I just made some crude approximations and renormalized some probabilities to 1.

[ QUOTE ]
[ QUOTE ]
Another tractable problem related to the ICM is showing that you always lose E$ when you take an EChip-neutral gamble. As I recall, no one posted a proof on a past thread where this was conjectured. Maybe it would be good to gamble to knock out the short stack on the bubble when you have the second or third stack, but the ICM doesn't seem to say this.

[/ QUOTE ]

Isn't this another way of saying that for any case of the ICM, the curve is always convex end-to-end?

[/ QUOTE ]
I think the curve you mean is the result of taking chips from all opponents equally or in proportion, but I refer to gambling against each opponent individually. I expect that a counterexample could be constructed easily if you allow sidepots, but perhaps multiway gambles are also ok if there are no sidepots.

I didn't specify the payout structure, and I think it should hold for all decreasing structures. It suffices to prove it for satellites, i.e., that the probability of reaching the nth place or higher always decreases when you take an EChip-neutral gamble.

[thylacine]

[ QUOTE ]
[ QUOTE ]
This leaves open the interesting possibility that the general statement of the ICM might reduce to a relatively simple formula, through the application of higher mathematics. Does anyone know if this has been attempted? Or if it's been shown to be impossible?

[/ QUOTE ]
I've tried and failed so far, but some simplifications could be possible.

One way of ruling out some levels of complexity is to work out examples exactly. Some of the denominators are huge, so any simplification would still have to be able to produce huge denominators, too.


[/ QUOTE ]

Would I be right to say that if you want to input integer stack sizes, and output exact rational numbers for the probability of player i getting position j in this ICM model, then in terms of encoding input and output as binary strings, the output length is exponential in the input length?

[pzhon]

[ QUOTE ]
[ QUOTE ]

One way of ruling out some levels of complexity is to work out examples exactly. Some of the denominators are huge, so any simplification would still have to be able to produce huge denominators, too.


[/ QUOTE ]

Would I be right to say that if you want to input integer stack sizes, and output exact rational numbers for the probability of player i getting position j in this ICM model, then in terms of encoding input and output as binary strings, the output length is exponential in the input length?

[/ QUOTE ]
It could be worse than that, as a factorial is involved, but I think that is a poor measure of complexity. n! and (2n choose n) would also seem very complicated that way.

[pzhon]

[ QUOTE ]
Does anyone know what the probabilities are of finishing last in a tournament where the stack sizes are 1, 2, ..., 100?

[/ QUOTE ]
I still don't, but here are some calculations of the ICM-predicted probability of finishing last in tournaments with stacks of size 1, 2, 3, ..., n.

n=2
1 2/3
2 1/3

n=3
1: 0.5833333333333334
2: 0.2666666666666666
3: 0.15

n=4
1 0.5511904761904762
2 0.24126984126984127
3 0.12976190476190477
4 0.07777777777777778

n=5
1 0.5361360861360861
2 0.22936507936507936
3 0.12031302031302031
4 0.07022977022977023
5 0.04395604395604396

n=10
1: 0.5184164152973668
2: 0.2151557713105984
3: 0.10893008631761322
4: 0.06109750853503585
5: 0.036606485042195436
6: 0.022998223608975937
7: 0.014984758061417186
8: 0.010053105474764727
9: 0.006909801915833682
10: 0.0048478444361987425

n=15
1: 0.5165407213004611
2: 0.21359514003346372
3: 0.10763726163687229
4: 0.06002971007838609
5: 0.03572609821501513
6: 0.02227291325368989
7: 0.014387192991584257
8: 0.009560467771416203
9: 0.006503209213545211
10: 0.0045117668120416956
11: 0.003183781349335634
12: 0.0022802773367725966
13: 0.001654769973221269
14: 0.0012150347599461867
15: 0.0009016552742487154

A brute-force calculation for n=15 (of all probabilities in all places) took only 2 minutes in Mathematica, but that method would run out of space around n=20 on my computer.

<ul type="square">
Mathematica code:

Clear[places]
places[n_, stacks_] := places[n, stacks] = If[Length[stacks] == 1, {1},
(1/Sum[stacks[[j]], {j, Length[stacks]}])
(Table[If[i == 1, stacks[[n]], 0], {i, Length[stacks]}] +
Sum[If[k &lt; n,
stacks[[k]]Prepend[places[n - 1, Delete[stacks, k]], 0],
stacks[[k + 1]]Prepend[places[n, Delete[stacks, k + 1]], 0]],
{k, Length[stacks] - 1}]
)
]
fullplaces[stacks_] := Table[places[i, stacks], {i, Length[stacks]}]

Input: places[1,{2,3,7}]
Output: {1/6, 13/45, 49/90}

Input: fullplaces[{2,3,7}]
Output: {{1/6,13/45,49/90},[1/4,2/5,7/20},{7/12,14/45,19/180}}
[/list]The total number of intermediate distributions calculated is the number of sub-multisets of the opponents' chip counts (when equal stack sizes are entered next to each other), at most 2^n when there are n other players. However, the coefficients are quite complicated.

From the data, I conjecture that as n increases, the probability that the player with the smallest stack finishes last converges to something over 1/2. It's easy to prove some upper and lower bounds, e.g, that the value is greater than the product of (1 - 1/(k choose 2)) from k=3 to infinity, 1/3. The general behavior for the larger stacks may be of more interest.

[pzhon]

[ QUOTE ]
I recommended the use of the ICM as a settlement for stopped tournaments to a major poker server. They seemed interested until I mentioned that the exact calculation is complicated, and they may need to use an approximation if there are hundreds of players. Does anyone have a good approximation?

[/ QUOTE ]
I think I have found a fast way to calculate the probabilities of placing in each position when the stacks are small multiples of a common chip size. This may be good enough in practice. While the results are complicated if computed exactly, this method should be numerically stable. Errors in approximations of intermediate steps should not blow up.

Start with just the target player's stack. Add the other players' stacks one by one, maintaining a joint distribution of the location of the player's highest chip and the player's rank. At the end, ignore the extra information about the location of the player's highest chip, i.e., sum over the possible locations.

I think this basic idea can be used to prove the convexity conjecture, too, by adding the player's and opponent's stacks last.

[pzhon]

ICM-predicted probabilities of finishing last with chip stacks 1, 2, ... 100:

1 0.51609432333124221785
2 0.21321188990848979709
3 0.10730956751035384068
4 0.059750455028267008731
5 0.035488752610857001093
6 0.022071595113771953758
7 0.014216683846631049432
8 0.0094161950449655082157
9 0.0063812062388728451803
10 0.0044086199339784030072
20 0.00021111503066950183804
30 0.000019498738229098345387
40 2.554789938882243882844891 x 10^-6
50 4.202955272341909711638795 x 10^-7
60 8.145255901318414223432787 x 10^-8
70 1.789417913036532507262767 x 10^-8
80 4.344852176919571241218451 x 10^-9
90 1.145466693678780882931910 x 10^-9
100 3.23650498103496640628121 x 10^-10

This took 12 hours with the faster method I described. It's still not quite fast enough to use on large tournaments as implemented in Mathematica, but it might be fast enough when programmed directly.

<ul type="square">
newarray[probarray_, addstack_] := {chiptotal = Length[probarray[[1]]];
Table[(1/Binomial[chiptotal + addstack, addstack])
(Binomial[chiptotal - j + addstack, addstack]
If[j &lt;= chiptotal &amp;&amp; ii &lt;= Length[probarray],probarray[[ii]][[j]], 0] +
Sum[If[k &gt;= j || ii == 1, 0,
Binomial[j - 1, k] Binomial[chiptotal - j + addstack, addstack - k]
If[j - k &lt;= chiptotal, probarray[[ii - 1]][[j - k]]],0], {k, addstack}]),
{ii, Length[probarray] + 1}, {j, chiptotal + addstack}]}[[1]]

fullarray[initstack_, oppstacks_] := fullarray[initstack, oppstacks] =
{temparray = {Table[If[ii == 1, 1, 0], {ii, initstack}]};
Do[temparray = newarray[temparray, oppstacks[[ii]]], {ii, Length[oppstacks]}];
temparray}[[1]]
[/list]

[pzhon]

[ QUOTE ]

I think this basic idea can be used to prove the convexity conjecture, too, by adding the player's and opponent's stacks last.

[/ QUOTE ]
That method didn't seem to work, but I proved the conjecture in a more direct fashion.

Let f(x) be the ICM-predicted probability that player A finishes in the top n places after taking x chips from player B.

Claim: f"(x) &lt; 0.
Proof: f(x) is the complement of the probability that player A is not among the top n players, which can be written as a constant (wrt x) plus a sum of terms with positive coefficients in proportion to

b-x
(b-x)/(c_1+x)
(b-x)/((c_1+x)(c_2+x))
... or
(b-x)/((c_1+x)(c_2+x)...(c_(n-1)+x))

It suffices to show that each of these terms has nonnegative second derivative.

Inductively, if g(x)&gt;0, g'(x)&lt;0, and g"(x)&gt;0, then the same is true of h(x) = g(x)/(c+x), where c&gt;0. This is satisfied by (b-x), so it is satisfied by (b-x)/(c_1+x), etc.

This shows that for any sensibly non-decreasing distribution of prizes, the ICM will predict that your E$ can't increase by taking an EChip-neutral gamble in a 2-way pot.