Opened 6 years ago

Closed 4 years ago

# Solvers for constant sum games

Reported by: Owned by: ptigwe minor sage-8.1 game theory Game Theory, Gambit, Zero-sum game Constant Sum Game, Normal Form Games vinceknight, dimpase, kcrisman, ncohen Tobenna P. Igwe Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik, David Coudert N/A 156ea0f 156ea0fb6214b694c34d3a85406dab63f32cf98e

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_`)

### comment:2 Changed 6 years ago by ptigwe

• Status changed from new to needs_review

### comment:3 follow-up: ↓ 7 Changed 6 years ago by kcrisman

• 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 :)
• E.g. although of course you test the gambit LP solver it would be nice to test the syntax here
```+        INPUT:
+
+        - ``solver`` - the solver to be used to solve the LP.
+
+          * ``'gambit'`` - This uses the solver included within the gambit library to
+            create and solve the LP.
```
same with other 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.)
• 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?
• The option `as_integer` is neither documented nor doctested.
```+    def _as_gambit_game(self, as_integer=False):
+        r"""
+        Creates a Gambit game from a ``NormalFormGame`` object
```
• `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?
• 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`?
• 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"
```
• 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`

Finally, I haven't yet actually pulled anything nor verified that the MILP in question will solve constant-sum games, so that would remain as well to review this. Should be fun to get in, though, great to see stuff coming to Trac so early from the GSOC!!!

Last edited 6 years ago by kcrisman (previous) (diff)

### comment:4 Changed 6 years ago by kcrisman

• Reviewers set to Karl-Dieter Crisman
• Status changed from needs_review to needs_work

### comment:5 Changed 6 years ago by git

• Commit changed from 19500540d3a3ccc3556e42299bdc2de1a54618ca to d9571793d208ed772fb8e7a7a335f9934dda1fe8

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

 ​29d4a7d `Added tests for PPL and Coin-OR solvers` ​6138791 `Raise error if gambit isn't installed` ​0029b3f `Improved documentation and doctests for _as_gambit_game` ​82da1bf `Raise error upon wrong solver being passed` ​d957179 `Update check for constant sum 'is_constant_sum'`

### comment:6 Changed 6 years ago by git

• Commit changed from d9571793d208ed772fb8e7a7a335f9934dda1fe8 to bb4eca8a48f9aa64a9e80a8df880d7ebb9cd20c0

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

 ​bb4eca8 `Updated doctests for '_solve_LP'`

### comment:7 in reply to: ↑ 3 ; follow-up: ↓ 8 Changed 6 years ago 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.

• 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.

 ​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.

 ​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.

 ​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`
 ​6138791 `Raise error if gambit isn't installed`

There are two possible `ValueError`'s that could be raised. The first comes from `NormalFormGame` upon entering a solver of the wrong format, and the second is from `MixedIntegerLinearProgram` if the LP solver is invalid.

Last edited 6 years ago by ptigwe (previous) (diff)

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 10 Changed 6 years ago by kcrisman

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.

Great, very quick work.

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.

Well, usually such underscore methods aren't "publicly" available. Vince, what do you think?

• `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.

 ​d957179 `Update check for constant sum 'is_constant_sum'`

But which one is in principle faster or better? I don't mind using numpy as long as importing it doesn't cause problems in speed, if it's better (which perhaps it is).

Currently, we are considering moving the `maximization` option into the constructor of the class.

Fine, but this is currently breaking functionality. So either you have to do that here, or make that change a prereq to this ticket, or something else. My recommendation is to just leave it here for now and then deal with the class constructor bit in a separate ticket (to make things as orthogonal as possible).

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.

Ah.

### comment:9 Changed 6 years ago by git

• Commit changed from bb4eca8a48f9aa64a9e80a8df880d7ebb9cd20c0 to 60efdc7f823c8aa64ac176addcd376f1f571b09d

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

 ​60efdc7 `Fixed '_as_gambit_game' to support 'maximization' parameter`

### comment:10 in reply to: ↑ 8 Changed 6 years ago by ptigwe

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.

Well, usually such underscore methods aren't "publicly" available. Vince, what do you think?

Actually, gambit performs it's own check as well, which makes three checks in total. So I've removed the one within `_solve_gambit_LP`, and added a doctest for the gambit error.

• `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.

 ​d957179 `Update check for constant sum 'is_constant_sum'`

But which one is in principle faster or better? I don't mind using numpy as long as importing it doesn't cause problems in speed, if it's better (which perhaps it is).

The current implementation is faster than the numpy implementation. I ran some bench marks using `timeit` and got `177 µs per loop` for the current implementation vs `992 ms per loop` for the numpy implementation using a matrix of size `1000x1000`.

Currently, we are considering moving the `maximization` option into the constructor of the class.

Fine, but this is currently breaking functionality. So either you have to do that here, or make that change a prereq to this ticket, or something else. My recommendation is to just leave it here for now and then deal with the class constructor bit in a separate ticket (to make things as orthogonal as possible).

Integrated the `maximization` parameter into `_as_gambit_game`.

### comment:11 Changed 6 years ago by ptigwe

• Status changed from needs_work to needs_review

### comment:12 follow-up: ↓ 16 Changed 6 years ago by kcrisman

Great. Here is what I think still needs to happen.

• You should add an example testing the `maximization=False`
• This error looks messed up because of the extra spaces - check for others like this:
```ValueError: The Gambit implementation of LCP only
allows for integer valued payoffs.
```
• You should fix the following formatting
```+        INPUT:
+        - ``as_integer`` - Boolean value which states whether the gambit representation should have
+                           the payoffs represented as integers or decimals.
```
(there should be a blank line between `INPUT:` and the rest, I think) even though it is an underscore method and won't appear in documentation.
• You should decide whether you want `# optional - Coin` or `# optional - cbc`
• Is `PPL` or `CVXOPT` really an optional thing? I think they are standard Sage packages...
• It would be really nice to have at least one example in the doc of a solved (not just constructed, as in the documentation of `is_constant_sum`) constant-sum non-zero-sum game.
• I (or another reviewer) need to check that the MILP is the right one
• I (or another reviewer) need to check that documentation builds right and looks good
• I (or another reviewer) need to check that the tests work right - guess I had better start installing some packages :)
• I (or another reviewer) need to do some spot checks of everything

Which is all not too hard, we're almost there.

What is the next project on the GSOC timeline?

Last edited 6 years ago by kcrisman (previous) (diff)

### comment:13 follow-up: ↓ 17 Changed 6 years ago by kcrisman

I cannot figure out how to get the changes in the doc built, it's maddening. I'll have to assume it's okay and I didn't miss anything.

The following could be improved, it really looks pretty meager. Not necessarily for this ticket, as definitely pre-existing - Vince, I'll blame you for this :)

```class NormalFormGame(SageObject, MutableMapping):
r"""
An object representing a Normal Form Game. Primarily used to compute the
Nash Equilibria.

