From 91660cdf9b0662f4d7f1d9ecea516dfea010a729 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Tue, 4 Oct 2016 20:41:03 -0400 Subject: [PATCH] Initial commit of something that returns an answer. --- README | 19 ++++++++ cones.py | 37 ++++++++++++++ matrices.py | 34 +++++++++++++ symmetric_linear_game.py | 102 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 192 insertions(+) create mode 100644 README create mode 100644 cones.py create mode 100644 matrices.py create mode 100644 symmetric_linear_game.py diff --git a/README b/README new file mode 100644 index 0000000..f019c27 --- /dev/null +++ b/README @@ -0,0 +1,19 @@ +== Overview == + +Dunshire is a CVXOPT-based library for solving cone games. The notion +of a cone game was introduced by Gowda[1] and extended to asymmetric +cones in my thesis[2]. + +== Requirements == + +The only requirement is the CVXOPT library, available for most Linux +distributions. Dunshire is targeted at python-3.x, but python-2.x will +probably work too. + +[1] M. S. Gowda and G. Ravindran. On the game-theoretic value of a + linear transformation relative to a self-dual cone. Linear Algebra + and its Applications, 469:440-463, 2015. + +[2] You wish. + +[3] http://cvxopt.org/ diff --git a/cones.py b/cones.py new file mode 100644 index 0000000..d1fa2a8 --- /dev/null +++ b/cones.py @@ -0,0 +1,37 @@ +class SymmetricCone: + def __init__(self, dimension): + self._dimension = dimension + + def dimension(self): + return self._dimension + + +class NonnegativeOrthant(SymmetricCone): + pass + +class IceCream(SymmetricCone): + pass + +class SymmetricPSD(SymmetricCone): + pass + +class CartesianProduct(SymmetricCone): + def __init__(self, *factors): + self._factors = factors + + def factors(self): + return self._factors + + def cvxopt_dims(self): + d = { 'l':0, 'q':[], 's':[] } + d['l'] += sum([ K.dimension() for K in self.factors() + if isinstance(K, NonnegativeOrthant) ]) + d['q'] = [ K.dimension() for K in self.factors() + if isinstance(K, IceCream) ] + d['s'] = [ K.dimension() for K in self.factors() + if isinstance(K, SymmetricPSD) ] + return d + + def dimension(self): + return sum([ f.dimension() for f in self.factors() ]) + diff --git a/matrices.py b/matrices.py new file mode 100644 index 0000000..01ab352 --- /dev/null +++ b/matrices.py @@ -0,0 +1,34 @@ +from cvxopt import matrix, spmatrix + +def append_col(A,b): + """ + Append the column ``b`` to the right side of the matrix ``A``. + """ + return matrix([A.trans(),b.trans()]).trans() + +def append_cols(cols): + """ + Append a bunch of columns together, left to right. + """ + if len(cols) == 0: + return cols + + result = cols[0] + del(cols[0]) + for column in cols: + result = append_col(result, column) + + return result + + +def append_row(A,b): + """ + Append the row ``b`` to the bottom of the matrix ``A``. + """ + return matrix([A,b]) + +def identity(n): + """ + Return the ``n``-by-``n`` identity matrix. + """ + return spmatrix(1,range(n),range(n)) diff --git a/symmetric_linear_game.py b/symmetric_linear_game.py new file mode 100644 index 0000000..09b63aa --- /dev/null +++ b/symmetric_linear_game.py @@ -0,0 +1,102 @@ +from cvxopt import matrix, printing, solvers + +from cones import CartesianProduct, NonnegativeOrthant +from matrices import append_cols, append_row, identity + +class SymmetricLinearGame: + """ + A representation of a symmetric linear game. + + The data for a linear game are, + + * A "payoff" operator ``L``. + * A cone ``K``. + * A point ``e`` in the interior of ``K``. + * A point ``f`` in the interior of the dual of ``K``. + + In a symmetric game, the cone ``K`` is be self-dual. We therefore + name the two interior points ``e1`` and ``e2`` to indicate that + they come from the same cone but are "chosen" by players one and + two respectively. + + The ambient space is assumed to be the span of ``K``. + """ + + def __init__(self, L, K, e1, e2): + """ + INPUT: + + - ``L`` -- an n-by-b matrix represented as a list of lists + of real numbers. + + - ``K`` -- a SymmetricCone instance. + + - ``e1`` -- the interior point of ``K`` belonging to player one, + as a column vector. + + - ``e2`` -- the interior point of ``K`` belonging to player two, + as a column vector. + + """ + self._K = K + self._C = CartesianProduct(NonnegativeOrthant(2), K, K) + n = self._K.dimension() + self._L = matrix(L, (n,n)) + self._e1 = matrix(e1, (n,1)) # TODO: check that e1 and e2 + self._e2 = matrix(e2, (n,1)) # are in the interior of K... + self._h = matrix(0, (self._C.dimension(),1), 'd') + self._b = matrix(1, (1,1), 'd') + self._c = matrix([-1,1] + ([0]*n), (n+2,1), 'd') + self._G = append_row(-identity(n+2), + append_cols([self._e1, -self._e1, -self._L])) + self._A = matrix([0,0] + e1, (1, n+2), 'd') + + def e1(self): + return self._e1 + + def e2(self): + return self._e2 + + def L(self): + return self._L + + def h(self): + return self._h + + def b(self): + return self._b + + def c(self): + return self._c + + def G(self): + return self._G + + def A(self): + return self._A + + def C(self): + return self._C + + def solve(self): + solvers.options['show_progress'] = False + soln = solvers.conelp(self.c(), + self.G(), + self.h(), + self.C().cvxopt_dims(), + self.A(), + self.b()) + + printing.options['dformat'] = '%.7f' + value = soln['x'][0] - soln['x'][1] + print('Value of the game: {:f}'.format(value)) + + opt1 = soln['x'][2:] + print('Optimal strategy (player one):') + print(opt1) + + #opt2 = soln['y'][2:] + #print('Optimal strategy (player two):') + #print(opt2) + + return soln -- 2.44.2