1""" 2Tests for lemke_howson.py 3 4""" 5import numpy as np 6from numpy.testing import assert_allclose 7from nose.tools import eq_, raises 8from quantecon.game_theory import Player, NormalFormGame, lemke_howson 9 10 11class TestLemkeHowson(): 12 def setUp(self): 13 self.game_dicts = [] 14 15 # From von Stengel 2007 in Algorithmic Game Theory 16 bimatrix = [[(3, 3), (3, 2)], 17 [(2, 2), (5, 6)], 18 [(0, 3), (6, 1)]] 19 NEs_dict = {0: ([1, 0, 0], [1, 0]), 20 1: ([0, 1/3, 2/3], [1/3, 2/3])} # init_pivot: NE 21 d = {'g': NormalFormGame(bimatrix), 22 'NEs_dict': NEs_dict} 23 self.game_dicts.append(d) 24 25 def test_lemke_howson(self): 26 for d in self.game_dicts: 27 for k in d['NEs_dict'].keys(): 28 NE_computed = lemke_howson(d['g'], init_pivot=k) 29 for action_computed, action in zip(NE_computed, 30 d['NEs_dict'][k]): 31 assert_allclose(action_computed, action) 32 33 34class TestLemkeHowsonDegenerate(): 35 def setUp(self): 36 self.game_dicts = [] 37 38 # From von Stengel 2007 in Algorithmic Game Theory 39 bimatrix = [[(3, 3), (3, 3)], 40 [(2, 2), (5, 6)], 41 [(0, 3), (6, 1)]] 42 NEs_dict = {0: ([0, 1/3, 2/3], [1/3, 2/3])} 43 d = {'g': NormalFormGame(bimatrix), 44 'NEs_dict': NEs_dict, 45 'converged': True} 46 self.game_dicts.append(d) 47 48 # == Examples of cycles by "ad hoc" tie breaking rules == # 49 50 # Example where tie breaking that picks the variable with 51 # the smallest row index in the tableau leads to cycling 52 A = np.array([[0, 0, 0], 53 [0, 1, 1], 54 [1, 1, 0]]) 55 B = np.array([[1, 0, 1], 56 [1, 1, 0], 57 [0, 0, 2]]) 58 NEs_dict = {0: ([0, 2/3, 1/3], [0, 1, 0])} 59 d = {'g': NormalFormGame((Player(A), Player(B))), 60 'NEs_dict': NEs_dict, 61 'converged': True} 62 self.game_dicts.append(d) 63 64 # Example where tie breaking that picks the variable with 65 # the smallest variable index in the tableau leads to cycling 66 perm = [2, 0, 1] 67 C = A[:, perm] 68 D = B[perm, :] 69 NEs_dict = {0: ([0, 2/3, 1/3], [0, 0, 1])} 70 d = {'g': NormalFormGame((Player(C), Player(D))), 71 'NEs_dict': NEs_dict, 72 'converged': True} 73 self.game_dicts.append(d) 74 75 def test_lemke_howson_degenerate(self): 76 for d in self.game_dicts: 77 for k in d['NEs_dict'].keys(): 78 NE_computed, res = lemke_howson(d['g'], init_pivot=k, 79 full_output=True) 80 for action_computed, action in zip(NE_computed, 81 d['NEs_dict'][k]): 82 assert_allclose(action_computed, action) 83 eq_(res.converged, d['converged']) 84 85 86def test_lemke_howson_capping(): 87 bimatrix = [[(3, 3), (3, 2)], 88 [(2, 2), (5, 6)], 89 [(0, 3), (6, 1)]] 90 g = NormalFormGame(bimatrix) 91 m, n = g.nums_actions 92 max_iter = 10**6 # big number 93 94 for k in range(m+n): 95 NE0, res0 = lemke_howson(g, init_pivot=k, max_iter=max_iter, 96 capping=None, full_output=True) 97 NE1, res1 = lemke_howson(g, init_pivot=k, max_iter=max_iter, 98 capping=max_iter, full_output=True) 99 for action0, action1 in zip(NE0, NE1): 100 assert_allclose(action0, action1) 101 eq_(res0.init, res1.init) 102 103 init_pivot = 1 104 max_iter = m+n 105 NE, res = lemke_howson(g, init_pivot=init_pivot, max_iter=max_iter, 106 capping=1, full_output=True) 107 eq_(res.num_iter, max_iter) 108 eq_(res.init, init_pivot-1) 109 110 111@raises(TypeError) 112def test_lemke_howson_invalid_g(): 113 bimatrix = [[(3, 3), (3, 2)], 114 [(2, 2), (5, 6)], 115 [(0, 3), (6, 1)]] 116 lemke_howson(bimatrix) 117 118 119@raises(ValueError) 120def test_lemke_howson_invalid_init_pivot_integer(): 121 bimatrix = [[(3, 3), (3, 2)], 122 [(2, 2), (5, 6)], 123 [(0, 3), (6, 1)]] 124 g = NormalFormGame(bimatrix) 125 lemke_howson(g, -1) 126 127 128@raises(TypeError) 129def test_lemke_howson_invalid_init_pivot_float(): 130 bimatrix = [[(3, 3), (3, 2)], 131 [(2, 2), (5, 6)], 132 [(0, 3), (6, 1)]] 133 g = NormalFormGame(bimatrix) 134 lemke_howson(g, 1.0) 135 136 137if __name__ == '__main__': 138 import sys 139 import nose 140 141 argv = sys.argv[:] 142 argv.append('--verbose') 143 argv.append('--nocapture') 144 nose.main(argv=argv, defaultTest=__file__) 145