From 82e5057f3954a56df76d7e52101f86f3758d3bb3 Mon Sep 17 00:00:00 2001 From: Michael Orlitzky Date: Fri, 14 Oct 2016 19:05:37 -0400 Subject: [PATCH] Do a bunch more README work. --- doc/README.rst | 108 ++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 97 insertions(+), 11 deletions(-) diff --git a/doc/README.rst b/doc/README.rst index 6d00dee..4640767 100644 --- a/doc/README.rst +++ b/doc/README.rst @@ -11,6 +11,93 @@ 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}`: + +>>> 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}`: + +>>> 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.5000000] + [0.5000000] +Player 2 optimal: + [0.5000000] + [0.5000000] + +(The answer when :math:`L`, :math:`e_{1}`, and :math:`e_{2}` are so +simple is independent of the cone.) + Requirements ------------ @@ -21,16 +108,15 @@ probably work too. Background ---------- -A linear game is a generalization of a two-person zero-sum matrix -game~\cite{karlin, parthasarathy-raghavan, -von_neumann-morgenstern}. Classically, such a game involves a matrix -:math:`A \in \mathbb{R}^{n \times n}` and a set (the unit simplex) of -"strategies" :math:`\Delta = \operatorname{conv}\left( -\left\lbrace e_{1}, e_{2}, \ldots, e_{n} \right\} \right)` from which two -players are free to choose. If the players choose :math:`x,y \in \Delta` -respectively, then the game is played by evaluating :math:`y^{T}Ax` as the -"payoff" to the first player. His payoff comes from the second -player, so that their total sums to zero. +A linear game is a generalization of a two-person zero-sum matrix game +[Karlin]_. Classically, such a game involves a matrix :math:`A \in +\mathbb{R}^{n \times n}` and a set (the unit simplex) of "strategies" +:math:`\Delta = \operatorname{conv}\left( \left\lbrace e_{1}, e_{2}, +\ldots, e_{n} \right\} \right)` from which two players are free to +choose. If the players choose :math:`x,y \in \Delta` respectively, +then the game is played by evaluating :math:`y^{T}Ax` as the "payoff" +to the first player. His payoff comes from the second player, so that +their total sums to zero. Each player will try to maximize his payoff in this scenario, or—what is equivalent—try to minimize the payoff of his @@ -76,7 +162,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 -- 2.44.2