9
$\begingroup$

This a a theoretical question about poker type games. I'm sure I don't have to explain the rules - you can consider No Limit Texas Hold'em or some simple theoretical model, where each player holds a number from the $(0,1)$ interval. We only consider heads-up, i.e., when two players play.

Suppose that at the beginning of the game the size of the pot is $1$, and both players have $n$ chips (their stack). The stack-to-pot-ratio of the game, SPR, is $n$.

Does the optimal strategy of the players converge as $n$ tends to $\infty$?

To me this seems like a fundamental question, but I could find practically no information about it. I'm interested in any sort of related results, which is why I haven't given precise definitions.

$\endgroup$
  • 1
    $\begingroup$ here is one description of possible strategies: cardsharp.org/infinite-stacks-a-thought-experiment $\endgroup$ – Carlo Beenakker May 23 '17 at 12:49
  • $\begingroup$ Indeed, it would be probably possible to define poker with an infinite stack size, though one must be careful with an infinite amount of re-raises. $\endgroup$ – domotorp May 23 '17 at 13:16
  • $\begingroup$ Unfortunately, that article has a lot of errors. $\endgroup$ – Douglas Zare May 24 '17 at 14:38
  • $\begingroup$ For the actual poker game of heads-up no-limit hold'em, this is much too hard: we have no idea what the optimal strategy looks like and only this year has AI been able to consistently beat top humans. Even for very simplified poker games that have been "solved", the "solution" is some gigabytes-sized object so proving anything about them seems very tricky. $\endgroup$ – usul May 28 '17 at 16:30
  • $\begingroup$ @usul There might be ways to prove theorems about properties of the optimal strategy without knowing it, so this doesn't seem relevant here. $\endgroup$ – domotorp May 28 '17 at 18:32
3
+50
$\begingroup$

The Clairvoyant Game

Here is a well-known toy problem (the Clairvoyant Game) that doesn't converge: Suppose your hand is face-up. You have no hidden information. You don't know whether your opponent's hand is stronger. There is no drawing. The optimal strategy is for your opponent to bet all-in for value with all strong hands, and bluff with some weaker hands. If the chance for your opponent to have a stronger hand $p$ is too large, then you have to fold to all bets, even smaller bets. If $p$ is not too large, then you can call to neutralize bluffs while your opponent bluffs to neutralize your folds.

Calling risks $n$ to gain $n+1$ so your opponent should bluff $n$ times for every $n+1$ value bets, with absolute probability $\frac{n}{n+1}p$, if that is possible. If $\frac{2n+1}{n+1}p \gt 1$ then you have to give up. Bluffing risks $n$ to gain $1$ so if $p \lt \frac{n+1}{2n+1}$ then you should call with probability $\frac{1}{n}$.

As $n\to\infty$, the bet size does not converge. Further, your calling probability goes to $0$. However, the conditional probability that your opponent bluffs, given a bet, converges to $1/2$. The probability that your opponent bluffs converges to $p$.

If you have a strong hand less than $1/2$ of the time, betting $n$ into a pot of size $1$ is not optional. It's not that you make an uncallable overbet, but a smaller one would do. If you don't bet all-in, you lose equity because you can't protect as many bluffs, or if your opponent calls with the right frequency, you don't get paid off enough when you do get called.

If there are $r$ betting rounds, the optimal strategy is for your opponent to bet so the pot grows geometrically, $\frac{1}{2}(\sqrt[r]{2n+1}-1)$ times the pot. Your opponent sometimes bluffs $i$ times for each $i \in \{1,...,r\}$. As $n\to\infty$, the chance to bet on round $i$ goes to $2^{r+1-i}p$.


Big Pots for Big Hands

Will Sawin mentioned a version of this result in his answer.

Suppose each player is dealt a hidden hand in $[0,1]$, with the lower number winning in case of a showdown.

Claim: For any SPR $n$, in the optimal strategy, the probability that you put more than $b$ into the pot against any strategy is $O(1/b)$.

Proof idea: If you put in more than $b$ more frequently, then you will often do so with hands that are not in the strongest $1/b$. So, your strategy will lose more than the pot to the suboptimal strategy of folding all hands except for the top $1/b$, and playing to provoke you to put at least $b$ into the pot, then reveal the hand and play the Clairvoyant Game above.

