Game representation formats

This section documents the file formats recognized by Gambit. These file formats are text-based and designed to be readable and editable by hand by humans to the extent possible, although programmatic tools to generate and manipulate these files are almost certainly needed for all but the most trivial of games.

These formats can be viewed as being low-level. They define games explicitly in terms of their structure, and do not support any sort of parameterization, macros, and the like. Thus, they are adapted largely to the type of input required by the numerical methods for computing Nash equilibria, which only apply to a particular realization of a game’s parameters. Higher-level tools, whether the graphical interface or scripting applications, are indicated for doing parametric analysis and the like.

Conventions common to all file formats

Several conventions are common to the interpretation of the file formats listed below.

Whitespace is not significant. In general, whitespace (carriage returns, horizontal and vertical tabs, and spaces) do not have an effect on the meaning of the file. The only exception is inside explicit double-quotes, where all characters are significant. The formatting shown here is the same as generated by the Gambit code and has been chosen for its readability; other formattings are possible (and legal).

Text labels. Most objects in an extensive game may be given textual labels. These are prominently used in the graphical interface, for example, and it is encouraged for users to assign nonempty text labels to objects if the game is going to be viewed in the graphical interface. In all cases, these labels are surrounded by the quotation character (”). The use of an explicit ” character within a text label can be accomplished by preceding the embedded ” characters with a backwards slash (). Example 5-1. Escaping quotes in a text label

This is an alternate version of the first line of the example file, in which the title of the game contains the term Bayesian game in quotation marks.

EFG 2 R "An example of a \"Bayesian game\"" { "Player 1" "Player 2" }

Numerical data. yNumerical data, namely, the payoffs at outcomes, and the action probabilities for chance nodes, may be expressed in integer, decimal, or rational formats. In all cases, numbers are understood by Gambit to be exact, and represented as such internally. For example, the numerical entries 0.1 and 1/10 represent the same quantity.

In versions 0.97 and prior, Gambit distinguished between floating point and rational data. In these versions, the quantity 0.1 was represented interally as a floating-point number. In this case, since 0.1 does not have an exact representation in binary floating point, the values 0.1 and 1/10 were not identical, and some methods for computing equilibria could give (slightly) different results for games using one versus the other. In particular, using rational-precision methods on games with the floating point numbers could give unexpected output, since the conversion of 0.1 first to floating-point then to rational would involve roundoff error. This is largely of technical concern, and the current Gambit implementation now behaves in such a way as to give the “expected” result when decimal numbers appear in the file format.

The extensive game (.efg) file format

The extensive game (.efg) file format has been used by Gambit, with minor variations, to represent extensive games since circa 1994. It replaced an earlier format, which had no particular name but which had the conventional extension .dt1. It is intended that some new formats will be introduced in the future; however, this format will be supported by Gambit, possibly through the use of converter programs to those putative future formats, for the foreseeable future.

A sample file

This is a sample file illustrating the general format of the file. This file is similar to the one distributed in the Gambit distribution under the name bayes1a.efg .

EFG 2 R "General Bayes game, one stage" { "Player 1" "Player 2" }
c "ROOT" 1 "(0,1)" { "1G" 0.500000 "1B" 0.500000 } 0
c "" 2 "(0,2)" { "2g" 0.500000 "2b" 0.500000 } 0
p "" 1 1 "(1,1)" { "H" "L" } 0
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 1 "Outcome 1" { 10.000000 2.000000 }
t "" 2 "Outcome 2" { 0.000000 10.000000 }
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 3 "Outcome 3" { 2.000000 4.000000 }
t "" 4 "Outcome 4" { 4.000000 0.000000 }
p "" 1 1 "(1,1)" { "H" "L" } 0
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 5 "Outcome 5" { 10.000000 2.000000 }
t "" 6 "Outcome 6" { 0.000000 10.000000 }
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 7 "Outcome 7" { 2.000000 4.000000 }
t "" 8 "Outcome 8" { 4.000000 0.000000 }
c "" 3 "(0,3)" { "2g" 0.500000 "2b" 0.500000 } 0
p "" 1 2 "(1,2)" { "H" "L" } 0
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 9 "Outcome 9" { 4.000000 2.000000 }
t "" 10 "Outcome 10" { 2.000000 10.000000 }
p "" 2 1 "(2,1)" { "h" "l" } 0
t "" 11 "Outcome 11" { 0.000000 4.000000 }
t "" 12 "Outcome 12" { 10.000000 2.000000 }
p "" 1 2 "(1,2)" { "H" "L" } 0
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 13 "Outcome 13" { 4.000000 2.000000 }
t "" 14 "Outcome 14" { 2.000000 10.000000 }
p "" 2 2 "(2,2)" { "h" "l" } 0
t "" 15 "Outcome 15" { 0.000000 4.000000 }
t "" 16 "Outcome 16" { 10.000000 0.000000 }

