From 843d46c5be5605d071f17481c48ed0cb7f5acbaf Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Sat, 15 Oct 2016 21:48:16 -0400 Subject: [PATCH] Separate and organize the various documentation sections. --- doc/{README.rst => source/background.rst} | 135 +--------------------- doc/source/developer-api.rst | 61 ++++++++++ doc/source/index.rst | 99 ++-------------- doc/source/overview.rst | 102 ++++++++++++++++ doc/source/references.rst | 19 +++ doc/source/requirements.rst | 6 + doc/source/user-api.rst | 33 ++++++ 7 files changed, 231 insertions(+), 224 deletions(-) rename doc/{README.rst => source/background.rst} (73%) create mode 100644 doc/source/developer-api.rst create mode 100644 doc/source/overview.rst create mode 100644 doc/source/references.rst create mode 100644 doc/source/requirements.rst create mode 100644 doc/source/user-api.rst diff --git a/doc/README.rst b/doc/source/background.rst similarity index 73% rename from doc/README.rst rename to doc/source/background.rst index 12eaf7a..7b3bf8c 100644 --- a/doc/README.rst +++ b/doc/source/background.rst @@ -1,113 +1,3 @@ -Overview --------- - -Dunshire is a `CVXOPT `_-based library for solving -linear (cone) games. The notion of a symmetric linear (cone) game was -introduced by Gowda and Ravindran [GowdaRav]_, and extended by -Orlitzky to asymmetric cones with two interior points. - -The state-of-the-art is that only symmetric games can be solved -efficiently, and thus the linear games supported by Dunshire are a -bastard of the two: the cones are symmetric, but the players get to -choose two interior points. - -In this game, we have two players who are competing for a "payoff." -There is a symmetric cone :math:`K`, a linear transformation :math:`L` -on the space in which :math:`K` lives, and two points :math:`e_{1}` -and :math:`e_{2}` in the interior of :math:`K`. The players make their -"moves" by choosing points from two strategy sets. Player one chooses -an :math:`\bar{x}` from - -.. math:: - \Delta_{1} = - \left\lbrace - x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1 - \right\rbrace - -and player two chooses a :math:`\bar{y}` from - -.. math:: - \Delta_{2} &= - \left\lbrace - y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1 - \right\rbrace. - -That ends the turn, and player one is paid :math:`\left\langle -L\left(\bar{x}\right),\bar{y}\right\rangle` out of player two's -pocket. As is usual to assume in game theory, we suppose that player -one wants to maximize his worst-case payoff, and that player two wants -to minimize his worst-case *payout*. In other words, player one wants -to solve the optimization problem, - -.. math:: - \text{find } - \underset{x \in \Delta_{1}}{\max}\ - \underset{y\in \Delta_{2}}{\min}\ - \left\langle L\left(x\right),y \right\rangle - -while player two tries to (simultaneously) solve a similar problem, - -.. math:: - \text{find } - \underset{y\in \Delta_{2}}{\min}\ - \underset{x \in \Delta_{1}}{\max}\ - \left\langle L\left(x\right),y \right\rangle. - -There is at least one pair :math:`\left(\bar{x},\bar{y}\right)` that -solves these problems optimally, and Dunshire can find it. The optimal -payoff, called *the value of the game*, is unique. At the moment, the -symmetric cone :math:`K` can be either the nonnegative orthant or the -Lorentz "ice cream" cone in :math:`\mathbb{R}^{n}`. Here are two of -the simplest possible examples, showing off the ability to solve a -game over both of those cones. - -First, we use the nonnegative orthant in :math:`\mathbb{R}^{2}`: - -.. doctest:: - - >>> from dunshire import * - >>> K = NonnegativeOrthant(2) - >>> L = [[1,0],[0,1]] - >>> e1 = [1,1] - >>> e2 = e1 - >>> G = SymmetricLinearGame(L,K,e1,e2) - >>> print(G.solution()) - Game value: 0.5000000 - Player 1 optimal: - [0.5000000] - [0.5000000] - Player 2 optimal: - [0.5000000] - [0.5000000] - -Next we try the Lorentz ice-cream cone in :math:`\mathbb{R}^{2}`: - -.. doctest:: - - >>> from dunshire import * - >>> K = IceCream(2) - >>> L = [[1,0],[0,1]] - >>> e1 = [1,1] - >>> e2 = e1 - >>> G = SymmetricLinearGame(L,K,e1,e2) - >>> print(G.solution()) - Game value: 0.5000000 - Player 1 optimal: - [0.8347039] - [0.1652961] - Player 2 optimal: - [0.5000000] - [0.5000000] - -Note that these solutions are not unique, although the game values are. - -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. - Background ---------- @@ -165,7 +55,7 @@ case, we will pretend from now on that our cones need to be symmetric. This simplifies some definitions. What is a linear game? -~~~~~~~~~~~~~~~~~~~~~~ +^^^^^^^^^^^^^^^^^^^^^^ In the classical setting, the interpretation of the strategies as probabilities results in a strategy set :math:`\Delta \subseteq @@ -300,7 +190,7 @@ payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is Cone program formulation -~~~~~~~~~~~~~~~~~~~~~~~~ +^^^^^^^^^^^^^^^^^^^^^^^^ As early as 1947, von Neumann knew [Dantzig]_ that a two-person zero-sum matrix game could be expressed as a linear program. It turns @@ -397,24 +287,3 @@ Substituting these values into the primal/dual CVXOPT cone programs recovers the objectives of player one (primal) and player two (dual) exactly. Therefore, we can use this formulation to solve a linear game, and that is precisely what Dunshire does. - - -References ----------- - -.. [Dantzig] G. B. Dantzig. Linear Programming and Extensions. - Princeton University Press, Princeton, 1963. - -.. [GowdaRav] 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. - -.. [Kaplansky] I. Kaplansky. A contribution to von Neumann’s theory of - games. Annals of Mathematics, 46(3):474-479, 1945. - -.. [Karlin] S. Karlin. Mathematical Methods and Theory in Games, - Programming, and Economics. Addison-Wesley Publishing Company, - Reading, Massachusetts, 1959. - -.. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear - Algebra and its Applications, 21:35-45, 1978. diff --git a/doc/source/developer-api.rst b/doc/source/developer-api.rst new file mode 100644 index 0000000..0a6d0e9 --- /dev/null +++ b/doc/source/developer-api.rst @@ -0,0 +1,61 @@ +Developer API Documentation +--------------------------- + +dunshire.cones module +^^^^^^^^^^^^^^^^^^^^^ + +.. automodule:: dunshire.cones + :noindex: + :members: + :undoc-members: + :show-inheritance: + +dunshire.errors module +^^^^^^^^^^^^^^^^^^^^^^ + +.. automodule:: dunshire.errors + :members: + :undoc-members: + :show-inheritance: + +dunshire.games module +^^^^^^^^^^^^^^^^^^^^^ + +.. automodule:: dunshire.games + :noindex: + :members: + :undoc-members: + :show-inheritance: + +dunshire.matrices module +^^^^^^^^^^^^^^^^^^^^^^^^ + +.. automodule:: dunshire.matrices + :members: + :undoc-members: + :show-inheritance: + +dunshire.options module +^^^^^^^^^^^^^^^^^^^^^^^ + +.. automodule:: dunshire.options + :members: + :undoc-members: + :show-inheritance: + + +test.suite module +^^^^^^^^^^^^^^^^^ + +.. automodule:: test.suite + :members: + :undoc-members: + :show-inheritance: + +test.symmetric_linear_game_test module +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +.. automodule:: test.symmetric_linear_game_test + :members: + :undoc-members: + :show-inheritance: diff --git a/doc/source/index.rst b/doc/source/index.rst index 0716d13..5edc5e6 100644 --- a/doc/source/index.rst +++ b/doc/source/index.rst @@ -1,94 +1,11 @@ Dunshire ======== -.. include:: ../README.rst - - -API Documentation ------------------ - -dunshire package -================ - -Submodules ----------- - -dunshire.cones module ---------------------- - -.. automodule:: dunshire.cones - :members: - :undoc-members: - :show-inheritance: - -dunshire.errors module ----------------------- - -.. automodule:: dunshire.errors - :members: - :undoc-members: - :show-inheritance: - -dunshire.games module ---------------------- - -.. automodule:: dunshire.games - :members: - :undoc-members: - :show-inheritance: - -dunshire.matrices module ------------------------- - -.. automodule:: dunshire.matrices - :members: - :undoc-members: - :show-inheritance: - -dunshire.options module ------------------------ - -.. automodule:: dunshire.options - :members: - :undoc-members: - :show-inheritance: - - -Module contents ---------------- - -.. automodule:: dunshire - :members: - :undoc-members: - :show-inheritance: - -test package -============ - -Submodules ----------- - -test.suite module ------------------ - -.. automodule:: test.suite - :members: - :undoc-members: - :show-inheritance: - -test.symmetric_linear_game_test module --------------------------------------- - -.. automodule:: test.symmetric_linear_game_test - :members: - :undoc-members: - :show-inheritance: - - -Module contents ---------------- - -.. automodule:: test - :members: - :undoc-members: - :show-inheritance: +.. toctree:: + + overview + requirements + user-api + background + references + developer-api diff --git a/doc/source/overview.rst b/doc/source/overview.rst new file mode 100644 index 0000000..f4b4220 --- /dev/null +++ b/doc/source/overview.rst @@ -0,0 +1,102 @@ +Overview +-------- + +Dunshire is a `CVXOPT `_-based library for solving +linear (cone) games. The notion of a symmetric linear (cone) game was +introduced by Gowda and Ravindran [GowdaRav]_, and extended by +Orlitzky to asymmetric cones with two interior points. + +The state-of-the-art is that only symmetric games can be solved +efficiently, and thus the linear games supported by Dunshire are a +bastard of the two: the cones are symmetric, but the players get to +choose two interior points. + +In this game, we have two players who are competing for a "payoff." +There is a symmetric cone :math:`K`, a linear transformation :math:`L` +on the space in which :math:`K` lives, and two points :math:`e_{1}` +and :math:`e_{2}` in the interior of :math:`K`. The players make their +"moves" by choosing points from two strategy sets. Player one chooses +an :math:`\bar{x}` from + +.. math:: + \Delta_{1} = + \left\lbrace + x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1 + \right\rbrace + +and player two chooses a :math:`\bar{y}` from + +.. math:: + \Delta_{2} &= + \left\lbrace + y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1 + \right\rbrace. + +That ends the turn, and player one is paid :math:`\left\langle +L\left(\bar{x}\right),\bar{y}\right\rangle` out of player two's +pocket. As is usual to assume in game theory, we suppose that player +one wants to maximize his worst-case payoff, and that player two wants +to minimize his worst-case *payout*. In other words, player one wants +to solve the optimization problem, + +.. math:: + \text{find } + \underset{x \in \Delta_{1}}{\max}\ + \underset{y\in \Delta_{2}}{\min}\ + \left\langle L\left(x\right),y \right\rangle + +while player two tries to (simultaneously) solve a similar problem, + +.. math:: + \text{find } + \underset{y\in \Delta_{2}}{\min}\ + \underset{x \in \Delta_{1}}{\max}\ + \left\langle L\left(x\right),y \right\rangle. + +There is at least one pair :math:`\left(\bar{x},\bar{y}\right)` that +solves these problems optimally, and Dunshire can find it. The optimal +payoff, called *the value of the game*, is unique. At the moment, the +symmetric cone :math:`K` can be either the nonnegative orthant or the +Lorentz "ice cream" cone in :math:`\mathbb{R}^{n}`. Here are two of +the simplest possible examples, showing off the ability to solve a +game over both of those cones. + +First, we use the nonnegative orthant in :math:`\mathbb{R}^{2}`: + +.. doctest:: + + >>> from dunshire import * + >>> K = NonnegativeOrthant(2) + >>> L = [[1,0],[0,1]] + >>> e1 = [1,1] + >>> e2 = e1 + >>> G = SymmetricLinearGame(L,K,e1,e2) + >>> print(G.solution()) + Game value: 0.5000000 + Player 1 optimal: + [0.5000000] + [0.5000000] + Player 2 optimal: + [0.5000000] + [0.5000000] + +Next we try the Lorentz ice-cream cone in :math:`\mathbb{R}^{2}`: + +.. doctest:: + + >>> from dunshire import * + >>> K = IceCream(2) + >>> L = [[1,0],[0,1]] + >>> e1 = [1,1] + >>> e2 = e1 + >>> G = SymmetricLinearGame(L,K,e1,e2) + >>> print(G.solution()) + Game value: 0.5000000 + Player 1 optimal: + [0.8347039] + [0.1652961] + Player 2 optimal: + [0.5000000] + [0.5000000] + +Note that these solutions are not unique, although the game values are. diff --git a/doc/source/references.rst b/doc/source/references.rst new file mode 100644 index 0000000..66b8c76 --- /dev/null +++ b/doc/source/references.rst @@ -0,0 +1,19 @@ +References +---------- + +.. [Dantzig] G. B. Dantzig. Linear Programming and Extensions. + Princeton University Press, Princeton, 1963. + +.. [GowdaRav] 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. + +.. [Kaplansky] I. Kaplansky. A contribution to von Neumann’s theory of + games. Annals of Mathematics, 46(3):474-479, 1945. + +.. [Karlin] S. Karlin. Mathematical Methods and Theory in Games, + Programming, and Economics. Addison-Wesley Publishing Company, + Reading, Massachusetts, 1959. + +.. [Raghavan] T. Raghavan. Completely mixed games and M-matrices. Linear + Algebra and its Applications, 21:35-45, 1978. diff --git a/doc/source/requirements.rst b/doc/source/requirements.rst new file mode 100644 index 0000000..8f82266 --- /dev/null +++ b/doc/source/requirements.rst @@ -0,0 +1,6 @@ +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. diff --git a/doc/source/user-api.rst b/doc/source/user-api.rst new file mode 100644 index 0000000..22488f3 --- /dev/null +++ b/doc/source/user-api.rst @@ -0,0 +1,33 @@ +User API Documentation +--------------------------- + +You should only need to work with two modules, ``dunshire.cones`` and +``dunshire.games``. For convenience, you can import everything from +the ``dunshire`` package, and it will re-export what you need. For +example, + +.. testcode:: + + from dunshire import * + K = IceCream(3) + L = [[1,-1,12],[0,1,22],[-17,1,0]] + e1 = [1,0.5,0.25] + e2 = [1,0.25,0.5] + G = SymmetricLinearGame(L,K,e1,e2) + G.solution() + +dunshire.cones module +~~~~~~~~~~~~~~~~~~~~~ + +.. automodule:: dunshire.cones + :members: + :undoc-members: + :show-inheritance: + +dunshire.games module +~~~~~~~~~~~~~~~~~~~~~ + +.. automodule:: dunshire.games + :members: + :undoc-members: + :show-inheritance: -- 2.44.2