Support Enumeration (for Nondegenerate Games).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def best_response(payoff_matrixs, k, br):\n",
    "    \"\"\"\n",
    "    Given the a submatrix of player's payoff matrix\n",
    "    return by best response (may not be NE)\n",
    "    \"\"\"\n",
    "    for M in payoff_matrixs:\n",
    "        # contruct matrix and vector to be solved\n",
    "        C = np.empty((k+1, k+1))\n",
    "        C[:-1, :-1] = M\n",
    "        C[-1, :-1] = 1\n",
    "        C[:-1, -1] = -1\n",
    "        C[-1, -1] = 0\n",
    "        e = np.zeros(k+1)\n",
    "        e[-1] = 1\n",
    "        # use try-except block, because LinAlgError may raise\n",
    "        try:\n",
    "            br.append(np.linalg.solve(C, e))\n",
    "        except np.linalg.LinAlgError:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def support_Enumeration(A, B):\n",
    "    NEs = {}\n",
    "    m, n = A.shape\n",
    "    M = np.arange(m)\n",
    "    N = np.arange(n)\n",
    "    K = np.min([m, n])\n",
    "    for k in np.arange(1, K+1, 1):\n",
    "        NEs[k] = []\n",
    "        for I in combinations(range(m), k):\n",
    "            for J in combinations(range(n), k):\n",
    "                AIJ = A[I, :][:, J]\n",
    "                BJI = B[I, :][:, J].T\n",
    "                br = []\n",
    "                if best_response([AIJ, BJI], k, br):\n",
    "                    s1, s2 = br\n",
    "                else:\n",
    "                    continue\n",
    "                # Now let's check whether the solution satisfies NE\n",
    "                if (s1[:-1] > 0).all() & (s2[:-1] > 0).all():\n",
    "                    if (A[np.setdiff1d(M, I), :][:, J] @ s1[:-1] <= s1[-1]).all() \\\n",
    "                         & (B[I, :][:, np.setdiff1d(N, J)].T @ s2[:-1] <= s2[-1]).all():\n",
    "                        xI = np.zeros(m)\n",
    "                        xI[np.array(I)] = s2[:-1]\n",
    "                        yJ = np.zeros(n)\n",
    "                        yJ[np.array(J)] = s1[:-1]\n",
    "                        NEs[k].append({'yJ': yJ,\n",
    "                                       'u': s1[-1],\n",
    "                                       'xI': xI,\n",
    "                                       'v': s2[-1]})\n",
    "                else:\n",
    "                    continue\n",
    "    return NEs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a = np.matrix([[3,3],[2,5],[0,6]])\n",
    "b = np.matrix([[3,2],[2,6],[3,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: [{'u': 3.0,\n",
       "   'v': 3.0,\n",
       "   'xI': array([ 1.,  0.,  0.]),\n",
       "   'yJ': array([ 1.,  0.])}],\n",
       " 2: [{'u': 3.0,\n",
       "   'v': 2.7999999999999998,\n",
       "   'xI': array([ 0.8,  0.2,  0. ]),\n",
       "   'yJ': array([ 0.66666667,  0.33333333])},\n",
       "  {'u': 4.0,\n",
       "   'v': 2.6666666666666665,\n",
       "   'xI': array([ 0.        ,  0.33333333,  0.66666667]),\n",
       "   'yJ': array([ 0.33333333,  0.66666667])}]}"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support_Enumeration(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = np.matrix(\n",
    "    [[    9504,     -660,    19976,   -20526,     1776,    -8976],\n",
    "     [ -111771,    31680,  -130944,   168124,    -8514,    52764],\n",
    "     [  397584,  -113850,   451176,  -586476,    29216,  -178761],\n",
    "     [  171204,   -45936,   208626,  -263076,    14124,   -84436],\n",
    "     [ 1303104,  -453420,  1227336, -1718376,    72336,  -461736],\n",
    "     [  737154,  -227040,   774576, -1039236,    48081,  -300036]]\n",
    ")\n",
    "B_T = np.matrix(\n",
    "    [[   72336,  -461736,  1227336, -1718376,  1303104,  -453420],\n",
    "     [   48081,  -300036,   774576, -1039236,   737154,  -227040],\n",
    "     [   29216,  -178761,   451176,  -586476,   397584,  -113850],\n",
    "     [   14124,   -84436,   208626,  -263076,   171204,   -45936],\n",
    "     [    1776,    -8976,    19976,   -20526,     9504,     -660],\n",
    "     [   -8514,    52764,  -130944,   168124,  -111771,    31680]]\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "75"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.sum([len(i) for i in support_Enumeration(A,B_T.T).values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}