CS Paper Radar

Near-Exact Computation of Independent Chip Model Placement Probabilities for Thousands of Players

Wataru Inariba

cs.DS cs.GTmath.NA ·submitted 2026-10-05 09:26 UTC · v1

Abstract

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.

Comment
26 pages, 4 figures, 9 tables

Closest papers

Nearest neighbours by meaning across the whole index.

ICM Out! Better Tournament Strategy from Computed Continuations, vs. Solvers and LLMs

cs.AI cs.GTcs.MA ·2026-08-10 ·Boning Li, Longbo Huang
benchmark similarity 0.58
Abstract · 34 pages, 2 figures

The Independent Chip Model (ICM) converts tournament chips into reference prize equity, and policies are routinely constructed against those values. Because ICM reads only stack sizes, it omits action order, blind obligations, and seat rotation, and it does not price the elimination pressure a big stack puts on the short stacks it can bust. Those omissions can alter the successor-state contrasts that determine a move. We introduce Strategic-Continuation Optimization (SCO), a policy-construction method that enumerates current-hand outcomes, maps them to successor states, prices those states with continuation values computed from the finite tournament model, and optimizes and freezes the resulting current-hand policy. The fixed-ICM comparison policy changes one thing only: the same optimizer solves the same game with successor states priced by analytic ICM, so the two policies differ only through that pricing. We evaluate the resulting policies in a three-player jam/fold tournament with a \$1M prize pool. Relative to the frozen strategic-continuation benchmark, analytic ICM has \$9{,}036 mean absolute value error across all 2,838 state--seat entries. That value error rewrites the ranges it prices: measured against each decision point's own fixed-ICM jam range, SCO moves the jam frequency by an average of 14.08\%. To price those different moves, we compare all 946 states and three policy owners while changing only the focal policy and holding both opponents and the continuation evaluator fixed. The policy produced by SCO earns \$214.33 more prize equity per hand on average and is favored in 2,433 of 2,838 matched units. The ordering survives replacing the solver-built opponent with two LLMs and with a family of non-modeling threshold players. This value-to-policy-to-cost chain shows directly when ICM becomes an inadequate objective for tournament strategy construction.

0.47

Rank Confidence Sequences:Anytime-valid Leaderboards

cs.AI stat.ME ·2026-09-26 ·Hamed Khosravi, Xiaoming Huo
benchmark similarity 0.54
Abstract

Leaderboards rank models by their average scores on benchmark items, and they are consulted repeatedly while the evaluation is still running. Existing confidence intervals for a model's rank control their error rate only if they are computed once, after a number of items chosen in advance. If they are recomputed as results arrive, and the evaluation stops once they look decisive, their error rate exceeds its nominal level. Anytime-valid methods keep their guarantees at all sample sizes simultaneously and hence under any stopping rule. They exist for the accuracy of one model, for one pair of models and for the set of models that may be best. For pairwise battles they also give ranks. None gives ranks when all models are scored on the same items, which makes their scores dependent. We construct rank confidence sequences: for every model, a set of ranks that contains its true rank, simultaneously for all models and at all times, at a chosen error level $α$, in finite samples. The construction combines betting e-processes, one for each ordered pair of models, with closed testing over the possible orderings of the models. It allows any dependence between the models' scores on an item. The method has two advantages. A leaderboard can be inspected after every item without inflating its error rate. The evaluation of each model can stop as soon as the question asked about it is answered, which saves compute. When results are examined only once, halfway through or later, little power is lost relative to fixed-sample methods. The paper quantifies these advantages in simulations and on public leaderboard data.

0.57

Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences

cs.DS cs.IRcs.LGstat.ML ·2026-11-07 ·Kehan Liu, Zhaoyun Chen, Xianquan Yan
publishedcode/data similarity 0.53
Abstract · 10 pages, 3 figures, 5 tables. Accepted at the 20th ACM International Conference on Web Search and Data Mining (WSDM 2027). Code: https://gi…

