{ "cells": [ { "cell_type": "markdown", "id": "6818538c", "metadata": {}, "source": [ "# 4) Generating starting points for algorithms\n", "\n", "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.\n", "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.\n", "The equilibria found will depend on which starting point is selected.\n", "\n", "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.\n", "\n", "As an example, we consider a three-player game from McKelvey and McLennan (1997), in which each player has two strategies.\n", "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.\n", "\n", "Pure and mixed strategies:\n", "\n", "- **Pure strategy**: A player chooses the action with probability 1 (always picks the same move)\n", "- **Mixed strategy**: A player assigns probabilities to their available actions (some actions may have probability 0)\n", "- **Totally mixed strategy**: Mixed strategy where every available action is chosen with strictly positive probability (no action has probability 0)" ] }, { "cell_type": "code", "execution_count": 1, "id": "493cafb8", "metadata": {}, "outputs": [ { "data": { "text/html": [ "

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

\n", "
Subtable with strategies:
Player 3 Strategy 1
12
19,8,120,0,0
20,0,09,8,2
Subtable with strategies:
Player 3 Strategy 2
12
10,0,03,4,6
23,4,60,0,0
\n" ], "text/plain": [ "Game(title='2x2x2 Example from McKelvey-McLennan, with 9 Nash equilibria, 2 totally mixed')" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import pygambit as gbt\n", "g = gbt.read_nfg(\"../2x2x2.nfg\")\n", "g" ] }, { "cell_type": "markdown", "id": "1e68a5bd", "metadata": {}, "source": [ "We first consider finding Nash equilibria in this game using `liap_solve`.\n", "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." ] }, { "cell_type": "code", "execution_count": 2, "id": "b32adf22", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[[0.5, 0.5],[0.5, 0.5],[0.5, 0.5]\\right]$" ], "text/plain": [ "[[0.5, 0.5], [0.5, 0.5], [0.5, 0.5]]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "centroid_start = g.mixed_strategy_profile()\n", "centroid_start" ] }, { "cell_type": "code", "execution_count": 3, "id": "c0b62502", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[[0.3999999026224355, 0.6000000973775644],[0.49999981670851457, 0.5000001832914854],[0.3333329684317666, 0.6666670315682334]\\right]$" ], "text/plain": [ "[[0.3999999026224355, 0.6000000973775644], [0.49999981670851457, 0.5000001832914854], [0.3333329684317666, 0.6666670315682334]]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.liap_solve(centroid_start).equilibria[0]" ] }, { "cell_type": "markdown", "id": "df507eda", "metadata": {}, "source": [ "As you can see, in this totally mixed strategy equilibrium, no action has probability 0.\n", "\n", "Which equilibrium is found depends on the starting point.\n", "With a different starting point, we can find, for example, one of the pure-strategy equilibria." ] }, { "cell_type": "code", "execution_count": 4, "id": "cf22064e", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[[0.9, 0.1],[0.9, 0.1],[0.9, 0.1]\\right]$" ], "text/plain": [ "[[0.9, 0.1], [0.9, 0.1], [0.9, 0.1]]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "new_start = g.mixed_strategy_profile([[.9, .1], [.9, .1], [.9, .1]])\n", "new_start" ] }, { "cell_type": "code", "execution_count": 5, "id": "08a22505", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[[1.0, 0.0],[0.9999999944750116, 5.524988446860122e-09],[0.9999999991845827, 8.154173380971617e-10]\\right]$" ], "text/plain": [ "[[1.0, 0.0], [0.9999999944750116, 5.524988446860122e-09], [0.9999999991845827, 8.154173380971617e-10]]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.liap_solve(new_start).equilibria[0]" ] }, { "cell_type": "markdown", "id": "3977088f", "metadata": {}, "source": [ "To search for more equilibria, we can instead generate strategy profiles at random." ] }, { "cell_type": "code", "execution_count": 6, "id": "cfbc2714", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[[0.7187961367413075, 0.2812038632586925],[0.1291105793795489, 0.8708894206204512],[0.12367227612277114, 0.876327723877229]\\right]$" ], "text/plain": [ "[[0.7187961367413075, 0.2812038632586925], [0.1291105793795489, 0.8708894206204512], [0.12367227612277114, 0.876327723877229]]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_start = g.random_strategy_profile()\n", "random_start" ] }, { "cell_type": "code", "execution_count": 7, "id": "eb53062a", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[[0.5000003932357804, 0.4999996067642197],[0.3999998501612186, 0.6000001498387814],[0.2500001518113522, 0.7499998481886477]\\right]$" ], "text/plain": [ "[[0.5000003932357804, 0.4999996067642197], [0.3999998501612186, 0.6000001498387814], [0.2500001518113522, 0.7499998481886477]]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.liap_solve(random_start).equilibria[0]" ] }, { "cell_type": "markdown", "id": "185c6abb", "metadata": {}, "source": [ "Note that methods which take starting points do record the starting points used in the result object returned.\n", "However, the random profiles which are generated will differ in different runs of a program.\n", "\n", "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." ] }, { "cell_type": "code", "execution_count": 8, "id": "4293343a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import numpy as np\n", "gen = np.random.default_rng(seed=1234567890)\n", "p1 = g.random_strategy_profile(gen=gen)\n", "gen = np.random.default_rng(seed=1234567890)\n", "p2 = g.random_strategy_profile(gen=gen)\n", "p1 == p2" ] }, { "cell_type": "markdown", "id": "a98e0b66", "metadata": {}, "source": [ "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.\n", "However, in some applications generation of random profiles with probabilities as rational numbers is desired.\n", "\n", "For example, `simpdiv_solve` takes such a starting point, because it operates by successively refining a triangulation over the space of mixed strategy profiles.\n", "`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`.\n", "\n", "These can then be used in conjunction with `simpdiv_solve` to search for equilibria from different starting points." ] }, { "cell_type": "code", "execution_count": 9, "id": "e9716ae0", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[\\frac{1}{2},\\frac{1}{2}\\right],\\left[\\frac{7}{10},\\frac{3}{10}\\right],\\left[0,1\\right]\\right]$" ], "text/plain": [ "[[Rational(1, 2), Rational(1, 2)], [Rational(7, 10), Rational(3, 10)], [Rational(0, 1), Rational(1, 1)]]" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gen = np.random.default_rng(seed=1234567890)\n", "rsp = g.random_strategy_profile(denom=10, gen=gen)\n", "rsp" ] }, { "cell_type": "code", "execution_count": 10, "id": "c153918a", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[1,0\\right],\\left[1,0\\right],\\left[1,0\\right]\\right]$" ], "text/plain": [ "[[Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)]]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.simpdiv_solve(rsp).equilibria[0]" ] }, { "cell_type": "code", "execution_count": 11, "id": "70a57b26", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\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]$" ], "text/plain": [ "[[Rational(1, 10), Rational(9, 10)], [Rational(3, 5), Rational(2, 5)], [Rational(3, 5), Rational(2, 5)]]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rsp1 = g.random_strategy_profile(denom=10, gen=gen)\n", "rsp1" ] }, { "cell_type": "code", "execution_count": 12, "id": "11995836", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[0,1\\right],\\left[0,1\\right],\\left[1,0\\right]\\right]$" ], "text/plain": [ "[[Rational(0, 1), Rational(1, 1)], [Rational(0, 1), Rational(1, 1)], [Rational(1, 1), Rational(0, 1)]]" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.simpdiv_solve(rsp1).equilibria[0]" ] }, { "cell_type": "code", "execution_count": 13, "id": "2791ffe2", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[\\frac{7}{10},\\frac{3}{10}\\right],\\left[\\frac{4}{5},\\frac{1}{5}\\right],\\left[0,1\\right]\\right]$" ], "text/plain": [ "[[Rational(7, 10), Rational(3, 10)], [Rational(4, 5), Rational(1, 5)], [Rational(0, 1), Rational(1, 1)]]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "rsp2 = g.random_strategy_profile(denom=10, gen=gen)\n", "rsp2" ] }, { "cell_type": "code", "execution_count": 14, "id": "2ab2caa4", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[1,0\\right],\\left[1,0\\right],\\left[1,0\\right]\\right]$" ], "text/plain": [ "[[Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)], [Rational(1, 1), Rational(0, 1)]]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.simpdiv_solve(rsp2).equilibria[0]" ] } ], "metadata": { "kernelspec": { "display_name": "gambitvenv313", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.5" } }, "nbformat": 4, "nbformat_minor": 5 }