doc/source/overview.rst

   1 Overview
   2 --------
   3
   4 Dunshire is a `CVXOPT <http://cvxopt.org/>`_-based library for solving
   5 linear (cone) games. The notion of a symmetric linear (cone) game was
   6 introduced by Gowda and Ravindran [GowdaRav]_, and extended by
   7 Orlitzky to asymmetric cones with two interior points.
   8
   9 The state-of-the-art is that only symmetric games can be solved
  10 efficiently, and thus the linear games supported by Dunshire are a
  11 bastard of the two: the cones are symmetric, but the players get to
  12 choose two interior points.
  13
  14 In this game, we have two players who are competing for a "payoff."
  15 There is a symmetric cone :math:`K`, a linear transformation :math:`L`
  16 on the space in which :math:`K` lives, and two points :math:`e_{1}`
  17 and :math:`e_{2}` in the interior of :math:`K`. The players make their
  18 "moves" by choosing points from two strategy sets. Player one chooses
  19 an :math:`\bar{x}` from
  20
  21 .. math::
  22   \Delta_{1} =
  23     \left\lbrace
  24       x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
  25     \right\rbrace
  26
  27 and player two chooses a :math:`\bar{y}` from
  28
  29 .. math::
  30   \Delta_{2} &=
  31     \left\lbrace
  32       y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
  33     \right\rbrace.
  34
  35 That ends the turn, and player one is paid :math:`\left\langle
  36 L\left(\bar{x}\right),\bar{y}\right\rangle` out of player two's
  37 pocket. As is usual to assume in game theory, we suppose that player
  38 one wants to maximize his worst-case payoff, and that player two wants
  39 to minimize his worst-case *payout*. In other words, player one wants
  40 to solve the optimization problem,
  41
  42 .. math::
  43   \text{find }
  44   \underset{x \in \Delta_{1}}{\max}\
  45   \underset{y\in \Delta_{2}}{\min}\
  46   \left\langle L\left(x\right),y \right\rangle
  47
  48 while player two tries to (simultaneously) solve a similar problem,
  49
  50 .. math::
  51   \text{find }
  52   \underset{y\in \Delta_{2}}{\min}\
  53   \underset{x \in \Delta_{1}}{\max}\
  54   \left\langle L\left(x\right),y \right\rangle.
  55
  56 There is at least one pair :math:`\left(\bar{x},\bar{y}\right)` that
  57 solves these problems optimally, and Dunshire can find it. The optimal
  58 payoff, called *the value of the game*, is unique. At the moment, the
  59 symmetric cone :math:`K` can be either the nonnegative orthant or the
  60 Lorentz "ice cream" cone in :math:`\mathbb{R}^{n}`. Here are two of
  61 the simplest possible examples, showing off the ability to solve a
  62 game over both of those cones.
  63
  64 First, we use the nonnegative orthant in :math:`\mathbb{R}^{2}`:
  65
  66 .. doctest::
  67
  68   >>> from dunshire import *
  69   >>> K = NonnegativeOrthant(2)
  70   >>> L = [[1,0],[0,1]]
  71   >>> e1 = [1,1]
  72   >>> e2 = e1
  73   >>> G = SymmetricLinearGame(L,K,e1,e2)
  74   >>> print(G.solution())
  75   Game value: 0.500...
  76   Player 1 optimal:
  77     [0.500...]
  78     [0.500...]
  79   Player 2 optimal:
  80     [0.500...]
  81     [0.500...]
  82
  83 Next we try the Lorentz ice-cream cone in :math:`\mathbb{R}^{2}`:
  84
  85 .. doctest::
  86
  87   >>> from dunshire import *
  88   >>> K = IceCream(2)
  89   >>> L = [[1,0],[0,1]]
  90   >>> e1 = [1,0]
  91   >>> e2 = e1
  92   >>> G = SymmetricLinearGame(L,K,e1,e2)
  93   >>> print(G.solution())
  94   Game value: 1.000...
  95   Player 1 optimal:
  96     [1.000...]
  97     [0.000...]
  98   Player 2 optimal:
  99     [1.000...]
 100     [0.000...]
 101
 102 Note that these solutions are not unique, although the game values are.