Structure of the prologue

The extensive gamefile consists of two parts: the prologue, or header, and the list of nodes, or body. In the example file, the prologue is the first line. (Again, this is just a consequence of the formatting we have chosen and is not a requirement of the file structure itself.)

The prologue is constructed as follows. The file begins with the token EFG , identifying it as an extensive gamefile. Next is the digit 2 ; this digit is a version number. Since only version 2 files have been supported for more than a decade, all files have a 2 in this position. Next comes the letter R . The letter R used to distinguish files which had rational numbers for numerical data; this distinction is obsolete, so all new files should have R in this position.

The prologue continues with the title of the game. Following the title is a list of the names of the players defined in the game. This list follows the convention found elsewhere in the file of being surrounded by curly braces and delimited by whitespace (but not commas, semicolons, or any other character). The order of the players is significant; the first entry in the list will be numbered as player 1, the second entry as player 2, and so forth. At the end of the prologue is an optional text comment field.

Structure of the body (list of nodes)

The body of the file lists the nodes which comprise the game tree. These nodes are listed in the prefix traversal of the tree. The prefix traversal for a subtree is defined as being the root node of the subtree, followed by the prefix traversal of the subtree rooted by each child, in order from first to last. Thus, for the whole tree, the root node appears first, followed by the prefix traversals of its child subtrees. For convenience, the game above follows the convention of one line per node.

Each node entry begins with an unquoted character indicating the type of the node. There are three node types:

• c for a chance node
• p for a personal player node
• t for a terminal node

Each node type will be discussed individually below. There are three numbering conventions which are used to identify the information structure of the tree. Wherever a player number is called for, the integer specified corresponds to the index of the player in the player list from the prologue. The first player in the list is numbered 1, the second 2, and so on. Information sets are identified by an arbitrary positive integer which is unique within the player. Gambit generates these numbers as 1, 2, etc. as they appear first in the file, but there are no requirements other than uniqueness. The same integer may be used to specify information sets for different players; this is not ambiguous since the player number appears as well. Finally, outcomes are also arbitrarily numbered in the file format in the same way in which information sets are, except for the special number 0 which indicates the null outcome.

Information sets and outcomes may (and frequently will) appear multiple times within a game. By convention, the second and subsequent times an information set or outcome appears, the file may omit the descriptive information for that information set or outcome. Alternatively, the file may specify the descriptive information again; however, it must precisely match the original declaration of the information set or outcome. If any part of the description is omitted, the whole description must be omitted.

Outcomes may appear at nonterminal nodes. In these cases, payoffs are interepreted as incremental payoffs; the payoff to a player for a given path through the tree is interpreted as the sum of the payoffs at the outcomes encountered on that path (including at the terminal node). This is ideal for the representation of games with well- defined”stages”; see, for example, the file bayes2a.efg in the Gambit distribution for a two-stage example of the Bayesian game represented previously.

In the following lists, fields which are omittable according to the above rules are indicated by the label (optional).

Format of chance (nature) nodes. Entries for chance nodes begin with the character c . Following this, in order, are

• a text string, giving the name of the node
• a positive integer specifying the information set number
• (optional) the name of the information set
• (optional) a list of actions at the information set with their corresponding probabilities
• a nonnegative integer specifying the outcome
• (optional)the payoffs to each player for the outcome

