The complexity of poker

(A second in a series, drawn from joint work with K. Joseph Mourad.)
How do we measure the complexity of decision procedures in poker?  This is a question that is both complex and subtle, and seems to me interesting in thinking about the interplay between formal modeling of epistemological situations and more concrete strategic epistemic thinking.

Consider a typical decision situation in a poker game let's say Texas Hold-em. One has a bit of "direct" evidence - the cards that are on the table, the history of bets up to this point, one's own hole cards, and let's add in all everything that has happened so far in the game - what others have bet, in what situation, with what cards.  From this information, one can calculate a probability that your hole cards constitute the winning hand assuming a random distribution of hole cards among those still playing.  And from this and the money in the pot, one can work out an expected utility for, say, calling a bet.  

But of course that "direct" information is only the start.  You have also the information that, say, 3 people called initially and that one raised on the flop.  That raises the probability that at least some of them have better than average hole cards.  On the other hand, any of them might be bluffing - employing a strategy based on the hypothesis that you will think that they have better than average cards.

The point is that at any point in the game, one has a working hypothesis about the strategy being employed by the other players.  That is an element that goes into the definition of one's own strategy.  And then the impredicativity arises because one knows that others are basing their strategy on the strategy that you are employing.  So my current strategy is determined by my estimate of your strategy, which is determined by your estimate of my strategy, etc.  

This is an example of the phenomenon of finite impredicativity that I posted about a few days ago.  There are no infinite totalities in the vicinity.  No one is actually carrying out infinite calculations.  If, for example, we knew the facts about the cards, the pot, and the relevant causal dispositions of the other players, we would play optimally.  But we don't. Our ignorance of the cards is not really important.  There is uncertainty there, but the relevant odds are determinate and  we can perfectly well calculate an optimal expected utility plan. But the dispositions of the other players are the crux and an uncertainty that fundamentally changes how we should think about the situation.

Note that if we ignore our guesses about the strategy of the other players, there is no optimal poker strategy.  That is, let us define a "player-independent-strategy" to be a function that takes as input a complete description of the game situation - that is, the stack of each player, the pot, the current bet, the visible table cards, and one's own hole cards - and gives as output a response to the bet.  I claim that for any such function, there is another function that beats it in the long run. That is, if you knew what function someone was playing - what they would do in a given situation in response to a given action - it would be easy to devise a way to take all their money in the long run.  

But we don't know what function anyone is playing. First, we simply don't have direct evidence which player-independent-strategy they will act in accord with, but more deeply because  though over time one accords with exactly one such p-i-s, intentionally this is not what is determining a player's actions.  Rather, they are including in their calculational input their guess about the strategy of the other players.  

We can think, then, of poker strategy as a sort of ordinal construction.  We first, given our current behavioral evidence, assign a p-i-s to each player and figure out what this makes rational given the game situation.  But then, at the next stage, we consider what they are likely to attribute to us, given their behavioral evidence and the game situation.  That consideration changes our view about what strategy we assign to them, and so we now make a new calculation of what to do.  

What matters here are fixed points. Perhaps there is a huge bet and I have a terrible hand.  Then all the revisions of the nested strategies may just not matter. Folding is the thing to do.  That element of the player independent function - that action given the current game situation - is a fixed point.  What others are there?  I have no idea.  That's why poker is hard.  It is an impredicative game. 

One final point. There are strategies that interupt such calculations - specifically randomizing strategies.   Good players make sure to do something random now and then precisely to make it hard for others to calculate what they are doing.  I've seen folks even make it explicit.  One pro I watched, once announced.  "OK.  I'll call if the next drink that waitress brings is brown, and fold if it is clear."  And then he did.