4) Generating starting points for algorithms

In the previous tutorial, we demonstrated how to calculate the Nash equilibria of a game set up using Gambit and interpret the MixedStrategyProfile or MixedBehaviorProfile objects returned by the solver. In this tutorial, we will demonstrate how to use a MixedStrategyProfile or MixedBehaviorProfile as an initial condition, a starting point, for some methods of computing Nash equilibria. The equilibria found will depend on which starting point is selected.

To facilitate generating starting points, Gambit’s Game class provides the methods random_strategy_profile and random_behavior_profile, to generate profiles which are drawn from the uniform distribution on the product of simplices. In other words, the profiles are sampled from a uniform distribution so that each possible mixed strategy profile (or mixed behaviour profile) is equally likely to be selected.

As an example, we consider a three-player game from McKelvey and McLennan (1997), in which each player has two strategies. This game has nine equilibria in total, and in particular has two totally mixed Nash equilibria, which is the maximum possible number of regular totally mixed equilbria in games of this size.

Pure and mixed strategies:

• Pure strategy: A player chooses the action with probability 1 (always picks the same move)

• Mixed strategy: A player assigns probabilities to their available actions (some actions may have probability 0)

• Totally mixed strategy: Mixed strategy where every available action is chosen with strictly positive probability (no action has probability 0)

import pygambit as gbt
g = gbt.read_nfg("../2x2x2.nfg")
g

2x2x2 Example from McKelvey-McLennan, with 9 Nash equilibria, 2 totally mixed

Subtable with strategies:Player 3 Strategy 1

	1	2
1	9,8,12	0,0,0
2	0,0,0	9,8,2

Subtable with strategies:Player 3 Strategy 2

	1	2
1	0,0,0	3,4,6
2	3,4,6	0,0,0

We first consider finding Nash equilibria in this game using liap_solve. If we run this method starting from the centroid (uniform randomization across all strategies for each player), liap_solve finds one of the totally-mixed equilibria. Without providing a list to Game.mixed_strategy_profile, the method will return the centroid mixed strategy profile.

centroid_start = g.mixed_strategy_profile()
centroid_start

$\left[[0.5, 0.5],[0.5, 0.5],[0.5, 0.5]\right]$

gbt.nash.liap_solve(centroid_start).equilibria[0]

$\left[[0.3999999026224355, 0.6000000973775644],[0.49999981670851457, 0.5000001832914854],[0.3333329684317666, 0.6666670315682334]\right]$

As you can see, in this totally mixed strategy equilibrium, no action has probability 0.

Which equilibrium is found depends on the starting point. With a different starting point, we can find, for example, one of the pure-strategy equilibria.

new_start = g.mixed_strategy_profile([[.9, .1], [.9, .1], [.9, .1]])
new_start

$\left[[0.9, 0.1],[0.9, 0.1],[0.9, 0.1]\right]$

gbt.nash.liap_solve(new_start).equilibria[0]

$\left[[1.0, 0.0],[0.9999999944750116, 5.524988446860122e-09],[0.9999999991845827, 8.154173380971617e-10]\right]$

To search for more equilibria, we can instead generate strategy profiles at random.

random_start = g.random_strategy_profile()
random_start

$\left[[0.7187961367413075, 0.2812038632586925],[0.1291105793795489, 0.8708894206204512],[0.12367227612277114, 0.876327723877229]\right]$

gbt.nash.liap_solve(random_start).equilibria[0]

$\left[[0.5000003932357804, 0.4999996067642197],[0.3999998501612186, 0.6000001498387814],[0.2500001518113522, 0.7499998481886477]\right]$

Note that methods which take starting points do record the starting points used in the result object returned. However, the random profiles which are generated will differ in different runs of a program.

To support making the generation of random strategy profiles reproducible, and for finer-grained control of the generation of these profiles if desired, Game.random_strategy_profile and Game.random_behavior_profile optionally take a numpy.random.Generator object, which is used as the source of randomness for creating the profile.

import numpy as np
gen = np.random.default_rng(seed=1234567890)
p1 = g.random_strategy_profile(gen=gen)
gen = np.random.default_rng(seed=1234567890)
p2 = g.random_strategy_profile(gen=gen)
p1 == p2

True

When creating profiles in which probabilities are represented as floating-point numbers, Game.random_strategy_profile and Game.random_behavior_profile internally use the Dirichlet distribution for each simplex to generate correctly uniform sampling over probabilities. However, in some applications generation of random profiles with probabilities as rational numbers is desired.

For example, simpdiv_solve takes such a starting point, because it operates by successively refining a triangulation over the space of mixed strategy profiles. Game.random_strategy_profile and Game.random_behavior_profile both take an optional parameter denom which, if specified, generates a profile in which probabilities are generated uniformly from the grid in each simplex in which all probabilities have denominator denom.

These can then be used in conjunction with simpdiv_solve to search for equilibria from different starting points.

gen = np.random.default_rng(seed=1234567890)
rsp = g.random_strategy_profile(denom=10, gen=gen)
rsp

$\left[\left[\frac{1}{2},\frac{1}{2}\right],\left[\frac{7}{10},\frac{3}{10}\right],\left[0,1\right]\right]$

gbt.nash.simpdiv_solve(rsp).equilibria[0]

$\left[\left[1,0\right],\left[1,0\right],\left[1,0\right]\right]$

rsp1 = g.random_strategy_profile(denom=10, gen=gen)
rsp1

$\left[\left[\frac{1}{10},\frac{9}{10}\right],\left[\frac{3}{5},\frac{2}{5}\right],\left[\frac{3}{5},\frac{2}{5}\right]\right]$

gbt.nash.simpdiv_solve(rsp1).equilibria[0]

$\left[\left[0,1\right],\left[0,1\right],\left[1,0\right]\right]$

rsp2 = g.random_strategy_profile(denom=10, gen=gen)
rsp2

$\left[\left[\frac{7}{10},\frac{3}{10}\right],\left[\frac{4}{5},\frac{1}{5}\right],\left[0,1\right]\right]$

gbt.nash.simpdiv_solve(rsp2).equilibria[0]

$\left[\left[1,0\right],\left[1,0\right],\left[1,0\right]\right]$