INPUT:

- ``generator`` - Can be a list of 2 matrices, a single matrix or left
blank.

"""
```

It should at least tell how to get to more documentation from there.

The following

```+        p = MixedIntegerLinearProgram(maximization=False, solver=solver)
+        y = p.new_variable(nonnegative=True)
+        v = p.new_variable(nonnegative=False)
+        p.add_constraint(self.payoff_matrices()[0] * y - v[0] <= 0)
+        p.add_constraint(matrix([[1] * strategy_sizes[0]]) * y == 1)
+        p.set_objective(v[0])
```

looks good though I would prefer to use maximization and swap that first constraint or whatever is appropriate, but presumably this is the industry standard to minimize.

So... is the reason for doing this only for constant-sum games because it's only known to be in P for them? Is it potentially still faster even for non-constant-sum games?

Doctests pass.

I think it's worth pointing out somewhere in the documentation that the LP approach will give one NE but not all of them, should there be more than one. (Constant-sum games can have more than one NE, right? I guess the trivial game is an example.)

### comment:14 Changed 6 years ago by kcrisman

• Status changed from needs_review to needs_work

### comment:15 Changed 6 years ago by git

• Commit changed from 60efdc7f823c8aa64ac176addcd376f1f571b09d to a24c7dd1ebd473b679fe070c173e7c824138e3d2

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

 ​0e300ae `Fixed indentation and removed incorrect error` ​313f42c `Updated tests for cbc and PPL` ​a24c7dd `Included tests for constant-sum non-zero sum game and included maximization in the LP solver`

### comment:16 in reply to: ↑ 12 Changed 6 years ago by ptigwe

• You should add an example testing the `maximization=False`

There's currently one at the start of `obtain_nash`, showing that it's possible for the equilibrium found could be different. Do you want me to do something similar for all the methods, or would the one be enough?

• This error looks messed up because of the extra spaces - check for others like this:
```ValueError: The Gambit implementation of LCP only
allows for integer valued payoffs.
```

Actually, I was supposed to remove this error earlier on as it doesn't hold. I removed the documentation but forgot to remove the actual error.

• You should decide whether you want `# optional - Coin` or `# optional - cbc`
• Is `PPL` or `CVXOPT` really an optional thing? I think they are standard Sage packages...

I've removed `#optional - PPL`.

• I (or another reviewer) need to check that the MILP is the right one
• I (or another reviewer) need to check that documentation builds right and looks good
• I (or another reviewer) need to check that the tests work right - guess I had better start installing some packages :)
• I (or another reviewer) need to do some spot checks of everything

Which is all not too hard, we're almost there.

What is the next project on the GSOC timeline?

Coming up next would be the Lemke-Howson algorithm for solving 2-player games.

### comment:17 in reply to: ↑ 13 ; follow-ups: ↓ 18 ↓ 19 Changed 6 years ago by ptigwe

The following could be improved, it really looks pretty meager. Not necessarily for this ticket, as definitely pre-existing - Vince, I'll blame you for this :)

```class NormalFormGame(SageObject, MutableMapping):
r"""
An object representing a Normal Form Game. Primarily used to compute the
Nash Equilibria.

