#18536: Solvers for constant sum games
-------------------------------------+-------------------------------------
Reporter: ptigwe | Owner:
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-6.8
Component: game theory | Resolution:
Keywords: Game Theory, | Merged in:
Gambit, Zero-sum game Constant | Reviewers: Karl-Dieter Crisman
Sum Game, Normal Form Games | Work issues:
Authors: Tobenna P. Igwe | Commit:
Report Upstream: N/A | bb4eca8a48f9aa64a9e80a8df880d7ebb9cd20c0
Branch: | Stopgaps:
u/ptigwe/gt_extension |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ptigwe):
Thanks for your comments. I've implemented most of your comments, and
noted a few extra things below which would be done upon feedback. If I've
missed anything please let me know.
Replying to [comment:3 kcrisman]:
> Various comments:
> * We have other LP solvers, might as well test that they actually work
(with optional doctests of course). Surely Nathann will have interest in
yet another use of them :)
Done some doctests for `PPL` and `Coin-OR` solvers. Tests would be
included for `CVXOPT` once #18572 is done.
||[http://git.sagemath.org/sage.git/commit/?id=29d4a7d427d825b77a48e2a3871f29e320de2d52
29d4a7d]||{{{Added tests for PPL and Coin-OR solvers}}}||
> * In `_solve_gambit_LP` do you need
> {{{
> + if not self.is_constant_sum():
> + raise ValueError("Input game needs to be a two player
constant sum game")
> }}}
> since presumably this is already tested for end users in `_solve_LP`,
or do you think this sort of double-checking is needed? (In which case
you might want to test both of those branches.)
I included it again just in case if the `_solve_gambit_LP` function was
called externally without going through `_solve_LP`. If there is no need
to retest just for this reason, then I'm happy to take it out.
> * What sort of error is raised if gambit isn't available for these LP
things? Does it tell you to use gambit or does it say `None` has no such
attribute or something?
Just added a `ValueError` to be raised which is quite similar to what you
get by trying to solve the game with `algorithm='LCP'` option.
||[http://git.sagemath.org/sage.git/commit/?id=6138791449507d6527d98c78cd53b73748bb522a
6138791]||{{{Raise error if gambit isn't installed}}}||
> * `return c.numpy().max() == c.numpy().min()` - is there no way to do
this without using/importing `numpy`? It would be nice to not have to use
it - or is it slower to use Sage proper?
Currently, this compares all entries of the matrix and makes sure it is
within `sys.float_info.epsilon` of the first element.
||[http://git.sagemath.org/sage.git/commit/?id=d9571793d208ed772fb8e7a7a335f9934dda1fe8
d957179]||{{{Update check for constant sum 'is_constant_sum'}}}||
>
> * I don't mind in principle using the gambit conversion, obviously that
is better when factored out, but then what happens to `maximization` in
that case? Like
> {{{
> sage: c._solve_LCP(maximization=True) # optional - gambit
> [[(0.0, 1.0), (0.0, 1.0)]]
> }}}
> presumably still passes but what if one changed that to `False`?
Currently, we are considering moving the `maximization` option into the
constructor of the class.
> * Is this going to be more efficient in the constant-sum case even if
`lrs` is installed? I just don't know the answer to relative efficiency
here; presumably LP isn't always faster, even if often, but I don't know
anything about lrs (point-counting?) either.
> {{{
> + if self.is_constant_sum():
> + algorithm = "lp-glpk"
> }}}
The LP solvers would probably be faster primarily because `lrs` enumerates
all possible extreme Nash equilibria in a game, whereas the LP method
simply finds one Nash equilibrium in the constant-sum game.
> * At this point there are so many options maybe one should also check
for an invalid (read: mistyped) algorithm.
> {{{
>
> if algorithm.startswith('lp-'):
> return self._solve_LP(solver=algorithm[3:])
>
> if algorithm == "enumeration":
> return self._solve_enumeration(maximization)
> }}}
> and then `else: blow up with a useful message`
||[http://git.sagemath.org/sage.git/commit/?id=6138791449507d6527d98c78cd53b73748bb522a
6138791]||{{{Raise error if gambit isn't installed}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/18536#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