Format of personal (player) nodes. Entries for personal player decision nodes begin with the character p . Following this, in order, are:

• a text string, giving the name of the node
• a positive integer specifying the player who owns the node
• a positive integer specifying the information set
• (optional) the name of the information set
• (optional) a list of action names for the information set
• a nonnegative integer specifying the outcome
• (optional) the name of the outcome
• the payoffs to each player for the outcome

Format of terminal nodes. Entries for terminal nodes begin with the character t . Following this, in order, are:

• a text string, giving the name of the node
• a nonnegative integer specifying the outcome
• (optional) the name of the outcome
• the payoffs to each player for the outcome

There is no explicit end-of-file delimiter for the file.

The strategic game (.nfg) file format, payoff version

This file format defines a strategic N-player game. In this version, the payoffs are listed in a tabular format. See the next section for a version of this format in which outcomes can be used to identify an equivalence among multiple strategy profiles.

A sample file

This is a sample file illustrating the general format of the file. This file is distributed in the Gambit distribution under the name e02.nfg .

NFG 1 R "Selten (IJGT, 75), Figure 2, normal form"
{ "Player 1" "Player 2" } { 3 2 }

1 1 0 2 0 2 1 1 0 3 2 0

Structure of the prologue

The prologue is constructed as follows. The file begins with the token NFG , identifying it as a strategic gamefile. Next is the digit 1 ; this digit is a version number. Since only version 1 files have been supported for more than a decade, all files have a 1 in this position. Next comes the letter R . The letter R used to distinguish files which had rational numbers for numerical data; this distinction is obsolete, so all new files should have R in this position.

The prologue continues with the title of the game. Following the title is a list of the names of the players defined in the game. This list follows the convention found elsewhere in the file of being surrounded by curly braces and delimited by whitespace (but not commas, semicolons, or any other character). The order of the players is significant; the first entry in the list will be numbered as player 1, the second entry as player 2, and so forth.

Following the list of players is a list of positive integers. This list specifies the number of strategies available to each player, given in the same order as the players are listed in the list of players.

The prologue concludes with an optional text comment field.

Structure of the body (list of payoffs)

The body of the format lists the payoffs in the game. This is a “flat” list, not surrounded by braces or other punctuation.

The assignment of the numeric data in this list to the entries in the strategic game table proceeds as follows. The list begins with the strategy profile in which each player plays their first strategy. The payoffs to all players in this contingency are listed in the same order as the players are given in the prologus. This, in the example file, the first two payoff entries are 1 1 , which means, when both players play their first strategy, player 1 receives a payoff of 1, and player 2 receives a payoff of 1.

Next, the strategy of the first player is incremented. Thus, player 1’s strategy is incremented to his second strategy. In this case, when player 1 plays his second strategy and player 2 his first strategy, the payoffs are 0 2 : a payoff of 0 to player 1 and a payoff of 2 to player 2.

Now the strategy of the first player is again incremented. Thus, the first player is playing his third strategy, and the second player his first strategy; the payoffs are again 0 2 .

Now, the strategy of the first player is incremented yet again. But, the first player was already playing strategy number 3 of 3. Thus, his strategy now “rolls over” to 1, and the strategy of the second player increments to 2. Then, the next entries 1 1 correspond to the payoffs of player 1 and player 2, respectively, in the case where player 1 plays his second strategy, and player 2 his first strategy.

In general, the ordering of contingencies is done in the same way that we count: incrementing the least-significant digit place in the number first, and then incrementing more significant digit places in the number as the lower ones “roll over.” The only differences are that the counting starts with the digit 1, instead of 0, and that the “base” used for each digit is not 10, but instead is the number of strategies that player has in the game.

The strategic game (.nfg) file format, outcome version

This file format defines a strategic N-player game. In this version, the payoffs are defined by means of outcomes, which may appear more than one place in the game table. This may give a more compact means of representing a game where many different strategy combinations map to the same consequences for the players. For a version of this format in which payoffs are listed explicitly, without identification by outcomes, see the previous section.

