"""
-----------------------------------------------
--------------- NashEq Finder -----------------
-----------------------------------------------
This file contains a python implementation of the NashEq Finder algorithm (and its dependencies) presented in

Zomorrodi, AR, Segre, D, "Genome-driven evolutionary game theory helps understand the rise of metabolic interdependencies in microbial communities"

This script can identify all pure strategy Nash equilibria of a game with any number of players
and strategies in one shot.

NOTE:
1. The file also contains classes defining a under-specified error message, a class to define a pyomo solver
   and a class holding the informaiton about a game

2. NashEq Finder requires installing pyomo, which is a python-based optimization modeling software package
   Check out the followingn link for details:
   http://www.pyomo.org

3. NashEq Finder also requires an optimizaton solver such as gurobo or IBM cplex. Consult the respected 
   website for further details.   

Ali R. Zomorrodi, Segre Lab @ Boston University
Last updated: Auguest 31, 2017

Please contact Ali Zomorrodi at ali.r.zomorrodi@gmail.com for questions and updates
"""

#------- User-defined error message ---------
class userError(Exception):
    """ 
    A calss for returning user defined errors 

    Ali R. Zomorrodi, Segre lab @ Bosotn University
    """
    def __init__(self, error_msgs = ''):
        self.error = '\n**ERROR! ' + str(error_msgs) + '\n'

    def __str__(self):
        return self.error


#------- Create a pyomo solver -------------
from pyomo.environ import *
from pyomo.opt import *
from userError import userError
from globalVariables import *

def pyomoSolverCreator(optSolverName, max_threads_num = 1, **solver_options):
    """
    Creates a pyomo solver object and assigns the solver options

    INPUTS:
    ------
     optSolverName: A string containing the solver name
    solver_options: Additional solver options. These are to a dictionary whose keys are 
                    are the names of the arguments and values are the values 

    OUTPUTS:
    -------
    pymoSolverObject: Pyomo solver object with solver options assigned
    """    
    if not isinstance(max_threads_num,int):
        raise TypeError('An integer expected for max_threads_num. An object of type {} was provided instead'.format(type(max_threads_num)))
    elif max_threads_num < 1 or max_threads_num > 32:
        raise ValueError('An integer between 1 and 32 is expected for max_threads_num')

    # Pyomo solver object
    pymoSolverObject = SolverFactory(optSolverName)

    # - Set some default solver options -        
    if optSolverName.lower() == 'cplex':
        # Memory
        pymoSolverObject.options["workmem"]=2500

        # Feasbility tolerance (eprhs). Defaul = 1e-6
        pymoSolverObject.options["simplex_tolerances_feasibility"]=1e-9

        # Optimality tolerance (epopt). Default = 1e-6
        pymoSolverObject.options["simplex_tolerances_optimality"]=1e-9

        # Integrality tolerance (epint). Default = 1e-5
        pymoSolverObject.options["mip_tolerances_integrality"] = 1e-9

        # Relative MIP optimality gap, Default = 1e-4
        pymoSolverObject.options["mip_tolerances_mipgap"] = 1e-9

        # Absolute MIP optimality gap, Default = 1e-6
        pymoSolverObject.options["mip_tolerances_absmipgap"] = 1e-10

        # Bound strengthening indicator (bndstrenind). Default = -1 (let cplex decides) 
        pymoSolverObject.options["preprocessing_boundstrength"]=1

        # Number of threads (core) to use (this shouldn't be more than the value specified in your job
        pymoSolverObject.options["threads"] = max_threads_num
      
    elif optSolverName.lower() in 'gurobi':
        # Memory (in Gb). Default: Infinity
        pymoSolverObject.options["NodefileStart"]=2

        # Feasbility tolerance. Defaul = 1e-6
        pymoSolverObject.options["FeasibilityTol"]=1e-9

        # Optimality tolerance. Defaul = 1e-6
        pymoSolverObject.options["OptimalityTol"]=1e-9

        # Relative MIP optimality gap, Default = 1e-4
        pymoSolverObject.options["MIPGap"]=1e-9

        # Absolute MIP optimality gap, Default = 1e-10
        pymoSolverObject.options["MIPGapAbs"]=1e-10

        # Integrality tolerance (epint). Default = 1e-5
        pymoSolverObject.options["IntFeasTol"]= 1e-9

        # Branch variable selection strategy . Default = -1 (automatic)
        #pymoSolverObject.options["VarBranch"]=3

        # LP method used to solve sifting sub-problems. Default = -1 (automatic)
        #pymoSolverObject.options["SiftMethod"]=2

        # Number of cores to use for parallel computations (defaul 0 = all cores) 
        pymoSolverObject.options["Threads"] = max_threads_num 

    else:
        raise userError('Invalid solver name!') 

