In skranz/gtree: gtree basic functionality to model and solve games

knitr::opts_chunk$set(echo = TRUE, error=TRUE)
library(RTutor)
RTutor::set.knit.print.opts(html.data.frame=TRUE, table.max.rows=30, round.digits=3, signif.digits=8)
library(gtree)

Kuhn Poker Description

H.W. Kuhn (1951) developed a very simple poker game that is tractable for game theoretic analysis. Wikipedia describes the Kuhn Poker game in conventional poker terms as follows:

• Each player antes 1.

• Each player is dealt one of the three cards, and the third is put aside unseen.

• Player one can check or bet 1.

• If player one checks then player two can check or bet 1.
  • If player two checks there is a showdown for the pot of 2 (i.e. the higher card wins 1 from the other player).
  • If player two bets then player one can fold or call.
  • If player one folds then player two takes the pot of 3 (i.e. winning 1 from player 1).
  • If player one calls there is a showdown for the pot of 4 (i.e. the higher card wins 2 from the other player).
• If player one bets then player two can fold or call.
  • If player two folds then player one takes the pot of 3 (i.e. winning 1 from player 2).
  • If player two calls there is a showdown for the pot of 4 (i.e. the higher card wins 2 from the other player).

Specifying as gtree game

We specify the game in gtree as follows:

library(gtree)
game = org.game = new_game(
  gameId = "KuhnPoker",
  params = list(numPlayers=2),
  options = make_game_options(verbose=FALSE),
  stages = list(
    stage("dealCards",
      nature = list(
        # Player 1 gets a random card 1, 2, or 3
        natureMove("card1", 1:3),
        # Draw from remaining cards for player 2
        natureMove("card2", ~setdiff(1:3, card1))
      )
    ),
    stage("pl1CheckBet",
      player=1,
      observe = "card1",
      actions = list(
        action("cb1",c("check","bet"))
      )
    ),
    stage("pl2CheckBet",
      player=2,
      condition = ~ cb1 == "check",
      observe = c("card2","cb1"),
      actions = list(
        action("cb2",c("check","bet"))
      )
    ),
    stage("pl2FoldCall",
      player=2,
      condition = ~ cb1 == "bet",
      observe = c("card2","cb1"),
      actions = list(
        action("fc2",c("fold","call"))
      )
    ),
    stage("pl1FoldCall",
      player=1,
      condition = ~ is_true(cb1 == "check" & cb2=="bet"),
      observe = "cb2",
      actions = list(
        action("fc1",c("fold","call"))
      )
    ),
    stage("PayoffStage",
      player=1:2,
      compute=list(
        # Which player folds?
        folder ~ case_distinction(
          is_true(fc1 == "fold"),1,
          is_true(fc2 == "fold"),2,
          0 # 0 means no player folds
        ),

        # Which player wins?
        winner ~ case_distinction(
          folder == 1,2,
          folder == 2,1,
          folder == 0, (card2 > card1) +1
        ),

        # How much gave each player to the pot?
        gave1 ~ 1 + 1*is_true((cb1 == "bet") | (fc1 == "call")),
        gave2 ~ 1 + 1*is_true((cb2 == "bet") | (fc2 == "call")),
        pot ~ gave1 + gave2,

        # Final payoffs
        payoff_1 ~ (winner == 1)*pot - gave1,
        payoff_2 ~ (winner == 2)*pot - gave2
      )
    )
  )
) 

To better understand the definition and to check whether we have correctly specified the game, it is useful to take a look at the outcomes:

game %>% get_outcomes() %>% head(6)

Look at the first row. We see from cb1 and cb2 that this corresponds to an outcome in which both players check. The variables fc2 and fc1 take NA values because there is no decision to fold or call if both players check.

Formulas in the game definition will be internaly evaluated in a vectorized fashion over similar data frames and may take NA values. The helper function is_true takes a logical vector and replaces NA values with FALSE. I use this function in the game definition where a condition must evaluate to either TRUE or FALSE while NA values are not allowed.

You may also take a look at the definition of card2 in the first stage. Here the set of the random variable is a formula and depends on the previously computed value of card1.

Let us also take a look at the game size:

game %>%
  game_print_size_info()

While the number of pure strategy profiles is not really small, the game still seems of tractable size for numerical analysis.

Solving Kuhn Poker

Let us now solve the game using the gambit-logit solver, which is the default solver for finding a mixed strategy equilibrium:

game %>%
  game_gambit_solve(mixed=TRUE)

Let us first take a look at the expected equilibrium outcomes:

game %>% 
  eq_expected_outcomes() %>% 
  select(payoff_1,payoff_2, cb1, fc1, cb2,fc2)

We see that player 1 has a lower expected payoff than player 2. Even though the logit solver found only one equilibrium, it is well known that two player zero-sum games with finitely many actions have unique expected equilibrium payoffs.

