Gambit: Software Tools for Game Theory | ||
---|---|---|
<<< Previous | Getting Started with the Graphical Interface | Next >>> |
The analysis begins by searching for actions which might be dominated by other actions at the same move. The Dominance item on the Tools menu presents a dialog box giving options for finding dominated actions:
There are four sets of options:
Type: Actions can be removed based upon either strong (or strict) dominance, or weak dominance;
Conditional: Chooses whether actions are considered dominated overall, or only conditional on their information set being reached;
Depth: One round of dominance elimination can be performed; or, Gambit can continue to eliminate strategies until no more strategies are dominated;
Players: Actions for all, or only some, of the players in the game may be considered in doing elimination.
After clicking OK, a progress dialog briefly appears, and then the game display appears like this:
Gambit keeps track of all the sets of actions computed. On the View menu is an item Supports. Selecting this item displays an additional panel on the extensive form display, as shown below. (You may need to resize your window a bit to be able to see the whole tree as in this screenshot.)
To compute Nash equilibria for the game, use the Equilibrium item on the Tools menu. This menu item shows a dialog box listing the available algorithms for computing equilibria. The list of algorithms will vary depending on the game, as some algorithms apply only to constant-sum games, or to games with two players. In this case, since the poker game is a two-person constant-sum game, all the available algorithms are shown.
Algorithms are divided into two groups:
Standard algorithms. These are algorithms and parameter settings chosen as being recommended for computing the given number and type of equilibria shown.
Custom algorithms. These are the actual algorithms implemented in Gambit. Selecting these displays a corresponding panel presenting the options available to configure the algorithm's behavior.
After clicking OK, a progress box briefly appears. When the algorithm completes, the profiles panel is now shown at the bottom of the tree window, with one profile shown. The profile is also displayed schematically on the game tree. The profiles panel presents information about the profile:
Name: A label for the profile. This is automatically generated, and can be changed by double-clicking the profile's entry in the profile list to display the Properties dialog.
Creator: The algorithm which created the profile, or User if the profile was created or modified by the user.
Nash: Indicates if the profile is a Nash equilibrium; in this case, this field displays Y to indicate it is.
Perfect: Indicates if the profile is a subgame perfect Nash equilibrium; in this case, this field displays Y to indicate it is. (Since there are no proper subgames in this game, any Nash equilibrium must be subgame perfect.)
Sequential: Indicates if the profile is a sequential Nash equilibrium; in this case, this field displays DK to indicate this is unknown. Some algorithms can be shown to compute only sequential equilibria, but there is no implemented test for whether a given profile is sequential.
Liap value: Displays the Lyapunov value (see [McK91]) of the profile. The Lyapunov value is zero exactly when the profile is a Nash equilibrium.
In this case, the equilibrium involves Player 1, raising with probability one at his first information set, which follows his drawing the Red card. At his second information set, following a draw of a black card, he raises with probability one-third, and folds with probability two-thirds. Player 2, at her only information set, meets Player 1's raise with probability two-thirds, and passes with probability one-third.
These probabilities are represented schematically on the tree. At each information set, black segments proportional to the probability each action is played are plotted along the branch for each action. Additionally, by default, action probabilities are shown below each branch. (Which labels are shown at nodes and actions can be customized using the dialog accessed from the Legends item on the Display submenu on the Format menu.
Additional information about profiles is displayed on the navigation panel. This is displayed using the Navigation item on the View menu. When a node is selected in the tree (by clicking on it, or by using arrow keys to navigate to it), this panel displays the following information computed from the profile:
The node value: A vector of payoffs showing the expected payoff to each player, conditional on having reached this node in the play of the game.
The probability the information set to which this node belongs is reached.
The belief: the probability the choosing player assigns to being at this node, conditional on finding out he is at this information set.
The expected payoff of the choosing player, conditional on reaching this information set.
The expected payoff of choosing the action which leads to this node, evaluated from the perspective of the player who chooses that action.
The custom algorithms available in the Nash equilibrium algorithm dialog give the option, where appropriate, of using the extensive form or normal form for computing equilibria. Therefore, one can compute equilibria using normal-form based algorithms without having to explicitly create and display the normal form of the game. The next section will cover how to view the normal form of the game, and how to compute Nash equilibria in mixed profiles.
[1] | For an overview of tips and techniques for finding Nash equilibria, see the section called Tips on getting started in the appendix called Reference: Algorithms to Compute Nash Equilibria. |
<<< Previous | Home | Next >>> |
Getting Started with the Graphical Interface | Up | Finding Nash equilibria using the normal form |