Random weighted selection without replacement

Question

I am using the following procedure to select $m$ different numbers $\{i_1,\ldots,i_m\}$ from the set $\Omega = \{1,\ldots,N\}$, with $m,N\in\mathbb{N}$ such that $m< N$.

Selection procedure

Associate a weight $w_i > 0$ to each number $i\in\Omega$.

Set $\Omega_1 := \Omega$.

For each $k = 1,\ldots,m$, choose $i_k\in\Omega_k$ according to the following probability distribution: $$P\{i_k = j\} = w_j \cdot \left(\sum_{\ell \in \Omega_k}w_\ell\right)^{-1}, \quad \forall j \in \Omega_k.$$ Build the next set as $\Omega_{k+1}:= \Omega_k \setminus \{i_k\}$.

Question

Is there an official name for this random weighted selection without replacement?

[Comment: the nearest thing to what I am looking for that I've found so far is the Hypergeometric multivariate distribution, but unfortunately in that case repetitions are admitted.]

Answer 1

This model has come up on MO before: Drawing natural numbers without replacement. I don't think it has a standard name in mathematics.

In mathematical analysis of poker, this is called the Independent Chip Model (ICM), and professional tournament players most commonly use this model to convert a distribution of stacks to the expected values for the players, particularly at the final table and by those who specialize in single table tournaments where this is particularly important. Alternative models such as diffusion are not used much. Here is a Nash equilibrium calculator for the push/fold phase of the final table in a Texas Hold'em tournament, calculating equities by the ICM: HoldemResources.net.

One description of the ICM is that you choose which player wins the tournament in proportion with the stacks. Once you have determined the winner, choose the second place finisher in proportion with the remaining players' stacks etc.

An alternative description is that we use chips of the same size, and randomly remove one chip at a time from the table without regard to who owns the chip. Players are knocked out when their last chip is removed. The winner is the last player with chips, the second place player is the one eliminated just before that, etc.

It might not be obvious that these are the same model. In the first model, it's obvious that stacks of $(3,2,1)$ and $(30,20,10)$ are equivalent, but it's not obvious that the second model provides the same distribution on permutations. The second description requires rational proportions between the stacks, while the first description does not. One way to see that they are equivalent for rational proportions is to shuffle the chips, and rank players by their highest chips. If we reveal the shuffle from the top down, we get the first description. If we reveal the shuffle from the bottom up, we get the second description.

Usually, poker players don't care about the distribution on $S_n$, but only the doubly stochastic matrix of finishing probabilities. So, for example, people have developed algorithms faster than $n!$ for computing the finishing probabilities. I proved that if prizes are nonincreasing, then the ICM recommends risk aversion in every heads-up pot, that it's not right according to the ICM to take a gamble which decreases your expected number of chips in a heads-up pot, even if this might mean knocking a player out.

You can download my ICM calculator, ICM Explorer, for free. You can enter up to $10$ stacks, and press the ICM button to get the finishing probabilities, among other calculations designed to be useful for tournaments players such as the rational risk aversion due to the prize structure.