We also see that every player checks, bets, calls or folds with positive probability on the equilibrium path.

Exploring conditional expected equilibrium outcomes

To get better insight into the equilibria let us show the conditional expected outcomes in the case that player 1 gets as card either 1,2 or 3:

game %>%
  eq_cond_expected_outcomes("card1") %>%
  select(card1, payoff_1,payoff_2, cb1, fc1, cb2,fc2)

Naturally, player 1's payoffs increase in his card value. Interstingly, having a 2 yields to losses on average while the expected win of a 3 is larger than the expected loss of a 1.

We also see that player 1 is mixing between bet and check if his card is 1 or 3, while he always checks if his card is 2.

You may recall from fully mixed equilibria in simple bimatrix games, that in equilibrium each player chooses mixing probabilities that make the other player indifferent. This indifference requirement also plays a role in our Kuhn-Poker equilibrium, but the game is a bit more complex.

If you wanted to completely solve the game, you could already start sitting down and doing it per hand (take a look at the references on the Wikipedia page). It might be helpful, however, to first build more intution at the conditional equilibrium outcomes.

First consder the cases that player 1 has the highest card and either bets or checks:

game %>%
  eq_cond_expected_outcomes(card1=3, cb1=c("bet","check")) %>%
  select(card1, payoff_1,payoff_2, cb1, fc1, cb2,fc2)

We see that player 1 gets the same payoff from betting or checking. Of course, it must always be the case that a player is indifferent between all moves over which he mixes in an equilibrium.

We also see why player 1 is indifferent. Having the highest card player 1 will always win the pot. The only question is whether he can taunt player 2 into increasing the pot. If player 1 bets player 2 will call and thus increase the pot only with ca. 17% probability (see fc2). If player 1 checks, player 2 will also increase the pot with ca. 17% probability by betting.

How do we come to these probabilites of player 2's actions? Let us dive into the expected equilibrium outcomes conditional on the the different values of card2.

game %>%
  eq_cond_expected_outcomes("card2") %>%
  select(card2, payoff_1,payoff_2,cb2,fc2, cb1, fc1)

Like for player 1, player 2 has a negative expected payoff with a 2 while her expected wins are larger with 3 than her losses with a 1.

Player 2 only mixes between bet and check if she has a 1. Let us explore this case in more detail:

game %>%
  eq_cond_expected_outcomes(card2=1, cb2=c("bet","check")) %>%
  select(card2, payoff_1,payoff_2,cb2,fc2, cb1, fc1)

Indeed player 2 is indifferent between both moves. The drawback of bet is that inceases the pot and thus the losses if player 1 calls (with 67%). The advantage is that player 1 also folds after a bet with 33%: in this case player 2 has successfully bluffed and gets the small pot. Player 1 is indifferent between calling and folding because he does not know whether player 2 has a 1 or a 3. In contrast, if player 2 checks he always loses, but the losses are always small.

Alternative strategies

We may be interested in different strategies. For example, a consider a naive player 1 who thinks: "Obviously, it must be optimal to always bet if I have the highest card, and to never bet if I have the lowest card. That is what I will do."

What would be the resulting equilibrium strategies under this restriction? We include this behavior by adding 1000 units to player 1's utility if he follows this rule using the function game_prefer_outcomes:

game %>%
  game_prefer_outcomes(player1 =~ case_distinction(
    card1 == 1 & cb1 == "check", 1000,
    card1 == 3 & cb1 == "bet", 1000,
    0
  ))

Using some knowledge about the internal structure of the game object, we can have a look at the newly generated formulas for the utility functions:

game$pref$utils

But let us look at the resulting equilibrium outcomes

game %>%
  game_gambit_solve(mixed=TRUE) %>%
  eq_expected_outcomes()  %>%
  select(payoff_1,payoff_2, cb1, fc1, cb2,fc2)

We see that player 1 has a lower expected payoff if he wants to follow this rule than in the original equilibrium.

More details are available from the following conditional expected outcomes:

game %>%
  eq_cond_expected_outcomes("card1","cb1") %>%
  select(card1, payoff_1,payoff_2, cb1, fc1, cb2,fc2, is.eqo)  

We see that player 1 will also check if he has a 2. Given the resulting equilibrium play, he would rather like to bet if he has a 1 and check if he has a 3. Consider the later case. Since player 1 will bets only with a 3, player 2 will always fold

References

H. W. Kuhn (1951). 9. A SIMPLIFIED TWO-PERSON POKER. In Harold William Kuhn, Albert William Tucker (Eds.), Contributions to the Theory of Games (AM-24), Volume I (pp. 97–104). Princeton: Princeton

skranz/gtree documentation built on March 27, 2021, 6:03 a.m.