Derivation of Independent Chip Model (ICM)

[Collin Moshman]

Hi Tony,

This is an excellent post. I think it is open-minded indeed to start by demonstrating that P(J,1) = Sj/T which is usually taken for granted. Cool that the simulations jived with that idea as well. Assuming equal skill, it is a very intuitive result, but since it is used so often (in general tourny contexts, not just SNGs), I appreciate this justification.

I think the heart of your argument, and the most useful to those who want a theoretical, yet brief, justification of ICM, is this:

[ QUOTE ]
Let Si denote player i's stack. Player i's P(1st) = Si/T, so that's equivalent to player i winning a heads up match against you, where you hold T - Si chips which is, in turn, equivalent to you winning the sub tournament of k - 1 players consisting of T - Si chips. Your probability of winning that sub tournament is S/(T - Si)

[/ QUOTE ]

If this were a math class, a good homework problem would be:
Anywhere "equivalent" is used in the above quote, substitute an = sign and justify the statement the equality.

In my book I go through a simpler derivation for N=3 and concrete stack sizes, but this is a stand-out theoretical argument for the general case.

Best Regards,
Collin

[HighEV]

As a blanket response to the posts I've seen so far, the point of this post was to provide justification for a mathematical model that most players blindly use without knowing why its actually true. I once searched for justification online and was highly disappointed, so this post was for curious minds like mine.

I agree completely that you don't have to do the rigorous analysis like I provided to be a profitable player. However, I disagree with the notion that this means that such theoretical discussion is useless...understanding the underlying theory can do nothing but strengthen your game. Some theoreticians go overboard without giving any concrete playing examples whatsoever, but when the theory is tied to actual playing conditions, then the results are very powerful. The key in tying theory to playing conditions is to carefully treat the nuances of each situation separately...blanket responses are very dangerous.

ICM can be used in a wide range of circumstances, and once you understand the theory (along with good software and possibly a spreadsheet), analyzing even complicated situations isn't too bad...though it can be really time consuming in some cases. By applying rigorous analysis, it's possible to deduce conclusions that deviate from commonly accepted norms.

Many people seem to think that ICM is limited to analyzing decisions for a single hand...that's simply not true. For example, suppose you're down to three players. Every one has 6,000 chips, and the blinds are 500-1,000. You are dealt 72o, and you're in the small blind. The button folds, and you know that the BB will call an all-in with [AA,66]||[AK,AT]. When you push all-in, you can find the corresponding probabilities for each of your potential stack sizes ({push, called, win}, {push, called, lose}, {push, called, tie}, {push, steal}) and crank ICM analysis for each of those possibilities, weight the results accordingly and get your EV for pushing. Then, you can figure out what happens if you fold with the intention of pushing all-in next hand with a specific distribution (in fact, you can do ICM analysis to deduce the optimum distribution to be pushing with from the button).

You can tree out ALL your possible lines of play, applying ICM to each one and eventually deducing the line of play with the highest EV. In that sense, ICM calculations can be used to optimize decisions when considering play of future hands. ICM is much more powerful than most people realize. It's just that realizing the full power sometimes involves some really time-consuming calculations.

Tony G

[dwigt]

Didn't read the whole thread yet, but to prove that P(first)=S/T for all the rules you suggest you can use optional stopping theorem applied to the stopping rule tau=end of tourney. The stacks form a martingale and E[tau]<infinity is cleary finite.

The question I have is when for example the players are playing NE strategies, do the stacks form a martingale? At has to be at least a little bit off due to the blinds and for us to care about ICM, the disadvantages of the blinds are relevant.

[Shillx]

It is too tough to quantitatively employ all the things you suggest. It is pretty easy to see when ICM under/over shoots your equity and you can then make the proper adjustments. It probably takes 10-20 minutes to run a simulated ITM hand in SNGPT and it doesn't even factor in overcalls. To run one that can factor in overcalls, skill, blinds, implied edge, etc would be very tough. You also have to consider that each ITM hand has 7 possible outcomes so the tree will get large very quickly. It is pretty easy to make qualitative changes but it seems unlikely that the true NE will surface anytime soon.

