examples.py

"""
Author: Rahul Savani

- Methods to generate bimatrix games and their extreme equilibria as test cases

- Output suitable for use with lrs-nash, see

    - http://cgm.cs.mcgill.ca/~avis/C/lrs.html
    - https://github.com/rahulsavani/bimatrix_solver 

- The equilibria for these examples are either hardcoded, or produced based on
  the a known construction (rather than computed)

- Payoffs are computed from the bimatrix and equilibrium mixed strategy profiles
  using the method get_payoffs

"""

import sys, os
import numpy as np
from numpy import matlib
from itertools import chain, combinations, product
from fractions import Fraction
import string
# from abc import ABCMeta, abstractmethod
from abc import abstractmethod

VERBOSE = False

class BimatrixGame():
    
    def __init__(self, **kwargs):
        """
        The implemented version should define: A, B, eq1, eq2, and fname
        """
        self.set_game(**kwargs)

        if VERBOSE:
            self.print_bimatrix()
            self.print_eq()

        # write game to text file in suitable form for lrs-nash
        self.write_setnash_input()

    @abstractmethod
    def set_game(self, **kwargs):
        pass

    def get_payoffs(self):
        """
        compute payoffs from bimatrix and extreme equilibria
        assumes:    A and B are numpy arrays
                    eq1 and eq2 are lists of numpy arrays
        """
        self.pay1 = [e1.T.dot(A).dot(e2) for e1,e2 in zip(eq1,eq2)]
        self.pay2 = [e1.T.dot(B).dot(e2) for e1,e2 in zip(eq1,eq2)]

    def write_setnash_input(self):

        """
        writes game in format used as input for lrs-nash solver
        """
        
        with open(os.path.join("tmp",self.fname),'w') as f:
            f.write(" ".join([str(a) for a in self.A.shape]))
            f.write("\n")
            f.write("\n")
            np.savetxt(f, self.A, fmt='%d', delimiter=' ')
            f.write("\n")
            np.savetxt(f, self.B, fmt='%d', delimiter=' ')

    def print_bimatrix(self):
        """
        print A and B to stdout
        """
        print("A =")
        np.savetxt(sys.stdout, self.A, fmt='%d', delimiter=' ')
        print("B =")
        np.savetxt(sys.stdout, self.B, fmt='%d', delimiter=' ')

    def print_eq(self):
        """
        print extreme equilibria given a commensurate pair of lists, one for each player
        """
        for x,y in zip(self.eq1,self.eq2):
            print(x,y)

    def get_game_as_dict(self):

        return {'fname': self.fname, 
                'A': self.A, 
                'B': self.B, 
                'e1': self.eq1, 
                'e2': self.eq2}

###############################################################################
###############################################################################

class All_Zero(BimatrixGame):
    """
    creates a pair of all zero matrices, so that there are (dim^2)-many extreme
    equilibria, namely all pairs of unit vectors; 
    every mixed strategy profile is an equilibrium
    """

    def set_game(self, dimension=3):

        self.fname = 'all_zero_' + str(dimension) + '.txt'

        self.A = np.zeros((dimension,dimension),dtype=int)
        self.B = np.zeros((dimension,dimension),dtype=int)

        # the set of extreme equilibria is the product of all unit vectors
        unit_vectors = []
        for i in range(1,dimension+1):
            tmp = [Fraction(numerator=1,denominator=1) if x == i else Fraction(0)\
                                                    for x in range(1,dimension+1)]
            unit_vectors.append(tmp)

        temp = list(product(unit_vectors,unit_vectors))
        self.eq1, self.eq2 = zip(*temp) 

class Coordination(BimatrixGame):
    """
    creates a coordination game where both players' payoff matrices
    are identity matrices; there are ((2^dim) - 1) extreme equilibria (which are all)
    """

    def set_game(self, dimension=3):

        self.fname = 'coordination_' + str(dimension) + '.txt'

        self.A = np.eye(dimension,dtype=int)
        self.B = np.eye(dimension,dtype=int)

        def powerset(iterable):
            "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
            s = list(iterable)
            return chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1))
    
        self.eq1 = []
        # eq1 is all the uniform mixtures over pure strategies
        pure_strats = range(1,dimension+1)
        a = powerset(pure_strats) # without empty set

        for supp in a:
            x = [Fraction(numerator=1,denominator=len(supp)) if (i+1) in supp else Fraction(0) for i in range(dimension)]
            self.eq1.append(x)
        
        self.eq2 = self.eq1

