Bayesian Games: Math Models for Poker

My article on game theory is not a prerequisite, but it may be useful for a better understanding of the last section of this article.

In card games, players have an incomplete information about the other players’ cards. This is actually the case in most games. Instead, players consider a probabilistic distribution over the incomplete information. In this setting, the concept of Nash Equilibrium no longer stands. To study such games, we need to change the way we think about players’ strategies. This requires a great change of perspective, which enable to rethink the way poker works, as explained briefly by French American professional law student and poker player Vanessa Rousso:

Now, poker is way too complicated to be studied in this article. So I’ll introduce two simpler games to better understand what bayesian games are and how they are modeled. This field is pretty much the intersection of John Nash’s world of game theory, Thomas Bayes’ world of probabilities.

In fact, thanks to the power of Bayesian game theory, Heads-up limit poker has been solved in January 2015! This is a monumental.

Highest Card Game

Let’s start with a basic 3-players highest card game, between Vanessa, John and Thomas. We consider cards of heart only, from the Ace to the King, Ace being the smallest, as displayed below:

Cards

Each player is given one of these cards. Then, each player is asked to write on a sheet of paper whether he believes he has the highest card. He can either answer yes or no. These are his possible actions. So which actions do you think players will choose?

It depends on the card they have!

Indeed! The card each player receives is called its type. In a more general setting, this type corresponds to all of the player’s private information. As you said, a player’s best action depends on its type. This is a crucial remark which we’ll get to later. Right now, let’s assume players receive cards as follows:

So what are the best actions of players?

Let’s do the reasoning for Vanessa (not that she needs me to…). She should say yes if her card is actually the highest card, that is, if her card is higher than both John’s and Thomas’. But without perfect information about other players’ cards, she needs to include probability in her reasoning. She’ll be assuming that the cards were well mixed, and thus, that the probability of the others’ cards being one of the 13 cards is 1/13. This is called the belief. This belief is updated with Vanessa’s knowledge of her own card.

Now, out of the 12 cards other than hers, there are 8 cards lower than 9. Thus, the probability that John’s card is lower than hers is 8/12. If it’s not the case, then the Vanessa’s card is not the highest. If it is, we need to go further in the reasoning.

So let’s assume that it’s the case, that is, John’s card is 8 or lower. Now, for Vanessa’s card to be the highest, it also needs to be higher than Thomas’. But now, there are only 11 possibilities for Thomas’ card, since Vanessa and John’s cards are already defined by our hypotheses. Out of these 11 cards, 7 are lower than Vanessa’s. Thus, assuming that Vanessa’s card is higher than John’s, the probability that her card is also higher than John’s is 7/11.

Overall, the probability that Vanessa’s card is the highest is the product of the probability that her card is higher than John’s and the probability that her card is higher than Thomas’ with regard to the fact that her card is higher than John’s. This yields (8/12)x(7/11) ≈ 0.42. This means that the probability of her having the highest card is lower than a half.

This reasoning is summed up in the following formula, where the vertical bar has to be read “knowing that“. If you don’t like formulas, don’t worry it’s the only formula of this article!

Conditional Probability

So this reads that the probability of Vanessa having the highest card is equal to…

the probability of her card being higher than John’s multiplied by the probability that her card is higher than Thomas’, knowing that her card is higher than John’s. This is a very useful formula in probability, and is also the cause of many mistakes when dealing with probabilities. That’s why I really wanted to show it. Let’s now get back to the fun stuffs.

So, since this probability is lower than a half, Vanessa should bet no, right?

Yes! This is her best action!

What about John and Thomas?

You should do the same reasoning for them, that’s good exercise!

Yes?

I guess John is thinking that there are 11 cards lower than his, and if Vanessa has a lower card, then this leaves 10 cards for Thomas…

Exactly! Thus, John’s probability of having the highest card is (11/12)x(10/11) ≈ 0.83.

So he should bet yes?

Yes. Thomas’ probability of having the highest card is (9/12)x(8/11) ≈ 0.55. So he should bet yes too… So, to recapitulate, here are the players’ bets:

Highest card game bets

As it turns out, while Vanessa and John would have won one point, Thomas would have lost one.

It seems that more generally, one should bet he has the best card if his card is higher or equal to 10…

Exactly. What you’re describing is the major concept of strategies. A strategy consists in choosing an action depending on one’s type. Mathematically, we call this a function mapping types with actions. The following figure displays the optimal strategy.

