]> gitweb.michael.orlitzky.com - dunshire.git/blob - doc/source/background.rst
7b3bf8ce6dec7caaefb2ce87d3ca6516c3ed9fe2
[dunshire.git] / doc / source / background.rst
1 Background
2 ----------
3
4 A linear game is a generalization of a two-person zero-sum matrix game
5 [Karlin]_. Classically, such a game involves a matrix :math:`A \in
6 \mathbb{R}^{n \times n}` and a set (the unit simplex) of "strategies"
7 :math:`\Delta = \operatorname{conv}\left( \left\lbrace e_{1}, e_{2},
8 \ldots, e_{n} \right\} \right)` from which two players are free to
9 choose. If the players choose :math:`x,y \in \Delta` respectively,
10 then the game is played by evaluating :math:`y^{T}Ax` as the "payoff"
11 to the first player. His payoff comes from the second player, so that
12 their total sums to zero.
13
14 Each player will try to maximize his payoff in this scenario,
15 or—what is equivalent—try to minimize the payoff of his
16 opponent. In fact, the existence of optimal strategies is
17 guaranteed [Karlin]_ for both players. The *value* of the
18 matrix game :math:`A` is the payoff resulting from optimal play,
19
20 .. math::
21 v\left(A\right)
22 =
23 \underset{x \in \Delta}{\max}\
24 \underset{y\in \Delta}{\min}
25 \left( y^{T}Ax \right)
26 =
27 \underset{y \in \Delta}{\min}\
28 \underset{x \in \Delta}{\max}
29 \left( y^{T}Ax \right).
30
31 The payoff to the first player in this case is
32 :math:`v\left(A\right)`. Corresponding to :math:`v\left(A\right)` is an
33 optimal strategy pair :math:`\left(\xi, \gamma\right) \in \Delta
34 \times \Delta` such that
35
36 .. math::
37 \gamma^{T}Ax
38 \le
39 v\left(A\right)
40 =
41 \gamma^{T}A\xi
42 \le
43 y^{T}A\xi
44 \text{ for all } \left(x,y\right) \in \Delta \times \Delta.
45
46 The relationship between :math:`A`, :math:`\xi`, :math:`\gamma`,
47 and :math:`v\left(A\right)` has been studied extensively [Kaplansky]_
48 [Raghavan]_. Gowda and Ravindran [GowdaRav]_ were motivated by these
49 results to ask if the matrix :math:`A` can be replaced by a linear
50 transformation :math:`L`, and whether or not the unit simplex
51 :math:`\Delta` can be replaced by a more general set—a base of a
52 symmetric cone. In fact, one can go all the way to asymmetric (but
53 still proper) cones. But, since Dunshire can only handle the symmetric
54 case, we will pretend from now on that our cones need to be
55 symmetric. This simplifies some definitions.
56
57 What is a linear game?
58 ^^^^^^^^^^^^^^^^^^^^^^
59
60 In the classical setting, the interpretation of the strategies as
61 probabilities results in a strategy set :math:`\Delta \subseteq
62 \mathbb{R}^{n}_{+}` that is compact, convex, and does not contain the
63 origin. Moreover, any nonzero :math:`x \in \mathbb{R}^{n}_{+}` is a
64 unique positive multiple :math:`x = \lambda b` of some :math:`b \in
65 \Delta`. Several existence and uniqueness results are predicated on
66 those properties.
67
68 **Definition.** Suppose that :math:`K` is a cone and :math:`B
69 \subseteq K` does not contain the origin. If any nonzero :math:`x \in
70 K` can be uniquely represented :math:`x = \lambda b` where
71 :math:`\lambda > 0` and :math:`b \in B`, then :math:`B` is a *base*
72 of :math:`K`.
73
74 The set :math:`\Delta` is a compact convex base for the proper cone
75 :math:`\mathbb{R}^{n}_{+}`. Every :math:`x \in \Delta` also has
76 entries that sum to unity, which can be abbreviated by the condition
77 :math:`\left\langle x,\mathbf{1} \right\rangle = 1` where
78 :math:`\mathbf{1} = \left(1,1,\ldots,1\right)^{T}` happens to lie in
79 the interior of :math:`\mathbb{R}^{n}_{+}`. In fact, the two
80 conditions :math:`x \in \mathbb{R}^{n}_{+}` and :math:`\left\langle
81 x,\mathbf{1} \right\rangle = 1` define :math:`\Delta`. This is no
82 coincidence; whenever :math:`K` is a symmetric cone and :math:`e_{2}
83 \in \operatorname{int}\left(K\right)`, the set :math:`\left\lbrace x
84 \in K \ \middle|\ \left\langle x,e_{2} \right\rangle = 1
85 \right\rbrace` is a compact convex base of :math:`K`. This motivates a
86 generalization where :math:`\mathbb{R}^{n}_{+}` is replaced by a
87 symmetric cone.
88
89 **Definition.** Let :math:`V` be a finite-dimensional real Hilbert
90 space. A *linear game* in :math:`V` is a tuple
91 :math:`\left(L,K,e_{1},e_{2}\right)` where :math:`L : V \rightarrow V`
92 is linear, the set :math:`K` is a symmetric cone in :math:`V`, and the
93 points :math:`e_{1}` and :math:`e_{2}` belong to
94 :math:`\operatorname{int}\left(K\right)`.
95
96 **Definition.** The strategy sets for our linear game are
97
98 .. math::
99 \begin{aligned}
100 \Delta_{1}\left(L,K,e_{1},e_{2}\right) &=
101 \left\lbrace
102 x \in K\ \middle|\ \left\langle x,e_{2} \right\rangle = 1
103 \right\rbrace\\
104 \Delta_{2}\left(L,K,e_{1},e_{2}\right) &=
105 \left\lbrace
106 y \in K\ \middle|\ \left\langle y,e_{1} \right\rangle = 1
107 \right\rbrace.
108 \end{aligned}
109
110 Since :math:`e_{1},e_{2} \in \operatorname{int}\left(K\right)`, these
111 are bases for :math:`K`. We will usually omit the arguments and write
112 :math:`\Delta_{i}` to mean :math:`\Delta_{i}\left(L,K,e_{1},e_{2}\right)`.
113
114 To play the game :math:`\left(L,K,e_{1},e_{2}\right)`, the first
115 player chooses an :math:`x \in \Delta_{1}`, and the second player
116 independently chooses a :math:`y \in \Delta_{2}`. This completes the
117 turn, and the payoffs are determined by applying the payoff operator
118 :math:`\left(x,y\right) \mapsto \left\langle L\left(x\right), y
119 \right\rangle`. The payoff to the first player is :math:`\left\langle
120 L\left(x\right), y \right\rangle`, and since we want the game to be
121 zero-sum, the payoff to the second player is :math:`-\left\langle
122 L\left(x\right), y \right\rangle`.
123
124 The payoff operator is continuous in both arguments because it is
125 bilinear and the ambient space is finite-dimensional. We constructed
126 the strategy sets :math:`\Delta_{1}` and :math:`\Delta_{2}` to be
127 compact and convex; as a result, Karlin's [Karlin]_ general min-max
128 Theorem 1.5.1, guarantees the existence of optimal strategies for both
129 players.
130
131 **Definition.** A pair :math:`\left(\xi,\gamma\right) \in
132 \Delta_{1} \times \Delta_{2}` is an *optimal pair* for the game
133 :math:`\left(L,K,e_{1},e_{2}\right)` if it satisfies the *saddle-point
134 inequality*,
135
136 .. math::
137 \left\langle L\left(x\right),\gamma \right\rangle
138 \le
139 \left\langle L\left( \xi\right), \gamma \right\rangle
140 \le
141 \left\langle L\left(\xi\right),y \right\rangle
142 \text{ for all }
143 \left(x,y\right) \in \Delta_{1} \times \Delta_{2}.
144
145 At an optimal pair, neither player can unilaterally increase his
146 payoff by changing his strategy. The value :math:`\left\langle L
147 \left( \xi \right) , \gamma \right\rangle` is unique (by the same
148 min-max theorem); it is shared by all optimal pairs. There exists at
149 least one optimal pair :math:`\left(\xi,\gamma\right)` of the
150 game :math:`\left(L,K,e_{1},e_{2}\right)` and its *value* is
151 :math:`v\left(L,K,e_{1},e_{2}\right) = \left\langle
152 L\left(\xi\right), \gamma \right\rangle`.
153
154 Thanks to Karlin [Karlin]_, we have an equivalent characterization of
155 a game's value that does not require us to have a particular optimal
156 pair in mind,
157
158 .. math::
159 v\left( L,K,e_{1},e_{2} \right)
160 =
161 \underset{x \in \Delta_{1}}{\max}\
162 \underset{y\in \Delta_{2}}{\min}\
163 \left\langle L\left(x\right),y \right\rangle
164 =
165 \underset{y\in \Delta_{2}}{\min}\
166 \underset{x \in \Delta_{1}}{\max}\
167 \left\langle L\left(x\right),y \right\rangle.
168
169 Linear games reduce to two-person zero-sum matrix games in the
170 right setting.
171
172 **Example.** If :math:`K = \mathbb{R}^{n}_{+}` in :math:`V =
173 \mathbb{R}^{n}` and :math:`e_{1} = e_{2} =
174 \left(1,1,\ldots,1\right)^{T} \in \operatorname{int}\left(K\right)`,
175 then :math:`\Delta_{1} = \Delta_{2} = \Delta`. For any :math:`L \in
176 \mathbb{R}^{n \times n}`, the linear game :math:`\left(
177 L,K,e_{2},e_{2} \right)` is a two-person zero-sum matrix game. Its
178 payoff is :math:`\left(x,y\right) \mapsto y^{T}Lx`, and its value is
179
180 .. math::
181 v\left( L,K,e_{1},e_{2} \right)
182 =
183 \underset{x \in \Delta}{\max}\
184 \underset{y\in \Delta}{\min}\
185 \left( y^{T}Lx \right)
186 =
187 \underset{y\in \Delta}{\min}\
188 \underset{x \in \Delta}{\max}\
189 \left( y^{T}Lx \right).
190
191
192 Cone program formulation
193 ^^^^^^^^^^^^^^^^^^^^^^^^
194
195 As early as 1947, von Neumann knew [Dantzig]_ that a two-person
196 zero-sum matrix game could be expressed as a linear program. It turns
197 out that the two concepts are equivalent, but turning a matrix game
198 into a linear program is the simpler transformation. Cone programs are
199 generalizations of linear programs where the cone is allowed to differ
200 from the nonnegative orthant. We will see that any linear game can be
201 formulated as a cone program, and if we're lucky, be solved.
202
203 Our main tool in formulating our cone program is the following
204 theorem. It closely mimics a similar result in classical game theory
205 where the cone is the nonnegative orthant and the result gives rise to
206 a linear program. The symbols :math:`\preccurlyeq` and
207 :math:`\succcurlyeq` indicate inequality with respect to the cone
208 ordering; that is, :math:`x \succcurlyeq y \iff x - y \in K`.
209
210 **Theorem.** In the game :math:`\left(L,K,e_{1},e_{2}\right)`, we have
211 :math:`L^{*}\left( \gamma \right) \preccurlyeq \nu e_{2}` and
212 :math:`L \left( \xi \right) \succcurlyeq \nu e_{1}` for
213 :math:`\nu \in \mathbb{R}` if and only if :math:`\nu` is the
214 value of the game :math:`\left(L,K,e_{1},e_{2}\right)` and
215 :math:`\left(\xi,\gamma\right)` is optimal for it.
216
217 The proof of this theorem is not difficult, and the version for
218 :math:`e_{1} \ne e_{2}` can easily be deduced from the one given by
219 Gowda and Ravidran [GowdaRav]_. Let us now restate the objectives of
220 the two players in terms of this theorem. Player one would like to,
221
222 .. math::
223 \begin{aligned}
224 &\text{ maximize } &\nu &\\
225 &\text{ subject to }& \xi &\in K&\\
226 & & \left\langle \xi,e_{1} \right\rangle &= 1&\\
227 & & \nu &\in \mathbb{R}&\\
228 & & L\left(\xi\right) &\succcurlyeq \nu e_{1}.&
229 \end{aligned}
230
231 Player two, on the other hand, would like to,
232
233 .. math::
234
235 \begin{aligned}
236 &\text{ minimize } &\omega &\\
237 &\text{ subject to }& \gamma &\in K&\\
238 & & \left\langle \gamma,e_{2} \right\rangle &= 1&\\
239 & & \omega &\in \mathbb{R}&\\
240 & & L^{*}\left(\gamma\right) &\preccurlyeq \omega e_{2}.&
241 \end{aligned}
242
243 The `CVXOPT <http://cvxopt.org/>` library can solve symmetric cone
244 programs in the following primal/dual format:
245
246 .. math::
247 \text{primal} =
248 \left\{
249 \begin{aligned}
250 \text{ minimize } & c^{T}x \\
251 \text{ subject to } & Gx + s = h \\
252 & Ax = b \\
253 & s \in C,
254 \end{aligned}
255 \right.
256
257 .. math::
258 \text{dual}
259 =
260 \left\{
261 \begin{aligned}
262 \text{ maximize } & -h^{T}z - b^{T}y \\
263 \text{ subject to } & G^{T}z + A^{T}y + c = 0 \\
264 & z \in C.
265 \end{aligned}
266 \right.
267
268 We will now pull a rabbit out of the hat, and choose the
269 matrices/vectors in these primal/dual programs so as to reconstruct
270 exactly the goals of the two players. Let,
271
272 .. math::
273 \begin{aligned}
274 C &= K \times K\\
275 x &= \begin{bmatrix} \nu & \xi \end{bmatrix} \\
276 b &= \begin{bmatrix} 1 \end{bmatrix} \\
277 h &= 0 \\
278 c &= \begin{bmatrix} -1 & 0 \end{bmatrix} \\
279 A &= \begin{bmatrix} 0 & e_{2}^{T} \end{bmatrix} \\
280 G &= \begin{bmatrix}
281 0 & -I\\
282 e_{1} & -L
283 \end{bmatrix}.
284 \end{aligned}
285
286 Substituting these values into the primal/dual CVXOPT cone programs
287 recovers the objectives of player one (primal) and player two (dual)
288 exactly. Therefore, we can use this formulation to solve a linear
289 game, and that is precisely what Dunshire does.