class Hide_and_Seek(BimatrixGame):
    """
    creates a hide and seek zero sum game 
    """
    def set_game(self, dimension=3):

        self.fname = 'hide_and_seek' + str(dimension) + '.txt'
        
        A = np.eye(dimension,dtype=int)
        self.A = 2*A - 1
        self.B = -self.A

        self.eq1 = []
        # eq1 is the single uniform completely mixed strategy
        x = [Fraction(numerator=1,denominator=dimension) for i in range(dimension)]
        self.eq1.append(x)
        self.eq2 = self.eq1

class Permuation_Game_1eq(BimatrixGame):
    """
    creates a game of two permutation matrices that has exactly one completely-mixed equilibrium
    """
    def set_game(self, dimension=3):

        self.fname = 'permutation_game_1eq_' + str(dimension) + '.txt'
        
        self.A = np.eye(dimension,dtype=int)
        permuted_cols = [(i+1) % dimension for i in range(dimension)]
        self.B = self.A[:,permuted_cols]

        self.eq1 = []
        # eq1 is the single uniform completely mixed strategy
        x = [Fraction(numerator=1,denominator=dimension) for i in range(dimension)]
        self.eq1.append(x)
        self.eq2 = self.eq1


class Dual_Cyclic_6x6_1eq(BimatrixGame):
    """ 
    6x6 example of the construction of von Stengel 
    
    B. von Stengel (1999), New maximal numbers of equilibria in bimatrix games. Discrete and Computational Geometry 21, 557-568.

    this game has a 75 equilibria

    the underlying polytopes are dual cyclic
    """

    def set_game(self):

        self.fname = 'dual_cyclic_6x6_1eq.txt'

        self.A = np.array([ 
        [-180,72,-333,297,-153,270],
        [-30,17,-33,42,-3,20],
        [-81,36,-126,126,-36,90],
        [90,-36,126,-126,36,-81],
        [20,-3,42,-33,17,-30],
        [270,-153,297,-333,72,-180],
        ])

        self.B = np.array([ 
        [72,36,17,-3,-36,-153],
        [-180,-81,-30,20,90,270],
        [297,126,42,-33,-126,-333],
        [-333,-126,-33,42,126,297],
        [270,90,20,-30,-81,-180],
        [-153,-36,-3,17,36,72],
        ])

        temp = [(['1/30','1/6','3/10','3/10','1/6','1/30'],['1/6','1/30','3/10','3/10','1/30','1/6'])]

        self.eq1 = [[Fraction(e) for e in f] for f,g in temp]
        self.eq2 = [[Fraction(e) for e in g] for f,g in temp]