Highest card game - Best strategy

By the way, if Thomas Bayes played this game, he’d probably be quite bored and feel his presence useless.

Why? Just because you made him lose?

No! Well, maybe a little a bit… But more importantly, so far, it’s just about basic probabilities which existed before Thomas Bayes!

Sequential Highest Card Game

So let’s make the game more interesting. We’ll now assume that Vanessa will bet first out loud, followed by John, and then Thomas. This means that John can take into account Vanessa’s action to improve his decision making.

But Vanessa has no more information than before, right?

Indeed. Therefore, her best strategy remains the same. Now, let’s assume the following cards are the one dealt:

Sequential cards

So Vanessa should bet that she doesn’t have the highest card, right?

Yes. Now, let’s do John’s reasoning. Before taking his decision, he knows that Vanessa said no. And he also knows that she says no if and only if she has a card lower or equal to 9. His card is 8, thus, Vanessa’s card is either a card between 1 and 7 or card 9. Out of these 8 cards, 7 of these cards are lower than his, thus, the probability that Vanessa’s card is lower than his is 7/8. Now, assuming that Vanessa’s card is lower than John’s, there are 6 cards lower than John’s left, out of 11 cards. This implies that the probability that Thomas’ card is lower than John’s is 6/11. Overall, the probability that John’s card is the highest is (7/8)x(6/11) ≈ 0.48.

So John should say no, right?

Indeed! Let’s move on to Thomas now. He knows that both Vanessa and John said no. Since Vanessa said no, Thomas knows that her card is 9 or lower. Since Thomas has 9, he knows that, for sure, Vanessa’s card is lower than his. Now, John also said no. But if John had 10 or higher, he would have said yes. Thus, Thomas knows that John too has lower than 9. Thus, he knows for a fact (well, assuming that both John and Vanessa plays smartly), that he has the highest card. Thus, he’ll say yes with absolute confidence:

So where does Thomas Bayes’ contribution to the theory of probabilities apply?

In the updating of beliefs with information received during the game. In our case, because the probabilities before having any information were extremely simple, we haven’t had to go through the difficulty of updating beliefs. In a more general case, this is done with Bayes’ theorem. Daniel Negreanu does a similar updating of beliefs in the following hand:

Do not forget about updating beliefs. If you do, you may end up with apparent paradox such as the Monty Hall problem, explained on AsapSCIENCE.

What do optimal strategies now look like?

Well, they are a little bit more complicated, as the best action now also depends on the bets made so far. Now, to be consistent with the concept of strategy we have introduced earlier, let’s introduce the concept of super action. It corresponds to the way a player chooses his bet given the knowledge of the bets made so far. In other words, a super action is a reaction to information obtained during the game. Now, a strategy corresponds to a mapping of a type with a super action.

Super action is a concept I have introduced here and is not common in the literature, where it’s rather called strategy too, in the setting of extensive form games. However, I wanted to distinguish it from the strategy corresponding to bayesian games.
I’m not sure I’m getting it…

Let me rephrase. Given a player’s type, he chooses a way to react to the bets made before him. This choice of a super action depending on a type is a strategy! Let me illustrate this by displaying John’s optimal strategy:

John's Best Strategy

Why are you spending so much time on redefining strategy here to match the earlier definition?

It may seem pointless here, but this will be tremendously important in the next section.

By the way, if John Nash read my article, he’d probably be pretty mad at me so far.

Why? You didn’t make him lose!

I’m not sure this is what’s most important to him! The reason why he wouldn’t appreciate this article until now is that what I described isn’t really a game! Well, at least in the mathematical sense!

What do you mean?

In this highest card game, there is no actual bilateral interaction between players. This makes things not fun enough! Well, at least for John…

Bayesian-Nash Equilibrium

Now, I could modify the game to make Vanessa’s best strategy also depend on the other players’ strategies, like for instance, allowing her to double the bets after having heard all other players’ bets. However, this would make the game very hard to understand. So, instead, I’m going to bet on your understanding of the concepts we’ve introduced so far to be more abstract.

Could you recapitulate these concepts?

Sure. Players all have different private types. A vector of types, that is, a list of types for all players, is called a type profile. Players have a belief about the other players’ types. They are asked to play an action (or what I called super action). Similarly to type profile, we define the action profile. The way they associate their types with their actions is called the strategy. Once again, we define the strategy profile.

OK, I think I get it all…