#----------- A class holding the information about a game -------------
from __future__ import division
import sys, time, random
import numpy as np
from copy import deepcopy
from itertools import product
from userError import userError
from NashEqFinder import NashEqFinder

class game(object):
    """
    This is a general class holding information for a N-player game 

    """
    def __init__(self, game_name, players_names, players_strategies, payoff_matrix, players_strategiesDetails = None, pureNashEq = None, **additional_args):
       """
       INPUTS:    
       -------
       game_name: 
       A string containing the name of the game (e.g., 'Prisoner;s dilemma') 

       players_names: 
       A list of strings containing the name of game players

       players_strategies: 
       A dictionary whose keys are the names of players and values are a list of strings 
       containing the names of strategies played by that player. Example:
       {'player1':['strategy1','strategy2'], 'player2':['strategy1','strategy2','strategy3']}

       payoff_matrix: 
       Payoff matrix of the game. This is a dictionary with keys and values as follow: 
           Keys: 
           Tuple of tuples where each inner tuple has two elements:
           The first element is the name of the player
           The second element is the name of the strategy. 
           Note that keys cannot be a dictionary or a list because pythong
           will complain if the keys are not tuples

           Values: 
           A dictionary with keys and values as follows:
           Keys: Name of the players
           Values: Their payoff

           Example: If we have two players p1 and p2 and each can play strategies s1 or s2,
                    then the payoff_matrix is as follows: 
                    {(('p1','s1),('p2','s1')):{'p1':2,'p2':3},
                    (('p1','s1'),('p2','s2')):{'p1':0,'p':1}}

       players_strategiesDetails (optional input): 
       A diciotnary of dictionaries. The keys of the main dictionary are the names of  the game 
       palyers. The values are another dictionary. The keys of this inner dictionary are the 
       names of strategies that could be taken by that player  and the values can be any 
       data type that the user may wish (such as a list, tuple, etc). This is particularly 
       useful as sometimes a strategy invovles multiple simultaneous actions. For example, a  
       strategy by a microbial strain can be to produce three different compounds. In this case 
       the exchange rxns correspondong to those three compounds can be used as the values 
       of the inner dicitonary. Example:
       {'player1':{'strategy1':['EX_m1','EX_m2','EX_m2'],
        'strategy2':['Ex_m4']'},'player2':{'strategy1':['EX_m5'],
        'strategy2':['EX_m6','EX_m7']}'} 

       pureNashEq (optional input): 
       Pure strategy Nash equilibria of the game. This is a list of tuples whose elements are 
       the elements of the payoff matrix that are pure strategy Nash equilibria of the game. 
       For example, 
       [(('player1','strategy1'),('player2','strategy2')),(('player1','strategy3'),('player2','strategy5'))]

       additional_args: 
       Additoinal arguments, which are entered as normal but they are converted to a dictionary 
       whose keys are the names of the arguments and values are the values of those arguments
       """

       # Game name 
       self.game_name = game_name

       # Names of the game players
       self.players_names = players_names[:]

       # Number of the game players
       self.numberOfPlayers = len(self.players_names) 

       # Players strategies 
       self.players_strategies = players_strategies.copy()

       # Strategy details 
       self.players_strategiesDetails = deepcopy(players_strategiesDetails)

       #-- Payoff matrix of the game --
       # First check if the total number of elements of the payoff matrix is equal to the 
       # product of the number of strategies for each player. 

       # The set of all strategies based on payoff_matrix 
       strategy_set_payoff_matrix = payoff_matrix.keys()

       # The list of strategies based on players_strategies for different types of players      
       # Two-player game
       listOfStrategies = []
       for player in self.players_names:
          listOfStrategies.append([(player,k) for k in self.players_strategies[player]]) 
       strategy_set = [k for k in product(*listOfStrategies)]
             
       if set(strategy_set_payoff_matrix) == set(strategy_set):
          self.payoff_matrix = deepcopy(payoff_matrix) 
       else:
          raise userError("The set of strategies given in the payoff matrix does not match those given for each player.\nStrategies in the payoff matrix = {}\n\nStrategies in strategy_set: {}\n\nStrategies in payoff matrix but not in players's strategies: {}\n\nStrategies not in payoff matrx but in player's strategies: {}".format(set(strategy_set_payoff_matrix), set(strategy_set), [s for s in strategy_set_payoff_matrix if s not in strategy_set], [s for s in strategy_set if s not in strategy_set_payoff_matrix]))

       # A list of tuples whose elements are the elements of the payoff matrix that are pure 
       # strategy Nash equilibria of the game. For example, 
       # [(('player1','strategy1'),('player2','strategy2')),(('player1','strategy3'),('player2','strategy5'))]
       self.pureNashEq = deepcopy(pureNashEq)

       # Additoinal arguments. Additional arguments should be entered as normal but they are 
       # converted to a dictionary whose keys are the names of the arguments and values are 
       # the values of  those arguments
       argnames = additional_args.keys()
       argvals = additional_args.values()
       for argname in argnames:
         exec "self." + argname + " = " +"additional_args['" + argname + "']"

    def find_NashEq(self, NashEq_type = 'pure', stdout_msgs = True):
        """
        Finds the Nash equilibrium of the game using the NashEq Finder algorithm
        """
        NashEqFinder_inst = NashEqFinder(game = self, stdout_msgs = stdout_msgs, NashEq_type = NashEq_type)
        [Nash_equilibria,exit_flag] = NashEqFinder_inst.run()
        if NashEq_type.lower() == 'pure':
            self.pureNash_equilibria = Nash_equilibria
            self.pureNashEq_exitflag = exit_flag
        elif NashEq_type.lower() == 'mixed':
            self.mixedNash_equilibria = Nash_equilibria
            self.mixedNashEq_exitflag = exit_flag

    def create_symmetric_payoff_matrix(self):
        """
        Creates the payoff matrix of a symmetric game where players' names are removed
        and we just deal with strategy combinations.

        Example: If the payoff matrix of the game is as follows:
        payoff_matrix = {(('player1','C'),('player2','C')):{'player1':5,'player2':5},
                         (('player1','C'),('player2','D')):{'player1':10,'player2':1},
                         (('player1','D'),('player2','C')):{'player1':1,'player2':10},
                         (('player1','D'),('player2','D')):{'player1':1,'player2':1}}             
        then the payoff matrix of the symmetric game will be a dictionary as follows 
        payoff_matrix_symmetric = [('C':'C'):{'C':5, 'C':5},
                                   ('C','D'):{'C':10,'D':1},
                                   ('D':'D'):{'D':1, 'D':1}]             
        """
        # Essentially, what we need to do here is to remove the players names from keys of th epayoff matrix 
        # and replace the players' names in the values of the payoff matrix with their corresponding strategy
        self.symmetric_payoff_matrix = {}

        for players_strategies in self.payoff_matrix.keys():
            players_strategies_dict = dict(players_strategies)

            # Key fo the payoff matrix 
            symPayoffMatrix_key = tuple(sorted(players_strategies_dict.values()))
        
            if symPayoffMatrix_key not in self.symmetric_payoff_matrix.keys():
                symPayoffMatrix_value = {} # Corresponding entry of the symmetric_payoff_matrix

                for player_name in self.payoff_matrix[players_strategies].keys():
                    symPayoffMatrix_value[players_strategies_dict[player_name]] = self.payoff_matrix[players_strategies][player_name]

                self.symmetric_payoff_matrix[symPayoffMatrix_key] = symPayoffMatrix_value


