## A Sender-Receiver Game: Gambit’s Python API vs gtree

Here is a jupyter notebook by Valeria Burdea that creates a sender-receive game using Gambit’s Python interface. For a comparison, this tutorial shows how one can create and analyse the same game in a relatively simple fashion using gtree.

I just copy the game description from the Jupyter notebook:

“This is a 2-player sequential game the structure of which is inspired by Glazer and Rubinstein (2004, 2006). In the first stage, the sender is dealt 2 cards - one card orange, one card blue. Each card can take a value between 1 and 9; each combination of values is equally likely. A hand is good if the sum of the two cards is at least 9; a hand is bad otherwise. Upon observing the two cards, the sender chooses one to reveal to the receiver. The receiver observes the revealed card and chooses an action between ‘Accept’ and ‘Reject’. The incentives are such that the sender would always want the receiver to accept, while the receiver would only want to accept if the hand is good and reject otherwise.”

Here is the implementation of the game using gtree (the exact payoffs were taken from the Python code):

library(gtree)
game = new_game(
params = list(numPlayers=2, maxVal=9),
options = make_game_options(verbose=FALSE),
stages = list(
stage("DrawStage",
nature = list(
natureMove("orange", ~1:maxVal),
natureMove("blue", ~1:maxVal)
)
),
stage("RevealStage",
player=1,
observe = c("orange","blue"),
actions = list(
action("reveal",c("orange","blue"))
)
),
stage("AcceptStage",
player=2,
compute = list(
shownVal ~ ifelse(reveal=="orange", orange, blue)
),
observe = c("shownVal"),
actions = list(
action("accept",c(TRUE, FALSE))
)
),
stage("PayoffStage",
player=1:2,
compute=list(
payoff_1 ~ ifelse(accept, 1,0), # Sender wants accept
payoff_2 ~ case_distinction(
accept & hand=="good", 1,
!accept & hand=="good",0,
)
)
)
)
) 

I would argue that gtree’s game definition using stages follows in a straightforward and simple fashion the verbal game description.

Gambit’s Python API is instead designed to directly specify game trees. For comparison, take a look here.

## Huge number of strategy profiles

Shall we try to compute all pure SPE?

game %>% game_solve()
## Error in compute.tg.fields.for.internal.solver(tg, verbose = verbose): Even using subgames there are 1.23794003928538e+27 relevant strategy profile.
## Yet as an upper bound the internal gtree solver only attempts to fully compile and solve the game
## if there are fewer than 1e+06 relevant strategy profiles.
##  You can change this bound e.g. to 2 Mio by calling
##
## options(gtree.max.sp = 2000000)
##
## Some Gambit solvers, like gambit-logit, use algorithms that can still find one equilibrium
## in reasonable time for certain but not all games with a very large number of strategy profiles.
## So try out game_gambit_solve with a fitting Gambit command line tool (see Gambit documention).

Ups… looks like the game is too large to be solved. Here is some additional size information.

# Get some size information about the game
game %>%
game_print_size_info()
##
##
## Size Information:
##   - 324 possible outcomes
##   - 90 information sets (81 + 9)
##   - 1.23794e+27 pure strategy profiles (2.41785163922926e+24 * 512)
##   - 1 subgames
##   - 1.23794e+27 relevant pure strategy profiles in subgames

The game has a gigantic number of strategy profiles.

## Only one subgame???

Interestingly, the game also has only 1 subgame, even though player 1 perfectly observes the values of the orange and blue card. For an illustration, why there is only one subgame, we export a smaller version of the game in which cards only take values of 1 or 2 to a Gambit efg file.

game %>%
game_change_param(maxVal = 2) %>%
game_write_efg("sender_receiver.efg")

I have manually opened the efg file with Gambit and exported the following game tree as an svg graphic:

Recall the definition of a subgame, e.g. from Wikipedia:

1. It has a single initial node that is the only member of that node’s information set (i.e. the initial node is in a singleton information set).
2. If a node is contained in the subgame then so are all of its successors.
3. If a node in a particular information set is in the subgame then all members of that information set belong to the subgame.

Even though the moves of player 1 start at singleton information sets (Condition 1), candidate subgames starting at these nodes violate Condition 3.

