{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "

Computing equilibria in games with three or more players

\n", "Theodore L. Turocy
\n", "University of East Anglia\n", "

\n", "

EC'16 Workshop\n", "24 July 2016

" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import gambit" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Three player games\n", "\n", "The situation with games with three (or more) players is a bit more complex. There are several methods which can be used to compute equilibria for games with three or more players, but all have some limitations, whether theoretical, practical, or both.\n", "\n", "We will use a three-player game as our example, in which each player has exactly two strategies each. This game has nine Nash equilibria, which is the maximum number of isolated equilibria a game of this dimension can have. It is also well-behaved in that the game continues to have nine equilibria even if payoffs are perturbed slightly." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "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": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = gambit.Game.read_game(\"2x2x2.nfg\")\n", "import IPython.display; IPython.display.HTML(g.write('html'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For this example, I will run the various methods using the command-line tools via the shell. Several of these tools optionally print out some useful status information when run on the command-line, which is not (yet) logged and returned by the Python calls.\n", "\n", "First up is *simplicial subdivision*, `gambit-simpdiv`. This operates essentially like the proof of the Brouwer fixed point theorem: It divides up the space of mixed strategies into a \"grid\" of simplices, and follows a path along that grid. The grid is then refined, and the process repeated.\n", "\n", "Each run of the algorithm requires a starting point in the space of mixed strategy profiles. Which equilibrium you find depends on your starting point, and there's no guarantee the equilibrium you find bears any clear relationship to your starting point (it could in principle be arbitrarily far away in the space of mixed strategy profiles)." ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using simplicial subdivision\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\n", "This is free software, distributed under the GNU GPL\n", "\n", "NE,1,0,1,0,1,0\n" ] } ], "source": [ "!gambit-simpdiv 2x2x2.nfg" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using simplicial subdivision\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "Usage: gambit-simpdiv [OPTIONS] [file]\r\n", "If file is not specified, attempts to read game from standard input.\r\n", "With no options, computes one approximate Nash equilibrium.\r\n", "\r\n", "Options:\r\n", " -g MULT granularity of grid refinement at each step (default is 2)\r\n", " -h, --help print this help message\r\n", " -r DENOM generate random starting points with denominator DENOM\r\n", " -n COUNT number of starting points to generate (requires -r)\r\n", " -s FILE file containing starting points\r\n", " -q quiet mode (suppresses banner)\r\n", " -V, --verbose verbose mode (shows intermediate output)\r\n", " -v, --version print version information\r\n", " (default is to only show equilibria)\r\n" ] } ], "source": [ "!gambit-simpdiv -h" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using simplicial subdivision\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "start,5/16,11/16,7/8,1/8,11/16,5/16\r\n", "1/32,1,0,1,0,1,0\r\n", "NE,1,0,1,0,1,0\r\n", "start,3/4,1/4,11/16,5/16,3/8,5/8\r\n", "1/32,1,0,1,0,1,0\r\n", "NE,1,0,1,0,1,0\r\n", "start,1/4,3/4,1,0,15/16,1/16\r\n", "1/32,1,0,1,0,1,0\r\n", "NE,1,0,1,0,1,0\r\n", "start,9/16,7/16,15/16,1/16,1/4,3/4\r\n", "1/32,1,0,1,0,1,0\r\n", "NE,1,0,1,0,1,0\r\n", "start,1,0,3/16,13/16,1,0\r\n", "1/32,1,0,1,0,1,0\r\n", "NE,1,0,1,0,1,0\r\n" ] } ], "source": [ "!gambit-simpdiv -n 5 -r 16 -V 2x2x2.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The next two methods were proposed by Govindan and Wilson, and this implementation is based on the Gametracer package by Blum and Shelton. The *global Newton method* `gambit-gnm` uses the idea of the structure theorem (as we encountered in Bagwell's example). It picks a perturbation vector of the payoffs of the game, goes far out enough in that \"direction\" in payoff space such that the game has a unique equilibrium, and then traces backwards towards the original game. As the path of equilibria is followed, it may cross the original game more than once, so it is possible that this method will find more than one equilibrium - but it will not necessarily find all of them, and which equilibria are found depends on the choice of the perturbation vector." ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using a global Newton method\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\n", "This is free software, distributed under the GNU GPL\n", "\n", "NE,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\n", "NE,0.500000,0.500000,0.400000,0.600000,0.250000,0.750000\n", "NE,0.400000,0.600000,0.500000,0.500000,0.333333,0.666667\n", "NE,0.333333,0.666667,1.000000,0.000000,0.250000,0.750000\n", "NE,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000\n", "NE,0.000000,1.000000,0.250000,0.750000,0.333333,0.666667\n", "NE,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000\n" ] } ], "source": [ "!gambit-gnm 2x2x2.nfg" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using a global Newton method\r\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "Usage: gambit-gnm [OPTIONS] [file]\r\n", "If file is not specified, attempts to read game from standard input.\r\n", "Options:\r\n", " -d DECIMALS show equilibria as floating point with DECIMALS digits\r\n", " -h, --help print this help message\r\n", " -n COUNT number of perturbation vectors to generate\r\n", " -s FILE file containing perturbation vectors\r\n", " -q quiet mode (suppresses banner)\r\n", " -V, --verbose verbose mode (shows intermediate output)\r\n", " -v, --version print version information\r\n", " (default is to only show equilibria)\r\n" ] } ], "source": [ "!gambit-gnm -h" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can use the `-V` switch to understand a bit more how the equilibria are found. Each intermediate step shows, in the first column, the homotopy parameter (how much the perturbation vector is multiplied by). Each entry shows a \"turning point\" in the path." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using a global Newton method\r\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "pert,0.611434,0.105483,0.189587,0.527330,0.210106,0.506811\r\n", "start,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\r\n", "-0.494119,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\r\n", "-0.494119,0.750328,0.249672,0.000000,1.000000,0.000000,1.000000\r\n", "-0.236365,0.619746,0.380254,0.260821,0.739179,0.000000,1.000000\r\n", "-1.1317,0.109407,0.890593,1.000000,0.000000,0.822777,0.177223\r\n", "0.122597,0.357583,0.642417,1.000000,0.000000,0.187972,0.812028\r\n", "0.158741,0.419582,0.580418,0.660623,0.339377,0.000000,1.000000\r\n", "0.494119,0.249672,0.750328,1.000000,0.000000,0.000000,1.000000\r\n", "0.494119,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000\r\n", "-1.68518,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000\r\n", "-1.68518,0.000000,1.000000,1.000000,0.000000,0.902490,0.097510\r\n", "0.0671458,0.000000,1.000000,0.220116,0.779884,0.310655,0.689345\r\n", "0.0756722,0.216326,0.783674,0.000000,1.000000,0.288286,0.711714\r\n", "0.561726,0.000000,1.000000,0.000000,1.000000,0.534206,0.465794\r\n", "0.561726,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000\r\n", "-1.97389,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000\r\n", "-1.97389,0.000000,1.000000,1.000000,0.000000,1.000000,0.000000\r\n", "gnm(): return since the path crosses no more support boundaries and no next eqlm\r\n", "NE,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\r\n", "NE,0.500000,0.500000,0.400000,0.600000,0.250000,0.750000\r\n", "NE,0.400000,0.600000,0.500000,0.500000,0.333333,0.666667\r\n", "NE,0.333333,0.666667,1.000000,0.000000,0.250000,0.750000\r\n", "NE,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000\r\n", "NE,0.000000,1.000000,0.250000,0.750000,0.333333,0.666667\r\n", "NE,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000\r\n" ] } ], "source": [ "!gambit-gnm -V 2x2x2.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Closely related (and also proposed by Govindan and Wilson and implemented in Gametracer by Blum and Shelton) is *iterated polymatrix approximation*, which speeds up the homotopy calculation by approximating the game as a *polymatrix* game (i.e., one where each player, in effect, plays a two-player game against each other player)." ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using iterated polymatrix approximation\r\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "Usage: gambit-ipa [OPTIONS] [file]\r\n", "If file is not specified, attempts to read game from standard input.\r\n", "Options:\r\n", " -d DECIMALS show equilibria as floating point with DECIMALS digits\r\n", " -h, --help print this help message\r\n", " -q quiet mode (suppresses banner)\r\n", " -V, --verbose verbose mode (shows intermediate output)\r\n", " -v, --version print version information\r\n" ] } ], "source": [ "!gambit-ipa -h" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using iterated polymatrix approximation\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\n", "This is free software, distributed under the GNU GPL\n", "\n", "NE,1.000000,0.000000,1.000000,0.000000,1.000000,0.000000\n" ] } ], "source": [ "!gambit-ipa 2x2x2.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Another path-following approach uses *quantal response equilibria*, as proposed by McKelvey and Palfrey (1995) and implemented by Turocy (2005). Instead of perturbing the payoffs of the game, QRE perturbs the accuracy of the best response. Turocy (2005) showed that using the logit form of the accuracy of the best response has nice computational properties. The method starts from uniform randomisation across all strategies, and in the limit computes a Nash equilibrium. As instrumented here, this computes one Nash equilibrium (which McKelvey-Palfrey called the \"logit solution\"), but there do exist other branches of the QRE correspondence which can be used to compute equilibria (if you can find them, which is the tricky part...)\n", "\n", "This is at present the best and most reliable way to compute one equilibrium of a game with three or more players. This is not a theoretical claim; this is simply because I invested a lot of time implementing it carefully for the 2005 GEB paper (and subsequent use in experimental game theory), so it has received rather more love and attention than other methods to date." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute a branch of the logit equilibrium correspondence\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "0.000000,0.5,0.5,0.5,0.5,0.5,0.5\r\n", "0.028284,0.5,0.5,0.5,0.5,0.503535,0.496465\r\n", "0.059397,0.5,0.5,0.5,0.5,0.507424,0.492576\r\n", "0.093620,0.5,0.5,0.5,0.5,0.5117,0.4883\r\n", "0.131264,0.5,0.5,0.5,0.5,0.516402,0.483598\r\n", "0.172672,0.5,0.5,0.5,0.5,0.521571,0.478429\r\n", "0.218218,0.5,0.5,0.5,0.5,0.52725,0.47275\r\n", "0.268314,0.5,0.5,0.5,0.5,0.533489,0.466511\r\n", "0.323415,0.5,0.5,0.5,0.5,0.540339,0.459661\r\n", "0.384018,0.5,0.5,0.5,0.5,0.547855,0.452145\r\n", "0.450670,0.5,0.5,0.5,0.5,0.556097,0.443903\r\n", "0.523972,0.5,0.5,0.5,0.5,0.565124,0.434876\r\n", "0.604581,0.5,0.5,0.5,0.5,0.575002,0.424998\r\n", "0.693220,0.5,0.5,0.5,0.5,0.585795,0.414205\r\n", "0.790681,0.5,0.5,0.5,0.5,0.597568,0.402432\r\n", "0.897830,0.5,0.5,0.5,0.5,0.610381,0.389619\r\n", "1.015617,0.5,0.5,0.5,0.5,0.624293,0.375707\r\n", "1.145079,0.5,0.5,0.5,0.5,0.639349,0.360651\r\n", "1.287348,0.5,0.5,0.5,0.5,0.655584,0.344416\r\n", "1.443663,0.5,0.5,0.5,0.5,0.67301,0.32699\r\n", "1.615373,0.5,0.5,0.5,0.5,0.691616,0.308384\r\n", "1.803949,0.5,0.5,0.5,0.5,0.711355,0.288645\r\n", "2.010994,0.5,0.5,0.5,0.5,0.732138,0.267862\r\n", "2.238253,0.5,0.5,0.5,0.5,0.753827,0.246173\r\n", "2.487633,0.5,0.5,0.5,0.5,0.776228,0.223772\r\n", "2.761212,0.5,0.5,0.5,0.5,0.799088,0.200912\r\n", "3.061267,0.5,0.5,0.5,0.5,0.822099,0.177901\r\n", "3.390293,0.5,0.5,0.5,0.5,0.8449,0.1551\r\n", "3.751038,0.5,0.5,0.5,0.5,0.867096,0.132904\r\n", "4.146537,0.5,0.5,0.5,0.5,0.888278,0.111722\r\n", "4.580150,0.5,0.5,0.5,0.5,0.908052,0.0919483\r\n", "5.055609,0.5,0.5,0.5,0.5,0.926068,0.0739318\r\n", "5.577064,0.5,0.5,0.5,0.5,0.942053,0.0579471\r\n", "6.149130,0.5,0.5,0.5,0.5,0.955831,0.0441687\r\n", "6.776937,0.5,0.5,0.5,0.5,0.967342,0.0326578\r\n", "7.466175,0.5,0.5,0.5,0.5,0.97664,0.0233601\r\n", "8.223140,0.5,0.5,0.5,0.5,0.983882,0.016118\r\n", "9.054784,0.5,0.5,0.5,0.5,0.989307,0.0106932\r\n", "9.968763,0.5,0.5,0.5,0.5,0.993203,0.00679749\r\n", "10.973496,0.5,0.5,0.5,0.5,0.995876,0.00412421\r\n", "12.078225,0.5,0.5,0.5,0.5,0.997622,0.00237801\r\n", "13.293090,0.5,0.5,0.5,0.5,0.998703,0.00129682\r\n", "14.629220,0.5,0.5,0.5,0.5,0.999335,0.000665298\r\n", "16.098822,0.5,0.5,0.5,0.5,0.999681,0.000319188\r\n", "17.715304,0.5,0.5,0.5,0.5,0.999858,0.000142269\r\n", "19.493389,0.5,0.5,0.5,0.5,0.999942,5.84843e-05\r\n", "21.449260,0.5,0.5,0.5,0.5,0.999978,2.1996e-05\r\n", "23.600709,0.5,0.5,0.5,0.5,0.999992,7.50184e-06\r\n", "25.967298,0.5,0.5,0.5,0.5,0.999998,2.29759e-06\r\n", "28.570544,0.5,0.5,0.5,0.5,0.999999,6.25151e-07\r\n", "31.434114,0.5,0.5,0.5,0.5,1,1.49337e-07\r\n", "34.584041,0.5,0.5,0.5,0.5,1,3.09151e-08\r\n", "38.048961,0.5,0.5,0.5,0.5,1,5.4673e-09\r\n", "41.860373,0.5,0.5,0.5,0.5,1,8.13084e-10\r\n", "46.052926,0.5,0.5,0.5,0.5,1,9.99388e-11\r\n", "50.664734,0.5,0.5,0.5,0.5,1,9.96077e-12\r\n", "55.737724,0.5,0.5,0.5,0.5,1,7.88328e-13\r\n", "61.318012,0.5,0.5,0.5,0.5,1,4.84131e-14\r\n", "67.456328,0.5,0.5,0.5,0.5,1,2.24928e-15\r\n", "74.208477,0.5,0.5,0.5,0.5,1,7.68836e-17\r\n", "81.635840,0.5,0.5,0.5,0.5,1,1.87501e-18\r\n", "89.805940,0.5,0.5,0.5,0.5,1,3.15419e-20\r\n", "98.793050,0.5,0.5,0.5,0.5,1,3.52665e-22\r\n", "108.678870,0.5,0.5,0.5,0.5,1,2.51584e-24\r\n", "119.553273,0.5,0.5,0.5,0.5,1,1.0948e-26\r\n", "131.515116,0.5,0.5,0.5,0.5,1,2.76602e-29\r\n", "144.673144,0.5,0.5,0.5,0.5,1,3.84261e-32\r\n", "159.146974,0.5,0.5,0.5,0.5,1,2.76486e-35\r\n", "175.068187,0.5,0.5,0.5,0.5,1,9.64776e-39\r\n", "192.581521,0.5,0.5,0.5,0.5,1,1.51864e-42\r\n", "211.846189,0.5,0.5,0.5,0.5,1,9.95829e-47\r\n", "233.037323,0.5,0.5,0.5,0.5,1,2.49223e-51\r\n", "256.347571,0.5,0.5,0.5,0.5,1,2.16188e-56\r\n", "281.988844,0.5,0.5,0.5,0.5,1,5.84656e-62\r\n", "310.194244,0.5,0.5,0.5,0.5,1,4.38708e-68\r\n", "341.220184,0.5,0.5,0.5,0.5,1,8.03486e-75\r\n", "375.348719,0.5,0.5,0.5,0.5,1,3.11933e-82\r\n", "412.890106,0.5,0.5,0.5,0.5,1,2.19813e-90\r\n", "454.185632,0.5,0.5,0.5,0.5,1,2.37052e-99\r\n", "499.610711,0.5,0.5,0.5,0.5,1,3.24274e-109\r\n", "549.578298,0.5,0.5,0.5,0.5,1,4.57708e-120\r\n", "604.542644,0.5,0.5,0.5,0.5,1,5.31169e-132\r\n", "665.003424,0.5,0.5,0.5,0.5,1,3.94767e-145\r\n", "731.510282,0.5,0.5,0.5,0.5,1,1.42745e-159\r\n", "804.667826,0.5,0.5,0.5,0.5,1,1.8561e-175\r\n", "885.141124,0.5,0.5,0.5,0.5,1,6.22368e-193\r\n", "973.661752,0.5,0.5,0.5,0.5,1,3.73282e-212\r\n", "1071.034443,0.5,0.5,0.5,0.5,1,2.67809e-233\r\n", "1178.144403,0.5,0.5,0.5,0.5,1,1.47636e-256\r\n", "1295.965359,0.5,0.5,0.5,0.5,1,3.84324e-282\r\n", "1425.568410,0.5,0.5,0.5,0.5,1,2.76537e-310\r\n", "1568.131767,0.5,0.5,0.5,0.5,1,0\r\n", "1724.951459,0.5,0.5,0.5,0.5,1,0\r\n", "1897.453121,0.5,0.5,0.5,0.5,1,0\r\n", "2087.204949,0.5,0.5,0.5,0.5,1,0\r\n", "2295.931959,0.5,0.5,0.5,0.5,1,0\r\n", "2525.531671,0.5,0.5,0.5,0.5,1,0\r\n", "2778.091354,0.5,0.5,0.5,0.5,1,0\r\n", "3055.907005,0.5,0.5,0.5,0.5,1,0\r\n", "3361.504221,0.5,0.5,0.5,0.5,1,0\r\n", "3697.661159,0.5,0.5,0.5,0.5,1,0\r\n", "4067.433790,0.5,0.5,0.5,0.5,1,0\r\n", "4474.183685,0.5,0.5,0.5,0.5,1,0\r\n", "4921.608569,0.5,0.5,0.5,0.5,1,0\r\n", "5413.775942,0.5,0.5,0.5,0.5,1,0\r\n", "5955.160052,0.5,0.5,0.5,0.5,1,0\r\n", "6550.682573,0.5,0.5,0.5,0.5,1,0\r\n", "7205.757345,0.5,0.5,0.5,0.5,1,0\r\n", "7926.339596,0.5,0.5,0.5,0.5,1,0\r\n", "8718.980071,0.5,0.5,0.5,0.5,1,0\r\n", "9590.884594,0.5,0.5,0.5,0.5,1,0\r\n", "10549.979569,0.5,0.5,0.5,0.5,1,0\r\n", "11604.984041,0.5,0.5,0.5,0.5,1,0\r\n", "12765.488961,0.5,0.5,0.5,0.5,1,0\r\n", "14042.044373,0.5,0.5,0.5,0.5,1,0\r\n", "15446.255326,0.5,0.5,0.5,0.5,1,0\r\n", "16990.887374,0.5,0.5,0.5,0.5,1,0\r\n", "18689.982627,0.5,0.5,0.5,0.5,1,0\r\n", "20558.987406,0.5,0.5,0.5,0.5,1,0\r\n", "22614.892662,0.5,0.5,0.5,0.5,1,0\r\n", "24876.388444,0.5,0.5,0.5,0.5,1,0\r\n", "27364.033804,0.5,0.5,0.5,0.5,1,0\r\n", "30100.443700,0.5,0.5,0.5,0.5,1,0\r\n", "33110.494586,0.5,0.5,0.5,0.5,1,0\r\n", "36421.550560,0.5,0.5,0.5,0.5,1,0\r\n", "40063.712132,0.5,0.5,0.5,0.5,1,0\r\n", "44070.089861,0.5,0.5,0.5,0.5,1,0\r\n", "48477.105363,0.5,0.5,0.5,0.5,1,0\r\n", "53324.822414,0.5,0.5,0.5,0.5,1,0\r\n", "58657.311172,0.5,0.5,0.5,0.5,1,0\r\n", "64523.048804,0.5,0.5,0.5,0.5,1,0\r\n", "70975.360201,0.5,0.5,0.5,0.5,1,0\r\n", "78072.902736,0.5,0.5,0.5,0.5,1,0\r\n", "85880.199526,0.5,0.5,0.5,0.5,1,0\r\n", "94468.225994,0.5,0.5,0.5,0.5,1,0\r\n", "103915.055109,0.5,0.5,0.5,0.5,1,0\r\n", "114306.567136,0.5,0.5,0.5,0.5,1,0\r\n", "125737.230365,0.5,0.5,0.5,0.5,1,0\r\n", "138310.959917,0.5,0.5,0.5,0.5,1,0\r\n", "152142.062424,0.5,0.5,0.5,0.5,1,0\r\n", "167356.275182,0.5,0.5,0.5,0.5,1,0\r\n", "184091.909216,0.5,0.5,0.5,0.5,1,0\r\n", "202501.106654,0.5,0.5,0.5,0.5,1,0\r\n", "222751.223835,0.5,0.5,0.5,0.5,1,0\r\n", "245026.352734,0.5,0.5,0.5,0.5,1,0\r\n", "269528.994523,0.5,0.5,0.5,0.5,1,0\r\n", "296481.900491,0.5,0.5,0.5,0.5,1,0\r\n", "326130.097056,0.5,0.5,0.5,0.5,1,0\r\n", "358743.113277,0.5,0.5,0.5,0.5,1,0\r\n", "394617.431121,0.5,0.5,0.5,0.5,1,0\r\n", "434079.180748,0.5,0.5,0.5,0.5,1,0\r\n", "477487.105339,0.5,0.5,0.5,0.5,1,0\r\n", "525235.822388,0.5,0.5,0.5,0.5,1,0\r\n", "577759.411143,0.5,0.5,0.5,0.5,1,0\r\n", "635535.358773,0.5,0.5,0.5,0.5,1,0\r\n", "699088.901166,0.5,0.5,0.5,0.5,1,0\r\n", "768997.797798,0.5,0.5,0.5,0.5,1,0\r\n", "845897.584094,0.5,0.5,0.5,0.5,1,0\r\n", "930487.349019,0.5,0.5,0.5,0.5,1,0\r\n", "1023536.090436,0.5,0.5,0.5,0.5,1,0\r\n" ] } ], "source": [ "!gambit-logit 2x2x2.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "All methods so far compute one, or possibly many, equilibria, but none are guaranteed to find all equilibria in all games. There is exactly one such method, which operates by enumerating all of the subsets of supports in the game, and, for each of them, asks whether there is a totally mixed equilibrium on that support. The latter question amounts to a collection of polynomial equations. The number of possible supports grows quickly (but searching them is embarrassingly parallelizable!), but finding all solutions to a system of polynomial equations does take a bit of work in practice.\n", "\n", "In Gambit, we have one implementation of this, done in the mid-1990s by Andrew McLennan, which currently ships as `gambit-enumpoly`. It uses the Pelican library by Birk Huber, which dates from the early 1990s, which I believe was translated from FORTRAN (and which is the bane of my existence in terms of maintenance with each new compiler version...)\n", "\n", "If you give the `-V` switch, you can see each candidate support reported as it is inspected. In the case of this example, it works great on most of the supports, but has a problem with the full support (on which there are two totally mixed equilibria)." ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria by solving polynomial systems\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\n", "Heuristic search implementation Copyright (C) 2006, Litao Wei\n", "This is free software, distributed under the GNU GPL\n", "\n", "candidate,10,10,10\n", "NE,1.000000,0.000000,1.000000,0.000000,1.000000,0.000000\n", "candidate,10,01,01\n", "NE,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\n", "candidate,01,01,10\n", "NE,0.000000,1.000000,0.000000,1.000000,1.000000,0.000000\n", "candidate,01,10,01\n", "NE,0.000000,1.000000,1.000000,0.000000,0.000000,1.000000\n", "candidate,10,11,11\n", "candidate,01,11,11\n", "NE,0.000000,1.000000,0.250000,0.750000,0.333333,0.666667\n", "candidate,11,11,10\n", "NE,0.500000,0.500000,0.500000,0.500000,1.000000,0.000000\n", "candidate,11,01,11\n", "candidate,11,10,11\n", "NE,0.333333,0.666667,1.000000,0.000000,0.250000,0.750000\n", "candidate,11,11,01\n", "candidate,11,11,11\n", "^C\n" ] } ], "source": [ "!gambit-enumpoly -V 2x2x2.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### A game with an equilibrium set with positive dimension\n", "\n", "This example comes from Nau et al (IJGT 2004) *On the geometry of Nash equilibria and correlated equilibria*. It is a very useful example case for computing Nash equilibria, in that there is an equilibrium component which is one-dimensional, and also spans three different supports. If you think of the set of mixed strategy profiles of this 2x2x2 game as a cube, this component starts along one edge (corresponding to incompletely-mixed equilibria), then curves across through the centre of the cube until it reaches the edge catercorner from the first, then continues along that edge (corresponding to more incompletely-mixed equilibria)." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "

2x2x2 example with 3 pure, 2 incompletely mixed, and a continuum of completely mixed NE

\n", "
Subtable with strategies:
Player 3 Strategy 1
12
10,0,20,3,0
23,0,00,0,0
Subtable with strategies:
Player 3 Strategy 2
12
11,1,00,0,0
20,0,00,0,3
\n" ], "text/plain": [ "" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = gambit.Game.read_game(\"2x2x2-nau.nfg\")\n", "import IPython.display; IPython.display.HTML(g.write('html'))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "None of the existing implementations do very well at giving the naive user much insight into the equilibrium structure." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using a global Newton method\r\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "pert,0.611434,0.105483,0.189587,0.527330,0.210106,0.506811\r\n", "start,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\r\n", "0.496714,1.000000,0.000000,0.000000,1.000000,0.000000,1.000000\r\n", "0.496714,1.000000,0.000000,0.439246,0.560754,0.000000,1.000000\r\n", "2.49584e-05,1.000000,0.000000,0.000022,0.999978,0.249987,0.750013\r\n", "gnm(): return due to too much error. error is 0.0108534\r\n" ] } ], "source": [ "!gambit-gnm -V 2x2x2-nau.nfg" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria using iterated polymatrix approximation\r\n", "Gametracer version 0.2, Copyright (C) 2002, Ben Blum and Christian Shelton\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "NE,1.000000,0.000000,1.000000,0.000000,1.000000,0.000000\r\n" ] } ], "source": [ "!gambit-ipa 2x2x2-nau.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`gambit-logit` does successfully pick out one of the totally-mixed equilibria at least, but doesn't (on its own) warn you about the one-dimensional component.\n", "\n", "**Interesting observation**: This is the equilibrium in that component that has the highest entropy. I have a conjecture that any limiting QRE is either a local max or local min of entropy over the set of Nash equilibria. Anyone interested in having a go at trying to prove this, chat to me! I have no idea what use such a result would be however... ;)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute a branch of the logit equilibrium correspondence\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "0.000000,0.5,0.5,0.5,0.5,0.5,0.5\r\n", "0.026524,0.49673,0.50327,0.49673,0.50327,0.498234,0.501766\r\n", "0.055756,0.493234,0.506766,0.493234,0.506766,0.496043,0.503957\r\n", "0.087975,0.489522,0.510478,0.489522,0.510478,0.493347,0.506653\r\n", "0.123487,0.485609,0.514391,0.485609,0.514391,0.490056,0.509944\r\n", "0.162631,0.481522,0.518478,0.481522,0.518478,0.486069,0.513931\r\n", "0.205779,0.477299,0.522701,0.477299,0.522701,0.481282,0.518718\r\n", "0.253343,0.472994,0.527006,0.472994,0.527006,0.475587,0.524413\r\n", "0.305776,0.468673,0.531327,0.468673,0.531327,0.468881,0.531119\r\n", "0.363588,0.46442,0.53558,0.46442,0.53558,0.461069,0.538931\r\n", "0.427345,0.46033,0.53967,0.46033,0.53967,0.45208,0.54792\r\n", "0.497687,0.456516,0.543484,0.456516,0.543484,0.441872,0.558128\r\n", "0.575339,0.453098,0.546902,0.453098,0.546902,0.430448,0.569552\r\n", "0.661126,0.450202,0.549798,0.450202,0.549798,0.417867,0.582133\r\n", "0.755990,0.447952,0.552048,0.447952,0.552048,0.404251,0.595749\r\n", "0.861001,0.446468,0.553532,0.446468,0.553532,0.389795,0.610205\r\n", "0.977371,0.445847,0.554153,0.445847,0.554153,0.374761,0.625239\r\n", "1.106452,0.446166,0.553834,0.446166,0.553834,0.359475,0.640525\r\n", "1.249739,0.447461,0.552539,0.447461,0.552539,0.344301,0.655699\r\n", "1.408844,0.449725,0.550275,0.449725,0.550275,0.329617,0.670383\r\n", "1.585485,0.452905,0.547095,0.452905,0.547095,0.315781,0.684219\r\n", "1.781461,0.456895,0.543105,0.456895,0.543105,0.30309,0.69691\r\n", "1.998653,0.461552,0.538448,0.461552,0.538448,0.291762,0.708238\r\n", "2.239037,0.466703,0.533297,0.466703,0.533297,0.281911,0.718089\r\n", "2.504725,0.47217,0.52783,0.47217,0.52783,0.273556,0.726444\r\n", "2.798012,0.477778,0.522222,0.477778,0.522222,0.266634,0.733366\r\n", "3.121431,0.483377,0.516623,0.483377,0.516623,0.261022,0.738978\r\n", "3.477796,0.488842,0.511158,0.488842,0.511158,0.256564,0.743436\r\n", "3.870241,0.494084,0.505916,0.494084,0.505916,0.253094,0.746906\r\n", "4.302252,0.49904,0.50096,0.49904,0.50096,0.250447,0.749553\r\n", "4.777696,0.503672,0.496328,0.503672,0.496328,0.248474,0.751526\r\n", "5.300850,0.507965,0.492035,0.507965,0.492035,0.247042,0.752958\r\n", "5.876440,0.511915,0.488085,0.511915,0.488085,0.246038,0.753962\r\n", "6.509676,0.515532,0.484468,0.515532,0.484468,0.24537,0.75463\r\n", "7.206299,0.51883,0.48117,0.51883,0.48117,0.244961,0.755039\r\n", "7.972631,0.521828,0.478172,0.521828,0.478172,0.24475,0.75525\r\n", "8.815632,0.524549,0.475451,0.524549,0.475451,0.244687,0.755313\r\n", "9.742958,0.527013,0.472987,0.527013,0.472987,0.244734,0.755266\r\n", "10.763036,0.529244,0.470756,0.529244,0.470756,0.24486,0.75514\r\n", "11.885135,0.53126,0.46874,0.53126,0.46874,0.245043,0.754957\r\n", "13.119456,0.533083,0.466917,0.533083,0.466917,0.245263,0.754737\r\n", "14.477217,0.534731,0.465269,0.534731,0.465269,0.245506,0.754494\r\n", "15.970759,0.53622,0.46378,0.53622,0.46378,0.245763,0.754237\r\n", "17.613661,0.537566,0.462434,0.537566,0.462434,0.246025,0.753975\r\n", "19.420856,0.538782,0.461218,0.538782,0.461218,0.246286,0.753714\r\n", "21.408772,0.539882,0.460118,0.539882,0.460118,0.246542,0.753458\r\n", "23.595483,0.540876,0.459124,0.540876,0.459124,0.24679,0.75321\r\n", "26.000866,0.541776,0.458224,0.541776,0.458224,0.247027,0.752973\r\n", "28.646788,0.54259,0.45741,0.54259,0.45741,0.247253,0.752747\r\n", "31.557303,0.543327,0.456673,0.543327,0.456673,0.247467,0.752533\r\n", "34.758871,0.543994,0.456006,0.543994,0.456006,0.247667,0.752333\r\n", "38.280595,0.544598,0.455402,0.544598,0.455402,0.247855,0.752145\r\n", "42.154493,0.545145,0.454855,0.545145,0.454855,0.24803,0.75197\r\n", "46.415780,0.545641,0.454359,0.545641,0.454359,0.248193,0.751807\r\n", "51.103197,0.546091,0.453909,0.546091,0.453909,0.248344,0.751656\r\n", "56.259355,0.546498,0.453502,0.546498,0.453502,0.248483,0.751517\r\n", "61.931129,0.546868,0.453132,0.546868,0.453132,0.248612,0.751388\r\n", "68.170080,0.547203,0.452797,0.547203,0.452797,0.248731,0.751269\r\n", "75.032927,0.547507,0.452493,0.547507,0.452493,0.24884,0.75116\r\n", "82.582059,0.547782,0.452218,0.547782,0.452218,0.248941,0.751059\r\n", "90.886103,0.548032,0.451968,0.548032,0.451968,0.249033,0.750967\r\n", "100.020552,0.54826,0.45174,0.54826,0.45174,0.249117,0.750883\r\n", "110.068446,0.548466,0.451534,0.548466,0.451534,0.249195,0.750805\r\n", "121.121130,0.548653,0.451347,0.548653,0.451347,0.249266,0.750734\r\n", "133.279082,0.548823,0.451177,0.548823,0.451177,0.24933,0.75067\r\n", "146.652829,0.548977,0.451023,0.548977,0.451023,0.24939,0.75061\r\n", "161.363951,0.549117,0.450883,0.549117,0.450883,0.249444,0.750556\r\n", "177.546184,0.549244,0.450756,0.549244,0.450756,0.249493,0.750507\r\n", "195.346642,0.54936,0.45064,0.54936,0.45064,0.249539,0.750461\r\n", "214.927145,0.549465,0.450535,0.549465,0.450535,0.24958,0.75042\r\n", "236.465698,0.54956,0.45044,0.54956,0.45044,0.249617,0.750383\r\n", "260.158107,0.549647,0.450353,0.549647,0.450353,0.249652,0.750348\r\n", "286.219756,0.549726,0.450274,0.549726,0.450274,0.249683,0.750317\r\n", "314.887571,0.549797,0.450203,0.549797,0.450203,0.249711,0.750289\r\n", "346.422167,0.549862,0.450138,0.549862,0.450138,0.249737,0.750263\r\n", "381.110223,0.549921,0.450079,0.549921,0.450079,0.249761,0.750239\r\n", "419.267084,0.549975,0.450025,0.549975,0.450025,0.249783,0.750217\r\n", "461.239631,0.550024,0.449976,0.550024,0.449976,0.249802,0.750198\r\n", "507.409433,0.550068,0.449932,0.550068,0.449932,0.24982,0.75018\r\n", "558.196215,0.550108,0.449892,0.550108,0.449892,0.249836,0.750164\r\n", "614.061675,0.550145,0.449855,0.550145,0.449855,0.249851,0.750149\r\n", "675.513682,0.550178,0.449822,0.550178,0.449822,0.249865,0.750135\r\n", "743.110889,0.550208,0.449792,0.550208,0.449792,0.249877,0.750123\r\n", "817.467817,0.550236,0.449764,0.550236,0.449764,0.249888,0.750112\r\n", "899.260437,0.550261,0.449739,0.550261,0.449739,0.249898,0.750102\r\n", "989.232320,0.550283,0.449717,0.550283,0.449717,0.249907,0.750093\r\n", "1088.201391,0.550304,0.449696,0.550304,0.449696,0.249916,0.750084\r\n", "1197.067369,0.550323,0.449677,0.550323,0.449677,0.249923,0.750077\r\n", "1316.819945,0.55034,0.44966,0.55034,0.44966,0.24993,0.75007\r\n", "1448.547778,0.550355,0.449645,0.550355,0.449645,0.249937,0.750063\r\n", "1593.448395,0.550369,0.449631,0.550369,0.449631,0.249942,0.750058\r\n", "1752.839073,0.550382,0.449618,0.550382,0.449618,0.249948,0.750052\r\n", "1928.168819,0.550394,0.449606,0.550394,0.449606,0.249952,0.750048\r\n", "2121.031540,0.550405,0.449595,0.550405,0.449595,0.249957,0.750043\r\n", "2333.180533,0.550414,0.449586,0.550414,0.449586,0.249961,0.750039\r\n", "2566.544425,0.550423,0.449577,0.550423,0.449577,0.249964,0.750036\r\n", "2823.244706,0.550431,0.449569,0.550431,0.449569,0.249967,0.750033\r\n", "3105.615016,0.550438,0.449562,0.550438,0.449562,0.24997,0.75003\r\n", "3416.222357,0.550445,0.449555,0.550445,0.449555,0.249973,0.750027\r\n", "3757.890431,0.550451,0.449549,0.550451,0.449549,0.249976,0.750024\r\n", "4133.725313,0.550456,0.449544,0.550456,0.449544,0.249978,0.750022\r\n", "4547.143683,0.550461,0.449539,0.550461,0.449539,0.24998,0.75002\r\n", "5001.903890,0.550465,0.449535,0.550465,0.449535,0.249982,0.750018\r\n", "5502.140118,0.550469,0.449531,0.550469,0.449531,0.249983,0.750017\r\n", "6052.399969,0.550473,0.449527,0.550473,0.449527,0.249985,0.750015\r\n", "6657.685805,0.550477,0.449523,0.550477,0.449523,0.249986,0.750014\r\n", "7323.500224,0.55048,0.44952,0.55048,0.44952,0.249987,0.750013\r\n", "8055.896086,0.550482,0.449518,0.550482,0.449518,0.249989,0.750011\r\n", "8861.531533,0.550485,0.449515,0.550485,0.449515,0.24999,0.75001\r\n", "9747.730525,0.550487,0.449513,0.550487,0.449513,0.249991,0.750009\r\n", "10722.549417,0.550489,0.449511,0.550489,0.449511,0.249991,0.750009\r\n", "11794.850197,0.550491,0.449509,0.550491,0.449509,0.249992,0.750008\r\n", "12974.381056,0.550493,0.449507,0.550493,0.449507,0.249993,0.750007\r\n", "14271.865000,0.550495,0.449505,0.550495,0.449505,0.249994,0.750006\r\n", "15699.097339,0.550496,0.449504,0.550496,0.449504,0.249994,0.750006\r\n", "17269.052912,0.550497,0.449503,0.550497,0.449503,0.249995,0.750005\r\n", "18996.004042,0.550498,0.449502,0.550498,0.449502,0.249995,0.750005\r\n", "20895.650285,0.5505,0.4495,0.5505,0.4495,0.249996,0.750004\r\n", "22985.261153,0.550501,0.449499,0.550501,0.449499,0.249996,0.750004\r\n", "25283.833107,0.550501,0.449499,0.550501,0.449499,0.249996,0.750004\r\n", "27812.262256,0.550502,0.449498,0.550502,0.449498,0.249997,0.750003\r\n", "30593.534321,0.550503,0.449497,0.550503,0.449497,0.249997,0.750003\r\n", "33652.933592,0.550504,0.449496,0.550504,0.449496,0.249997,0.750003\r\n", "37018.272790,0.550504,0.449496,0.550504,0.449496,0.249998,0.750002\r\n", "40720.145908,0.550505,0.449495,0.550505,0.449495,0.249998,0.750002\r\n", "44792.206338,0.550505,0.449495,0.550505,0.449495,0.249998,0.750002\r\n", "49271.472810,0.550506,0.449494,0.550506,0.449494,0.249998,0.750002\r\n", "54198.665930,0.550506,0.449494,0.550506,0.449494,0.249998,0.750002\r\n", "59618.578362,0.550506,0.449494,0.550506,0.449494,0.249998,0.750002\r\n", "65580.482037,0.550507,0.449493,0.550507,0.449493,0.249999,0.750001\r\n", "72138.576080,0.550507,0.449493,0.550507,0.449493,0.249999,0.750001\r\n", "79352.479527,0.550507,0.449493,0.550507,0.449493,0.249999,0.750001\r\n", "87287.773318,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001\r\n", "96016.596489,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001\r\n", "105618.301977,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001\r\n", "116180.178013,0.550508,0.449492,0.550508,0.449492,0.249999,0.750001\r\n", "127798.241654,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001\r\n", "140578.111658,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001\r\n", "154635.968663,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001\r\n", "170099.611368,0.550509,0.449491,0.550509,0.449491,0.249999,0.750001\r\n", "187109.618343,0.550509,0.449491,0.550509,0.449491,0.25,0.75\r\n", "205820.626017,0.550509,0.449491,0.550509,0.449491,0.25,0.75\r\n", "226402.734457,0.550509,0.449491,0.550509,0.449491,0.25,0.75\r\n", "249043.053742,0.550509,0.449491,0.550509,0.449491,0.25,0.75\r\n", "273947.404955,0.550509,0.449491,0.550509,0.449491,0.25,0.75\r\n", "301342.191289,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "331476.456257,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "364624.147721,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "401086.608332,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "441195.315005,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "485314.892344,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "533846.427417,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "587231.115998,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "645954.273437,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "710549.746619,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "781604.767120,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "859765.289671,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "945741.864477,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n", "1040316.096763,0.55051,0.44949,0.55051,0.44949,0.25,0.75\r\n" ] } ], "source": [ "!gambit-logit 2x2x2-nau.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The performance of `gambit-enumpoly` on this game is a bit of a mixed bag. It fails to find anything but the pure equilibria. However, it *does* provide interesting diagnostic information, that some of the supports are \"singular.\" Actually, this mostly just means that something went wrong and it gave up - but often this happens because the set of equations has a positive-dimensional set of solutions. So at least it provides some diagnostics that one might want to inspect those supports more closely." ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compute Nash equilibria by solving polynomial systems\r\n", "Gambit version 16.0.0, Copyright (C) 1994-2016, The Gambit Project\r\n", "Heuristic search implementation Copyright (C) 2006, Litao Wei\r\n", "This is free software, distributed under the GNU GPL\r\n", "\r\n", "candidate,10,01,10\r\n", "NE,1.000000,0.000000,0.000000,1.000000,1.000000,0.000000\r\n", "candidate,01,01,01\r\n", "NE,0.000000,1.000000,0.000000,1.000000,0.000000,1.000000\r\n", "candidate,01,10,10\r\n", "NE,0.000000,1.000000,1.000000,0.000000,1.000000,0.000000\r\n", "candidate,01,10,11\r\n", "singular,01,10,11\r\n", "candidate,10,01,11\r\n", "singular,10,01,11\r\n", "candidate,11,11,11\r\n", "singular,11,11,11\r\n" ] } ], "source": [ "!gambit-enumpoly -V 2x2x2-nau.nfg" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "There is however some hope on the horizon. Both PHCpack http://homepages.math.uic.edu/~jan/download.html and Bertini https://bertini.nd.edu are polynomial system solvers that deal with positive-dimensional sets of solutions. There is a Python script in the `contrib/` directory of the Gambit repository which interfaces with these (but the script needs updating to the current version of the Python interface)." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.12" } }, "nbformat": 4, "nbformat_minor": 0 }