solver_comparison.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compare different Nash equilibrium solvers\n",
    "1. time\n",
    "2. success rate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from equilibrium_solver import *\n",
    "import numpy as np\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/quantumiracle/anaconda3/envs/x/lib/python3.7/site-packages/pulp/pulp.py:1711: UserWarning: Overwriting previously set objective.\n",
      "  warnings.warn(\"Overwriting previously set objective.\")\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                        Solver      Time  Failure rate\n",
      "0         NashEquilibriaSolver  0.208456          0.00\n",
      "1        NashEquilibriumSolver  0.000571          0.00\n",
      "2      NashEquilibriumLPSolver  0.013513          0.00\n",
      "3   NashEquilibriumCVXPYSolver  0.003935          0.00\n",
      "4  NashEquilibriumGUROBISolver  0.000951          0.14\n",
      "5    NashEquilibriumECOSSolver  0.000384          0.00\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/home/quantumiracle/anaconda3/envs/x/lib/python3.7/site-packages/ecos/ecos.py:26: UserWarning: Converting G to a CSC matrix; may take a while.\n",
      "  warn(\"Converting G to a CSC matrix; may take a while.\")\n",
      "/home/quantumiracle/anaconda3/envs/x/lib/python3.7/site-packages/ecos/ecos.py:29: UserWarning: Converting A to a CSC matrix; may take a while.\n",
      "  warn(\"Converting A to a CSC matrix; may take a while.\")\n"
     ]
    }
   ],
   "source": [
    "itr = 100  # number of test matrices\n",
    "matrix_size = (6, 6)\n",
    "t_list=[]\n",
    "fail_list=[]\n",
    "\n",
    "solvers = [NashEquilibriaSolver, NashEquilibriumSolver, NashEquilibriumLPSolver, NashEquilibriumCVXPYSolver, NashEquilibriumGUROBISolver, NashEquilibriumECOSSolver]\n",
    "# print(solvers)\n",
    "\n",
    "# generate random matrices for test\n",
    "rand_matrices=[np.array(np.random.uniform(-1, 1, matrix_size)) for _ in range(itr)]\n",
    "\n",
    "for solver in solvers:\n",
    "    t0 = time.time()\n",
    "    fail = 0.\n",
    "    for i in range(itr):\n",
    "        try:\n",
    "            solver(rand_matrices[i])\n",
    "        except:  # TODO this is not accurate since sometimes it returns wrong results but no error\n",
    "            # print(rand_matrices[i])\n",
    "            fail+=1\n",
    "    t1=time.time()\n",
    "    t_list.append((t1-t0)/itr)\n",
    "    fail_list.append(fail/itr)\n",
    "\n",
    "solvers = [s.__name__ for s in solvers]\n",
    "results = {'Solver': solvers, 'Time': t_list, 'Failure rate': fail_list}\n",
    "import pandas as pd\n",
    "df = pd.DataFrame(results)\n",
    "print(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "-0.21943068402422208\n",
      "1\n",
      "0.11823117232687501\n",
      "2\n",
      "0.42183561498487365\n",
      "3\n",
      "1.2118251625908834\n",
      "4\n",
      "-1.1603927897100847\n",
      "5\n",
      "-3.4270418308104977\n",
      "6\n",
      "-0.778322127602816\n",
      "7\n",
      "-0.1724547018305776\n",
      "8\n",
      "-0.13103288229400437\n",
      "9\n",
      "0.825318321187979\n",
      "10\n",
      "1.5512597820907925\n",
      "11\n",
      "-0.32914406881714847\n",
      "12\n",
      "-0.36389052891648854\n",
      "13\n",
      "0.01209214350701601\n",
      "14\n",
      "1.2707624912505255\n",
      "15\n",
      "0.40887028507482226\n",
      "Not solved matrix:  [[-0.41301346  0.03481041 -0.12241227  0.63579532  0.1566146   0.47455712]\n",
      " [-0.9480402   0.79097008 -0.86289357  0.05175797  0.24760642  0.65818024]\n",
      " [-0.79550654  0.590004    0.2312181   0.52699437  0.24746801  0.89843936]\n",
      " [-0.53679791  0.68036029 -0.57018641  0.49281511 -0.02027984 -0.02856437]\n",
      " [-0.86130637  0.33901386  0.88523092 -0.93055369 -0.03208438  0.40901916]\n",
      " [-0.65256575  0.30034441 -0.97946958 -0.70661677 -0.65086773  0.96750481]]\n",
      "16\n",
      "0.5341072191627828\n",
      "17\n",
      "-0.4509151694470714\n",
      "18\n",
      "0.6301634837120715\n",
      "19\n",
      "-0.6740257502476832\n"
     ]
    }
   ],
   "source": [
    "# Gurobi solver does not work in all cases\n",
    "import numpy as np\n",
    "matrix_size = (6, 6)\n",
    "# a=np.array([[ 0.036,  0.023,  0.042,  0.001, -0.002, -0.029],\n",
    "#  [ 0.031, -0.026,  0.062, -0.034,  0.017, -0.043],\n",
    "#  [ 0.004, -0.011, -0.026, -0.066, -0.008, -0.031],\n",
    "#  [-0.03,  -0.032,  0.032, -0.026,  0.01,   0.001],\n",
    "#  [-0.009,  0.042,  0.047, -0.023, -0.03,  -0.001],\n",
    "#  [ 0.024,  0.034,  0.017,  0.017, -0.043, -0.061]])\n",
    "# print(np.linalg.det(a))\n",
    "a=np.array([[95, 97], [97, 97]])\n",
    "NashEquilibriumGUROBISolver(a)\n",
    "\n",
    "for i in range(20):\n",
    "    print(i)\n",
    "    a=np.array(np.random.uniform(-1, 1, matrix_size))\n",
    "    print(np.linalg.det(a))\n",
    "    try:\n",
    "        NashEquilibriumGUROBISolver(a)\n",
    "    except:\n",
    "        print('Not solved matrix: ', a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "28c6861e59928cb790236f7047915368f37afc12f670e78fd0101a6f825a02b1"
  },
  "kernelspec": {
   "display_name": "Python 3.7.0 64-bit ('x': conda)",
   "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.7.0"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}