{ "cells": [ { "cell_type": "markdown", "id": "98eb65d8", "metadata": {}, "source": [ "# 3) A one-card poker game with private information\n", "\n", "In this tutorial, we'll create an extensive form representation of a one-card poker game [[Mye91](#references)] and use it to demonstrate and explain the following with Gambit:\n", "\n", "1. Setting up an extensive form game with imperfect information using [information sets](#information-sets)\n", "2. [Computing and interpreting Nash equilibria](#computing-and-interpreting-nash-equilibria) and understanding mixed behaviour and mixed strategy profiles\n", "3. [Acceptance criteria for Nash equilibria](#acceptance-criteria-for-nash-equilibria)\n", "\n", "A version of this game also appears in [[RUW08](#references)], as a classroom game under the name \"stripped-down poker\".\n", "This is perhaps the simplest interesting game with imperfect information.\n", "\n", "In our version of the game, there are two players, **Alice** and **Bob**, and a deck of cards, with equal numbers of **King** and **Queen** cards.\n", "\n", "- The game begins with each player putting $1 in the pot.\n", "- A card is dealt at random to Alice\n", " - Alice observes her card\n", " - Bob does not observe the card\n", "- Alice then chooses either to **Raise** or to **Fold**.\n", " - If she chooses to Fold, Bob wins the pot and the game ends.\n", " - If she chooses to Raise, she adds another $1 to the pot.\n", "- Bob then chooses either to **Meet** or **Pass**.\n", " - If he chooses to Pass, Alice wins the pot and the game ends.\n", " - If he chooses to Meet, he adds another $1 to the pot.\n", "- There is then a showdown, in which Alice reveals her card.\n", " - If she has a King, then she wins the pot;\n", " - If she has a Queen, then Bob wins the pot." ] }, { "cell_type": "code", "execution_count": 1, "id": "69cbfe81", "metadata": {}, "outputs": [], "source": [ "import pygambit as gbt" ] }, { "cell_type": "markdown", "id": "70819881", "metadata": {}, "source": [ "Create the game with two players." ] }, { "cell_type": "code", "execution_count": 2, "id": "ad6a1119", "metadata": {}, "outputs": [], "source": [ "g = gbt.Game.new_tree(\n", " players=[\"Alice\", \"Bob\"], \n", " title=\"One card poker\"\n", ")" ] }, { "cell_type": "markdown", "id": "d9796238", "metadata": {}, "source": [ "In addition to the two named players, Gambit also instantiates a chance player." ] }, { "cell_type": "code", "execution_count": 3, "id": "841f9f74", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Player(game=Game(title='One card poker'), label='Alice')\n", "Player(game=Game(title='One card poker'), label='Bob')\n", "ChancePlayer(game=Game(title='One card poker'))\n" ] } ], "source": [ "print(g.players[\"Alice\"])\n", "print(g.players[\"Bob\"])\n", "print(g.players.chance)" ] }, { "cell_type": "markdown", "id": "0d4c7f5b", "metadata": {}, "source": [ "Moves belonging to the chance player can be added in the same way as to other players.\n", "\n", "At any new move created for the chance player, the action probabilities default to uniform randomization over the actions at the move.\n", "\n", "The first step in this game is that Alice is dealt a card which could be a King or Queen, each with probability 1/2.\n", "\n", "To simulate this in Gambit, we create a chance player move at the root node of the game.\n", "\n", "Note: throughout this tutorial, we'll also label nodes according to the actions that precede them in the game tree to improve code readability." ] }, { "cell_type": "code", "execution_count": 4, "id": "fe80c64c", "metadata": {}, "outputs": [], "source": [ "g.append_move(\n", " g.root,\n", " player=g.players.chance,\n", " actions=[\"King\", \"Queen\"] # By default, chance actions have equal probabilities\n", ")\n", "for node in g.root.children: # Add labels to the new child nodes to improve code readability\n", " node.label = node.prior_action.label" ] }, { "cell_type": "markdown", "id": "5cf73f0a", "metadata": {}, "source": [ "## Information sets\n", "\n", "In this game, information structure is important.\n", "Alice knows her card, so the two nodes at which she has the move are part of different **information sets**.\n", "\n", "We'll therefore need to append Alice's move separately for each of the root node's children, i.e. the scenarios where she has a King or a Queen.\n", "Let's now add both of these possible moves." ] }, { "cell_type": "code", "execution_count": 5, "id": "0e3bb5ef", "metadata": {}, "outputs": [], "source": [ "for node in g.root.children:\n", " g.append_move(\n", " node,\n", " player=\"Alice\",\n", " actions=[\"Raise\", \"Fold\"]\n", " )\n", " for child_node in node.children:\n", " child_node.label = child_node.prior_action.label" ] }, { "cell_type": "markdown", "id": "4c8d0343", "metadata": {}, "source": [ "The loop above causes each of the newly-appended moves to be in new information sets, reflecting the fact that Alice's decision depends on the knowledge of which card she holds.\n", "\n", "In contrast, Bob does not know Alice’s card, and therefore cannot distinguish between the two nodes at which he has to make his decision:\n", "\n", " - Chance player chooses King, then Alice Raises: `g.root.children[\"King\"].children[\"Raise\"]`\n", " - Chance player chooses Queen, then Alice Raises: `g.root.children[\"Queen\"].children[\"Raise\"]`\n", "\n", "In other words, Bob's decision when Alice raises with a Queen should be part of the same information set as Bob's decision when Alice raises with a King.\n", "\n", "To set this scenario up in Gambit, we'll need to use `Game.append_infoset` to add a move as part of an existing information set (represented in Gambit as an `Infoset`).\n", "\n", "First, let's add Bob's move to the node where Alice has raised with a King." ] }, { "cell_type": "code", "execution_count": 6, "id": "dbfa7035", "metadata": {}, "outputs": [], "source": [ "g.append_move(\n", " g.root.children[\"King\"].children[\"Raise\"],\n", " player=\"Bob\",\n", " actions=[\"Meet\", \"Pass\"]\n", ")\n", "for node in g.root.children[\"King\"].children[\"Raise\"].children:\n", " node.label = node.prior_action.label" ] }, { "cell_type": "markdown", "id": "689ce12c", "metadata": {}, "source": [ "Now let's add the information set we created at the node where Alice raised with a King, to the node where Alice raised with a Queen." ] }, { "cell_type": "code", "execution_count": 7, "id": "655cdae3", "metadata": {}, "outputs": [], "source": [ "g.append_infoset(\n", " g.root.children[\"Queen\"].children[\"Raise\"],\n", " infoset=g.root.children[\"King\"].children[\"Raise\"].infoset\n", ")\n", "for node in g.root.children[\"Queen\"].children[\"Raise\"].children:\n", " node.label = node.prior_action.label" ] }, { "cell_type": "markdown", "id": "c4eeb65f", "metadata": {}, "source": [ "In game theory terms, this creates \"imperfect information\".\n", "Bob cannot distinguish between these two nodes in the game tree, so he must use the same strategy (same probabilities for Meet vs. Pass) in both situations.\n", "\n", "This is crucial in games where players must make decisions without complete knowledge of their opponents' private information.\n", "\n", "Let's now set up the four possible payoff outcomes for the game." ] }, { "cell_type": "code", "execution_count": 8, "id": "87c988be", "metadata": {}, "outputs": [], "source": [ "alice_winsbig = g.add_outcome([2, -2], label=\"Alice wins big\")\n", "alice_wins = g.add_outcome([1, -1], label=\"Alice wins\")\n", "bob_winsbig = g.add_outcome([-2, 2], label=\"Bob wins big\")\n", "bob_wins = g.add_outcome([-1, 1], label=\"Bob wins\")" ] }, { "cell_type": "markdown", "id": "467a2c39", "metadata": {}, "source": [ "Finally, we should assign an outcome to each of the terminal nodes in the game tree." ] }, { "cell_type": "code", "execution_count": 9, "id": "29aa60a0", "metadata": {}, "outputs": [], "source": [ "# Alice folds, Bob wins small\n", "g.set_outcome(g.root.children[\"King\"].children[\"Fold\"], bob_wins)\n", "g.set_outcome(g.root.children[\"Queen\"].children[\"Fold\"], bob_wins)\n", "\n", "# Bob sees Alice raise and calls, correctly believing she is bluffing, Bob wins big\n", "g.set_outcome(g.root.children[\"Queen\"].children[\"Raise\"].children[\"Meet\"], bob_winsbig)\n", "\n", "# Bob sees Alice raise and calls, incorrectly believing she is bluffing, Alice wins big\n", "g.set_outcome(g.root.children[\"King\"].children[\"Raise\"].children[\"Meet\"], alice_winsbig)\n", "\n", "# Bob does not call Alice's raise, Alice wins small\n", "g.set_outcome(g.root.children[\"King\"].children[\"Raise\"].children[\"Pass\"], alice_wins)\n", "g.set_outcome(g.root.children[\"Queen\"].children[\"Raise\"].children[\"Pass\"], alice_wins)" ] }, { "cell_type": "markdown", "id": "17eb6af5", "metadata": {}, "source": [ "## Computing and interpreting Nash equilibria\n", "\n", "\n", "Since our one-card poker game is extensive form and has two players, we can use the `lcp_solve` algorithm in Gambit to compute the Nash equilibria." ] }, { "cell_type": "code", "execution_count": 10, "id": "4d92c8d9", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "NashComputationResult(method='lcp', rational=True, use_strategic=False, equilibria=[[[[Rational(1, 1), Rational(0, 1)], [Rational(1, 3), Rational(2, 3)]], [[Rational(2, 3), Rational(1, 3)]]]], parameters={'stop_after': 0, 'max_depth': 0})" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "result = gbt.nash.lcp_solve(g)\n", "result" ] }, { "cell_type": "markdown", "id": "e5946077", "metadata": {}, "source": [ "The result of the calculation is returned as a `NashComputationResult` object.\n", "\n", "The set of equilibria found is reported in `NashComputationResult.equilibria`; in this case, this is a list of `MixedBehaviorProfile`'s.\n", "\n", "For one-card poker, we expect to find a single equilibrium (one `MixedBehaviorProfile`):" ] }, { "cell_type": "code", "execution_count": 11, "id": "9967d6f7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Number of equilibria found: 1\n" ] } ], "source": [ "print(\"Number of equilibria found:\", len(result.equilibria))\n", "eqm = result.equilibria[0]" ] }, { "cell_type": "code", "execution_count": 12, "id": "3293e818", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "pygambit.gambit.MixedBehaviorProfileRational" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Note: MixedBehaviorProfileRational is a subclass of MixedBehaviorProfile that uses rational numbers for probabilities.\n", "type(eqm)" ] }, { "cell_type": "markdown", "id": "69f67b5b", "metadata": {}, "source": [ "A mixed behavior profile specifies, for each information set, the probability distribution over actions at that information set.\n", "\n", "Indexing a mixed behaviour profile by a player gives a `MixedBehavior`, which specifies probability distributions at each of the player's information sets:" ] }, { "cell_type": "code", "execution_count": 13, "id": "4cf38264", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "pygambit.gambit.MixedBehavior" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "type(eqm[\"Alice\"])" ] }, { "cell_type": "code", "execution_count": 14, "id": "85e7fdda", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[1,0\\right],\\left[\\frac{1}{3},\\frac{2}{3}\\right]\\right]$" ], "text/plain": [ "[[Rational(1, 1), Rational(0, 1)], [Rational(1, 3), Rational(2, 3)]]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm[\"Alice\"]" ] }, { "cell_type": "markdown", "id": "6615115d", "metadata": {}, "source": [ "In this case, at Alice's first information set, the one at which she has the King, she always raises.\n", "\n", "At her second information set, where she has the Queen, she sometimes bluffs, raising with probability one-third.\n", "\n", "The probability distribution at an information set is represented by a `MixedAction`.\n", "\n", "`MixedBehavior.mixed_actions` iterates over these for the player:" ] }, { "cell_type": "code", "execution_count": 15, "id": "f45a82b6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "At information set 0, Alice plays Raise with probability: 1 and Fold with probability: 0\n", "At information set 1, Alice plays Raise with probability: 1/3 and Fold with probability: 2/3\n" ] } ], "source": [ "for infoset, mixed_action in eqm[\"Alice\"].mixed_actions():\n", " print(\n", " f\"At information set {infoset.number}, \"\n", " f\"Alice plays Raise with probability: {mixed_action['Raise']}\"\n", " f\" and Fold with probability: {mixed_action['Fold']}\"\n", " )" ] }, { "cell_type": "markdown", "id": "9eeae046", "metadata": {}, "source": [ "We can alternatively iterate through each of a player's actions like so:" ] }, { "cell_type": "code", "execution_count": 16, "id": "83bbd3e5", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "At information set 0, Alice plays Raise with probability: 1\n", "At information set 0, Alice plays Fold with probability: 0\n", "At information set 1, Alice plays Raise with probability: 1/3\n", "At information set 1, Alice plays Fold with probability: 2/3\n" ] } ], "source": [ "for action in g.players[\"Alice\"].actions:\n", " print(\n", " f\"At information set {action.infoset.number}, \"\n", " f\"Alice plays {action.label} with probability: {eqm[action]}\"\n", " )" ] }, { "cell_type": "markdown", "id": "1f121d48", "metadata": {}, "source": [ "Now let's look at Bob’s strategy:" ] }, { "cell_type": "code", "execution_count": 17, "id": "6bf51b38", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\left[\\left[\\frac{2}{3},\\frac{1}{3}\\right]\\right]$" ], "text/plain": [ "[[Rational(2, 3), Rational(1, 3)]]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm[\"Bob\"]" ] }, { "cell_type": "markdown", "id": "e906c4c4", "metadata": {}, "source": [ "Bob meets Alice’s raise two-thirds of the time.\n", "The label “Raise” is used in more than one information set for Alice, so in the above we had to specify information sets when indexing.\n", "\n", "When there is no ambiguity, we can specify action labels directly.\n", "So for example, because Bob has only one action named “Meet” in the game, we can extract the probability that Bob plays “Meet” by:" ] }, { "cell_type": "code", "execution_count": 18, "id": "2966e700", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\frac{2}{3}$" ], "text/plain": [ "Rational(2, 3)" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm[\"Bob\"][\"Meet\"]" ] }, { "cell_type": "markdown", "id": "2ec69f8c", "metadata": {}, "source": [ "Moreover, this is the only action with that label in the game, so we can index the profile directly using the action label without any ambiguity:" ] }, { "cell_type": "code", "execution_count": 19, "id": "f5a7f110", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\frac{2}{3}$" ], "text/plain": [ "Rational(2, 3)" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm[\"Meet\"]" ] }, { "cell_type": "markdown", "id": "db19411b", "metadata": {}, "source": [ "Because this is an equilibrium, Bob is indifferent between the two actions at his information set, meaning he has no reason to prefer one action over the other, given Alice's expected strategy.\n", "\n", "`MixedBehaviorProfile.action_value` returns the expected payoff of taking an action, conditional on reaching that action's information set:" ] }, { "cell_type": "code", "execution_count": 20, "id": "a7d3816d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "When Bob plays Meet he can expect the payoff: -1\n", "When Bob plays Pass he can expect the payoff: -1\n" ] } ], "source": [ "# Remember that Bob has a single information set\n", "for action in g.players[\"Bob\"].infosets[0].actions:\n", " print(\n", " f\"When Bob plays {action.label} he can expect the payoff: {eqm.action_value(action)}\"\n", " )" ] }, { "cell_type": "markdown", "id": "6491fdda", "metadata": {}, "source": [ "Bob's indifference between his actions arises because of his beliefs given Alice's strategy.\n", "\n", "`MixedBehaviorProfile.belief` returns the probability of reaching a node, conditional on its information set being reached.\n", "\n", "Recall that the two nodes in Bob's only information set are `g.root.children[\"King\"].children[\"Raise\"]` and `g.root.children[\"Queen\"].children[\"Raise\"]`):" ] }, { "cell_type": "code", "execution_count": 21, "id": "4a54b20c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bob's belief in reaching the King -> Raise node is: 3/4\n", "Bob's belief in reaching the Queen -> Raise node is: 1/4\n" ] } ], "source": [ "for node in g.players[\"Bob\"].infosets[0].members:\n", " print(\n", " f\"Bob's belief in reaching the {node.parent.label} -> {node.label} node is: {eqm.belief(node)}\"\n", " )" ] }, { "cell_type": "markdown", "id": "351bb3ce", "metadata": {}, "source": [ "Bob believes that, conditional on Alice raising, there's a 3/4 chance that she has the King; therefore, the expected payoff to meeting is in fact -1 as computed.\n", "\n", "`MixedBehaviorProfile.infoset_prob` returns the probability that an information set is reached:" ] }, { "cell_type": "code", "execution_count": 22, "id": "b250c1cd", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\frac{2}{3}$" ], "text/plain": [ "Rational(2, 3)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm.infoset_prob(g.players[\"Bob\"].infosets[0])" ] }, { "cell_type": "markdown", "id": "9216ea34", "metadata": {}, "source": [ "The corresponding probability that a node is reached in the play of the game is given by `MixedBehaviorProfile.realiz_prob`, and the expected payoff to a player conditional on reaching a node is given by `MixedBehaviorProfile.node_value`." ] }, { "cell_type": "code", "execution_count": 23, "id": "6f01846b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The probability that the node King -> Raise is reached is: 1/2. Bob's expected payoff conditional on reaching this node is: -5/3\n", "The probability that the node Queen -> Raise is reached is: 1/6. Bob's expected payoff conditional on reaching this node is: 1\n" ] } ], "source": [ "for node in g.players[\"Bob\"].infosets[0].members:\n", " print(\n", " f\"The probability that the node {node.parent.label} -> {node.label} is reached is: {eqm.realiz_prob(node)}. \",\n", " f\"Bob's expected payoff conditional on reaching this node is: {eqm.node_value(\"Bob\", node)}\"\n", " )" ] }, { "cell_type": "markdown", "id": "5ba0c241", "metadata": {}, "source": [ "The overall expected payoff to a player given the behavior profile is returned by `MixedBehaviorProfile.payoff`:" ] }, { "cell_type": "code", "execution_count": 24, "id": "5079d231", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\frac{1}{3}$" ], "text/plain": [ "Rational(1, 3)" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm.payoff(\"Alice\")" ] }, { "cell_type": "code", "execution_count": 25, "id": "c55f2c7a", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$\\frac{-1}{3}$" ], "text/plain": [ "Rational(-1, 3)" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "eqm.payoff(\"Bob\")" ] }, { "cell_type": "markdown", "id": "26d5e8ff", "metadata": {}, "source": [ "The equilibrium computed expresses probabilities in rational numbers.\n", "\n", "Because the numerical data of games in Gambit [are represented exactly](#representation-of-numerical-data-of-a-game), methods which are specialized to two-player games, `lp_solve`, `lcp_solve`, and `enummixed_solve`, can report exact probabilities for equilibrium strategy profiles.\n", "\n", "This is enabled by default for these methods.\n", "\n", "When a game has an extensive representation, equilibrium finding methods default to computing on that representation.\n", "It is also possible to compute using the strategic representation.\n", "`pygambit` transparently computes the reduced strategic form representation of an extensive game." ] }, { "cell_type": "code", "execution_count": 26, "id": "d4ecff88", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['11', '12', '21', '22']" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[s.label for s in g.players[\"Alice\"].strategies]" ] }, { "cell_type": "markdown", "id": "a9bf9b73", "metadata": {}, "source": [ "In the strategic form of this game, Alice has four strategies.\n", "\n", "The generated strategy labels list the action numbers taken at each information set.\n", "For example, label '11' refers to the strategy gets dealt the King, then raises.\n", "\n", "We can therefore apply a method which operates on a strategic game to any game with an extensive representation." ] }, { "cell_type": "code", "execution_count": 27, "id": "24e4b6e8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "NashComputationResult(method='gnm', rational=False, use_strategic=True, equilibria=[[[0.33333333333866677, 0.6666666666613335, 0.0, 0.0], [0.6666666666559997, 0.3333333333440004]]], parameters={'perturbation': [[1.0, 0.0, 0.0, 0.0], [1.0, 0.0]], 'end_lambda': -10.0, 'steps': 100, 'local_newton_interval': 3, 'local_newton_maxits': 10})" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gnm_result = gbt.nash.gnm_solve(g)\n", "gnm_result" ] }, { "cell_type": "markdown", "id": "d88b736b", "metadata": {}, "source": [ "`gnm_solve` can be applied to any game with any number of players, and uses a path-following process in floating-point arithmetic, so it returns profiles with probabilities expressed as floating-point numbers.\n", "\n", "This method operates on the strategic representation of the game, so the returned results are of type `MixedStrategyProfile` (specifically `MixedStrategyProfileDouble`)." ] }, { "cell_type": "code", "execution_count": 28, "id": "d9ffb4b8", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "pygambit.gambit.MixedStrategyProfileDouble" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gnm_eqm = gnm_result.equilibria[0]\n", "type(gnm_eqm)" ] }, { "cell_type": "markdown", "id": "102d22c2", "metadata": {}, "source": [ "Indexing a `MixedStrategyProfile` by a player gives the probability distribution over that player's strategies only.\n", "\n", "The expected payoff to a strategy is provided by `MixedStrategyProfile.strategy_value` and the overall expected payoff to a player is returned by `MixedStrategyProfile.payoff`:" ] }, { "cell_type": "code", "execution_count": 29, "id": "56e2f847", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Alice's expected payoffs playing:\n", "Strategy 11: 0.3333\n", "Strategy 12: 0.3333\n", "Strategy 21: -1.0000\n", "Strategy 22: -1.0000\n", "Alice's overall expected payoff: 0.3333\n", "\n", "Bob's expected payoffs playing:\n", "Strategy 1: -0.3333\n", "Strategy 2: -0.3333\n", "Bob's overall expected payoff: -0.3333\n", "\n" ] } ], "source": [ "for player in g.players:\n", " print(\n", " f\"{player.label}'s expected payoffs playing:\"\n", " )\n", " for strategy in player.strategies:\n", " print(\n", " f\"Strategy {strategy.label}: {gnm_eqm.strategy_value(strategy):.4f}\"\n", " )\n", " print(\n", " f\"{player.label}'s overall expected payoff: {gnm_eqm.payoff(player):.4f}\"\n", " )\n", " print()" ] }, { "cell_type": "markdown", "id": "874be231", "metadata": {}, "source": [ "When a game has an extensive representation, we can convert freely between a mixed strategy profile and the corresponding mixed behaviour profile representation of the same strategies using `MixedStrategyProfile.as_behavior` and `MixedBehaviorProfile.as_strategy`.\n", "\n", "- A mixed **strategy** profile maps each strategy in a game to the corresponding probability with which that strategy is played.\n", "- A mixed **behaviour** profile maps each action at each information set in a game to the corresponding probability with which the action is played, conditional on that information set being reached.\n", "\n", "Let's convert the equilibrium we found using `gnm_solve` to a mixed behaviour profile and iterate through the players actions to show their expected payoffs, comparing as we go with the payoffs found by `lcp_solve`:" ] }, { "cell_type": "code", "execution_count": 30, "id": "d18a91f0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Alice's expected payoffs:\n", "At information set 0, when playing Raise - gnm: 1.6667, lcp: 1.6667\n", "At information set 0, when playing Fold - gnm: -1.0000, lcp: -1.0000\n", "At information set 1, when playing Raise - gnm: -1.0000, lcp: -1.0000\n", "At information set 1, when playing Fold - gnm: -1.0000, lcp: -1.0000\n", "\n", "Bob's expected payoffs:\n", "At information set 0, when playing Meet - gnm: -1.0000, lcp: -1.0000\n", "At information set 0, when playing Pass - gnm: -1.0000, lcp: -1.0000\n", "\n" ] } ], "source": [ "for player in g.players:\n", " print(\n", " f\"{player.label}'s expected payoffs:\"\n", " )\n", " for action in player.actions:\n", " print(\n", " f\"At information set {action.infoset.number}, \"\n", " f\"when playing {action.label} - \"\n", " f\"gnm: {gnm_eqm.as_behavior().action_value(action):.4f}\"\n", " f\", lcp: {eqm.action_value(action):.4f}\"\n", " )\n", " print()" ] }, { "cell_type": "markdown", "id": "b2867dca", "metadata": {}, "source": [ "Acceptance criteria for Nash equilibria\n", "---------------------------------------\n", "\n", "Some methods for computing Nash equilibria operate using floating-point arithmetic and/or generate candidate equilibrium profiles using methods which involve some form of successive approximations.\n", "The outputs of these methods therefore are in general $\\varepsilon$-equilibria, for some positive $\\varepsilon$.\n", "\n", "$\\varepsilon$-equilibria (from [Wikipedia](https://en.wikipedia.org/wiki/Epsilon-equilibrium)):\n", "\n", "> In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different.\n", "\n", "> Given a game and a real non-negative parameter $\\varepsilon$, a strategy profile is said to be an $\\varepsilon$-equilibrium if it is not possible for any player to gain more than $\\varepsilon$ in expected payoff by unilaterally deviating from his strategy. Every Nash Equilibrium is equivalent to an $\\varepsilon$-equilibrium where $\\varepsilon = 0$.\n", "\n", "\n", "To provide a uniform interface across methods, where relevant Gambit provides a parameter\n", "`maxregret`, which specifies the acceptance criterion for labeling the output of the\n", "algorithm as an equilibrium.\n", "This parameter is interpreted *proportionally* to the range of payoffs in the game.\n", "Any profile returned as an equilibrium is guaranteed to be an $\\varepsilon$-equilibrium, for $\\varepsilon$ no more than `maxregret`\n", "times the difference of the game's maximum and minimum payoffs.\n", "\n", "As an example, consider solving our one-card poker game using `logit_solve`. The range of the payoffs in this game is 4 (from +2 to -2).\n" ] }, { "cell_type": "code", "execution_count": 31, "id": "0c55f745", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(Rational(2, 1), Rational(-2, 1))" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g.max_payoff, g.min_payoff" ] }, { "cell_type": "markdown", "id": "6263ad6e", "metadata": {}, "source": [ "`logit_solve` is a globally-convergent method, in that it computes a sequence of profiles which is guaranteed to have a subsequence that converges to a\n", "Nash equilibrium.\n", "\n", "The default value of `maxregret` for this method is set at $10^{-8}$:" ] }, { "cell_type": "code", "execution_count": 32, "id": "101598c6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "logit_solve_result = gbt.nash.logit_solve(g, maxregret=1e-8)\n", "len(logit_solve_result.equilibria)" ] }, { "cell_type": "code", "execution_count": 33, "id": "9b142728", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3.987411578698641e-08" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ls_eqm = logit_solve_result.equilibria[0]\n", "ls_eqm.max_regret()" ] }, { "cell_type": "markdown", "id": "a2ba06c4", "metadata": {}, "source": [ "The value of `MixedBehaviorProfile.max_regret` of the computed profile exceeds $10^{-8}$ measured in payoffs of the game.\n", "However, when considered relative to the scale of the game's payoffs, we see it is less than $10^{-8}$ of the payoff range, as requested:" ] }, { "cell_type": "code", "execution_count": 34, "id": "ff405409", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9.968528946746602e-09" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ls_eqm.max_regret() / (g.max_payoff - g.min_payoff)" ] }, { "cell_type": "markdown", "id": "54635455", "metadata": {}, "source": [ "In general, for globally-convergent methods especially, there is a tradeoff between precision and running time.\n", "\n", "We could instead ask only for an $\\varepsilon$-equilibrium with a (scaled) $\\varepsilon$ of no more than $10^{-4}$:" ] }, { "cell_type": "code", "execution_count": 35, "id": "31b0143c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9.395259956013202e-05" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.logit_solve(g, maxregret=1e-4).equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)" ] }, { "cell_type": "markdown", "id": "dc8c8509", "metadata": {}, "source": [ "The tradeoff comes from some methods being slow to converge on some games, making it useful instead to get a more coarse approximation to an equilibrium (higher `maxregret` value) which is faster to calculate. " ] }, { "cell_type": "code", "execution_count": 36, "id": "7cfba34a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 10.5 ms, sys: 269 μs, total: 10.7 ms\n", "Wall time: 10.7 ms\n" ] }, { "data": { "text/plain": [ "NashComputationResult(method='logit', rational=False, use_strategic=False, equilibria=[[[[1.0, 0.0], [0.3338351656285655, 0.666164834417892]], [[0.6670407651644307, 0.3329592348608147]]]], parameters={'first_step': 0.03, 'max_accel': 1.1})" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "gbt.nash.logit_solve(g, maxregret=1e-4)" ] }, { "cell_type": "code", "execution_count": 37, "id": "6f1809a7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 20.1 ms, sys: 610 μs, total: 20.7 ms\n", "Wall time: 21.5 ms\n" ] }, { "data": { "text/plain": [ "NashComputationResult(method='logit', rational=False, use_strategic=False, equilibria=[[[[1.0, 0.0], [0.33333338649882943, 0.6666666135011706]], [[0.6666667065407631, 0.3333332934592369]]]], parameters={'first_step': 0.03, 'max_accel': 1.1})" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "gbt.nash.logit_solve(g, maxregret=1e-8)" ] }, { "cell_type": "markdown", "id": "76461069", "metadata": {}, "source": [ "The convention of expressing `maxregret` scaled by the game's payoffs standardises the behavior of methods across games.\n", "\n", "For example, consider solving the poker game instead using `liap_solve()`." ] }, { "cell_type": "code", "execution_count": 38, "id": "414b6f65", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5.509533871672634e-05" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.nash.liap_solve(g.mixed_behavior_profile(), maxregret=1.0e-4).equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)" ] }, { "cell_type": "markdown", "id": "c6853432", "metadata": {}, "source": [ "If, instead, we double all payoffs, the output of the method is unchanged." ] }, { "cell_type": "code", "execution_count": 39, "id": "a892dc2b", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5.509533871672634e-05" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "for outcome in g.outcomes:\n", " outcome[\"Alice\"] = outcome[\"Alice\"] * 2\n", " outcome[\"Bob\"] = outcome[\"Bob\"] * 2\n", "\n", "gbt.nash.liap_solve(g.mixed_behavior_profile(), maxregret=1.0e-4).equilibria[0].max_regret() / (g.max_payoff - g.min_payoff)" ] }, { "cell_type": "markdown", "id": "5f1f66e0", "metadata": {}, "source": [ "## Representation of numerical data of a game\n", "\n", "Payoffs to players and probabilities of actions at chance information sets are specified as numbers.\n", "Gambit represents the numerical values in a game in exact precision, using either decimal or rational representations.\n", "\n", "To illustrate, consider a trivial game which just has one move for the chance player:" ] }, { "cell_type": "code", "execution_count": 40, "id": "2f79695a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Rational(1, 3), Rational(1, 3), Rational(1, 3)]" ] }, "execution_count": 40, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_game = gbt.Game.new_tree()\n", "small_game.append_move(small_game.root, small_game.players.chance, [\"a\", \"b\", \"c\"])\n", "[act.prob for act in small_game.root.infoset.actions]" ] }, { "cell_type": "markdown", "id": "dc4522b5", "metadata": {}, "source": [ "The default when creating a new move for chance is that all actions are chosen with equal probability.\n", "These probabilities are represented as rational numbers, using `pygambit`'s `Rational` class, which is derived from Python's `fractions.Fraction`.\n", "\n", "Numerical data can be set as rational numbers. Here we update the chance action probabilities with `Rational` numbers:" ] }, { "cell_type": "code", "execution_count": 41, "id": "5de6acb2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Rational(1, 4), Rational(1, 2), Rational(1, 4)]" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_game.set_chance_probs(\n", " small_game.root.infoset,\n", " [gbt.Rational(1, 4), gbt.Rational(1, 2), gbt.Rational(1, 4)]\n", ")\n", "[act.prob for act in small_game.root.infoset.actions]" ] }, { "cell_type": "markdown", "id": "23263b21", "metadata": {}, "source": [ "Numerical data can also be explicitly specified as decimal numbers:" ] }, { "cell_type": "code", "execution_count": 42, "id": "c47d2ab6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Decimal('0.25'), Decimal('0.50'), Decimal('0.25')]" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_game.set_chance_probs(\n", " small_game.root.infoset,\n", " [gbt.Decimal(\".25\"), gbt.Decimal(\".50\"), gbt.Decimal(\".25\")]\n", ")\n", "[act.prob for act in small_game.root.infoset.actions]" ] }, { "cell_type": "markdown", "id": "bffda303", "metadata": {}, "source": [ "Although the two representations above are mathematically equivalent, `pygambit` remembers the format in which the values were specified.\n", "\n", "Expressing rational or decimal numbers as above is verbose and tedious.\n", "`pygambit` offers a more concise way to express numerical data in games: when setting numerical game data, `pygambit` will attempt to convert text strings to their rational or decimal representation.\n", "The above can therefore be written more compactly using string representations:" ] }, { "cell_type": "code", "execution_count": 43, "id": "04329084", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Rational(1, 4), Rational(1, 2), Rational(1, 4)]" ] }, "execution_count": 43, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_game.set_chance_probs(small_game.root.infoset, [\"1/4\", \"1/2\", \"1/4\"])\n", "[act.prob for act in small_game.root.infoset.actions]" ] }, { "cell_type": "code", "execution_count": 44, "id": "9015e129", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Decimal('0.25'), Decimal('0.50'), Decimal('0.25')]" ] }, "execution_count": 44, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_game.set_chance_probs(small_game.root.infoset, [\".25\", \".50\", \".25\"])\n", "[act.prob for act in small_game.root.infoset.actions]" ] }, { "cell_type": "markdown", "id": "9f22d40d", "metadata": {}, "source": [ "As a further convenience, `pygambit` will accept Python `int` and `float` values.\n", "`int` values are always interpreted as `Rational` values.\n", "\n", "`pygambit` attempts to render `float` values in an appropriate `Decimal` equivalent.\n", "In the majority of cases, this creates no problems.\n", "For example," ] }, { "cell_type": "code", "execution_count": 45, "id": "0a019aa5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[Decimal('0.25'), Decimal('0.5'), Decimal('0.25')]" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "small_game.set_chance_probs(small_game.root.infoset, [.25, .50, .25])\n", "[act.prob for act in small_game.root.infoset.actions]" ] }, { "cell_type": "markdown", "id": "d53adcd4", "metadata": {}, "source": [ "However, rounding can cause difficulties when attempting to use `float` values to represent values which do not have an exact decimal representation" ] }, { "cell_type": "code", "execution_count": 46, "id": "1991d288", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "ValueError: set_chance_probs(): must specify non-negative probabilities that sum to one\n" ] } ], "source": [ "try:\n", " small_game.set_chance_probs(small_game.root.infoset, [1/3, 1/3, 1/3])\n", "except ValueError as e:\n", " print(\"ValueError:\", e)\n" ] }, { "cell_type": "markdown", "id": "89fefd34", "metadata": {}, "source": [ "This behavior can be slightly surprising, especially in light of the fact that\n", "in Python," ] }, { "cell_type": "code", "execution_count": 47, "id": "b1dc37fd", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1.0" ] }, "execution_count": 47, "metadata": {}, "output_type": "execute_result" } ], "source": [ "1/3 + 1/3 + 1/3" ] }, { "cell_type": "markdown", "id": "a06699af", "metadata": {}, "source": [ "In checking whether these probabilities sum to one, `pygambit` first converts each of the probabilities to a `Decimal` representation, via the following method" ] }, { "cell_type": "code", "execution_count": 48, "id": "dc1edea2", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Decimal('0.3333333333333333')" ] }, "execution_count": 48, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.Decimal(str(1/3))" ] }, { "cell_type": "markdown", "id": "4bfff415", "metadata": {}, "source": [ "and the sum-to-one check then fails because" ] }, { "cell_type": "code", "execution_count": 49, "id": "1edd90d6", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "Decimal('0.9999999999999999')" ] }, "execution_count": 49, "metadata": {}, "output_type": "execute_result" } ], "source": [ "gbt.Decimal(str(1/3)) + gbt.Decimal(str(1/3)) + gbt.Decimal(str(1/3))" ] }, { "cell_type": "markdown", "id": "5208b7a4", "metadata": {}, "source": [ "Setting payoffs for players also follows the same rules.\n", "Representing probabilities and payoffs exactly is essential, because `pygambit` offers (in particular for two-player games) the possibility of computation of equilibria exactly, because the Nash equilibria of any two-player game with rational payoffs and chance probabilities can be expressed exactly in terms of rational numbers.\n", "\n", "It is therefore advisable always to specify the numerical data of games either in terms of `Decimal` or `Rational` values, or their string equivalents.\n", "It is safe to use `int` values, but `float` values should be used with some care to ensure the values are recorded as intended." ] }, { "cell_type": "markdown", "id": "65def67e", "metadata": {}, "source": [ "#### References\n", "\n", "Myerson, Roger B. (1991) *Game Theory: Analysis of Conflict*. Cambridge: Harvard University Press.\n", "\n", "Reiley, David H., Michael B. Urbancic and Mark Walker. (2008) \"Stripped-down poker: A classroom game with signaling and bluffing.\" *The Journal of Economic Education* 39(4): 323-341." ] } ], "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 }