If this bound were $o(1/b)$ then it would imply convergence of the optimal strategy as $n\to \infty$ since we could play the optimal strategy for SPR $b$ and forfeit if the pot reached $b$, costing $o_b(1)$. I believe the solutions to some restricted games indicate that there is some power law with a power strictly less than $-1$.

As Will Sawin mentioned, this lets you prove some sorts of convergence of subsequences for $[0,1]$ games as long as you ensure that the ways for the pot to get up to $b$ are compact.


Nut-Blockers

So, what about poker games people play? Should we see people use the full stack, so that we might get convergence of equities and probabilities of betting but not amounts, or does poker resemble a $[0,1]$ game where the pot can't get very big because players are afraid of paying off extremely strong hands?

The consensus among poker players may be that it almost never makes sense to bet more than the pot. However, the consensus of poker players is unreliable and it's wrong here. I've posted examples from my own play (in poker strategy forums) where I argued that particular overbets were much better than pot-sized bets. In some situations, this is to exploit suboptimal play, such as that people rarely want to fold a hand that has just improved, or to fold a full house or better, even if it is quite possible that someone has a stronger hand. However, there are also times when people have a limited range and the game resembles the Clairvoyant Game. You have to make large overbets to maximize the power of your range.

Will Sawin mentioned the example of a nut-blocker hand, a hand that might not be strong, but which blocks your opponent from having the strongest hand. For example, if you are playing Texas Hold'em and the community cards are KQQ, the nut hand is QQ for four-of-a-kind. The second-best hand is KK for a high full house. The third best hand is KQ for the low full house. It also blocks your opponent from having the nuts. So, if a significant portion of your opponent's range is KK, and you have just QQ and KQ in your range, then you should overbet with QQ, and for every time you do that, you can overbet almost as often with KQ, playing the Clairvoyant Game.

$\endgroup$
  • $\begingroup$ Finally I've managed to digest (most of) your answer. Now that I know so much about poker, I wonder what other notion convergence could be replaced with to make a true statement. For example, suppose that in a one-card poker Clairvoyant has A, Q or T, while the other player has K or J (say, uniformly). Would the bet size be unbounded with a Q, or only with A (strongest) and T (used to bluff)? $\endgroup$ – domotorp May 29 '17 at 8:33
  • $\begingroup$ @domotorp: If you have a jack, the Clairvoyant knows this, and then there isn't any difference between a queen and an ace. If you have a king, there is no difference between the queen and the ten. So, the bet sizes could be unbounded with every hand. $\endgroup$ – Douglas Zare May 31 '17 at 10:18
  • $\begingroup$ I'm sorry, I shouldn't have called one of the players Clairvoyant - I wanted to ask what happens if none of them knows the card of the other. $\endgroup$ – domotorp May 31 '17 at 11:55
  • $\begingroup$ @domotorp: If there are two or more betting streets, then on the first street, the AQT player can bet big (but not all-in) and the KJ player can't call. In just one betting street, there doesn't seem to be any point to betting with a queen, and the player with AQT would bet big with every ace and some tens, asymptotically all tens as the SPR increases to infinity. Some restricted continuous games are solved, and the bet size narrows a player's range, with smaller bets for more mediocre hands. The consensus of poker players is to bet just one amount, but I disagree with it. $\endgroup$ – Douglas Zare Jun 1 '17 at 3:46
  • $\begingroup$ So with one street and large SPR, this would practically give away whether AQT has a Q or not, so the KJ player "becomes the Clearvoyant" and can asymptotically win the blind if there's a Q. This doesn't seem like a smart thing to do, but might be optimal, I don't know, it gives that AQT has $33\%$ blind advantage. Do you have some reference? $\endgroup$ – domotorp Jun 1 '17 at 4:30
1
$\begingroup$

