Finding Nash equilibria using the extensive form

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:

In this example, we will look for one Nash equilibrium of this game, so we will conditionally eliminat weakly dominated strategies iteratively for all players, as shown in the screenshot. [1]

After clicking OK, a progress dialog briefly appears, and then the game display appears like this:

The action "Fold" is weakly dominated for Player 1 when he has the Red card; therefore, in this display, the "Fold" action is erased from the game tree.

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.)

The Supports tab in the information pane on the left schematically displays the current support. The action "Fold" in Fred's first information set is light grey, indicating it is not in the support called "Support2". All other actions are in black, indicating they are included in the support. The drop-down box at the top of the support display lists all the supports that have been computed; if you click on it now, you'll see the support "Full Support", which is the support containing all actions for all players, and "Support2", the support we obtained by our dominance elimination. If you select "Full Support" from the dropdown, the tree display will return to its original form, and the "Fold" action in Fred's first information set will appear in black in the schematic display.

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:

For this example, select "one Nash equilibrium" which uses the sequence form formulation (the custom algorithm LcpSolve) of Koller, Megiddo, and von Stengel [KolMegSte94] to compute one Nash equilibrium on the extensive form.

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:

The remaining fields in the profile list display the probabilities assigned to each action by the profile. These are labeled in the format (x,y):z, where x gives the player number, y gives the information set number for the player, and z gives the action number at the information set.

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 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.

Notes

[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.