## Find a mixed strategy equilibrium using the gambit-logit solver from gtree

If we cannot reduce the number of relevant strategy profiles by subgames, our internal gtree solver cannot practically solve games with so many strategy profiles. However, Gambit has solvers that can find at least one equilibrium of this game. Here we let gambit-logit solver do its magic.

To make the vignette build quicker I reduce the size of the game, but you can change maxVal to 9. (Takes then around 2 minutes to solve on my notebook).

game %>%
game_change_param(maxVal = 4) %>%
game_print_size_info() %>%
game_gambit_solve("gambit-logit -q -e")
##
##
## Size Information:
##   - 64 possible outcomes
##   - 20 information sets (16 + 4)
##   - 1 048 576 pure strategy profiles (65536 * 16)
##   - 1 subgames
##   - 1 048 576 relevant pure strategy profiles in subgames
game %>%  eq_tables()
## $reveal ## # A tibble: 24 x 5 ## # Groups: orange, blue, reveal [24] ## orange blue reveal .prob eq.inds ## <int> <int> <chr> <dbl> <chr> ## 1 1 1 blue 0.5 1 ## 2 1 1 orange 0.5 1 ## 3 1 2 blue 0.500 1 ## 4 1 2 orange 0.500 1 ## 5 1 3 blue 1 1 ## 6 1 4 blue 1 1 ## 7 2 1 blue 0.500 1 ## 8 2 1 orange 0.500 1 ## 9 2 2 blue 0.5 1 ## 10 2 2 orange 0.5 1 ## # ... with 14 more rows ## ##$accept
## # A tibble: 4 x 4
## # Groups:   shownVal, accept [4]
##   shownVal accept .prob eq.inds
##      <int> <lgl>  <dbl> <chr>
## 1        1 FALSE      1 1
## 2        2 FALSE      1 1
## 3        3 TRUE       1 1
## 4        4 TRUE       1 1

The results seem intutive: Player 2 only accepts if and only if the shown card is at least a 6. Player 1 always shows a card that is at least 6 if he has one.

## Find a quantal response equilibrium

You may first take a look at the Wikipedia page for quantal response equilibria. The following code uses the gambit-logit solver to compute a logit agent quantal response equilibrium using the parameter lambda=3.

game %>%
game_change_param(maxVal = 4) %>%
game_print_size_info() %>%
game_gambit_solve("gambit-logit -q -e -m 3") %>%
eq_tables()
##
##
## Size Information:
##   - 64 possible outcomes
##   - 20 information sets (16 + 4)
##   - 1 048 576 pure strategy profiles (65536 * 16)
##   - 1 subgames
##   - 1 048 576 relevant pure strategy profiles in subgames
## $reveal ## # A tibble: 32 x 5 ## # Groups: orange, blue, reveal [32] ## orange blue reveal .prob eq.inds ## <int> <int> <chr> <dbl> <chr> ## 1 1 1 blue 0.5 1 ## 2 1 1 orange 0.5 1 ## 3 1 2 blue 0.801 1 ## 4 1 2 orange 0.199 1 ## 5 1 3 blue 0.928 1 ## 6 1 3 orange 0.0722 1 ## 7 1 4 blue 0.928 1 ## 8 1 4 orange 0.0722 1 ## 9 2 1 blue 0.199 1 ## 10 2 1 orange 0.801 1 ## # ... with 22 more rows ## ##$accept
## # A tibble: 8 x 4
## # Groups:   shownVal, accept [8]
##   shownVal accept  .prob eq.inds
##      <int> <lgl>   <dbl> <chr>
## 1        1 FALSE  0.881  1
## 2        1 TRUE   0.119  1
## 3        2 FALSE  0.425  1
## 4        2 TRUE   0.575  1
## 5        3 FALSE  0.0451 1
## 6        3 TRUE   0.955  1
## 7        4 FALSE  0.0451 1
## 8        4 TRUE   0.955  1

The python code called gambit-logit without the option -e. It then returns a table of (approximated) equilibria for many values of lambda up to the maximum specified by the option -m. I have currently not implemented a feature in gtree to automatically parse that whole table. But if there is interest, just let me know, via Github issue or email.