Pairwise probabilities arise in rank aggregation, recommendation, and human or LLM evaluation, yet converting them into a maximum-likelihood list is a weighted Kemeny problem and is NP-hard in general. Known exact algorithms for rank-two tournaments use only comparison signs and do not optimize this likelihood. We show that the weighted problem is exactly solvable when the skew-symmetric log-odds matrix $W_{ij}=\log(p_{ij}/p_{ji})$ has rank two, including when the induced preferences contain cycles. Writing $W_{ij}=\det(h_i,h_j)$ and adding the closing vector $h_0=-\sum_i h_i$ turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the $n+1$ edge vectors, cuts after $h_0$, and returns a global maximum-likelihood order in $O(n\log n)$ time from the factors. The same geometry identifies the runner-up and gives a stability certificate beyond exact rank two. When the smallest determinant $δ$ of two consecutive edges in the closed angular cycle is positive, it is exactly the best-to-runner-up log-likelihood gap. For $W=W_0+E$, the CloseSort order of $W_0$ has regret at most $\sum_{i<j}|E_{ij}|$ on $W$ and remains optimal whenever this sum is below $δ$, a worst-case tight threshold. In 5,120 determinant-logit simulations, increasing the observations per pair from 4 to 64 raises the fraction on which rank-two projection outperforms the empirical plug-in optimum from 68.6% to 85.7%. On 3,600 Arena-Hard LLM-judge profiles drawn from 63 systems and ten judges, the leading rank-two component captures 89.2% of the log-odds energy. On profiles containing a directed majority triangle, CloseSort reduces normalized regret by 44% relative to Borda and improves the mean normalized objective over each of eight baselines. With factors supplied, it is 8,407 times faster than exact dynamic programming on 18-item rankings.

0.52

The Complexity of Exact and Approximate Nash Equilibria in Anonymous Games

cs.GT ·2026-10-12 ·Zhengyang Liu
theory similarity 0.52
Abstract · 48 pages, including appendices and references; 2 figures and 4 tables

We prove that, for every fixed rational $c>0$, computing a $2^{-n^c}$-approximate Nash equilibrium in an $n$-player two-strategy anonymous game is $\mathsf{PPAD}$-complete. This holds even when one strategy always pays $1/2$ and, for all but two players, the other is constant outside at most five opponent counts. The reduction uses coefficient estimates to simulate circuit constraints approximately. Exact computation requires eliminating the simulation error: with three strategies, a separate construction uses polynomial roots to implement circuit gates exactly. This yields $\mathsf{FIXP}$-completeness of exact equilibrium computation under separable-linear reductions and $\mathsf{FIXP}_a$-completeness of approximation in distance to an exact equilibrium.

0.15

An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube

cs.DS cs.DMmath.OC ·2026-10-15 ·Thomas Dueholm Hansen, Uri Zwick
published similarity 0.51
Abstract · To appear in SOSA 2027

Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region is a combinatorial hypercube, to 2-player turn-based stochastic games (2TBSGs) in which one of the players has two actions from each one of its states. The currently fastest known randomized algorithm for finding the sink of such AUSOs is the Random-Facet algorithm of Kalai (STOC 1992), and of Matoušek, Sharir and Welzl (SoCG 1992), adapted to the binary hypercube by Gärtner (RSA 2002). The expected number of vertex queries made by the algorithm is at most $e^{2\sqrt{n}}$, where $n$ is the dimension of the cube. We design an improved randomized sink-finding algorithm that performs an expected number of only $e^{\sqrt{(2+o(1))n}}$ queries. This is the first improved bound for the problem in over two decades. The improved algorithm is obtained by adapting improved versions of the Random-Facet algorithm for solving general linear programs, and LP-type problems, developed by Kalai (STOC 1992), Gärtner (FOCS 1992), and by Hansen and Zwick (STOC 2015). The improved bound is not implied by these much more general algorithms. A key feature of the improved algorithm and its analysis is its simplicity. The structure of binary AUSOs enables a simpler description and a much simpler analysis of the adapted algorithm. In particular, the recurrence relations bounding the complexity of the algorithm depend on only one variable, and not two, and they can be solved using fairly straightforward techniques.