[Galwegian]

[ QUOTE ]
There's a lot of great information out there concerning how to use ICM properly, including the following thread referenced in the STT FAQ:

http://archiveserver.twoplustwo.com/...te_id/1#import

There's not much along the lines of justifying the model...at least not much that I've been satisfied with (I'm assuming the link to the UCLA site was awesome, but it's been dead for as long as I've known). This post is an attempt to alleviate that problem [img]/images/graemlins/smile.gif[/img]

The first issue to tackle is proving the assumed notion that your probability of finishing in 1st, denoted as P(1st), is equal to S/T

S = Your Stack Size
T = Total Number of Chips in Play

If we let n denote the number of double ups required to obtain all the chips in the tournament, then T = S(2^n). Solving this expression for n, we get n = log2(T/S), where log2 is my way of referring to a base 2 logarithm since I have no subscripts to work with here [img]/images/graemlins/smile.gif[/img]

Now, assuming your probability of doubling up is D, then the following expression is true:

P(1st) = D^n. Assuming that you and your opponents are of equal skill (this is the only assumption that ICM makes, and it's a great assumption given the push or fold nature of most endgames...especially STT endgames), P(1st) = (1/2)^n. Substituting n = log2(T/S), we get that P(1st) = (1/2)^log2(T/S) = S/T. Bang!

Now, of course, many out there might cry out that a tournament doesn't take place as a series of double-ups. Since that's true, I ran four computer simulations (well, technically, a good friend of mine ran them since my coding skillz are a bit rusty and I was too busy to brush up, but anyway...).

Simulation #1 was a heads-up match in which both players went all-in every hand. Simulation #2 was a heads-up match in which the small blind limps and both players check the hand to the river. Simulation #3 was a three-handed tournament in which all players went all-in every hand. Simulation #4 was a three-handed tournament in which all players limped preflop and checked down to the river. All these simulations were done for lots of different combinations of relative stack sizes.

The results of these four simulations agreed with the derived result that P(1st) = S/T.

Having proven that P(1st) = S/T, we can now use this piece of information along with conditional probabilities to derive the general ICM formula.

Using conditional probabilities to deduce your P(2nd), we get the following, where P(x,y) is the probablity that player x finishes in yth place (you are player M):

P(M,2) = P(1,1)P(M,2|1,1) + P(2,1)P(M,2|2,1) + ... P(k,1)P(M,2|k,1)

In this expression, P(M,2|i,1) is the probability that you finish in 2nd given that player i finishes in first. Effectively, this probablity is the same as your probability of winning a reduced tournament against every player except player i:

Let Si denote player i's stack. Player i's P(1st) = Si/T, so that's equivalent to player i winning a heads up match against you, where you hold T - Si chips which is, in turn, equivalent to you winning the sub tournament of k - 1 players consisting of T - Si chips. Your probability of winning that sub tournament is S/(T - Si) (recall that S is your stack size) The reason we can just ignore player i's chips in the sub tournament is because player i finishing in first is effectively the result of him winning a heads up match in which he starts with Si chips.

Since player i's probability of placing first is Si/T, your probability of finishing in second is the sum of (Si/T)(S/(T - Si))

Having considered P(2nd), we can generalize this process to come up with P(nth):

P(nth) = Sum[P(a,1)P(b,2)...P(k,n-1)P(M,n|finishing order of top n-1 players)]

Essentially, all this formula means is that you consider each possible subtournament of k - (n-1) players and weight the result of each appropriately according to the finishes of the top n-1 players. Your probability of finishing in nth in each possible sub tournament is S/(T-S1-S2-S3-...-Sn-1). In other words, you ignore the stack sizes of the top n-1 finishers and you then just find the probability of you winning a minitournament between every one else. It's a long recursive process that you don't want to have to do by hand. And actually, the number of terms required to find P(nth) in a k player tournament is (k-1)!/(k-n)!, so this formula even has limited use on computers if you want to get results instantly (for example, the sum contains 32,432,400 terms when you find your probability of finishing in 8th in a 16 player tournament and 57,657,600 terms when you find your probability of finishing in 8th in a 17 player tournament). However, given that this model assumes players of equal skill, it's really only best applied at the end of tournaments anyway.

Well, I hope this helps those out there who've been trying to justify why the ICM model works. I'm looking forward to hearing people's additional thoughts here!

Tony Guerrera

[/ QUOTE ]

Tony
There is a simpler way to see that P(1st) =S/T.
If all players have equal skill level then your expected number of chips after "infinitely" many hands = S (ie your chip count should stay constant in the long run). However, your expected number of chips = P(1st)T, since the 1st place player ends up with T chips. Therefore,
P(1st) T = S or P(1st) = S/T.

[Collin Moshman]

[ QUOTE ]
You can tree out ALL your possible lines of play, applying ICM to each one and eventually deducing the line of play with the highest EV. In that sense, ICM calculations can be used to optimize decisions when considering play of future hands. ICM is much more powerful than most people realize. It's just that realizing the full power sometimes involves some really time-consuming calculations.

[/ QUOTE ]

Do you think this could be coded, assuming some calculation-reducing assumptions could be made? Don't get me wrong, it is still an interesting theoretical idea regardless, but do you disagree with Shillx and think software could indeed emerge from it with the introduction of reasonable simplifying assumptions?

Best Regards,
Collin

[beserious]

[ QUOTE ]
Having proven that P(1st) = S/T, we can now use this piece of information along with conditional probabilities to derive the general ICM formula.


[/ QUOTE ]

I like your post, but your argument is definitely not a PROOF that P(1st) = S/T. It seems like you drew this conclusion based on four arbitrary simulations, none of which are remotely close to how good players would play in reality. An actual proof that P(1st) is approximately S/T with optimal play with 2 players left is in this paper: http://www.daimi.au.dk/~trold/papers/poker.pdf. The generalization to n players is reasonable, but would be much more difficult to prove.

[HighEV]

There is clearly a lot of think about on the software front. I know a non-commital stance is sometimes seen as the easy way out, but I'm taking one here.

I lean towards saying that such a software package is possible. At the same time, though, I acknowledge the validity of Shillx's assertion, and if I were to work on such a software package and run into the a problem where the number of calculations required grew at an unreasonable rate that made analysis impractical, I wouldn't necessarily be surprised.

Generally, though, I believe that solutions to seemingly impossible problems arise when one looks at things from enough different perspectives.

[HighEV]

beserious,

Thanks for the article reference. I really want to read the article, but the link you provided doesn't work [img]/images/graemlins/frown.gif[/img]

I concede that I used the word "proof/prove" too loosely...I write 1000's of words per day, so I guess a bad word choice has to slip in once in awhile. I hope I'm not slowly regressing towards the mediocrity that today's society is so complacent to accept [img]/images/graemlins/smile.gif[/img]

Without having read the article, I do have one possible point of contention to make. You say the article proves the S/T formula for optimal play; however, what if two players play identically even if not optimally? I think that all our time spent playing profitable poker reveals that assuming two players will tend towards optimal play is absurd [img]/images/graemlins/smile.gif[/img]

Everyone,

Thanks for some interesting posts so far! A lot of people seem to worship the ground I walk on, so butting heads with the intelligent, assertive minds in this forum is a refreshing (and necessary) change of pace!

[HighEV]

[ QUOTE ]
Tony
There is a simpler way to see that P(1st) =S/T.
If all players have equal skill level then your expected number of chips after "infinitely" many hands = S (ie your chip count should stay constant in the long run). However, your expected number of chips = P(1st)T, since the 1st place player ends up with T chips. Therefore,
P(1st) T = S or P(1st) = S/T.

[/ QUOTE ]

Galwegian,

Uhhh...I feel really embarrassed [img]/images/graemlins/smile.gif[/img] Nice post!