class Dual_Cyclic_6x6_75eq(BimatrixGame):
    """ 
    6x6 example of the construction of von Stengel 
    
    B. von Stengel (1999), New maximal numbers of equilibria in bimatrix games. Discrete and Computational Geometry 21, 557-568.

    this game has a 75 equilibria

    the underlying polytopes are dual cyclic
    """

    def set_game(self):

        self.fname = 'dual_cyclic_6x6_75eq.txt'

        self.A = np.array([ 
        [-81,36,-126,126,-36,90],
        [-180,72,-333,297,-153,270],
        [20,-3,42,-33,17,-30],
        [-30,17,-33,42,-3,20],
        [270,-153,297,-333,72,-180],
        [90,-36,126,-126,36,-81],
        ])

        self.B = np.array([ 
        [72,36,17,-3,-36,-153],
        [-180,-81,-30,20,90,270],
        [297,126,42,-33,-126,-333],
        [-333,-126,-33,42,126,297],
        [270,90,20,-30,-81,-180],
        [-153,-36,-3,17,36,72],
        ])

        temp = [(['1/30','1/6','3/10','3/10','1/6','1/30'],['1/6','1/30','3/10','3/10','1/30','1/6']),
            (['0','0','1/33','5/33','4/11','5/11'],['0','0','5/33','1/33','5/11','4/11']),
            (['1/128','0','0','7/64','47/128','33/64'],['0','0','5/21','13/189','59/189','8/21']),
            (['0','0','13/189','5/21','8/21','59/189'],['0','1/128','7/64','0','33/64','47/128']),
            (['13/524','0','0','87/524','53/131','53/131'],['0','13/524','87/524','0','53/131','53/131']),
            (['10/179','39/179','60/179','50/179','20/179','0'],['20/179','0','60/179','50/179','10/179','39/179']),
            (['10/89','29/89','100/267','50/267','0','0'],['0','0','100/267','50/267','10/89','29/89']),
            (['30/197','67/197','50/197','0','0','50/197'],['0','0','53/151','93/604','87/604','53/151']),
            (['5/87','7/87','0','0','25/87','50/87'],['0','0','31/98','11/98','4/21','8/21']),
            (['0','0','0','0','4/15','11/15'],['0','0','0','0','11/15','4/15']),
            (['0','0','0','0','19/70','51/70'],['0','0','0','4/27','23/27','0']),
            (['0','1/30','0','0','3/10','2/3'],['0','0','19/42','3/14','0','1/3']),
            (['0','0','0','0','2/7','5/7'],['0','0','23/42','19/42','0','0']),
            (['0','0','4/27','0','0','23/27'],['0','0','0','0','51/70','19/70']),
            (['0','0','19/112','0','0','93/112'],['0','0','0','19/112','93/112','0']),
            (['0','5/21','2/7','0','0','10/21'],['0','0','41/90','1/4','0','53/180']),
            (['0','0','4/19','0','0','15/19'],['0','0','31/59','28/59','0','0']),
            (['0','0','19/42','23/42','0','0'],['0','0','0','0','5/7','2/7']),
            (['0','0','28/59','31/59','0','0'],['0','0','0','4/19','15/19','0']),
            (['0','9/35','16/35','2/7','0','0'],['0','0','16/35','2/7','0','9/35']),
            (['0','0','1/2','1/2','0','0'],['0','0','1/2','1/2','0','0']),
            (['0','0','3/14','19/42','1/3','0'],['1/30','0','0','0','2/3','3/10']),
            (['0','0','1/4','41/90','53/180','0'],['5/21','0','0','2/7','10/21','0']),
            (['0','9/58','10/29','10/29','9/58','0'],['9/58','0','10/29','10/29','0','9/58']),
            (['0','0','2/7','16/35','9/35','0'],['9/35','0','2/7','16/35','0','0']),
            (['0','0','11/98','31/98','8/21','4/21'],['7/87','5/87','0','0','50/87','25/87']),
            (['11/193','0','0','45/193','84/193','53/193'],['29/189','25/189','0','0','82/189','53/189']),
            (['0','0','93/604','53/151','53/151','87/604'],['67/197','30/197','0','50/197','50/197','0']),
            (['31/213','0','0','53/213','28/71','15/71'],['28/71','15/71','0','53/213','31/213','0']),
            (['87/604','53/151','53/151','93/604','0','0'],['0','50/197','50/197','0','30/197','67/197']),
            (['15/71','28/71','53/213','0','0','31/213'],['0','31/213','53/213','0','15/71','28/71']),
            (['25/189','29/189','0','0','53/189','82/189'],['0','11/193','45/193','0','53/193','84/193']),
            (['0','2/27','0','0','1/3','16/27'],['0','2/11','25/66','0','0','29/66']),
            (['0','0','0','0','33/103','70/103'],['0','19/32','13/32','0','0','0']),
            (['0','1/3','1/3','0','0','1/3'],['0','1/3','1/3','0','0','1/3']),
            (['0','0','11/39','0','0','28/39'],['0','28/39','11/39','0','0','0']),
            (['0','53/180','41/90','1/4','0','0'],['0','10/21','2/7','0','0','5/21']),
            (['0','0','31/59','28/59','0','0'],['0','15/19','4/19','0','0','0']),
            (['4/21','8/21','31/98','11/98','0','0'],['25/87','50/87','0','0','5/87','7/87']),
            (['53/193','84/193','45/193','0','0','11/193'],['53/189','82/189','0','0','25/189','29/189']),
            (['1/4','1/4','0','0','1/4','1/4'],['1/4','1/4','0','0','1/4','1/4']),
            (['0','2/13','0','0','5/13','6/13'],['5/13','6/13','0','0','0','2/13']),
            (['0','0','0','0','13/33','20/33'],['13/33','20/33','0','0','0','0']),
            (['0','29/66','25/66','0','0','2/11'],['1/3','16/27','0','0','0','2/27']),
            (['6/13','5/13','0','0','2/13','0'],['2/13','0','0','0','6/13','5/13']),
            (['2/11','0','0','25/66','29/66','0'],['2/27','0','0','0','16/27','1/3']),
            (['0','1/2','0','0','1/2','0'],['1/2','0','0','0','0','1/2']),
            (['20/33','13/33','0','0','0','0'],['0','0','0','0','20/33','13/33']),
            (['19/32','0','0','13/32','0','0'],['0','0','0','0','70/103','33/103']),
            (['0','1','0','0','0','0'],['0','0','0','0','0','1']),
            (['0','1/3','19/42','3/14','0','0'],['3/10','2/3','0','0','0','1/30']),
            (['0','0','23/42','19/42','0','0'],['2/7','5/7','0','0','0','0']),
            (['0','20/179','50/179','60/179','39/179','10/179'],['39/179','10/179','50/179','60/179','0','20/179']),
            (['0','0','50/267','100/267','29/89','10/89'],['29/89','10/89','50/267','100/267','0','0']),
            (['50/197','0','0','50/197','67/197','30/197'],['53/151','87/604','93/604','53/151','0','0']),
            (['59/189','8/21','5/21','13/189','0','0'],['47/128','33/64','0','7/64','1/128','0']),
            (['53/131','53/131','87/524','0','0','13/524'],['53/131','53/131','0','87/524','13/524','0']),
            (['82/189','53/189','0','0','29/189','25/189'],['84/193','53/193','0','45/193','11/193','0']),
            (['16/27','1/3','0','0','2/27','0'],['29/66','0','0','25/66','2/11','0']),
            (['1/3','0','0','1/3','1/3','0'],['1/3','0','0','1/3','1/3','0']),
            (['70/103','33/103','0','0','0','0'],['0','0','0','13/32','19/32','0']),
            (['28/39','0','0','11/39','0','0'],['0','0','0','11/39','28/39','0']),
            (['5/11','4/11','5/33','1/33','0','0'],['4/11','5/11','1/33','5/33','0','0']),
            (['33/64','47/128','7/64','0','0','1/128'],['8/21','59/189','13/189','5/21','0','0']),
            (['50/87','25/87','0','0','7/87','5/87'],['8/21','4/21','11/98','31/98','0','0']),
            (['2/3','3/10','0','0','1/30','0'],['1/3','0','3/14','19/42','0','0']),
            (['10/21','0','0','2/7','5/21','0'],['53/180','0','1/4','41/90','0','0']),
            (['5/7','2/7','0','0','0','0'],['0','0','19/42','23/42','0','0']),
            (['15/19','0','0','4/19','0','0'],['0','0','28/59','31/59','0','0']),
            (['51/70','19/70','0','0','0','0'],['0','23/27','4/27','0','0','0']),
            (['93/112','0','0','19/112','0','0'],['0','93/112','19/112','0','0','0']),
            (['11/15','4/15','0','0','0','0'],['4/15','11/15','0','0','0','0']),
            (['23/27','0','0','4/27','0','0'],['19/70','51/70','0','0','0','0']),
            (['0','0','13/32','0','0','19/32'],['33/103','70/103','0','0','0','0']),
            (['0','0','0','0','1','0'],['1','0','0','0','0','0'])]

        self.eq1 = [[Fraction(e) for e in f] for f,g in temp]
        self.eq2 = [[Fraction(e) for e in g] for f,g in temp]

class Battle_of_the_Sexes(BimatrixGame):
    """
    A variant of the standard 2x2 Battle of the Sexes which is non-degenerate
    with 3 extrema equilibria that are all equilibria
    """
    def set_game(self):

        self.fname = 'battle_of_the_sexes.txt'

        self.A = np.array([ 
        [3,1],
        [0,2]
        ])

        self.B = np.array([ 
        [2,1],
        [0,3],
        ])

        temp = [
            (['1','0'],['1','0']),
            (['0','1'],['0','1']),
            (['3/4','1/4'],['1/4','3/4'])
        ]

        self.eq1 = [[Fraction(e) for e in f] for f,g in temp]
        self.eq2 = [[Fraction(e) for e in g] for f,g in temp]

if __name__ == "__main__":

    # All_Zero(dimension=3)
    # Battle_of_the_Sexes()
    # Dual_Cyclic_6x6_75()

    p2 = Permuation_Game_1eq(dimension=2)
    p3 = Permuation_Game_1eq(dimension=3)
    p4 = Permuation_Game_1eq(dimension=4)

    d6 = Dual_Cyclic_6x6_1eq()