Experimental Analysis of Lemke Howson Algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from quantecon.game_theory import lemke_howson, NormalFormGame, Player\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def Experimental_Analysis(n, loops, capping = False):\n",
    "    \n",
    "    step = []\n",
    "    for i in range(loops):\n",
    "        num = 0\n",
    "        A,B = [np.random.rand(n, n) for i in range(2)]\n",
    "        q = NormalFormGame((Player(A), Player(B)))\n",
    "        if not capping:\n",
    "            num = lemke_howson(q, init_pivot = 0)[1]\n",
    "            step.append(num)\n",
    "        else:\n",
    "            for j in range(n):\n",
    "                num_iter, success = lemke_howson(q, init_pivot = j, max_iter = capping)[1:]\n",
    "                num += num_iter\n",
    "                if success:\n",
    "                    step.append(num)\n",
    "                    break\n",
    "            if not success:\n",
    "                num = lemke_howson(q, init_pivot = 0)[1]\n",
    "                step.append(num)\n",
    "                \n",
    "    return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "step1 = np.array(Experimental_Analysis(40, 10000, capping = 10))\n",
    "step2 = np.array(Experimental_Analysis(40, 10000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "55.871899999999997"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(step1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "110.6525"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(step2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX0AAAEACAYAAABfxaZOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAF3FJREFUeJzt3X+sZOV93/H3ZyEsxm7Itin3VkBYIlwHoqi2VeNKbiQk\nNxQnEqBWQlRqBXb9l5vaUqWW3VTVbv9pTKSq8h/ljzaOta2IKEllQ6rULAhfRalkIDXY1LsmW0W7\nwVvv2M0PVw4yAvPtH3Pm3rNzZ+6duXdm586c90tazZlnnnPO82jufs8zz/Oc56SqkCR1w6FFF0CS\ndOUY9CWpQwz6ktQhBn1J6hCDviR1iEFfkjpkoqCf5Pokv5XkbJJvJvlwkiNJTid5LckzSa5v5T+e\n5FyT/+75FV+SNI1JW/qfA363qm4H/gbwLeAY8FxVvQ94HjgOkOQO4AHgduBjwGNJMuuCS5Kmt2vQ\nT/LjwM9X1RcAqurtqvo+cB9wqsl2Cri/2b4XeKLJdx44B9w564JLkqY3SUv/VuD/JvlCkq8l+Q9J\nrgPWqqoHUFWXgBua/DcCr7f2v9ikSZIWbJKgfzXwQeDfV9UHgb+g37UzvH6D6zlI0gF39QR5vg28\nXlV/0Lz/r/SDfi/JWlX1kqwD320+vwjc3Nr/pibtMkm8SEjSHlTVnsdJd23pN104ryf5603SR4Fv\nAk8DDzdpDwFPNdtPAw8muSbJrcBtwItjjr2y/06cOLHwMlg/69fF+q1y3ar231aepKUP8Gng8SQ/\nBvwR8HHgKuDJJJ8ALtCfsUNVnUnyJHAGeAv4VM2ipJKkfZso6FfV14EPjfjo74zJ/6vAr+6jXJKk\nOfCO3Dm56667Fl2EubJ+y22V67fKdZuFLKrnJYm9PpI0pSTUPAdyJUmrw6AvSR1i0JekDjHoS1KH\nGPQlqUMM+pLUIQZ9SeoQg74kdYhBX5I6xKAvSR1i0JekDjHoS1KHGPQlqUMM+pLUIQZ9SeoQg74k\ndYhBX5I6xKAvSR1i0JekDjHoS1KHGPQlqUMM+pLUIQZ9SeoQg74kdYhBX5I6xKAvSR0yUdBPcj7J\n15O8nOTFJu1IktNJXkvyTJLrW/mPJzmX5GySu+dVeEnSdCZt6b8D3FVVH6iqO5u0Y8BzVfU+4Hng\nOECSO4AHgNuBjwGPJclsiy1J2otJg35G5L0PONVsnwLub7bvBZ6oqrer6jxwDriTCayvHyUJ6+tH\nJyyWJGkakwb9Ap5N8lKSTzZpa1XVA6iqS8ANTfqNwOutfS82aWMNgn2vdwGo5lWSNGtXT5jvI1X1\nnSR/FTid5DX6F4K24fcTGwT7/g8KSdK8TBT0q+o7zev3knyJfndNL8laVfWSrAPfbbJfBG5u7X5T\nk7bNyZMnW+82piu5JHXAxsYGGxsbMzteqnZuoCe5DjhUVT9I8m7gNPCvgY8Cf1pVjyZ5BDhSVcea\ngdzHgQ/T79Z5FnhvDZ0oyWZSf5x30NLvv+5WLknqoiRU1Z67RSZp6a8BX0xSTf7Hq+p0kj8Ankzy\nCeAC/Rk7VNWZJE8CZ4C3gE8NB3xJ0mLs2tKf24lt6UvS1Pbb0veOXEnqEIO+JHXIgQj6hwFI8ypJ\nmpdJ5+nP1Zs4S1+SroQD0dKXJF0ZBn1J6hCDviR1iEFfkjrEoC9JHWLQl6QOMehLUocY9CWpQwz6\nktQhBn1J6pADFfRdg0eS5utArL0z4Bo8kjRfB6qlL0maL4O+JHWIQV+SOsSgL0kdYtCXpA4x6EtS\nhxj0JalDDPqS1CEGfUnqEIO+JHWIQV+SOsSgL0kdYtCXpA6ZOOgnOZTka0mebt4fSXI6yWtJnkly\nfSvv8STnkpxNcvc8Ci5Jmt40Lf3PAGda748Bz1XV+4DngeMASe4AHgBuBz4GPJZkqtWSD/ePw9H1\n9Wl2kyTtYqKgn+Qm4BeBX28l3wecarZPAfc32/cCT1TV21V1HjgH3DlNoQbr6l/o9abZTZK0i0lb\n+v8O+Of0Y/HAWlX1AKrqEnBDk34j8Hor38UmTZK0YLs+OSvJLwG9qnolyV07ZK0dPhvp5MmTm9sb\n0+4sSR2wsbHBxsbGzI6Xqp1jdZJ/A/xD4G3gXcBfAr4I/E3grqrqJVkHvlJVtyc5BlRVPdrs/2Xg\nRFW9MHTcGpw7yeZjEre97lI+SeqSJFTVnp8qu2v3TlX9SlX9VFX9NPAg8HxV/SPgd4CHm2wPAU81\n208DDya5JsmtwG3Ai3stoCRpdvbzYPTPAk8m+QRwgf6MHarqTJIn6c/0eQv4VNlcl6QDYdfunbmd\n2O4dSZra3Lt3JEmrw6AvSR1i0JekDjHoS1KHLF3QX18/ShLW148uuiiStHSWbvZOf+22/qfO7JHU\nNc7ekSRNbImD/mG7eSRpSgc66O+8rn5/AeZe78IVLpUkLa+D36fP5X377T59+/YldY19+pKkiRn0\nJalDDPqS1CEGfUnqEIO+JHWIQV+SOsSgL0kdYtCXpA4x6EtShxj0JalDDPqS1CEGfUnqEIO+JHWI\nQV+SOmQFgr4PU5GkSa3Eevquqy+pKzqxnv7gCVpJOLzowkjSErt60QWYRP/BiH17vrxJknZv6Sc5\nnOSFJC8neTXJiSb9SJLTSV5L8kyS61v7HE9yLsnZJHfPswKSpMlN1Kef5LqqeiPJVcD/AD4N/H3g\nT6rq15I8AhypqmNJ7gAeBz4E3AQ8B7y3hk40dZ/+YD8Ym8s+fUmr7or06VfVG83mYfpdQgXcB5xq\n0k8B9zfb9wJPVNXbVXUeOAfcudcCSpJmZ6Kgn+RQkpeBS8CzVfUSsFZVPYCqugTc0GS/EXi9tfvF\nJm3ODm8O9jp9U5JGm2ggt6reAT6Q5MeBLyb5WbZ6XDazTXvykydPbm5vTLvzNlvDvb2ew72SVsPG\nxgYbGxszO97U8/ST/CvgDeCTwF1V1UuyDnylqm5Pcgyoqnq0yf9l4ERVvTB0nJn36bdz2b8vaRXN\nvU8/yU8OZuYkeRfwC8BZ4Gng4SbbQ8BTzfbTwINJrklyK3Ab8OJeCzgL6+tH7faRJCbr3vlrwKkk\nh+hfJP5LVf1ukq8CTyb5BHABeACgqs4keRI4A7wFfGp45s6V1utdAMpuH0mdtzzLMDT7XUu/9/4w\n8CbFYXLZ++bol3XvtJdusNtH0jLbb/fOUtyR2zYYrs2Y95Kk8ZZi7R1J0mwY9CWpQ1Y66A9m7UiS\n+pZuILedtjk4e9n7fq6qGrn2vgO5kpZZJ9bTnx2XapDUbZ1r6XvXrqRl1tmWfv8JWvbXS9I0ljbo\nt5+mJUmazNIGfUnS9Az6ktQhBn1J6hCDviR1iEFfkjrEoC9JHWLQl6QOWZmgv3WzVprt6QwWZ7vq\nqne7VIOklbXUyzDsmGfKZRi2592eR5IWrbPLMEiSpmfQl6QOMehLUocY9CWpQzoc9A87Q0dS51y9\n6AIsTn9x5l7PNfkldUeHW/qS1D0GfUnqkJUO+oO7dPdyh64kraKV7tMfPFLRXntJ6tu1pZ/kpiTP\nJ/lmkleTfLpJP5LkdJLXkjyT5PrWPseTnEtyNsnd86yAJGlyu669k2QdWK+qV5K8B/ifwH3Ax4E/\nqapfS/IIcKSqjiW5A3gc+BBwE/Ac8N4aOtE81965ln4rH9ot/fFHGr1OD7j2jqSDZu5r71TVpap6\npdn+AXCWfjC/DzjVZDsF3N9s3ws8UVVvV9V54Bxw514LuBeDbp39cy6/pNUy1UBukqPA+4GvAmtV\n1YP+hQG4ocl2I/B6a7eLTdoSGszlv7DogkjSTEw8kNt07fw28Jmq+kGS4cb01I3rkydPbm5vTLvz\nAq2vH6XXu8Da2i1cunR+0cWRtMI2NjbY2NiY2fEmWk8/ydXAfwP+e1V9rkk7C9xVVb2m3/8rVXV7\nkmNAVdWjTb4vAyeq6oWhY853Pf2h17326bfztMo+Ml2S5u1Kraf/G8CZQcBvPA083Gw/BDzVSn8w\nyTVJbgVuA17cawElSbMzyeydjwC/B7xKv3lbwK/QD+RPAjcDF4AHqurPm32OA/8YeIt+d9DpEce1\npS9JU9pvS391H5eIQV/S6vFxiZKkiRn096U/j9+5/JKWxUqvvTPsMPBm09nT396vrdvAXJdf0jLo\nVNBv36lriJbURXbvSFKHdCLoD9bVl6Su60TQn90CbJK03DoR9EcZtP6vpT/v1adrSeqCTg3ktrWf\nquXTtSR1RWdb+tOZfF399fWjztuXdGB1ZhmG3fIMnrbVn78//kjjl2zY/rwul2iQNGv7XYahs907\nw/b/EHUfwy7p4LN7R5I6xKAvSR1i0J+zwcBuEq666t0O8kpaKAdyR7zulGuStfdH52XbZ5I0LdfT\nlyRNzKAvSR1i0N/BYKkGl2iQtCqcp78DZ95LWjW29CWpQwz6Q7bW3p9n+373tXxcw0fSPDhlc8I8\ns56yudvUzfY5nN4pacApmwswuwHeyVfvlKRZcCB3Av2VN7eC/GCA91pg8DvgMFtrbE6uf6Rez6Fi\nSVeGLf0JtB+32O92uTy92EvAl6Qrz6A/hYP6rF0HfSVNyoHcfeQZzgvFYbL5MJYfTjCQO26wdpqB\nXAd9pe6Y+0Buks8n6SX5RivtSJLTSV5L8kyS61ufHU9yLsnZJHfvtWDLavBrwO4eSQfRJN07XwD+\n7lDaMeC5qnof8DxwHCDJHcADwO3Ax4DH0u4E164GXTXj0u3CkbQfuwb9qvp94M+Gku8DTjXbp4D7\nm+17gSeq6u2qOg+cA+6cTVEPtq2buvan17vAqJGDQXr/VZL2Zq8DuTdUVQ+gqi4BNzTpNwKvt/Jd\nbNJW3vAg72H6fW+j5vK7kJukRZnVPH1HD4fstFibC7lJWpS9Bv1ekrWq6iVZB77bpF8Ebm7lu6lJ\nG+nkyZOb2xt7LMhBN7ixa2t7+2fXsjX/f/tNXodH9vFL6oaNjQ02NjZmdryJpmwmOQr8TlX9XPP+\nUeBPq+rRJI8AR6rqWDOQ+zjwYfrdOs8C760RJ1nFKZu75bmWrYC+29TPvU3v7J9hbe0WLl06j6TV\ns98pm7u29JP8JnAX8FeS/DFwAvgs8FtJPgFcoD9jh6o6k+RJ4AzwFvCpUQG/q+bfreOyDpJ25s1Z\n+8gzr3PuvaXvTVrSqnOVTUnSxAz6S2zcjVyDwd9RN3N5k5fUbXbv7CPPort3RnXrjDpiVbG+frR1\nY5ddQNKysntnxc3qRq5xd/pK6hYfonLAeSOXpFmypX/AXLklGsb3+w/Y/y+tHoP+AbPb0syDNX3G\nresz/ZnGL+K210XevFhIB5cDufvIM89zjrp7d3MAtpV31JEGD3KB7Q9zaT/k5c2hwd5he304iw91\nkebHgdwVNWrVzkl79kc9u3ew/34f8mIrXlpuDuQuiVEDuu0F237YjAMMB/NBdxAj9m/nSrLDmj3D\ni7651IO0rAz6S6x9IRh0CQ2H9XGzf7av/rlTIG//7jDYS8vM7p0VMtwlNEneUV094+/0lbTsbOlr\n27r+/f5/7w6QVpEtfW22+n/I6MHfrW6jaaeJHh476DvNgPDR9XWScHR9faqzS9rOKZv7yLPK52xP\nDx21NtBg6ucta2ucv3RpaG0fth1xp+Wgd/sbvOzvwymg6ri5P0RFGmVzgLjXa/X/9wNy/4KwfTbR\n9guDpCvN7h1tM809AX2Xt77H3Quwtejb5XcgzGPev/cTSKPZvbOPPF085/CdwoP3/XsFtrQ/G74r\neNxZx/0t7qV7x7uCtaq8I1dX1PC00OFB4FGf7fXu31FsvUv7Y5++5m5wV/C4O4bb00WvO3SIv/jR\nj3Y4mncDS/thS19zt1OLf/iXwhvvvLOvcw368ndaonp4CuhO/f9OF9WqsU9/H3k85/R5Lp/hw2bK\nIM9gHOC6Q4cuuwBcvn8/V3utoMHMoPavia19+gb5B39v7TGHN8f0/ztdVAeNffpaGluzgjJ2yYhB\n+o9GtPi3bhbrh/Xv9y5sPlvg+81U0NHH7Y82DE8XvTzvVhfTTi37wa+CJLz7qqt2/RXgLCIdNLb0\n95HHcx78c7ZnG7VnGO12vFHPM6gRM5Danx1dX+dCr7d5wxrgLCLNnC19aQftheUG4wbT7DcwGIxu\nL0kx/NmFXo8CLjU3rE36dLNpxg32MsbguITaDPrSBCaZmjr8vhg/XXUQiNsXiwu93sg87WC9W952\n/kHaqIuRF4DuMuhLV8Thy8YBBoF4+JfHqDztYL11tNF52xeEQdpA+2I0fNGYZAbT4FzDrzuNb4y6\nGC2bVahDm0FfuiL6IfeNd94Z28U06AoaztMO1sNp/RlO048VDC4agyA2WCLjz5vB8VG/LgblGn5t\nbw9fTEZdjAbm3a01K6PqcCXLM/NzVdVc/gH3AN8C/hB4ZMTnNQBUNX/XO70etDye03Puludw877/\nuv1vfb/lGhx/1DknOc5O5WOX4+x0vFvW1i77v93+7LpDh7Yft6puWVvbTB/s305r520b5BnsM4lR\n+4w7zrZ6DsesCc/Vrvdge5IyD5+reWWv//a8444H7f+C+N/ALcCPAa8APzOUZ3SlrtB/xoMaJDzn\nap5zXCBedLnGla/9fhbH22n/aS5c7fThi8fmBSzZTB8OqjtdRIaPc+2k5arRF6xx8W1UfXa6CAyf\nq3llr//m1b1zJ3Cuqi5U1VvAE8B9czqXdOBN8yjLRdhpMHoWx5s27273cRTju8HerNrMMxgPGXSN\nDI9z7FSeUbO9RpVreExlcM7BOMck5xruHmuPI8zavNbeuRF4vfX+2/QvBJJ0xQyC6rWXPfdhy2Bs\nY69GrSe1+ayJJpBPc/R2eQYXl1mH/YUuuLa2tsY999yzyCJI6oDNQDwmnRGf7ee4ezXr440ylzty\nk/wt4GRV3dO8P0a/H+rRVp6D/GtXkg6s2scdufMK+lcBrwEfBb4DvAj8g6o6O/OTSZImNpfunar6\nUZJfBk7Tn8nzeQO+JC3ewhZckyRdeQu5IzfJPUm+leQPkzyyiDLMWpLzSb6e5OUkLzZpR5KcTvJa\nkmeSXL/ock4iyeeT9JJ8o5U2ti5Jjic5l+RskrsXU+rJjanfiSTfTvK15t89rc+WrX43JXk+yTeT\nvJrk0036SnyHI+r3T5v0pf8OkxxO8kITR15NcqJJn913N4+bs/Z749Yy/gP+CDgylPYo8C+a7UeA\nzy66nBPW5W8D7we+sVtdgDuAl+l3FR5tvtssug57qN8J4J+NyHv7EtZvHXh/s/0e+uNrP7Mq3+EO\n9VuJ7xC4rnm9Cvgq/enuM/vuFtHSX9Ubt8L2X073Aaea7VPA/Ve0RHtUVb8P/NlQ8ri63As8UVVv\nV9V54BwH/J6MMfWD0TPl7mP56nepql5ptn8AnAVuYkW+wzH1u7H5eOm/w6p6o9k8TD+YFzP87hYR\n9EfduHXjmLzLpIBnk7yU5JNN2lpV9aD/hwrcsLDS7d8NY+oy/H1eZHm/z19O8kqSX2/9fF7q+iU5\nSv9XzVcZ//e4tHVs1e+FJmnpv8Mkh5K8DFwCnq2ql5jhd+cqm7Pzkar6IPCLwD9J8vNsv2N7lUbN\nV6kuAI8BP11V76f/n+3fLrg8+5bkPcBvA59pWsQr9fc4on4r8R1W1TtV9QH6v87uTPKzzPC7W0TQ\nvwj8VOv9TU3aUquq7zSv3wO+RP8nVi/JGkCSdeC7iyvhvo2ry0Xg5la+pfw+q+p71XSSAv+RrZ/I\nS1m/JFfTD4j/uaqeapJX5jscVb9V+w6r6v8BG/RXLJ7Zd7eIoP8ScFuSW5JcAzwIPL2AcsxMkuua\nVgdJ3g3cDbxKv14PN9keAp4aeYCD6fJnAo6vy9PAg0muSXIrcBv9m/EOusvq1/xHGvh7wP9qtpe1\nfr8BnKmqz7XSVuk73Fa/VfgOk/zkoFsqybuAX6A/ZjG7725Bo9P30B9xPwccW/Ro+Qzqcyv9WUgv\n0w/2x5r0vww819T1NPATiy7rhPX5TeD/0F8K5I+BjwNHxtUFOE5/1sBZ4O5Fl3+P9ftPwDea7/FL\n9PtQl7V+HwF+1Pqb/Frzf27s3+My1XGH+i39dwj8XFOfV5q6/MsmfWbfnTdnSVKHOJArSR1i0Jek\nDjHoS1KHGPQlqUMM+pLUIQZ9SeoQg74kdYhBX5I65P8DbleKhWi1p/oAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x11de597b8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure()\n",
    "\n",
    "for (step, c) in zip([step1, step2], ['b', 'r']):\n",
    "    plt.hist(step, bins=np.arange(0, 300, 2), color = c)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "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
}