#----------- NashEq Finder ---------------------------
from __future__ import division
import sys, copy, time, random
from datetime import timedelta  # To convert elapsed time to hh:mm:ss format
from tools.pyomoSolverCreator import *


class NashEqFinder(object):
    """
    General class for NashEq Finder. Sample usage is provided at the end 
    """   

    def __init__(self,game, NashEq_type = 'pure', optimization_solver = 'gurobi', warnings = True, stdout_msgs = True, output_file = ''):
        """
        INPUTS 
        ------
        game: 
        An instance of the class game (see game.py for details) 

        NashEq_type: 
        Type of the Nash equilibrium to find (currently only pure strategy Nash equilibria)

        optimization_solver: 
        Name of the LP solver to be used to solve the LP. Current 
        allowable choices are cplex and gurobi

        warnings: 
        Can be True or False indicating whether warnings should be written 
        in the standard output

        stdout_msgs: 
        By default (True) writes a summary including the solve 
        status, optimality status (if not optimal), objective 
        function value and the elapsed time on the screen.
        if set to a value of False no resuults are written on 
        the screen, in which case The user can instead specifiy 
        an output file using the option output_file, or store 
        them in a variable (see the 'run' method for details)

        output_file: 
        Optional input. It is a string containg the path to a 
        file and its name (e.g., 'results/fbaResults.txt'), where
        the results should be written to. 
        """
       
        # Metabolic model
        self.game = game

        # Type of the Nash equilibrium to find
        if NashEq_type.lower() not in ['pure','mixed']:
            raise ValueError("Invalid NashEq_type (allowed choices are 'pure' or 'mixed')")
        else:
            self.NashEq_type = NashEq_type

        # Solver name
        if optimization_solver == None:
            self.optimization_solver = 'gurobi'
        else:
            if optimization_solver.lower() in ['cplex','gurobi']:
                self.optimization_solver = optimization_solver
            else:
                raise ValueError('Invalid solver name (eligible choices are cplex and gurobi)\n')          
               
        # Output to the screen 
        if not isinstance(warnings,bool):
            raise TypeError("Error! warnings should be True or False")
        else:
             self.warnings = warnings

        if not isinstance(stdout_msgs,bool):
            raise TypeError("Error! stdout_msgs should be True or False")
        else:
             self.stdout_msgs = stdout_msgs

        # Output file
        if not isinstance(output_file, str):
            raise TypeError('output_file must be a string')
        else:
            self.output_file = output_file

        # Lower bound on payoff values according to the payoff matrix
        payoffMin = min([k for sublist in self.game.payoff_matrix.values() for k in sublist.values()]) 

        # Sometimes we run into problems when both LB and max payoff of a plyaer given
        # the fixed strategies of other players are zero (i.e., we arrive at a trivial
        # solution of e.g., 2 >= 0 as both terms in the RHS of constraint NashCond are
        # Cancelled out. This happens for problem 9 of Homework 1 of Game Theory I
        # for example). Therefore, it is better to always avoid a LB of zero. 
        if payoffMin - 1 > 0: 
            self.payoffLB = payoffMin - 1 
        else:
            self.payoffLB = payoffMin - 2 

    def convert_to_payoffMatrix_key(self,i):
        """
        This function converts the elements of the set I in the pyomo model
        (or elements of gameStatesForI) to the format of keys of the payoff matrix
        of the game, i.e., ('p1','s1','p2','s2') is converted to (('p1','s1'),('p2','s2')) 
        (see optModel.I for details)
        """
        gameState = []
        done = 0
        k1 = list(i)
        while done == 0:
            gameState.append(tuple(k1[0:2]))
            del k1[0:2]
            if len(k1) == 0:
                done = 1
        return tuple(gameState)

        
    def createPyomoModel(self):
        """
        This creates a pyomo optimization model 

        Instead of several indicies for binary variables (y), we just define a single set I containing all
        possible labels of the payoff matrix (combinations of players and strategies). 
        """   
        #--- Create a pyomo model optModel ---
        optModel = ConcreteModel()
        
        #--- Define sets ---
        # Set of players
        optModel.P = Set(initialize = self.game.players_names)   

        # Set of players' strategy combinations 
        # Keys of the game.payoff_matrix are in the form of a list of tuples, where each
        # tuple is compased of inner tuple of length two, e.g., 
        # [(('p1','s1'),('p2','s2')),(('p1','s2'),('p2','s1')),...]
        # These keys should serve as the elements of the set I in the optimization model,
        # however, pyomo does not accept list of tuples with nested tuples. Therefore, we 
        # need to convert this to a list of tuples with no inner tuples, i.e.,
        # [('p1','s1','p2','s2'),('p1','s2','p2','s1'),...]
        optModel.I = Set(initialize = [tuple([k3 for k2 in k1 for k3 in k2]) for k1 in self.game.payoff_matrix.keys()])   

        #--- Define the variables --- 
        optModel.y = Var(optModel.I, domain=Boolean)
        
        #--- Define the objective function and constraints ----
        # Objective function
        optModel.objective_rule = Objective(rule = lambda optModel: sum(optModel.y[i] for i in optModel.I), sense = maximize)

        # Constraint checking the best strategy of player p given the strategy of 
        # all other players 
        def NashCond_rule(optModel,p,*i):

            # Convert the game state to the format of keys of the payoff matrix
            i = self.convert_to_payoffMatrix_key(i)

            # All possible responses of P to the action all other players
            # have taken in i
            responseP = [k for k in self.game.payoff_matrix.keys() if False not in [dict(k)[pp] == dict(i)[pp] for  pp in dict(i).keys() if pp != p]] 

            # Find the payoff of the best response of player P 
            bestResP = max([self.game.payoff_matrix[k][p] for k in responseP])

            return self.game.payoff_matrix[i][p] >= bestResP*optModel.y[i] + self.payoffLB*(1 - optModel.y[i])
        
        optModel.NashCond = Constraint(optModel.P,optModel.I, rule=NashCond_rule)

        self.optModel = optModel 
    
    
    def findPure(self):
        """ 
        This method runs the optimization problem finding the pure strategy Nash
        equilbirium. 

        OUTPUTS:
        -------
        Nash_equilibria: 
        Is a list containing the labels of the cells of the payoff matrix
        that were found to be a pure strategy Nash equilibrium. For example, in a two-player 
        game if the set of strategies for players 1 and 2 are {s11,s12} and {s21,s22},
        respectively, the optimal values of binary varaibles for each cell can be as follows 
        {('s11','s21'):0,('s11','s21'):1,('s12','s21'):0,('s21','s22'):0}
        and additionally we may have an alternative solution as:
        {('s11','s21'):0,('s11','s21'):0,('s12','s21'):0,('s21','s22'):1}
        Nash_equilibria would be then be a list [('s11','s21'),('s21','s22')] 

        exit_flag: 
        Shows the condition the termination condition of the code (this is different from 
        optimExitflag for solving the optimization problem). exit_flag can take 
        either of the following values:
        - 'objIsZero': The objective function is zero
        - 'solverError': There was an error in both optimization solvers (cplex & guorobi)
        - 'objNotZeroNotOne': An erroneous case where the objective function is neither
                              zero nor one
        - A string showing a non-optimal solution for the optimization problem     
        """
        # Processing and wall time
        start_run_pt = time.clock()
        start_run_wt = time.time()

        #---- Creating and instantiating the optModel ----
        start_pyomo_pt = time.clock()
        start_pyomo_wt = time.time()

        # Create the optModel model        
        self.createPyomoModel()

        #---- Solve the model ----
        # Create a solver and set the options
        solverType = pyomoSolverCreator(self.optimization_solver)

        elapsed_pyomo_pt = str(timedelta(seconds = time.clock() - start_pyomo_pt))
        elapsed_pyomo_wt = str(timedelta(seconds = time.time() - start_pyomo_wt))

        #-- Some initializations --
        # Instantiate the optModel with new fixed variables
        self.optModel.preprocess()

        #- Solve the optModel (tee=True shows the solver output) -
        try:
            start_solver_pt = time.clock()
            start_solver_wt = time.time()

            optSoln = solverType.solve(self.optModel,tee=False)
            solverFlag = 'normal'
    
        # In the case of an error switch the solver
        except:
            if self.warnings:
                print "WARNING! ",self.optimization_solver," failed. An alternative solver is tried"        
    
            if self.optimization_solver.lower() == 'gurobi':
                self.optimization_solver = 'cplex'
            elif self.optimization_solver.lower() == 'cplex':
                self.optimization_solver = 'gurobi'
    
            # Try solving with the alternative solver
            solverType = pyomoSolverCreator(self.optimization_solver)
            try:
                start_solver_pt = time.clock()
                start_solver_wt = time.time()

                optSoln = solverType.solve(self.optModel,tee=False)
                solverFlag = 'normal'
            except:
                solverFlag = 'solverError'
                if self.warnings:
                    print '\nWARNING! The alternative solver failed. No solution was returned'

        elapsed_solver_pt = str(timedelta(seconds = time.clock() - start_solver_pt))
        elapsed_solver_wt = str(timedelta(seconds = time.time() - start_solver_wt))
    
        #----- Print the results in the output (screen, file and/or variable) ------
        # Load the results
        self.optModel.load(optSoln)
            
        # Set of the Nash equilibria
        self.Nash_equilibria = []
        
        if solverFlag == 'normal' and str(optSoln.solver.termination_condition).lower() == 'optimal':
            
            optimExitflag = 'globallyOptimal'
    
            # Value of the objective function
            objValue = self.optModel.objective_rule()
    
            # Print the results on the screen 
            if self.stdout_msgs:
                print "\nsolver.status = ",optSoln.solver.termination_condition,"\n"
                print "objective value = ",objValue

            if objValue >= 1:
                self.exit_flag = 'objGreaterThanZero'
                for i in self.optModel.I.value: 
                    if self.optModel.y[i].value == 1:
                        self.Nash_equilibria.append(list(self.convert_to_payoffMatrix_key(i)))
            elif objValue == 0:
                done = 1
                self.exit_flag = 'objIsZero'
                      
            # Write the results into the output file 
            if self.output_file != '': 
                pass   # To be added 

        # If the optimization problem was not solved successfully
        else:

            if solverFlag == 'solverError':
                optimExitflag = solverFlag
                self.exit_flag = solverFlag
            else:
                optimExitflag = str(optSoln.solver.termination_condition)
                self.exit_flag = str(optSoln.solver.termination_condition)
 
            objValue = None 
    
            # Write on the screen
            if self.warnings:
                print "\nWARNING! No optimal solutions found (solution.solver.status = ",optSoln.Solution.status,", solver.status =",optSoln.solver.status,", solver.termination_condition = ",optSoln.solver.termination_condition,")\n"
    
            # Write the results into the output file
            if self.output_file != None: 
                pass    # *** To be completed ***
            else:
                pass
    
        # Time required to run 
        elapsed_run_pt = str(timedelta(seconds = time.clock() - start_run_pt))
        elapsed_run_wt = str(timedelta(seconds = time.time() - start_run_wt))
    
        if self.stdout_msgs:
           print 'NashEqFinder took (hh:mm:ss) (processing/wall) time: pyomo = {}/{}  ,  solver = {}/{}  ,  run = {}/{} for a game with {} cells in its payoff matrix\n'.format(elapsed_pyomo_pt,elapsed_pyomo_wt,elapsed_solver_pt,elapsed_solver_wt,elapsed_run_pt,elapsed_run_wt, len(self.game.payoff_matrix)) 
    
    def run(self):
        """
        Runs the Nash equilibrium finder
        """
        if self.NashEq_type.lower() == 'pure':
            self.findPure()
        else:
            pass 

        return [self.Nash_equilibria,self.exit_flag]

