Metraipolis › archive › dc_bfee5bc93fef

Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players — arXiv:2610.06028

Source: arXiv
Original: https://arxiv.org/abs/2610.06028
License (as archived): CC0-1.0
Archived: 2026-10-06T05:29:32.085Z
SHA-256 of the archived text: c6ccfc453afbe38b5e60ae497795eaca8e4fe8a8c3dd65b5b1017249c9f22742
Stable URL of this page: https://metraipolis.com/documento/dc_bfee5bc93fef

How to cite

Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players — arXiv:2610.06028 — arXiv, https://arxiv.org/abs/2610.06028 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bfee5bc93fef (Metraipolis archive dc_bfee5bc93fef, sha256 c6ccfc453afbe38b5e60ae497795eaca8e4fe8a8c3dd65b5b1017249c9f22742)

BibTeX

@misc{dcbfee5bc93fef,
  title = {Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players — arXiv:2610.06028},
  howpublished = {arXiv},
  url = {https://arxiv.org/abs/2610.06028},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bfee5bc93fef; sha256 c6ccfc453afbe38b5e60ae497795eaca8e4fe8a8c3dd65b5b1017249c9f22742},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv, https://arxiv.org/abs/2610.06028. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Independent Chip Model (ICM) converts the chip stacks of the players remaining in a poker tournament into finishing-place probabilities and prize equities. It is the standard model in tournament solvers, but its definition considers all possible finishing orders, and exact computation has been regarded as intractable for large fields. The same mathematics appears in other fields; for instance, the ICM is a Plackett-Luce ranking model with stacks as weights. We present DE-ICM, a deterministic algorithm that computes the placement probabilities of all $n$ players for all paid places in $O(M n^{2})$ time, where the number $M$ of quadrature nodes is fixed for the admissible inputs and the target accuracy. Its numerical scheme allows the target to be set close to the accuracy of double-precision arithmetic. The algorithm evaluates a classical integral representation in which, conditional on a player's exponential clock, the number of players ahead is Poisson-binomial. A double-exponential quadrature on a single grid evaluates every integral; its truncation errors have closed-form bounds, and the step size, which controls the discretization error, follows from the field size. A numerically stable deconvolution then recovers each player's leave-one-out coefficients in $O(n)$ time from one shared product. On exactly solvable instances with up to 4,000 players, the worst observed relative error of an equity is $4.0 \times 10^{-14}$ and the worst absolute error of a placement probability $1.1 \times 10^{-14}$. The full placement matrix for 1,000 players takes 0.2 seconds on one CPU core.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computer Science and Game Theory (cs.GT); Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2610.06028 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T05:25:35.334Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).