]>
gitweb.michael.orlitzky.com - dunshire.git/blob - src/dunshire/games.py
1364fddd16ea2221601ca150b78d2944216e83ad
2 Symmetric linear games and their solutions.
4 This module contains the main :class:`SymmetricLinearGame` class that
5 knows how to solve a linear game.
8 # These few are used only for tests.
10 from random
import randint
, uniform
11 from unittest
import TestCase
13 # These are mostly actually needed.
14 from cvxopt
import matrix
, printing
, solvers
15 from cones
import CartesianProduct
, IceCream
, NonnegativeOrthant
16 from errors
import GameUnsolvableException
17 from matrices
import (append_col
, append_row
, eigenvalues_re
, identity
,
21 printing
.options
['dformat'] = options
.FLOAT_FORMAT
22 solvers
.options
['show_progress'] = options
.VERBOSE
27 A representation of the solution of a linear game. It should contain
28 the value of the game, and both players' strategies.
33 >>> print(Solution(10, matrix([1,2]), matrix([3,4])))
34 Game value: 10.0000000
43 def __init__(self
, game_value
, p1_optimal
, p2_optimal
):
45 Create a new Solution object from a game value and two optimal
46 strategies for the players.
48 self
._game
_value
= game_value
49 self
._player
1_optimal
= p1_optimal
50 self
._player
2_optimal
= p2_optimal
54 Return a string describing the solution of a linear game.
56 The three data that are described are,
58 * The value of the game.
59 * The optimal strategy of player one.
60 * The optimal strategy of player two.
62 The two optimal strategy vectors are indented by two spaces.
64 tpl
= 'Game value: {:.7f}\n' \
65 'Player 1 optimal:{:s}\n' \
66 'Player 2 optimal:{:s}'
68 p1_str
= '\n{!s}'.format(self
.player1_optimal())
69 p1_str
= '\n '.join(p1_str
.splitlines())
70 p2_str
= '\n{!s}'.format(self
.player2_optimal())
71 p2_str
= '\n '.join(p2_str
.splitlines())
73 return tpl
.format(self
.game_value(), p1_str
, p2_str
)
78 Return the game value for this solution.
83 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
88 return self
._game
_value
91 def player1_optimal(self
):
93 Return player one's optimal strategy in this solution.
98 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
99 >>> print(s.player1_optimal())
105 return self
._player
1_optimal
108 def player2_optimal(self
):
110 Return player two's optimal strategy in this solution.
115 >>> s = Solution(10, matrix([1,2]), matrix([3,4]))
116 >>> print(s.player2_optimal())
122 return self
._player
2_optimal
125 class SymmetricLinearGame
:
127 A representation of a symmetric linear game.
129 The data for a symmetric linear game are,
131 * A "payoff" operator ``L``.
132 * A symmetric cone ``K``.
133 * Two points ``e1`` and ``e2`` in the interior of ``K``.
135 The ambient space is assumed to be the span of ``K``.
137 With those data understood, the game is played as follows. Players
138 one and two choose points :math:`x` and :math:`y` respectively, from
139 their respective strategy sets,
146 x \in K \ \middle|\ \left\langle x, e_{2} \right\rangle = 1
151 y \in K \ \middle|\ \left\langle y, e_{1} \right\rangle = 1
155 Afterwards, a "payout" is computed as :math:`\left\langle
156 L\left(x\right), y \right\rangle` and is paid to player one out of
157 player two's pocket. The game is therefore zero sum, and we suppose
158 that player one would like to guarantee himself the largest minimum
159 payout possible. That is, player one wishes to,
164 &\underset{y \in \Delta_{2}}{\min}\left(
165 \left\langle L\left(x\right), y \right\rangle
167 \text{subject to } & x \in \Delta_{1}.
170 Player two has the simultaneous goal to,
175 &\underset{x \in \Delta_{1}}{\max}\left(
176 \left\langle L\left(x\right), y \right\rangle
178 \text{subject to } & y \in \Delta_{2}.
181 These goals obviously conflict (the game is zero sum), but an
182 existence theorem guarantees at least one optimal min-max solution
183 from which neither player would like to deviate. This class is
184 able to find such a solution.
189 L : list of list of float
190 A matrix represented as a list of ROWS. This representation
191 agrees with (for example) SageMath and NumPy, but not with CVXOPT
192 (whose matrix constructor accepts a list of columns).
194 K : :class:`SymmetricCone`
195 The symmetric cone instance over which the game is played.
198 The interior point of ``K`` belonging to player one; it
199 can be of any iterable type having the correct length.
202 The interior point of ``K`` belonging to player two; it
203 can be of any enumerable type having the correct length.
209 If either ``e1`` or ``e2`` lie outside of the cone ``K``.
214 >>> from cones import NonnegativeOrthant
215 >>> K = NonnegativeOrthant(3)
216 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
219 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
221 The linear game (L, K, e1, e2) where
225 K = Nonnegative orthant in the real 3-space,
233 Lists can (and probably should) be used for every argument::
235 >>> from cones import NonnegativeOrthant
236 >>> K = NonnegativeOrthant(2)
237 >>> L = [[1,0],[0,1]]
240 >>> G = SymmetricLinearGame(L, K, e1, e2)
242 The linear game (L, K, e1, e2) where
245 K = Nonnegative orthant in the real 2-space,
251 The points ``e1`` and ``e2`` can also be passed as some other
252 enumerable type (of the correct length) without much harm, since
253 there is no row/column ambiguity::
257 >>> from cones import NonnegativeOrthant
258 >>> K = NonnegativeOrthant(2)
259 >>> L = [[1,0],[0,1]]
260 >>> e1 = cvxopt.matrix([1,1])
261 >>> e2 = numpy.matrix([1,1])
262 >>> G = SymmetricLinearGame(L, K, e1, e2)
264 The linear game (L, K, e1, e2) where
267 K = Nonnegative orthant in the real 2-space,
273 However, ``L`` will always be intepreted as a list of rows, even
274 if it is passed as a :class:`cvxopt.base.matrix` which is
275 otherwise indexed by columns::
278 >>> from cones import NonnegativeOrthant
279 >>> K = NonnegativeOrthant(2)
280 >>> L = [[1,2],[3,4]]
283 >>> G = SymmetricLinearGame(L, K, e1, e2)
285 The linear game (L, K, e1, e2) where
288 K = Nonnegative orthant in the real 2-space,
293 >>> L = cvxopt.matrix(L)
298 >>> G = SymmetricLinearGame(L, K, e1, e2)
300 The linear game (L, K, e1, e2) where
303 K = Nonnegative orthant in the real 2-space,
310 def __init__(self
, L
, K
, e1
, e2
):
312 Create a new SymmetricLinearGame object.
315 self
._e
1 = matrix(e1
, (K
.dimension(), 1))
316 self
._e
2 = matrix(e2
, (K
.dimension(), 1))
318 # Our input ``L`` is indexed by rows but CVXOPT matrices are
319 # indexed by columns, so we need to transpose the input before
320 # feeding it to CVXOPT.
321 self
._L = matrix(L
, (K
.dimension(), K
.dimension())).trans()
323 if not self
._e
1 in K
:
324 raise ValueError('the point e1 must lie in the interior of K')
326 if not self
._e
2 in K
:
327 raise ValueError('the point e2 must lie in the interior of K')
331 Return a string representation of this game.
333 tpl
= 'The linear game (L, K, e1, e2) where\n' \
338 indented_L
= '\n '.join(str(self
._L).splitlines())
339 indented_e1
= '\n '.join(str(self
._e
1).splitlines())
340 indented_e2
= '\n '.join(str(self
._e
2).splitlines())
341 return tpl
.format(indented_L
, str(self
._K
), indented_e1
, indented_e2
)
346 Solve this linear game and return a :class:`Solution`.
352 A :class:`Solution` object describing the game's value and
353 the optimal strategies of both players.
357 GameUnsolvableException
358 If the game could not be solved (if an optimal solution to its
359 associated cone program was not found).
364 This example is computed in Gowda and Ravindran in the section
365 "The value of a Z-transformation"::
367 >>> from cones import NonnegativeOrthant
368 >>> K = NonnegativeOrthant(3)
369 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
372 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
373 >>> print(SLG.solution())
374 Game value: -6.1724138
384 The value of the following game can be computed using the fact
385 that the identity is invertible::
387 >>> from cones import NonnegativeOrthant
388 >>> K = NonnegativeOrthant(3)
389 >>> L = [[1,0,0],[0,1,0],[0,0,1]]
392 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
393 >>> print(SLG.solution())
394 Game value: 0.0312500
405 # The cone "C" that appears in the statement of the CVXOPT
407 C
= CartesianProduct(self
._K
, self
._K
)
409 # The column vector "b" that appears on the right-hand side of
410 # Ax = b in the statement of the CVXOPT conelp program.
411 b
= matrix([1], tc
='d')
413 # A column of zeros that fits K.
414 zero
= matrix(0, (self
._K
.dimension(), 1), tc
='d')
416 # The column vector "h" that appears on the right-hand side of
417 # Gx + s = h in the statement of the CVXOPT conelp program.
418 h
= matrix([zero
, zero
])
420 # The column vector "c" that appears in the objective function
421 # value <c,x> in the statement of the CVXOPT conelp program.
422 c
= matrix([-1, zero
])
424 # The matrix "G" that appears on the left-hand side of Gx + s = h
425 # in the statement of the CVXOPT conelp program.
426 G
= append_row(append_col(zero
, -identity(self
._K
.dimension())),
427 append_col(self
._e
1, -self
._L))
429 # The matrix "A" that appears on the right-hand side of Ax = b
430 # in the statement of the CVXOPT conelp program.
431 A
= matrix([0, self
._e
2], (1, self
._K
.dimension() + 1), 'd')
433 # Actually solve the thing and obtain a dictionary describing
435 soln_dict
= solvers
.conelp(c
, G
, h
, C
.cvxopt_dims(), A
, b
)
437 p1_value
= -soln_dict
['primal objective']
438 p2_value
= -soln_dict
['dual objective']
439 p1_optimal
= soln_dict
['x'][1:]
440 p2_optimal
= soln_dict
['z'][self
._K
.dimension():]
442 # The "status" field contains "optimal" if everything went
443 # according to plan. Other possible values are "primal
444 # infeasible", "dual infeasible", "unknown", all of which mean
445 # we didn't get a solution. The "infeasible" ones are the
446 # worst, since they indicate that CVXOPT is convinced the
447 # problem is infeasible (and that cannot happen).
448 if soln_dict
['status'] in ['primal infeasible', 'dual infeasible']:
449 raise GameUnsolvableException(soln_dict
)
450 elif soln_dict
['status'] == 'unknown':
451 # When we get a status of "unknown", we may still be able
452 # to salvage a solution out of the returned
453 # dictionary. Often this is the result of numerical
454 # difficulty and we can simply check that the primal/dual
455 # objectives match (within a tolerance) and that the
456 # primal/dual optimal solutions are within the cone (to a
457 # tolerance as well).
458 if abs(p1_value
- p2_value
) > options
.ABS_TOL
:
459 raise GameUnsolvableException(soln_dict
)
460 if (p1_optimal
not in self
._K
) or (p2_optimal
not in self
._K
):
461 raise GameUnsolvableException(soln_dict
)
463 return Solution(p1_value
, p1_optimal
, p2_optimal
)
468 Return the dual game to this game.
470 If :math:`G = \left(L,K,e_{1},e_{2}\right)` is a linear game,
471 then its dual is :math:`G^{*} =
472 \left(L^{*},K^{*},e_{2},e_{1}\right)`. However, since this cone
473 is symmetric, :math:`K^{*} = K`.
478 >>> from cones import NonnegativeOrthant
479 >>> K = NonnegativeOrthant(3)
480 >>> L = [[1,-5,-15],[-1,2,-3],[-12,-15,1]]
483 >>> SLG = SymmetricLinearGame(L, K, e1, e2)
484 >>> print(SLG.dual())
485 The linear game (L, K, e1, e2) where
489 K = Nonnegative orthant in the real 3-space,
498 # We pass ``self._L`` right back into the constructor, because
499 # it will be transposed there. And keep in mind that ``self._K``
501 return SymmetricLinearGame(self
._L,
508 def _random_matrix(dims
):
510 Generate a random square (``dims``-by-``dims``) matrix. This is used
511 only by the :class:`SymmetricLinearGameTest` class.
513 return matrix([[uniform(-10, 10) for i
in range(dims
)]
514 for j
in range(dims
)])
516 def _random_nonnegative_matrix(dims
):
518 Generate a random square (``dims``-by-``dims``) matrix with
519 nonnegative entries. This is used only by the
520 :class:`SymmetricLinearGameTest` class.
522 L
= _random_matrix(dims
)
523 return matrix([abs(entry
) for entry
in L
], (dims
, dims
))
525 def _random_diagonal_matrix(dims
):
527 Generate a random square (``dims``-by-``dims``) matrix with nonzero
528 entries only on the diagonal. This is used only by the
529 :class:`SymmetricLinearGameTest` class.
531 return matrix([[uniform(-10, 10)*int(i
== j
) for i
in range(dims
)]
532 for j
in range(dims
)])
534 def _random_orthant_params():
536 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
537 random game over the nonnegative orthant. This is only used by
538 the :class:`SymmetricLinearGameTest` class.
540 ambient_dim
= randint(1, 10)
541 K
= NonnegativeOrthant(ambient_dim
)
542 e1
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
543 e2
= [uniform(0.5, 10) for idx
in range(K
.dimension())]
544 L
= _random_matrix(K
.dimension())
545 return (L
, K
, matrix(e1
), matrix(e2
))
548 def _random_icecream_params():
550 Generate the ``L``, ``K``, ``e1``, and ``e2`` parameters for a
551 random game over the ice cream cone. This is only used by
552 the :class:`SymmetricLinearGameTest` class.
554 # Use a minimum dimension of two to avoid divide-by-zero in
555 # the fudge factor we make up later.
556 ambient_dim
= randint(2, 10)
557 K
= IceCream(ambient_dim
)
558 e1
= [1] # Set the "height" of e1 to one
559 e2
= [1] # And the same for e2
561 # If we choose the rest of the components of e1,e2 randomly
562 # between 0 and 1, then the largest the squared norm of the
563 # non-height part of e1,e2 could be is the 1*(dim(K) - 1). We
564 # need to make it less than one (the height of the cone) so
565 # that the whole thing is in the cone. The norm of the
566 # non-height part is sqrt(dim(K) - 1), and we can divide by
568 fudge_factor
= 1.0 / (2.0*sqrt(K
.dimension() - 1.0))
569 e1
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
570 e2
+= [fudge_factor
*uniform(0, 1) for idx
in range(K
.dimension() - 1)]
571 L
= _random_matrix(K
.dimension())
573 return (L
, K
, matrix(e1
), matrix(e2
))
576 class SymmetricLinearGameTest(TestCase
):
578 Tests for the SymmetricLinearGame and Solution classes.
580 def assert_within_tol(self
, first
, second
):
582 Test that ``first`` and ``second`` are equal within our default
585 self
.assertTrue(abs(first
- second
) < options
.ABS_TOL
)
588 def assert_norm_within_tol(self
, first
, second
):
590 Test that ``first`` and ``second`` vectors are equal in the
591 sense that the norm of their difference is within our default
594 self
.assert_within_tol(norm(first
- second
), 0)
597 def assert_solution_exists(self
, L
, K
, e1
, e2
):
599 Given the parameters needed to construct a SymmetricLinearGame,
600 ensure that that game has a solution.
602 # The matrix() constructor assumes that ``L`` is a list of
603 # columns, so we transpose it to agree with what
604 # SymmetricLinearGame() thinks.
605 G
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
608 expected
= inner_product(L
*soln
.player1_optimal(),
609 soln
.player2_optimal())
610 self
.assert_within_tol(soln
.game_value(), expected
)
613 def test_solution_exists_orthant(self
):
615 Every linear game has a solution, so we should be able to solve
616 every symmetric linear game over the NonnegativeOrthant. Pick
617 some parameters randomly and give it a shot. The resulting
618 optimal solutions should give us the optimal game value when we
619 apply the payoff operator to them.
621 (L
, K
, e1
, e2
) = _random_orthant_params()
622 self
.assert_solution_exists(L
, K
, e1
, e2
)
625 def test_solution_exists_icecream(self
):
627 Like :meth:`test_solution_exists_nonnegative_orthant`, except
628 over the ice cream cone.
630 (L
, K
, e1
, e2
) = _random_icecream_params()
631 self
.assert_solution_exists(L
, K
, e1
, e2
)
634 def test_negative_value_z_operator(self
):
636 Test the example given in Gowda/Ravindran of a Z-matrix with
637 negative game value on the nonnegative orthant.
639 K
= NonnegativeOrthant(2)
642 L
= [[1, -2], [-2, 1]]
643 G
= SymmetricLinearGame(L
, K
, e1
, e2
)
644 self
.assertTrue(G
.solution().game_value() < -options
.ABS_TOL
)
647 def assert_scaling_works(self
, L
, K
, e1
, e2
):
649 Test that scaling ``L`` by a nonnegative number scales the value
650 of the game by the same number.
652 game1
= SymmetricLinearGame(L
, K
, e1
, e2
)
653 value1
= game1
.solution().game_value()
655 alpha
= uniform(0.1, 10)
656 game2
= SymmetricLinearGame(alpha
*L
, K
, e1
, e2
)
657 value2
= game2
.solution().game_value()
658 self
.assert_within_tol(alpha
*value1
, value2
)
661 def test_scaling_orthant(self
):
663 Test that scaling ``L`` by a nonnegative number scales the value
664 of the game by the same number over the nonnegative orthant.
666 (L
, K
, e1
, e2
) = _random_orthant_params()
667 self
.assert_scaling_works(L
, K
, e1
, e2
)
670 def test_scaling_icecream(self
):
672 The same test as :meth:`test_nonnegative_scaling_orthant`,
673 except over the ice cream cone.
675 (L
, K
, e1
, e2
) = _random_icecream_params()
676 self
.assert_scaling_works(L
, K
, e1
, e2
)
679 def assert_translation_works(self
, L
, K
, e1
, e2
):
681 Check that translating ``L`` by alpha*(e1*e2.trans()) increases
682 the value of the associated game by alpha.
684 # We need to use ``L`` later, so make sure we transpose it
685 # before passing it in as a column-indexed matrix.
686 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
687 soln1
= game1
.solution()
688 value1
= soln1
.game_value()
689 x_bar
= soln1
.player1_optimal()
690 y_bar
= soln1
.player2_optimal()
692 alpha
= uniform(-10, 10)
693 tensor_prod
= e1
*e2
.trans()
695 # This is the "correct" representation of ``M``, but COLUMN
697 M
= L
+ alpha
*tensor_prod
699 # so we have to transpose it when we feed it to the constructor.
700 game2
= SymmetricLinearGame(M
.trans(), K
, e1
, e2
)
701 value2
= game2
.solution().game_value()
703 self
.assert_within_tol(value1
+ alpha
, value2
)
705 # Make sure the same optimal pair works.
706 self
.assert_within_tol(value2
, inner_product(M
*x_bar
, y_bar
))
709 def test_translation_orthant(self
):
711 Test that translation works over the nonnegative orthant.
713 (L
, K
, e1
, e2
) = _random_orthant_params()
714 self
.assert_translation_works(L
, K
, e1
, e2
)
717 def test_translation_icecream(self
):
719 The same as :meth:`test_translation_orthant`, except over the
722 (L
, K
, e1
, e2
) = _random_icecream_params()
723 self
.assert_translation_works(L
, K
, e1
, e2
)
726 def assert_opposite_game_works(self
, L
, K
, e1
, e2
):
728 Check the value of the "opposite" game that gives rise to a
729 value that is the negation of the original game. Comes from
732 # We need to use ``L`` later, so make sure we transpose it
733 # before passing it in as a column-indexed matrix.
734 game1
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
736 # This is the "correct" representation of ``M``, but
740 # so we have to transpose it when we feed it to the constructor.
741 game2
= SymmetricLinearGame(M
.trans(), K
, e2
, e1
)
743 soln1
= game1
.solution()
744 x_bar
= soln1
.player1_optimal()
745 y_bar
= soln1
.player2_optimal()
746 soln2
= game2
.solution()
748 self
.assert_within_tol(-soln1
.game_value(), soln2
.game_value())
750 # Make sure the switched optimal pair works.
751 self
.assert_within_tol(soln2
.game_value(),
752 inner_product(M
*y_bar
, x_bar
))
755 def test_opposite_game_orthant(self
):
757 Test the value of the "opposite" game over the nonnegative
760 (L
, K
, e1
, e2
) = _random_orthant_params()
761 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
764 def test_opposite_game_icecream(self
):
766 Like :meth:`test_opposite_game_orthant`, except over the
769 (L
, K
, e1
, e2
) = _random_icecream_params()
770 self
.assert_opposite_game_works(L
, K
, e1
, e2
)
773 def assert_orthogonality(self
, L
, K
, e1
, e2
):
775 Two orthogonality relations hold at an optimal solution, and we
778 # We need to use ``L`` later, so make sure we transpose it
779 # before passing it in as a column-indexed matrix.
780 game
= SymmetricLinearGame(L
.trans(), K
, e1
, e2
)
781 soln
= game
.solution()
782 x_bar
= soln
.player1_optimal()
783 y_bar
= soln
.player2_optimal()
784 value
= soln
.game_value()
786 ip1
= inner_product(y_bar
, L
*x_bar
- value
*e1
)
787 self
.assert_within_tol(ip1
, 0)
789 ip2
= inner_product(value
*e2
- L
.trans()*y_bar
, x_bar
)
790 self
.assert_within_tol(ip2
, 0)
793 def test_orthogonality_orthant(self
):
795 Check the orthgonality relationships that hold for a solution
796 over the nonnegative orthant.
798 (L
, K
, e1
, e2
) = _random_orthant_params()
799 self
.assert_orthogonality(L
, K
, e1
, e2
)
802 def test_orthogonality_icecream(self
):
804 Check the orthgonality relationships that hold for a solution
805 over the ice-cream cone.
807 (L
, K
, e1
, e2
) = _random_icecream_params()
808 self
.assert_orthogonality(L
, K
, e1
, e2
)
811 def test_positive_operator_value(self
):
813 Test that a positive operator on the nonnegative orthant gives
814 rise to a a game with a nonnegative value.
816 This test theoretically applies to the ice-cream cone as well,
817 but we don't know how to make positive operators on that cone.
819 (_
, K
, e1
, e2
) = _random_orthant_params()
821 # Ignore that L, we need a nonnegative one.
822 L
= _random_nonnegative_matrix(K
.dimension())
824 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
825 self
.assertTrue(game
.solution().game_value() >= -options
.ABS_TOL
)
828 def test_lyapunov_orthant(self
):
830 Test that a Lyapunov game on the nonnegative orthant works.
832 (L
, K
, e1
, e2
) = _random_orthant_params()
834 # Ignore that L, we need a diagonal (Lyapunov-like) one.
835 # (And we don't need to transpose those.)
836 L
= _random_diagonal_matrix(K
.dimension())
837 game
= SymmetricLinearGame(L
, K
, e1
, e2
)
838 soln
= game
.solution()
840 # We only check for positive/negative stability if the game
841 # value is not basically zero. If the value is that close to
842 # zero, we just won't check any assertions.
843 if soln
.game_value() > options
.ABS_TOL
:
844 # L should be positive stable
845 ps
= all([eig
> -options
.ABS_TOL
for eig
in eigenvalues_re(L
)])
847 elif soln
.game_value() < -options
.ABS_TOL
:
848 # L should be negative stable
849 ns
= all([eig
< options
.ABS_TOL
for eig
in eigenvalues_re(L
)])
852 # The dual game's value should always equal the primal's.
853 dualsoln
= game
.dual().solution()
854 self
.assert_within_tol(dualsoln
.game_value(), soln
.game_value())