INPUT:

- ``generator`` - Can be a list of 2 matrices, a single matrix or left
blank.

"""
```

It should at least tell how to get to more documentation from there.

OK. I was planning on opening a ticket, towards the end of GSOC, which would address the documentation as a whole. In the mean time, changes to the documentation would be based on changes made to the code.

The following

```+        p = MixedIntegerLinearProgram(maximization=False, solver=solver)
+        y = p.new_variable(nonnegative=True)
+        v = p.new_variable(nonnegative=False)
+        p.add_constraint(self.payoff_matrices()[0] * y - v[0] <= 0)
+        p.add_constraint(matrix([[1] * strategy_sizes[0]]) * y == 1)
+        p.set_objective(v[0])
```

looks good though I would prefer to use maximization and swap that first constraint or whatever is appropriate, but presumably this is the industry standard to minimize.

So... is the reason for doing this only for constant-sum games because it's only known to be in P for them?

Yeah.

Is it potentially still faster even for non-constant-sum games?

Not sure if you are asking about using the LP for non-constant-sum games or the general classification of finding a Nash in a general game. In case if it was a bit of both:

• LP's aren't guaranteed to find a Nash equilibrium in a two player non-constant-sum game.
• Finding a Nash is PPAD-complete. Even the problem of approximation is hard.

Doctests pass.

That's Good.

I think it's worth pointing out somewhere in the documentation that the LP approach will give one NE but not all of them, should there be more than one. (Constant-sum games can have more than one NE, right? I guess the trivial game is an example.)

OK.

### comment:18 in reply to: ↑ 17 Changed 6 years ago by kcrisman

OK. I was planning on opening a ticket, towards the end of GSOC, which would address the documentation as a whole.

Sounds fair.

Not sure if you are asking about using the LP for non-constant-sum games or the general classification of finding a Nash in a general game. In case if it was a bit of both:

• LP's aren't guaranteed to find a Nash equilibrium in a two player non-constant-sum game.

Very interesting!

### comment:19 in reply to: ↑ 17 ; follow-up: ↓ 20 Changed 6 years ago by vinceknight

Hi both,

Apologies for my silence (on organisation committee of a conference that has been running this week so have been pretty busy). Apologies also if as a result my comments below don't make full sense (in case I missed something).

I cannot figure out how to get the changes in the doc built, it's maddening. I'll have to assume it's okay and I didn't miss anything.

The following could be improved, it really looks pretty meager. Not necessarily for this ticket, as definitely pre-existing - Vince, I'll blame you for this :)

```class NormalFormGame(SageObject, MutableMapping):
r"""
An object representing a Normal Form Game. Primarily used to compute the
Nash Equilibria.

