2.6. Computing Nash equilibria

2.6.1. Selecting the method of computing equilibria

The process of computing Nash equilibria in extensive and strategic games is similar. This section focuses on the case of extensive games; the process for strategic games is analogous, except the extensive game-specific features, such as displaying the profiles on the game tree, are not applicable.

Gambit presents options for computing Nash equilibrium in a dialog, as shown in Figure 2-17.

The methods applicable to a particular game depend on three criteria: the number of equilibria to compute, whether the computation is to be done on the extensive or strategic games, and on details of the game, such as whether the game has two players or more, and whether the game is constant-sum.

The first step in finding equilibria is to specify how many equilibria are to be found. Some algorithms for computing equilibria are adapted to finding a single equilibrium, while others attempt to compute the whole equilibrium set. The first drop-down in the dialog specifies how many equilibria to compute. In this drop-down there are options for "as many equilibria as possible" and "all equilibria." For some games, there exist algorithms which will compute many equilibria (relatively) efficiently, but are not guaranteed to find all equilibria.

To simplify this process of choosing the method to compute equilibria in the second drop-down, Gambit provides for any game "recommended" methods for computing one, some, and all Nash equilibria, respectively. These methods are selected based on experience as to the efficiency and reliability of the methods, and should generally work well on most games. For more control over the process, the user can select from the second drop-down in the dialog one of the appropriate methods for computing equilibria. This list only shows the methods which are appropriate for the game, given the selection of how many equilibria to compute. More details on these methods are contained in Section 3.1.

Finally, for extensive games, there is an option of whether to use the extensive or strategic game for computation. In general, computation using the extensive game is preferred, since it is often a significantly more compact representation of the strategic characeteristics of the game than the reduced strategic game is.

For even moderate sized games, computation of equilibrium can be a time-intensive process. Gambit runs all computations in the background, and displays a dialog, like the one in Figure 2-18, showing all equilibria computed so far. The computation can be cancelled at any time by clicking on the cancel icon , which terminates the computation but keeps any equilibria computed.

2.6.2. Viewing computed profiles in the game

After computing equilibria, a panel showing the list of equilibria computed is displayed automatically. The display of this panel can be toggled by selecting View->Profiles, or clicking on the playing card icon on the toolbar. For example, after computing all equilibria in the poker example, the game window looks like Figure 2-19.

This game has a unique equilibrium in which Fred raises after Red with probability one, and raises with probability one-third after Black. Alice, at her only information set, plays meet with probability two-thirds and raise with probability one-third.

This equilibrium is displayed in a table in the profiles panel. If more than one equilibrium is found, this panel lists all equilibria found. Equilibria computed are grouped by separate computational runs; computing equilibria using a different method (or different settings) will add a second list of profiles. The list of profiles displayed is selected using the drop-down at the top left of the profiles panel; in Figure 2-19, it is set to Profiles 1. A brief description of the method used to compute the equilibria is listed across the top of the profiles panel.

The currently selected equilibrium is shown in bold in the profiles listing, and information about this equilibrium is displayed in the extensive game. In the figure, the probabilities of selecting each action are displayed below each branch of the tree. (This is the default Gambit setting; see Section 2.3.7 for configuring the labeling of trees.) Each branch of the tree also shows a black line, the length of which is proportional to the probability with which the action is played.

Clicking on any node in the tree displays additional information about the profile at that node. For example, Figure 2-20 shows the display after clicking on the first (top) node in Alice's information set. The player panel displays information relevant to this node, including the payoff to all players conditional on reaching the node, as well as information about Alice's beliefs at the node.

The computed profiles can also be viewed in the reduced strategic game. Clicking on the strategic game icon changes the view to the reduced strategic form of the game, and shows the equilibrium profiles converted to mixed strategies in the strategic game.