There is one failure of literal convergence. Consider a situation in the final round of betting where both players have the nuts, i.e. a hand that could not possibly lose, could only win or chop. Then it is always correct for both players to raise, as it never loses money and might win money. (If after a certain number of raises there is a zero probability in any Nash equilibrium strategy that the opponent doesn't have the nuts, then it is still equally good to call or raise, and so there is some Nash equilibrium strategy with this property). Because of this, the players will continue raising until one bets all-in. This happens with positive probability independent of $n$, and so with probability bounded away from zero, the pot after betting is complete is $2n+1$. This clearly does not describe a convergent distribution.

I guess one needs an existence proof for both players having the nuts. In Texas Hold'em, this is provided by an AAKK9 board where both players have AK, the best possible full house, and because each player knows there is only one more ace and one more king in the deck, the other player cannot have four of a kind, and neither can they have a straight flush (in fact they cannot even have a straight).

There may also be problems with nut blockers. If the board is unpaired with three spades and no possible straight flush, then the only hand that can't lose is a flush with the ace of spades. It may be the correct strategy to bet all-in with these hands and also with certain very poor hands that lack the ace of spades, with the probabilities chosen so that the opponent is indifferent between calling and folding with any of their medium-strength hands. I don't know whether that the probability of doing this in the optimal strategy goes to zero as $n$ goes to $\infty$.


Instead, I will bound the player's strategies in the case where each player fears the other may have the nuts. I think this should work in modified form for games with multiple rounds of betting, but let's consider only one round of betting.

For each $n$, each player is playing a probabilistic strategy (a function from sequences of bets to a probability of folding, a probability of calling, and a distribution over raise sizes) for each hand. Given a probabilistic strategy for one player and a deterministic strategy for the other, we obtain a probability distribution over all possible lines of gameplay (e.g. Player 1 bets 1 chip, Player 2 raises to 3 chips, and then Player 1 calls). In fact we may view a probabilistic strategy as a function from deterministic strategies to probability distributions over lines of gameplay, satisfying certain linear coherence conditions.

The key lemma is that if Player 1's hand gives him a positive probability of Player 2 having the nuts, then for each deterministic strategy of Player 2, the expectation of the total number of chips Player 1 puts in the pot (either by betting, raising, or calling) is bounded by an absolute constant.

Indeed, Player 2 can play the strategy of folding every hand but the nuts and playing that exact deterministic strategy with the nuts. He forfeits the one chip in the pot with everything but the nuts, at works breaks even with the nuts against every other hand, and against the chosen hand of Player 1 earns the expected bet size times the probability that Player 1 has that hand and Player 2 has the nuts. If Player 2's expected winnings are greater than the one chip in the pot, then Player 1's strategy cannot be a Nash equilibrium strategy, as then Player 2's expected winnings would also be greater than one chip with some Nash equilibrium strategy, but then Player 1 could do better by simply folding every hand.

It follows from this lemma that the valid probabilitistic strategies are functions from deterministic strategies to distributions on game actions of bounded total bet size. Because there are finitely many lines with bounded total bet size, and because the space of probability distributions on the natural numbers with expectation bounded by some constant is compact in the $\ell^1$ metric topology, this space of distributions is compact. Hence a product of such spaces is compact as well. Thus there is at least a subsequence of $n$ where the probability distributions in the Nash equilibrium strategy converge to probability distributions, without escape of mass.


However, a weakness of this approach is that the expectation of the bet size of this convergent subsequence may not converge to the expectation of the bet size of the limit. For instance, with a stack size of $n$ we could have a $1/n$ probability of betting $n$ chips and a $1-1/n$ probability of betting zero.

$\endgroup$
  • $\begingroup$ Yes, I was aware of most of this. I'm not sure I understand "the space of probability distributions on the natural numbers with expectation bounded by some constant is compact." What would be the limit of the distribution that takes $n$ with probability $\frac 1n$ (and zero otherwise)? $\endgroup$ – domotorp May 27 '17 at 20:25
  • $\begingroup$ @domotorp It would be the probability distribution that is zero with probability one. $\endgroup$ – Will Sawin May 27 '17 at 20:33
  • $\begingroup$ @domotorp I will see if I can say something more substantial. $\endgroup$ – Will Sawin May 27 '17 at 20:34
  • $\begingroup$ Oh, I see, of course. Anyhow, the real issue is what you describe in the last para. $\endgroup$ – domotorp May 27 '17 at 20:52
  • $\begingroup$ @domotorp What definition of convergence would you use where this issue would block convergence? $\endgroup$ – Will Sawin May 27 '17 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.