INPUT:

- ``generator`` - Can be a list of 2 matrices, a single matrix or left
blank.

"""
```

It should at least tell how to get to more documentation from there.

This is certainly due to me, it happened as a result of moving the documentation that was there to the front matter, I think I perhaps did not fully understand :) Perhaps a ticket could be opened about the documentation (as Tobenna suggested towards the end of gsoc) that fully describes what we want the docs to look like :)

I think it's worth pointing out somewhere in the documentation that the LP approach will give one NE but not all of them, should there be more than one. (Constant-sum games can have more than one NE, right? I guess the trivial game is an example.)

OK.

I think it could be worth doctesting also? (So showing that all equilibria are find by some algorithms and not by LP etc...)

Great work on this Tobenna, really looking solid and thanks to Karl for reviewing (as always this is greatly appreciated).

### comment:20 in reply to: ↑ 19 ; follow-up: ↓ 22 Changed 6 years ago by kcrisman

This is certainly due to me, it happened as a result of moving the documentation that was there to the front matter, I think I perhaps did not fully understand :) Perhaps a ticket could be opened about the documentation (as Tobenna suggested towards the end of gsoc) that fully describes what we want the docs to look like :)

Actually, I'll open it now and set it to sage-pending so we don't forget. #18609.

I think it's worth pointing out somewhere in the documentation that the LP approach will give one NE but not all of them, should there be more than one. (Constant-sum games can have more than one NE, right? I guess the trivial game is an example.)

OK.

I think it could be worth doctesting also? (So showing that all equilibria are find by some algorithms and not by LP etc...)

Okay, so we're agreed on this.

Another small point - no maximization here.

```        if algorithm.startswith('lp-'):
return self._solve_LP(solver=algorithm[3:])
```

Of course, at some point this is pedantic if you are planning on removing it - but actually, given that it pre-existed this ticket, I guess you'll have to deprecate that keyword.

You should add an example testing the maximization=False

There's currently one at the start of obtain_nash, showing that it's possible for the equilibrium found could be different. Do you want me to do something similar for all the methods, or would the one be enough?

What I meant was one for the new LP solver functionality.

### comment:21 Changed 6 years ago by git

• Commit changed from a24c7dd1ebd473b679fe070c173e7c824138e3d2 to fb4461ce6d228ad7f6709ee4b8b523243012daf9

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

 ​2f44485 `Tests for single / multiple Nash equilibria` ​fb4461c `Fixed minor error with LP solver`

### comment:22 in reply to: ↑ 20 Changed 6 years ago by ptigwe

Another small point - no maximization here.

```        if algorithm.startswith('lp-'):
return self._solve_LP(solver=algorithm[3:])
```

Of course, at some point this is pedantic if you are planning on removing it - but actually, given that it pre-existed this ticket, I guess you'll have to deprecate that keyword.

You should add an example testing the maximization=False

There's currently one at the start of obtain_nash, showing that it's possible for the equilibrium found could be different. Do you want me to do something similar for all the methods, or would the one be enough?

What I meant was one for the new LP solver functionality.

Dima, Vince and I have thought and discussed about this issue for a while, and have decided to remove maximization completely. So the next few patches should be addressing this.

### comment:23 Changed 6 years ago by kcrisman

Okay. Probably best is to have that be a dependency of this ticket... And if you end up not deprecating this and just remove it (which could conceivably be reasonable in the particular context) be sure to have plenty of good arguments backing up that decision "for posterity's sake".

### comment:24 Changed 6 years ago by git

• Commit changed from fb4461ce6d228ad7f6709ee4b8b523243012daf9 to e4107dcffd292341c016e7878e28cc3150a6c434

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

 ​e4107dc `Updated tests for normal form games`

### comment:25 Changed 6 years ago by ptigwe

• Status changed from needs_work to needs_review

Besides the deprecation (which would be done in a separate ticket), I believe that's everything for this one. If I've missed anything please let me know.

### comment:26 Changed 6 years ago by ptigwe

• Status changed from needs_review to needs_work

### comment:27 Changed 6 years ago by git

• Commit changed from e4107dcffd292341c016e7878e28cc3150a6c434 to c225b92b1b6619612591e58066231cbef48b99b4

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

 ​c225b92 `Remove maximization from LP functions as it is going to be deprecated`

### comment:28 Changed 6 years ago by git

• Commit changed from c225b92b1b6619612591e58066231cbef48b99b4 to 93229b7b4169912e6fa686e18bd36c172db7334c

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

 ​93229b7 `Revert "Remove maximization from LP functions as it is going to be deprecated"`

### comment:29 Changed 6 years ago by ptigwe

• Status changed from needs_work to needs_review

### comment:30 Changed 6 years ago by tscrim

Instead of calling the method `_as_gambit_game`, to be consistent with other parts of Sage, I would call it `_gambit_` (like how the `_gap_` method returns a representation of the object in GAP). Also the doc for `INPUT:` for that method is misaligned.

### comment:31 Changed 6 years ago by git

• Commit changed from 93229b7b4169912e6fa686e18bd36c172db7334c to ddd6f7e3cc658e0630896edbf7b038ee805c5147

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

 ​ddd6f7e `Renamed '_as_gambit_game' to '_gambit_' and fixed 'INPUT' indentation issues`

### comment:32 Changed 6 years ago by git

• Commit changed from ddd6f7e3cc658e0630896edbf7b038ee805c5147 to 06d6b4c1f0edabdd3561df2de2bb2819fdf25e17

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

 ​6e2aae5 `Merge branch 'develop' into gt_extension` ​92345cc `Modified the '_gambit_' function to support n-player games` ​2c6aee7 `Update doctests` ​06d6b4c `Updated doctests of `catalog` to use `enumeration``

### comment:33 Changed 6 years ago by git

• Commit changed from 06d6b4c1f0edabdd3561df2de2bb2819fdf25e17 to 2c4d951c7be2b10c45e8c8643ca8f4f2e0cc0dd7

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

 ​2c4d951 `Updated front matter`

### comment:34 Changed 6 years ago by git

• Commit changed from 2c4d951c7be2b10c45e8c8643ca8f4f2e0cc0dd7 to e538b14e92e9b1669262f9043bb2d89ec43e06bd

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

 ​e538b14 `Added name to AUTHORS`

### comment:35 Changed 6 years ago by kdilks

• Status changed from needs_review to needs_work

More doctests need to be marked as optional.

### comment:36 Changed 5 years ago by git

• Commit changed from e538b14e92e9b1669262f9043bb2d89ec43e06bd to 90f7051254b885f79423432061b85fb8e1741316

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

 ​51912a5 `Updated optional flags` ​90f7051 `Merge branch 'develop' into gt_extension`

### comment:37 Changed 5 years ago by ptigwe

• Status changed from needs_work to needs_review

### comment:38 Changed 4 years ago by mderickx

• Status changed from needs_review to needs_work

Needs to be rebased on sage8.1.beta3

### comment:39 Changed 4 years ago by tscrim

• Branch changed from u/ptigwe/gt_extension to public/game_theory/solves_constant_sum_games-18536
• Commit changed from 90f7051254b885f79423432061b85fb8e1741316 to 9b4a9cb01a2d4fc6cff0aec257af9049cd49ad1a
• Milestone changed from sage-6.8 to sage-8.1
• Reviewers changed from Karl-Dieter Crisman to Karl-Dieter Crisman, Travis Scrimshaw
• Status changed from needs_work to needs_review

Rebased version.

New commits:

 ​9b4a9cb `Rebased on 8.1.beta9.`

### comment:40 Changed 4 years ago by git

• Commit changed from 9b4a9cb01a2d4fc6cff0aec257af9049cd49ad1a to 9e009fbe113cf6cc277800182ff4f60da8c63aa8

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

 ​9e009fb `Some small documentation updates.`

### comment:41 Changed 4 years ago by tscrim

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

### comment:42 Changed 4 years ago by dimpase

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)],
```

### comment:43 Changed 4 years ago by git

• Commit changed from 9e009fbe113cf6cc277800182ff4f60da8c63aa8 to c2a1187b541f0e89cd0a86bf3974bd5e056f4647

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

 ​c2a1187 `fixed doc building and a test`

### comment:44 Changed 4 years ago by dimpase

• Reviewers changed from Karl-Dieter Crisman, Travis Scrimshaw to Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik
• Status changed from needs_review to positive_review

Thank you.

### comment:46 follow-up: ↓ 49 Changed 4 years ago by dcoudert

• Status changed from positive_review to needs_work

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):
```

### comment:47 follow-up: ↓ 48 Changed 4 years ago by git

• Commit changed from c2a1187b541f0e89cd0a86bf3974bd5e056f4647 to f5b73ea3d982260e2cdfd8c12aea8596a65b9c13

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

 ​f5b73ea `fixed doc building and a test`

### comment:48 in reply to: ↑ 47 Changed 4 years ago by dimpase

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:...`

### comment:49 in reply to: ↑ 46 Changed 4 years ago by dimpase

• Reviewers changed from Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik to Karl-Dieter Crisman, Travis Scrimshaw, Dima Pasechnik, David Coudert
• Status changed from needs_work to needs_review

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.

### comment:50 Changed 4 years ago by tscrim

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.

### comment:51 Changed 4 years ago by git

• Commit changed from f5b73ea3d982260e2cdfd8c12aea8596a65b9c13 to fab09626d265466e74c0e7bdab7ac18cc7e2f6b5

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

 ​fab0962 `Using a solver argument for LP algorithm.`

### comment:52 Changed 4 years ago by tscrim

• Description modified (diff)

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

### comment:53 Changed 4 years ago by git

• Commit changed from fab09626d265466e74c0e7bdab7ac18cc7e2f6b5 to 80203f8ac9221ec93712207dd3f1bd9345eef4a4

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

 ​80203f8 `typo fixed`

### comment:54 Changed 4 years ago by git

• Commit changed from 80203f8ac9221ec93712207dd3f1bd9345eef4a4 to 156ea0fb6214b694c34d3a85406dab63f32cf98e

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

 ​156ea0f `some improvements to docs and tests`

### comment:55 Changed 4 years ago by dcoudert

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

### comment:56 Changed 4 years ago by dimpase

• Status changed from needs_review to positive_review

### comment:57 Changed 4 years ago by vbraun

• Branch changed from public/game_theory/solves_constant_sum_games-18536 to 156ea0fb6214b694c34d3a85406dab63f32cf98e
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.