Intransitivity Can Raise the Minimum Abstraction Size
Abstract
Large poker solvers group private hands into buckets before they solve. The number of buckets is a parameter set by experiment: coarse enough that the abstract game fits the solver, fine enough that the resulting strategy is not obviously exploitable. The theory of abstraction takes an abstraction as given. Lossless methods merge states that are interchangeable against every opponent, and lossy methods bound the exploitability of a coarsening already chosen. Neither answers how many buckets a game requires. The minimum also cannot be read off one equilibrium, which may distinguish hands it has no need to. We compute the exact minimum in one-card poker, a family small enough to enumerate. One player's strategy is a finite-state automaton reading the private card and then the public betting actions, so at each betting action a state is a bucket. When each post-card observation identifies one decision history, the fewest states attaining the equilibrium value equal the *joint width*, the fewest blocks of one partition of the deck that serves every decision the player faces. With one decision after the deal this is the *label-class width*; with several it can be larger, and the second player in four-card Kuhn poker needs four states although its two decisions need three and two. Sweeping the showdown relation exactly, we find a total order keeps width at most three on every deck from to cards, attained by a contiguous partition of card rank, with width three recurring with period ten. Reversing one comparison lifts width to on five cards. Over all seven-card isomorphism classes width reaches , one bucket per card, while three quarters of the classes need at most two. How many cards each card beats does not determine the width. Deck size alone does not set the bucket requirement: at seven cards the order needs two, the worst relation seven, others one.
est. 32% chance this paper gets accepted at ICLR 2027.
What do you think this paper will get?
All positions stay anonymous.