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