A sample file

This is a sample file illustrating the general format of the file. This file defines the same game as the example in the previous section.

NFG 1 R "Selten (IJGT, 75), Figure 2, normal form" { "Player 1" "Player 2" }

{
{ "1" "2" "3" }
{ "1" "2" }
}

{
{ "" 1, 1 }
{ "" 0, 2 }
{ "" 0, 2 }
{ "" 1, 1 }
{ "" 0, 3 }
{ "" 2, 0 }
}
1 2 3 4 5 6

Structure of the prologue

The prologue is constructed as follows. The file begins with the token NFG , identifying it as a strategic gamefile. Next is the digit 1 ; this digit is a version number. Since only version 1 files have been supported for more than a decade, all files have a 1 in this position. Next comes the letter R . The letter R used to distinguish files which had rational numbers for numerical data; this distinction is obsolete, so all new files should have R in this position.

The prologue continues with the title of the game. Following the title is a list of the names of the players defined in the game. This list follows the convention found elsewhere in the file of being surrounded by curly braces and delimited by whitespace (but not commas, semicolons, or any other character). The order of the players is significant; the first entry in the list will be numbered as player 1, the second entry as player 2, and so forth.

Following the list of players is a list of strategies. This is a nested list; each player’s strategies are given as a list of text labels, surrounded by curly braces.

The nested strategy list is followed by an optional text comment field.

The prologue closes with a list of outcomes. This is also a nested list. Each outcome is specified by a text string, followed by a list of numerical payoffs, one for each player defined. The payoffs may optionally be separated by commas, as in the example file. The outcomes are implicitly numbered in the order they appear; the first outcome is given the number 1, the second 2, and so forth.

Structure of the body (list of outcomes)

The body of the file is a list of outcome indices. These are presented in the same lexicographic order as the payoffs in the payoff file format; please see the documentation of that format for the description of the ordering. For each entry in the table, a nonnegative integer is given, corresponding to the outcome number assigned as described in the prologue section. The special outcome number 0 is reserved for the “null” outcome, which is defined as a payoff of zero to all players. The number of entries in this list, then, should be the same as the product of the number of strategies for all players in the game.

The action graph game (.agg) file format

Action graph games (AGGs) are a compact representation of simultaneous-move games with structured utility functions. For more information on AGGs, the following paper gives a comprehensive discussion.

A.X. Jiang, K. Leyton-Brown and N. Bhat, Action-Graph Games, Games and Economic Behavior, Volume 71, Issue 1, January 2011, Pages 141-173.

Each file in this format describes an action graph game. In order for the file to be recognized as AGG by GAMBIT, the initial line of the file should be:

#AGG

The rest of the file consists of 8 sections, separated by whitespaces. Lines with starting ‘#’ are treated as comments and are allowed between sections.

1. The number of players, n.

2. The number of action nodes, |S|.

3. The number of function nodes, |P|.

4. Size of action set for each player. This is a row of n integers:

   |S₁| |S₂| .... |S_n|

5. Each Player’s action set. We have N rows; row i has |S_i| integers in ascending order, which are indices of Action nodes. Action nodes are indexed from 0 to |S|-1.

6. The Action Graph. We have |S|+|P| nodes, indexed from 0 to |S|+|P|-1. The function nodes are indexed after the action nodes. The graph is represented as (|S|+|P|) neighbor lists, one list per row. Rows 0 to |S|-1 are for action nodes; rows |S| to |S|+|P|-1 are for function nodes. In each row, the first number |v| specifies the number of neighbors of the node. Then follows |v| numbers, corresponding to the indices of the neighbors.

   We require that each function node has at least one neighbor, and the neighbors of function nodes are action nodes. The action graph restricted to the function nodes has to be a directed acyclic graph (DAG).