Good. Because we’re getting to the fundamental concept of Bayesian-Nash equilibrium.

What’s a Bayesian-Nash equilibrium?

First, let’s consider a player’s reasoning, say Vanessa’s, provided she knows the other players’ strategies. Since she has a belief about their types, she can compute the belief about their actions, as displayed in the following figure:

Belief over Actions

Since she now knows the belief about other players’ actions, she can compute, for any of her types, her best-response action to the belief over other players’ actions. If she does this for all of her possible types, she will be defining her best strategy against other players’ strategies. This is called the best-response strategy.

More mathematically, the best-response strategy is a strategy that maximizes her gain, given the belief over other players’ actions.

I think I get it! A Bayesian-Nash equilibrium is a best-response strategy to best-response strategies?

Something like this. A Bayesian-Nash equilibrium is a strategy profile, such that, for each player, his strategy in the strategy profile is the best-response to the other players playing the strategies of the strategy profile. Equivalently, assuming the other players will play according to the strategy profile, every player should play the strategy profile. This is displayed in the following figure:

Bayesian-Nash Equilibrium

I haven’t written it on the picture, but, obviously, not only Vanessa but also John and Thomas need to have the same reasoning for the strategy profile to be a Bayesian-Nash Equilibrium. Now, if you perfectly understand the two last figures, then, congratulation, you have mastered the concepts of Bayesian games!

Let’s Conclude

Bayesian games are disturbing at first because we need to use a probabilistic reasoning to understand them. But once we manage to think in terms of strategies instead of actions (or super actions), they can be considered conceptually without too much difficulty. However, to consider them computationally is quite difficult. This is something I have tackled in my PhD (I have submitted a research paper on this very topic, which I will put in the bibliography once it will be published).

All along this article, we have considered types which are private information with a fairly simple and computable probabilistic distribution. However, in plenty of models including the ones I use, types may include private information for which it may be very hard to obtain a good belief of. For instance, in market competition, the marginal costs of rivals are types for which the probabilistic distribution is hard to guess. This creates another big difficulty of Bayesian games.

Finally, I’ll conclude by linking Bayesian games with my PhD research. I’m studying mechanism design, in which a mechanism designer needs to define a Bayesian game to be played by agents. The mechanism designer is particularly interested in defining games for which truthfulness is a Bayesian-Nash equilibrium. As soon as my research paper gets published, I’ll get to tell you more about this…

More on Science4All

Game Theory and the Nash Equilibrium Game Theory and the Nash Equilibrium
By Lê Nguyên Hoang | Updated:2016-01 | Views: 9390
In the movie "A Beautiful Mind", the character is John Nash. He is one of the founders of a large and important field of applied mathematics called game theory. Game Theory is the study of human interactions. Its fallouts in economy, politics or biology are countless. This article gives you an introduction to the concepts of this amazing way of thinking.

Advanced Game Theory Overview Advanced Game Theory Overview
By Lê Nguyên Hoang | Updated:2016-02 | Prerequisites: Game Theory and the Nash Equilibrium | Views: 4497
This article gives an overview of recent developments in game theory, including evolutionary game theory, extensive form games, mechanism design, bayesian games and mean field games.

Mechanism Design and the Revelation Principle Mechanism Design and the Revelation Principle
By Lê Nguyên Hoang | Updated:2016-02 | Views: 3525
Whenever you need to make a group of people interact, you are designing a mechanism. If you want to achieve a good interaction, you need to make sure your mechanism is well designed. In this article, I'll show you main features of mechanisms through various examples. I'll also talk about a great mathematical tool for mechanism design: the revelation principle.

A Mathematical Guide to Selling A Mathematical Guide to Selling
By Lê Nguyên Hoang | Updated:2015-12 | Views: 2806
How to best sell a good? Should we auction it like in movies? Since the 1960s, economists have addressed this question mathematically and found surprising results. Most notably, in 1981, Nobel prize winner Roger Myerson proved that most auctions you could think of would win you just as much as any basic auction, but that, as well, you could do better using his approach. Since, today, billions of dollars are at play in online auctions, you can imagine how hot a topic it has now become!

One comment to “Bayesian Games: Math Models for Poker

  1. Very nicely written!

    I’d love to hear more about your PhD!

    I am planning on doing research (PhD) in a similar field.

    ( Bravo: simple, clair et efficace! )

Leave a Reply

Your email address will not be published. Required fields are marked *