{
 "metadata": {
  "name": "",
  "signature": "sha256:dd064037a0c52bdc3ee1de09800702443e3f14abdbdd7f69f14d806ffa17ece8"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%pylab inline"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Populating the interactive namespace from numpy and matplotlib\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Elementary notions from game theory"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Game theory is a mathematical field dealing with the analysis of strategic interactions, of the kind found in games but also in things like economic behavior, international relations, decision makiing under uncertainty and so on. Game theory is a deep and exciting mathematical theory, but some of the elementary notions from game theory are easy to grasp and have become standard terminology in discussions of social behavior. They are often used by philosophers. Moreover, games, in the formal sense of game theory, are very often used as a modeling framework for studying social behavior, and are thus used to discuss justice, fairness, cooperation, norms and so on. \n",
      "\n",
      "Here I am just going to show some of the most basic notions from game theory and Python code for the simplest of cases. \n",
      "\n",
      "We start with some definitions. They are given here mostly for review. \n",
      "\n",
      "A *game* consists of a set of players, a set of possible moves (actions) each player can make, and a payoff function indicating the payoff each player gets depending on the moves made by every player (including herself, of course). Typically, positive numbers are cosnidered good, the higher the better, while negative payoff represents unwanted outcomes.\n",
      "\n",
      "\n",
      "A *strategy* of a player is, for now, simply an action in the game. For example, playing \"Rock\" in Rock-Paper-Scissors.\n",
      "\n",
      "The *best response strategy* for a player is the action that gives them the highest payoff *given* the actions made by all other players. \n",
      "\n",
      "A *Nash equilibrium* is a situation in which each player plays the best response strategy to all other players. Thus in a Nash equilibrium, no one has any incentive to change his or her strategy: each player is doing the best given how other players are acting! As we will see, this does not mean everyone is getting the best possible outcome: indeed, everyone might be better off in a different scenario. This is what happens in the Prisoners' Dillema, for example. \n",
      "\n",
      "First, we define some helper functions. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Helper functions\n",
      "\n",
      "def other(x):\n",
      "    return 1-x\n",
      "\n",
      "def first(x):\n",
      "    return x[0]\n",
      "\n",
      "def second(x):\n",
      "    return x[1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Print a 2x2 psayoff matrix\n",
      "def print_mat(payoffs):\n",
      "    for i in range(2):\n",
      "        for j in range(2):\n",
      "            print payoffs[i][j],\n",
      "        print"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Find Nash equilibria (2x2 matrix)\n",
      "\n",
      "def Nash(payoffs):\n",
      "    for i in range(2):\n",
      "        for j in range(2):\n",
      "            if first(payoffs[i][j])>=first(payoffs[other(i)][j]) and second(payoffs[i][j])>=second(payoffs[i][other(j)]):\n",
      "                    print moves[i],moves[j],' ===> resulting in:',payoffs[i][j]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# prisoners dillema\n",
      "\n",
      "moves=['C','D']\n",
      "payoffs=[[(-1,-1),(-3,0)],[(0,-3),(-2,-2)]]\n",
      "\n",
      "print_mat(payoffs)\n",
      "Nash(payoffs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(-1, -1) (-3, 0)\n",
        "(0, -3) (-2, -2)\n",
        "D D  ===> resulting in: (-2, -2)\n"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Note that both players would have been better of if they **both** chose to play C (\"cooperate\"). Why isn't (-1,-1) a Nash equilibrium?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Coordination games"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the coordination games we will find more than one Nash equilibrium."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Choosing sides\n",
      "\n",
      "moves=['left','right']\n",
      "payoffs=[[(10,10),(0,0)],[(0,0),(10,10)]]\n",
      "print_mat(payoffs)\n",
      "Nash(payoffs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(10, 10) (0, 0)\n",
        "(0, 0) (10, 10)\n",
        "left left  ===> resulting in: (10, 10)\n",
        "right right  ===> resulting in: (10, 10)\n"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Pure coordination game\n",
      "\n",
      "moves=['Party','Home']\n",
      "payoffs=[[(10,10),(0,0)],[(0,0),(5,5)]]\n",
      "print_mat(payoffs)\n",
      "Nash(payoffs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(10, 10) (0, 0)\n",
        "(0, 0) (5, 5)\n",
        "Party Party  ===> resulting in: (10, 10)\n",
        "Home Home  ===> resulting in: (5, 5)\n"
       ]
      }
     ],
     "prompt_number": 70
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Battle of the sexes\n",
      "\n",
      "moves=['Party','Home']\n",
      "payoffs=[[(10,5),(0,0)],[(0,0),(5,10)]]\n",
      "print_mat(payoffs)\n",
      "Nash(payoffs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(10, 5) (0, 0)\n",
        "(0, 0) (5, 10)\n",
        "Party Party  ===> resulting in: (10, 5)\n",
        "Home Home  ===> resulting in: (5, 10)\n"
       ]
      }
     ],
     "prompt_number": 71
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Stag hunt\n",
      "\n",
      "moves=['Stag','Hare']\n",
      "payoffs=[[(10,10),(0,8)],[(8,0),(7,7)]]\n",
      "print_mat(payoffs)\n",
      "Nash(payoffs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(10, 10) (0, 8)\n",
        "(8, 0) (7, 7)\n",
        "Stag Stag  ===> resulting in: (10, 10)\n",
        "Hare Hare  ===> resulting in: (7, 7)\n"
       ]
      }
     ],
     "prompt_number": 73
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Mixed strategy for coordination games\n",
      "\n",
      "Since there is more than a single Nash equilibrium, we look for a *mixed strategy* in which we decide which action to take randomly. In other words, the strategy is a probability distribution over the possible actions. \n",
      "\n",
      "Notation is the same as [Wikipedia](https://en.wikipedia.org/wiki/Coordination_game#Mixed_strategy_Nash_equilibrium)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def mixed(payoff):\n",
      "    top,bottom=payoffs\n",
      "    (A,a),(C,c)=top\n",
      "    (B,b),(D,d)=bottom\n",
      "    \n",
      "    print \"Player 1\"\n",
      "    p = float((d-b))/(a+d-b-c) \n",
      "    print p, \"for \",moves[0]\n",
      "    print 1-p, \"for \",moves[1]\n",
      "    \n",
      "    print \"Player 2\"\n",
      "    q = float((D-C))/(A+D-B-C)\n",
      "    print q, \"for \",moves[0]\n",
      "    print 1-q, \"for \",moves[1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 105
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "moves=['Party','Home']\n",
      "payoffs=[[(10,5),(0,0)],[(0,0),(5,10)]]\n",
      "print_mat(payoffs)\n",
      "mixed(payoffs)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "(10, 5) (0, 0)\n",
        "(0, 0) (5, 10)\n",
        "Player 1\n",
        "0.666666666667 for  Party\n",
        "0.333333333333 for  Home\n",
        "Player 2\n",
        "0.333333333333 for  Party\n",
        "0.666666666667 for  Home\n"
       ]
      }
     ],
     "prompt_number": 106
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Aside\n",
      "\n",
      "Here is how you get the formula for $p$ and $q$. Suppose you are player 1, your payoff will depend on how player **2** behaves, hence on $q$. So you calculate your expected payoff (which depends on $q$) for each of your possible actions (UP or DOWN). Your strategy is to be as indifferent about the other player as possible (some call this randomizing the other player). Think *why* this is the case (hint: think of the idea of \"best response\"). To be indifferent, we write down formulas for player 1's expected payoff for each of her possible actions and look for the value of $q$ that makes the expected payoff equal in tboth cases. We do the same for player 2, to calculate the value of $p$.\n",
      "\n",
      "Note that this may be somewhat confusing: we get the formula for player's 2 strategy, $q$, by thinking of player 1. Well, maybe this isn't too surprising...\n",
      "\n",
      "**Modeling question:** What does this mean about what the agents are presumed to *know* about the game?\n",
      "\n",
      "**Here is the algebra:**\n",
      "\n",
      "          Left(q) Right\n",
      "    Up(p) (A,a)   (C,c)\n",
      "\n",
      "    Down  (B,b)   (D,d) \n",
      "    \n",
      "Up payoff: $qA+(1-q)C$\n",
      "\n",
      "Down payoff $qB+(1-q)D$\n",
      "\n",
      "Setting $Up=Down$ gives us:\n",
      "\n",
      "$qA+(1-q)C=qB+(1-q)D$\n",
      "\n",
      "Rearranging we get:\n",
      "\n",
      "$q = \\frac{D-C}{A+D-B-C}$\n",
      "\n",
      "Similarly for p we get:\n",
      "\n",
      "$p = \\frac{d-b}{a+d-b-c}$\n"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Here is how you can get the computer to do the algebera for you.\n",
      "\n",
      "from sympy import *\n",
      "init_printing()\n",
      "\n",
      "a,b,c,d,p = symbols(\"a b c d p\")\n",
      "A,B,C,D,q = symbols(\"A B C D q\")\n",
      "\n",
      "# to find p where LEFT=RIGHT we solve LEFT-RIGHT=0 for p.\n",
      "print \"p=\"\n",
      "pretty_print(solve(\"p*a + (1-p)*b - p*c - (1-p)*d\",p))\n",
      "\n",
      "# to find q where UP=DOWN we solve UP-DOWN=0 for q.\n",
      "print \"q=\"\n",
      "pretty_print(solve(\"q*A + (1-q)*C - q*B - (1-q)*D\",q))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "p=\n",
        "\u23a1    -b + d   \u23a4\n",
        "\u23a2\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u23a5\n",
        "\u23a3a - b - c + d\u23a6"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "q=\n",
        "\u23a1    -C + D   \u23a4\n",
        "\u23a2\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u23a5\n",
        "\u23a3A - B - C + D\u23a6"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "### Modelling perspective: interpreting mixed strategies\n",
      "\n",
      "In some games the idea of resorting to a mixed strategy is quite intuitive. If two (or more) possible outcomes seem possible when we consider what the other player might do, it might make sense to randomize so that our cummulative payoff will reflect the relative preference we have for each outcome. It seems this should lead to maximal cummulative payoff (*why?*). The expected payoff of a mixed strategy also agrees nicely with the notion of *subjective expected utility*.\n",
      "\n",
      "A mixed strategy seems to presussopse multiple interactions, rather than a one-shot game. In a sense, then, probability or ranndomness represents time. Alternatively, we can think about mixed strategy as representing interactions in a population. According to this interpretation we can imagine two agents being chosen at random from the population (accodrding to the mixed strategy probabilities) and pitted against each other, each playing one of the non-mixed strategies. It is helpful to reflect on the fact that these intrepretations carry with them substantive assumptions about the temporal strcture of the situation or the role and structure of the population. As always, such assumptions are typically not netural with respect to the phenomemon we are studying.\n",
      "\n",
      "From the perspective of the agents, randomization can be a method of *confusing* the opponent. Alternatively, it can be used when players are *uncertain* about the other players actions and want to remain \"indifferent\" to their choices (we saw that in coordination games). More fundamentally, mixed strategies may be used not only to represent multiple interactions (repeated games) or interaction with players drawn from a heterogenous population but to enable agents to handle these situations appropriately.\n",
      "\n",
      "**Food for thought:** In the context of coordination games (in particular) it might be argued that a mixed strategy ensures fairness to some extent since the preferred outcomes of both players will occur, and with the appropriate frequency. Discuss. \n",
      " \n",
      "\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Rock-Paper-Scissors\n",
      "\n",
      "This is a zero-sum game. Let's denote the the actions by **R**ock, **P**aper, **S**cissors.\n",
      "\n",
      "The payoff matrix for the first player (on rows) is:\n",
      "\n",
      "        R    P   S\n",
      "    R   0   -1   1\n",
      "    \n",
      "    P   1    0  -1  \n",
      "    \n",
      "    S  -1    1   0\n",
      "    \n",
      "Let r,p,s be the probability the player 2 chooses the corresponding action and write down the expected payoff of player 1. \n",
      "\n",
      "\n",
      "Player 1 chooses R: $0r-1p+1s$\n",
      "\n",
      "Player 1 chooses P: $1r+0p-1s$\n",
      "\n",
      "Player 1 chooses S: $-1r+1p+0s$\n",
      "\n",
      "We want R=P, P=S, $r+p+s=1$. Which we will represent as R-P=0; P-S=0; 1-r-p-s=0.\n",
      "\n",
      "That's three equations in three variables, and the computer can easily solve the system for us."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "r,p,s = symbols(\"r p s\")\n",
      "\n",
      "solve([\"-p+s-r+s\",\n",
      "       \"r-s+r-p\",\n",
      "       \"1-r-p-s\"])\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "latex": [
        "$$\\left \\{ p : \\frac{1}{3}, \\quad r : \\frac{1}{3}, \\quad s : \\frac{1}{3}\\right \\}$$"
       ],
       "metadata": {},
       "output_type": "pyout",
       "png": "iVBORw0KGgoAAAANSUhEUgAAANcAAAAyBAMAAAA92lO3AAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAEJlUzSJmiTKrRN3v\ndrsdCiq5AAADSElEQVRYCe1Wz2sTQRT+Nj/bNE1Cr1UTCx4qovkDhMaePCgEiygUm5zEW3Prodqm\nIHgRbC+ehAZBKijWX5fioQo9SBEtCN5KSvUgIrS1VWyrrTtvZ5P9MZmdlKQH6UBm3vve997HvMzu\nLKCPjhSbmzkGSmZ1/0bWNJu1hnYSvPRgQaARMKOCmAmpcHCG2P3PjKSWTTPZsgZXvMVUOBhYo6pB\nLtJquBYlQFue9BRT4eBIN69+qkgC8YxNhztlTzFAhdPOxabzVDg5vh9iudQ+ivEt7c/ODsRE54ew\nek7jQRub3sbuDzP5miI8oMLx3du+S3Tpf+alVG/8vxe7U6i3JXvhx5coa7C0l+R6cwKvKeMVmyMj\nlxcnmDHDphpjamJqkYVkHIQXrzFOm+Pi8v9iaPgnza0vMKIb2hzzaozCl/R3PSTl4CyWWfqhDJst\nYzKrO9dLDOkLjGOQGZLRkp7BQ0mcQsFVjAk5rfNAJzUPiXgao4kKa5eN1YprGJq2ZUWEHGh/jltI\ncSIZwOkFdB41zOkEWIukw++UF7Gf7C6JYODRAnCiSLFhaD/EpCrqy1TtWlYfDtMhcMV9ehvh+014\nL0JvXAQHEC04AIF7DhDvf7TI2C8pZQe3mWc/ackMxcwpVyJLyvmKdr1d7tMY+Uu55ZK+RLZuHCPP\n9gy18Y8+iuhd56uMc+XTR2I5n7OYsd8ca074KS/El0tDn5n1wI7aPRVOcGgkTVn8UziZ0r0Am6oj\nmEJPXnfZr9ZQ4eACjFcHrFdM0tA3C7evI67vVcubgGBV4aCcxjblWsT8s+dt5SLzYIcjZAMdjgoH\nj0vaBuVZxBx1mEttFOBWSIUjaKO1hGH3uiEXosLhp0G2s5bhlKu0E1Dh4NZzI00mpt8GRWdxt6/C\nCb+lPLlY1PPtBahw8C7B1CRiwSxi6+6d2BAVDi4CK/RUScTia4jRPW4rb3dUONhNYCXP8iRi0SW0\niW+KqqAKB++B2ayHWCiPnoVqXaGlwsFV+I3XPb0UKxu0F7zf9c0OCDwVTqTrZIlScylaohlamjzx\nT+GY/dJqkqhxUSPo+e3RAH1thxcpex2FBoj1m6+I0GaiAeWkJfxzFYmOcSmzAcGbeVbkH4mC9R25\n3MdNAAAAAElFTkSuQmCC\n",
       "prompt_number": 20,
       "text": [
        "{p: 1/3, r: 1/3, s: 1/3}"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In other words, play each action with equal probability (could you have guessed this without doing the math?)"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}