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

knitr::opts_chunk$set(echo = TRUE, error=TRUE)
library(gtree)

This tutorial uses an even simpler ultimatum game example than the README file. Yet, we explain gtree in a bit more detail.

Specifying the game

First, we load the gtree library amd then define a simple ultimatum game with the function new_game.

library(gtree)
game = new_game(
  gameId = "UltimatumGame",
  options = make_game_options(verbose=TRUE),
  params = list(numPlayers=2,cake=4),
  stages = list(
    stage("proposerStage",
      player=1,
      actions = list(
        action("offer",~0:cake)
      )
    ),
    stage("responderStage",
      player=2,
      observe = "offer",
      actions = list(
        action("accept",c(FALSE,TRUE))
      )
    ),
    stage("PayoffStage",
      player=1:2,
      compute=list(
        payoff_1 ~ ifelse(accept, cake-offer,0),
        payoff_2 ~ ifelse(accept, offer,0)
      )
    )
  )
)

The gameId should be a unique name of the game. This is relevant if we want to conveniently save results, like computed equilibria, in the default folder structure used by gtree.

We then define a list of parameters params. Parameters can be referenced to in later definitions of the game. Note that you must always specify the number of players in a parameter called numPlayers. We also specify the size of the cake that can be distributed between the proposer and responder in the game.

Heart of our definition is a list of 3 stages. Each stage in the list should be generated with the function stage that sets defaults and transforms all formulas into a canoncial format.

1. In the first stage is named proposerStage. The argument player=1, specifies that player 1 acts here. She chooses an action offer, that is created with the function action and element of a list actions. The function action first requires a name and then a set of possible values the action can take. Here we specify the set as a formula ~ 0:cake. This means we compute the action set based on the specified parameters and possibly based on previously computed variables including chosen action values or realized moves of nature.
Alternatively, we could also provide a fixed action set without formula e.q. 0:4. This can not contain references to parameters or variables of the game and is always fixed when the game is created.

2. In the second stage player 2, observes the offer. This is specified by the argument observe="offer". The argument observe specifies all observed variables as a simple character vector, or remains NULL if nothing is observed.
Player 2 then decides whether to accept the action or not. Here we have chosen the fixed action set c(FALSE,TRUE). You could encode specify the set for accept in a different way, e.g. as a character vector c("reject","accept") or an integer vector c(0,1).

3. The third stage just computes variables as specified by the list provided for the field compute. You can briefly specify a computation with the formula syntax name ~ formula. Note that for each player i you must compute somewhere in your game the variable payoff_i, like payoff_1 and payoff_2, that specifies the (monetary) payoff for that player. We can later easily transform these monetary payoffs, using some alternative outcome based utility function, e.g. to account for inequality aversion or loss aversion.
You can use any vectorized, deterministic R function to specify a computed variable. Random variables must be declared separately, as a move of nature, however (see further below). Here we use the function ifelse for a simple distinction of two cases. For distinguishing more than two cases the functions cases in gtree provides a simple syntax. Note that we could have more compactly written: payoff_1 ~ (cake-offer)*accept and payoff_2 ~ offer*accept

For computing equilibria, it does not really matter which players you specify a stage in which no action takes place. However, gtree also has (currently rudimentary) features to run a game as a web-based experiment. When running as an experiment, a stage will be shown to all players that are specified in the players field. If an action is taken in a stage, exactly ONE player must be specified. For stages without actions, you can specify any number of players including no player.

We can get a short overview of a specified game by typing its variable name in the R console.

game

Compiling and Solving for equilibria

In order to compute equlibria gtree will create different internal representations of the game. While the function game_solve will automatically call the corresponding functions, it is useful to call them manually before.

game_compile(game, for.internal.solver = TRUE)
game

We now see some additional information about the size of the game in terms of number of outcomes, information sets, subgames and number of pure strategy profiles.

As a game tree our game looks as follows:

Remark 1: By default game_compile only computes the information neccessary to create a game tree that can be saved as a Gambit .efg file and then solved via Gambit. Gambit has a larger selection of solvers and for many cases, you have to use Gambit. E.g. when finding a mixed strategy equilibrium. Only for finding all pure strategy SPE, gtree has an internal solver (it is often faster than the corresponding gambit-enumpure solver of Gambit). The internal solver computes some additional information, e.g. identifying in which information sets new subgames start. The argument for.internal.solver forced the computation of this additional information.

Remark 2: A game object is an environment, this means functions like game_compile have side effects and directly change the game object. Nevertheless, all functions starting with game_ also return the changed game object invisibly. They thus can be conveniently used with pipes.

Remark 3: To generate an image of the game tree, we can export the game to a Gambit extensive form game format using the following command:

game_write_efg(game,"UG.efg")

We can then open the file with Gambit GUI, which draws the game tree.

Ok, enough remarks. Let us now solve the game. More precisely, we use the internal solver to find all pure strategy subgame (SPE) perfect equilibria.

game_solve(game)

Expected Equilibrium outcomes

The following code shows the equilibrium outcomes, i.e. all actions and computed variables on the equilibrium path.

eq_expected_outcomes(game)

We have two different equilibrium outcomes: the proposer either offers 0 or 1 and in both equilibrium outcomes the offer will be accepted. For games with moves of nature there is also a function eq_expected_outcomes that shows expected equilibrium outcomes.

Equilibria represented as action tables

An equilibrium also describes equilibrium play off the equilibrium path, e.g. it also describes whether player 2 would accept an out-off-equilibrium offer of 3.

In gtree there are different ways to represent the computed equilibria. Here is a convenient representation for pure strategy equilibria:

eq_tables(game, combine=2, reduce.tables = TRUE)

We have a list with a tibble for every action variable.

• The first table describes the equilibrium offers: In the first equilibrium the offer is 1 and in the 2nd it is 0.

• The second table describes the conditional accept decisions: In the first equilibrium an offer of 0 is rejected, in all other cases the offer is accepted.

The argument combine can take the values 0,1 and 2 and describes how the results of different equilibria are combined. For example, with combine = 0, we would get a separate list for every equilibrium. The argument reduce.tables automatically removes key columns that have no impact on the chosen equilibrium action.

Conditional expected equilibrium outcomes

Let me illustrate another useful function to explore equilibria:

eq_cond_expected_outcomes(game, offer=0)

Here we show the expected conditional equilibrium outcomes (for all equilibria) assuming that player 1 chooses an offer of 0.

The column is.eqo is TRUE if offer = 0 indeed could happen with positive probability on the equilibrium path of the corresponding equilibrium.

If that offer would not ever be chosen on the equilibrium path, think of the condition as an unexpected one-shot deviation from the equilbrium path.

We can study multiple conditions, e.g.

# Condition first on offer = 0 then on offer = 1
eq_cond_expected_outcomes(game, offer=0:1)

# Condition step-by-step on each possible offer
eq_cond_expected_outcomes(game, "offer")

We can also condition on different variables at the same time:

eq_cond_expected_outcomes(game, offer=2, accept=FALSE)

Here we assume that in the same play player 1 trembles to offer=2 and player 2 trembles to not accept.

Admittedly these functions are not really neccessary for our simple Ultimatum game. Yet, take a look at the the Kuhn-Poker tutorial to see how they help to illuminate more complicated equilibrium structures.

Internal representation of equilibria

The different representations of equilibria are computed from an internal representation of equilibria. To understand the internal representation, it is first useful to show all possible outcomes of the game:

get_outcomes(game, reduce.cols=TRUE)

This data frame corresponds to all possible full paths that can be taken through the game tree. (It does not fully describe the game tree, though, since it contains no specification of information sets.)

Let us now show the internal representation of our 2 equilibria:

eq_li(game)

It is a list with a matrix for each equilibrium. Each row corresponds to one possible outcome of the game and the column describe for each action the equilibrium choice probability on the corresponding outcome path. The last column specifies the total probality of the particular outcome in the equilibrium.

The attribute info.set.probs shows the most compact equilibrium representation. It is just a numerical vector that describes the move probability for every possible move in every information set. This is similar to the equilibrium representation that you get if you manually call a Gambit solver on an .efg file (except that Gambit has a different default ordering of the information sets). The information sets are further described in the game object. In principle you can access the information, e.g. by typing

game$tg$ise.df

Yet, there should not be any need to dig so deeply into the internal game representation of gtree.

Setting different preferences

So far we assumed that the specified payoffs payoff_1 and payoff_2 are equal to players' utility. One motivation for gtree is to conveniently solve games for different specifications of players' preferences that can account e.g. for inequality aversion or loss aversion.

While in principle, one could account for different outcome based preferences by directly adapting the formulas for payoff_1 and payoff_2 in the game definition, we prefer a slightly different approach.

In the preferred approach the specified payoffs in the game definition are interpreted as monetary or material payoffs. This means games created by new_game can very closely match the structure of economic experiments, for which we only know the specified monetary payoffs.

After the game is specified, we can use the function game_set_preferences to specify a utility function for which we want to find equilibria.

For example, consider the following inequality aversion utility function (Fehr and Schmidt, 1999) [ u_i = \pi_i - \alpha \frac {1}{n-1}\sum_{j \ne i} \max(\pi_j - \pi_i,0) + \beta \frac {1}{n-1}\sum_{j \ne i} \max(\pi_i - \pi_j,0) ] where $\pi$ denotes monetary payoffs.

The following code manually specifies these preferences and solves for subgame perfect equilibria:

pref = pref_custom(
  util_1 = payoff_1 - alpha*(pmax(payoff_2-payoff_1,0)) - beta*(pmax(payoff_1-payoff_2,0)),
  util_2 = payoff_2 - alpha*(pmax(payoff_1-payoff_2,0)) - beta*(pmax(payoff_1-payoff_2,0)),
  params = list(alpha = 1, beta=0.5),
  label = "ineqAv_100_50"
)

game %>%
  game_set_preferences(pref) %>%
  game_solve_spe() %>% 
  eq_tables()

We see that with inequality aversion with an envy parameter of alpha=1 and a guilt parameter of beta=0.5 there is a unique SPE in which the proposer offers half of the cake.

Some common preference clases that are only transformations of material payoffs are included into gtree. All functions start with the prefix pref_. The following code verifies that guilt is not essential for positive offers by the proposer.

game %>%
  game_set_preferences(pref_ineqAv(alpha=1,beta=0)) %>%
  game_solve() %>% 
  eq_tables()

We will discuss later how one can specify heterogenous preferences via different preference types.

Finding a logit quantal response equilibrium using Gambit

The internal gtree solver can only find pure strategy subgame perfect equilibria. To effectively use gtree you should also install Gambit on your computer. Then best add the Gambit directory to your system PATH. Otherwise adapt the following call to globably specify the gambit directory:

options(gtree.gambit.dir="C:/your/gambit/path")

The following code uses the gambit-logit command line solver to find a logit quantal response equilibrium using a parameter lambda = 2 assuming inequality aversion preferences.

game %>%
  game_set_preferences(pref_ineqAv(alpha=1,beta=0.5, player=1:2)) %>%
  game_gambit_solve(qre.lambda=2) %>% 
  eq_tables()

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