7. Signatures of functions. This is |P| rows, each specifying the mapping f_p that maps from the configuration of the function node p’s neighbors to an integer for p’s “action count”. Each function is specified by its “signature” consisting of an integer type, possibly followed by further parameters. Several types of mapping are implemented:

   • Types 0-3 require no further input.

     • Type 0: Sum. i.e. The action count of a function node p is the sum of the action counts of p’s neighbors.
     • Type 1: Existence: boolean for whether the sum of the counts of neighbors are positive.
     • Type 2: The index of the neighbor with the highest index that has non-zero counts, or |S|+|P| if none applies.
     • Type 3: The index of the neighbor with the lowest index that has non-zero counts, or |S|+|P| if none applies.

   • Types 10-13 are extended versions of type 0-3, each requiring further parameters of an integer default value and a list of weights, |S| integers enclosed in square brackets. Each action node is thus associated with an integer weight.

     • Type 10: Extended Sum. Each instance of an action in p’s neighborhood being chosen contributes the weight of that action to the sum. These are added to the default value.
     • Type 11: Extended Existence: boolean for whether the extended sum is positive. The input default value and weights are required to be nonnegative.
     • Type 12: The weight of the neighbor with the highest index that has non-zero counts, or the default value if none applies.
     • Type 13: The weight of the neighbor with the lowest index that has non-zero counts, or the default value if none applies.

   The following is an example of the signatures for an AGG with three action nodes and two function nodes:

   2
   10 0 [2 3 4]
   

8. The payoff function for each action node. So we have |S| subblocks of numbers. Payoff function for action s is a mapping from configurations to real numbers. Configurations are represented as a tuple of integers; the size of the tuple is the size of the neighborhood of s. Each configuration specifies the action counts for the neighbors of s, in the same order as the neighbor list of s.

   The first number of each subblock specifies the type of the payoff function. There are multiple ways of representing payoff functions; we (or other people) can extend the file format by defining new types of payoff functions. We define two basic types:

   Type 0

   The complete representation. The set of possible configurations can be derived from the action graph. This set of configurations can also be sorted in lexicographical order. So we can just specify the payoffs without explicitly giving the configurations. So we just need to give one row of real numbers, which correspond to payoffs for the ordered set of configurations.

   If action s is in multiple players’ action sets (say players i, j), then it is possible that the set of possible configurations given s_i is different from the set of possible configurations given s_j. In such cases, we need to specify payoffs for the union of the sets of configurations (sorted in lexicographical order).

   Type 1

   The mapping representation, in which we specify the configurations and the corresponding payoffs. For the payoff function of action s, first give Delta_s, the number of elements in the mapping. Then follows Delta_s rows. In each row, first specify the configuration, which is a tuple of integers, enclosed by a pair of brackets “[” and “]”, then the payoff. For example, the following specifies a payoff function of type 1, with two configurations:

   1 2
   [1 0] 2.5
   [1 1] -1.2
   

The Bayesian action graph game (.bagg) format

Bayesian action graph games (BAGGs) are a compact representation of Bayesian (i.e., incomplete-information) games. For more information on BAGGs, the following paper gives a detailed discussion.

A.X. Jiang and K. Leyton-Brown, Bayesian Action-Graph Games. NIPS, 2010.

Each file in this format describes a BAGG. In order for the file to be recognized as BAGG by GAMBIT, the initial line of the file should be:

#BAGG

The rest of the file consists of the following sections, separated by whitespaces. Lines with starting ‘#’ are treated as comments and are allowed between sections.

1. The number of Players, n.

2. The number of action nodes, |S|.

3. The number of function nodes, |P|.

4. The number of types for each player, as a row of n integers.

5. Type distribution for each player. The distributions are assumed to be independent. Each distribution is represented as a row of real numbers. The following example block gives the type distributions for a BAGG with two players and two types for each player:

   0.5 0.5
   0.2 0.8
   

6. Size of type-action set for each player’s each type.

7. Type-action set for each player’s each type. Each type-action set is represented as a row of integers in ascending order, which are indices of action nodes. Action nodes are indexed from 0 to |S|-1.

8. The action graph: same as in the AGG format.

9. types of functions: same as in the AGG format.

10. utility function for each action node: same as in the AGG format.