0.40

The Complexity of Multiplayer Colonel Blotto Games with Player-Specific Values

cs.GT cs.CCecon.TH ·2026-09-24 ·Martin Bichler, Abheek Ghosh
similarity 0.50
Abstract · 64 pages, 3 figures

We study equilibrium computation in discrete multiplayer Colonel Blotto games with player-specific battlefield values. In the two-player model with common battlefield values, equilibria can be computed in polynomial time. We show that this tractability breaks down in the multiplayer model with player-specific values under the standard uniform tie-breaking rule. In particular, computing a $(c/n)$-approximate Nash equilibrium is PPAD-hard for some constant $c>0$, even when every player has three resources, where $n$ is the number of players. The main technical step is PPAD-hardness for computing a constant-approximate well-supported Nash equilibrium. In contrast, under uniform tie-breaking, a pure Nash equilibrium can be computed in polynomial time when every player has one resource. We also prove PPAD membership for computing $\varepsilon$-approximate Nash equilibria for inverse-exponentially small $\varepsilon$. Finally, for non-uniform monotone tie-breaking, we show PPAD-hardness even when every player has one resource and all players have identical battlefield values.

0.25

Decentralized Dynamic Stable Matching

cs.DC ·2026-10-30 ·Jing Chen, Mengtong Gao, Zhenhe Zhang
similarity 0.50
Abstract

We study decentralized computing of the player-optimal stable matching under unannounced player arrivals and departures. Without a common clock, arrival/departure events information, or direct communication, players can only make individual proposals to arms and observe individual accept/reject outcomes. We measure mismatch cost --- the number of rounds in which the realized matching differs from that round's POSM, as the time horizon $T$ grows. For known preferences, we develop a deterministic polynomial-time self-calibrating protocol with mismatch cost $O(t_*+K^2\log T)$, greatly improving the existing upper-bound $O(T^{1-1/K}(\log T)^{2/K})$. $K$ is the number of arms and $t_*$ the last event time in the problem instance. Each player runs the protocol using their own local time and proposal-outcome history, without knowing~$t_*$ or $T$. More generally, configuring our protocol with a non-decreasing polynomial-time-computable function $g(t)=Ω(t)$ yields mismatch cost $O(g(t_*) + K^2 N_g(T))$, where $N_g(T)$ counts iterations of $t\mapsto t+g(t)$ below $T$. $g(t)$ reflects the protocol's convergence speed. The relationship between $g(t)$ and~$N_g(T)$ reflects the tradeoff between convergence speed and asymptotic mismatch cost. We show that any randomized protocol with convergence speed $g(t)\geq 1$ has worst-case expected cost $Ω(t_* + N_g(T))$. Thus, up to a $K^2$ factor, our protocol with $g(t)=t$ is optimal among protocols with convergence speed $O(t_*)$. For unknown preferences on both sides, each player and arm observe their own sampled utilities after being matched. We develop a decentralized learning protocol with expected mismatch cost $O(t_*+K^4Δ_{\mathrm{min}}^{-2}\log T)$, where $Δ_{\min}$ measures the preference gaps. A complementary static-setting lower-bound adapted from the literature shows that dependencies on $T$ and $Δ_{\min}$ are tight.

0.23

A Deterministic $(2+\varepsilon)$-Approximation for Weighted Feedback Vertex Set in Tournaments

cs.DS ·2026-09-14 ·Hanqing Li, Zihan Wu
theory similarity 0.50
Abstract · 8 pages, no figures

We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in $\mathcal B_7$-free tournaments in time $O(n^7)$, where $\mathcal B_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.

0.27