Solvers for constant sum games

[8ac3f0f3-bd13-47e7-baee-523ad1646342]

Constant-sum games are known to be solvable in polynomial time by using a linear program. This patch includes a solver which constructs and solves the LPs using the LP solvers within Sage (see http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html). It also makes use of the solver within gambit for such games.

Finally, an additional function was included which helps to convert games from the representation in sage to gambits representation (_gambit_)

CC: @drvinceknight @dimpase @kcrisman @nathanncohen

Component: game theory

Keywords: Gambit, Zero-sum game Constant Sum Game, Normal Form Games

Author: Tobenna P. Igwe

Branch/Commit: 156ea0f

Reviewer: Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik, David Coudert

Issue created by migration from https://trac.sagemath.org/ticket/18536

[tscrim]

comment:41

I believe this is essentially reviewed, so perhaps the only thing left to check are my little round of tweaks.

[dimpase]

comment:42

This still needs the following for doc building and to pass the tests

--- a/src/sage/game_theory/normal_form_game.py
+++ b/src/sage/game_theory/normal_form_game.py
@@ -216,7 +216,7 @@ currently available:

 * ``'lp-*'``: A solver for constant sum 2 player games using linear
   programming. This contructs a
- `:mod:MixedIntegerLinearProgram <sage.numerical.MILP>` using the
+  `:mod:MixedIntegerLinearProgram <sage.numerical.MILP>` using the
   solver which was passed in as part of the algorithm string to solve
   the linear programming representation of the game, for instance,
   ``'lp-glpk'`` would make use of the ``GLPK`` solver, while
@@ -568,6 +568,7 @@ Here is an example with the trivial game where all payoffs are 0::
     (
     [0 0 0]  [0 0 0]
     [0 0 0]  [0 0 0]
+    [0 0 0], [0 0 0]
     )
     sage: g.obtain_nash(algorithm='enumeration')
     [[(0, 0, 1), (0, 0, 1)], [(0, 0, 1), (0, 1, 0)], [(0, 0, 1), (1, 0, 0)],

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c2a1187

fixed doc building and a test

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9e009fb to c2a1187

[dimpase]

Changed reviewer from Karl-Dieter Crisman, Travis Scrimshaw to Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik

[tscrim]

comment:45

Thank you.

[dcoudert]

comment:46

The last commit has introduced a small mistake. One should do:

- `:mod:MixedIntegerLinearProgram <sage.numerical.MILP>` using the
+ :mod:`MixedIntegerLinearProgram <sage.numerical.MILP>` using the

I think that using algorithm = "lp-glpk" or algorithm = "lp-gambit" is not the best choice. It forces to specify the LP solver, while we usually let Sage use the default LP solver (GLPK, Cplex, ...). Why not using 2 parameters: algorithm="lp" and solver=None (or "gambit" or "gplk"or ...) ?

Typically, we usually do:

- def _solve_LP(self, solver='glpk', maximization=True):
+ def _solve_LP(self, solver=None, maximization=True):

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c2a1187 to f5b73ea

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f5b73ea

fixed doc building and a test

[dimpase]

comment:48

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f5b73ea

fixed doc building and a test

this fixes the wrongly placed backtick for :mod:...

[dimpase]

comment:49

Replying to @dcoudert:

I think that using algorithm = "lp-glpk" or algorithm = "lp-gambit" is not the best choice. It forces to specify the LP solver, while we usually let Sage use the default LP solver (GLPK, Cplex, ...). Why not using 2 parameters: algorithm="lp" and solver=None (or "gambit" or "gplk"or ...) ?

This is more subtle, as gambit is not one of LP-solvers supported by the Sage's LP backend, and thus the change you propose would introduce a bit of dissonance, too.

I would prefer to have such an improvement worked on on a followup ticket.

[dimpase]

Changed reviewer from Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik to Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik, David Coudert

[tscrim]

comment:50

Since this is being introduced on this ticket, I think we should try and decide now rather than later, especially since that would likely mean deprecations.

gambit does apparently come with a solver, so I feel it is only very mildly dissonant. I am working on David's suggestion.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f5b73ea to fab0962

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

fab0962

Using a solver argument for LP algorithm.

[tscrim]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 Constant-sum games are known to be solvable in polynomial time by using a linear program. This patch includes a solver which constructs and solves the LPs using the LP solvers within Sage (see http://doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html). It also makes use of the solver within gambit for such games.

-Finally, an additional function was included which helps to convert games from the representation in sage to gambits representation ('_as_gambit')
+Finally, an additional function was included which helps to convert games from the representation in sage to gambits representation (`_gambit_`)

[tscrim]

comment:52

Done. Now that it is done, I think this is a better approach.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

80203f8

typo fixed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fab0962 to 80203f8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 80203f8 to 156ea0f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

156ea0f

some improvements to docs and tests

[dcoudert]

comment:55

I think it's better now. I let you conclude on the status of this ticket since I have not evaluated the other parts.

[vbraun]

Changed branch from public/game_theory/solves_constant_sum_games-18536 to 156ea0f