#--------- Sample implementation ------
if __name__ == "__main__":

    from game import *
    
    print "\n-- Prisoner's Dilemma ---"
    # Pure strategy Nash eq = (D,D)
    
    game_name = "Prisoner's Dilemma"
    numberOfPlayers = 2
    players_names = ['row','column']
    
    players_strategies = {}
    players_strategies['row'] = ['C','D']
    players_strategies['column'] = ['C','D']
    
    payoff_matrix = {}
    payoff_matrix[(('row','C'),('column','C'))] = {'row':-1,'column':-1}
    payoff_matrix[(('row','C'),('column','D'))] = {'row':-4,'column':0}
    payoff_matrix[(('row','D'),('column','C'))] = {'row':0,'column':-4}
    payoff_matrix[(('row','D'),('column','D'))] = {'row':-3,'column':-3}
    
    # Define an instance of the game
    PD = game(game_name, players_names, players_strategies, payoff_matrix)
    
    # Define an instance of the NashEqFinder
    NashEqFinderInst = NashEqFinder(PD, stdout_msgs = True)
    [Nash_equilibria,exit_flag] = NashEqFinderInst.run()
    
    print 'exit_flag = ',exit_flag
    print 'Nash_equilibria = ',Nash_equilibria 
    
    
    print "\n-- Game of pure coordination ---"
    # Pure strategy Nash eq: (Left,Left) and (Right,Right)
    
    game_name = "Pure coordination"
    numberOfPlayers = 2
    players_names = ['row','column']
    
    players_strategies = {}
    players_strategies['row'] = ['Left','Right']
    players_strategies['column'] = ['Left','Right']
    
    payoff_matrix = {}
    payoff_matrix[(('row','Left'),('column','Left'))] = {'row':1,'column':1}
    payoff_matrix[(('row','Left'),('column','Right'))] = {'row':0,'column':0}
    payoff_matrix[(('row','Right'),('column','Left'))] = {'row':0,'column':0}
    payoff_matrix[(('row','Right'),('column','Right'))] = {'row':1,'column':1}
    
    # Define an instance of the game
    PC = game(game_name, players_names, players_strategies, payoff_matrix)
    
    # Define an instance of the NashEqFinder
    NashEqFinderInst = NashEqFinder(PC, stdout_msgs = True)
    [Nash_equilibria,exit_flag] = NashEqFinderInst.run()
    
    print 'exit_flag = ',exit_flag
    print 'Nash_equilibria = ',Nash_equilibria 
    
    print "\n-- Game of Battle of the sexes ---"
    # Pure strategy Nash eq: (B,B) and (F,F)
    
    game_name = "Battle of the sexes"
    numberOfPlayers = 2
    players_names = ['husband','wife']
    
    players_strategies = {}
    players_strategies['husband'] = ['B','F']
    players_strategies['wife'] = ['B','F']
    
    payoff_matrix = {}
    payoff_matrix[(('husband','B'),('wife','B'))] = {'husband':2,'wife':1}
    payoff_matrix[(('husband','B'),('wife','F'))] = {'husband':0,'wife':0}
    payoff_matrix[(('husband','F'),('wife','B'))] = {'husband':0,'wife':0}
    payoff_matrix[(('husband','F'),('wife','F'))] = {'husband':1,'wife':2}
    
    # Define an instance of the game
    BS = game(game_name, players_names, players_strategies, payoff_matrix)
    
    # Define an instance of the NashEqFinder
    NashEqFinderInst = NashEqFinder(BS, stdout_msgs = True)
    [Nash_equilibria,exit_flag] = NashEqFinderInst.run()
    
    print 'exit_flag = ',exit_flag
    print 'Nash_equilibria = ',Nash_equilibria 
    
    print "\n-- Game of Matching pennies ---"
    # Pure strategy Nash eq: None
    
    game_name = "Matching pennies"
    numberOfPlayers = 2
    players_names = ['row','column']
    
    players_strategies = {}
    players_strategies['row'] = ['Heads','Tails']
    players_strategies['column'] = ['Heads','Tails']
    
    payoff_matrix = {}
    payoff_matrix[(('row','Heads'),('column','Heads'))] = {'row':1,'column':-1}
    payoff_matrix[(('row','Heads'),('column','Tails'))] = {'row':-1,'column':1}
    payoff_matrix[(('row','Tails'),('column','Heads'))] = {'row':-1,'column':1}
    payoff_matrix[(('row','Tails'),('column','Tails'))] = {'row':1,'column':-1}
    
    # Define an instance of the game
    MP = game(game_name, players_names, players_strategies, payoff_matrix)
    
    # Define an instance of the NashEqFinder
    NashEqFinderInst = NashEqFinder(MP, stdout_msgs = True)
    [Nash_equilibria,exit_flag]  = NashEqFinderInst.run()
    
    print 'exit_flag = ',exit_flag
    print 'Nash_equilibria = ',Nash_equilibria 
    
    print "\n-- Test game with two players and several strategies for each player ---"
    # This is a game with two players and multiple strategies
    # Pure strategy Nash eq: (c,y)
    game_name = "Hw1Prob4"
    numberOfPlayers = 2
    players_names = ['row','column']
    
    players_strategies = {}
    players_strategies['row'] = ['a','b','c','d']
    players_strategies['column'] = ['x','y','z']
    
    payoff_matrix = {}
    payoff_matrix[(('row','a'),('column','x'))] = {'row':1,'column':2}
    payoff_matrix[(('row','a'),('column','y'))] = {'row':2,'column':2}
    payoff_matrix[(('row','a'),('column','z'))] = {'row':5,'column':1}
    
    payoff_matrix[(('row','b'),('column','x'))] = {'row':4,'column':1}
    payoff_matrix[(('row','b'),('column','y'))] = {'row':3,'column':5}
    payoff_matrix[(('row','b'),('column','z'))] = {'row':3,'column':3}
    
    payoff_matrix[(('row','c'),('column','x'))] = {'row':5,'column':2}
    payoff_matrix[(('row','c'),('column','y'))] = {'row':4,'column':4}
    payoff_matrix[(('row','c'),('column','z'))] = {'row':7,'column':0}
    
    payoff_matrix[(('row','d'),('column','x'))] = {'row':2,'column':3}
    payoff_matrix[(('row','d'),('column','y'))] = {'row':0,'column':4}
    payoff_matrix[(('row','d'),('column','z'))] = {'row':3,'column':0}
    
    # Define an instance of the game
    Hw1Pb4 = game(game_name, players_names, players_strategies, payoff_matrix)
    
    # Define an instance of the NashEqFinder
    NashEqFinderInst = NashEqFinder(Hw1Pb4, stdout_msgs = True)
    [Nash_equilibria,exit_flag] = NashEqFinderInst.run()
    
    print 'exit_flag = ',exit_flag
    print 'Nash_equilibria = ',Nash_equilibria 
    
    
    print "\n-- Test game with three players ---"
    # This is a game with three players and two strategies
    # Pure strategy Nash eq: (c,y)
    
    game_name = "Pure coordination"
    numberOfPlayers = 3
    players_names = ['voter1','voter2','voter3']
    
    players_strategies = {}
    players_strategies['voter1'] = ['candidateA','candidateB']
    players_strategies['voter2'] = ['candidateA','candidateB']
    players_strategies['voter3'] = ['candidateA','candidateB']
    
    payoff_matrix = {}
    payoff_matrix[(('voter1','candidateA'),('voter2','candidateA'),('voter3','candidateA'))] = {'voter1':1,'voter2':0,'voter3':0}
    payoff_matrix[(('voter1','candidateA'),('voter2','candidateA'),('voter3','candidateB'))] = {'voter1':1,'voter2':0,'voter3':0}
    payoff_matrix[(('voter1','candidateA'),('voter2','candidateB'),('voter3','candidateA'))] = {'voter1':1,'voter2':0,'voter3':0}
    payoff_matrix[(('voter1','candidateA'),('voter2','candidateB'),('voter3','candidateB'))] = {'voter1':0,'voter2':1,'voter3':1}
    payoff_matrix[(('voter1','candidateB'),('voter2','candidateA'),('voter3','candidateA'))] = {'voter1':1,'voter2':0,'voter3':0}
    payoff_matrix[(('voter1','candidateB'),('voter2','candidateA'),('voter3','candidateB'))] = {'voter1':0,'voter2':1,'voter3':1}
    payoff_matrix[(('voter1','candidateB'),('voter2','candidateB'),('voter3','candidateA'))] = {'voter1':0,'voter2':1,'voter3':1}
    payoff_matrix[(('voter1','candidateB'),('voter2','candidateB'),('voter3','candidateB'))] = {'voter1':0,'voter2':1,'voter3':1}
    
    # Define an instance of the game
    Hw1Pb9 = game(game_name, players_names, players_strategies, payoff_matrix)
    
    # Define an instance of the NashEqFinder
    NashEqFinderInst = NashEqFinder(Hw1Pb9, stdout_msgs = True)
    [Nash_equilibria,exit_flag] = NashEqFinderInst.run()
    
    print 'exit_flag = ',exit_flag
    print 'Nash_equilibria = ',Nash_equilibria