Game Theory: Build class for normal form games as well as ability to obtain Nash equilibria

Include class for 2 player normal form games.

Allow for calculation of Nash Equilibria using lrs optional package and a bespoke support enumeration algorithm (so that a light weight approach exists for small games which does not require installation of lrs).

CC: @kcrisman

Component: game theory

Keywords: Normal Form Games

Author: Vince Knight, James Campbell

Branch/Commit: 986fa93

Reviewer: Karl-Dieter Crisman

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

Commit: 33861c9

comment:3

Have removed gambit code so now there are just two algorithms that run (and both have a lot of tests). I (think I) have branched and just committed code straight from develop so hopefully there is no mess re branches etc... If there's still a mess please let me know.

New commits:

`0e080dd`	`Have ability to solve game with lrs and support enumeration`
`33861c9`	`Have ability to solve game with lrs and support enumeration`

comment:5

It's always easier to nitpick than test, because I don't have to think about branches or start Sage. Plus, I can see it will really take some time to go through the representation/algorithm stuff. So here goes.

Dumb question:

from sage.misc.package import is_package_installed

Is that really necessary in all.py? It does make sense in the other files.

minor

+    Normal form games, also referred to as strategic form games are used to
+    model situations where agents/players make strategic choices the outcome
+    of which depends on the strategic choices of all players involved.

maybe a few commas here

+    Normal form games, also referred to as strategic form games, are used to
+    model situations where agents/players make strategic choices, the outcome
+    of which depends on the strategic choices of all players involved.

I'll let "modelled" pass since you are based in the UK ;-)
I'll let you figure these out

Amy prefers to player video games
Gambit has it's own Python api

You have things like game: :: several times. Typically Sage code where a colon would be appropriate before a doctest is just game:: even though I suppose you are right that it might not look as good in built doc.
In your opening discussion, there is a discrepancy over 1.0 and 1 in the results of the Battle of the Sexes, also with 3/4 versus 0.75. I don't know which is preferable.
Sage should always be capitalized Sage not sage.
You may want to switch to Python 3 formatting in your example of printing the Nash equilibria utilities.
By the way, both here and in #16331, I'm wondering whether a lot of the (great) documentation you have for the main games maybe belongs (also) in the initial docstring. The reason is that this is what is at the top of the html/pdf documentation. But maybe these are such short files that the main game appears at the top anyway. Though for this ticket the starting documentation is SO long I think that really a lot of it should be at the top - and hopefully there will be some easy way for someone at the command line or notebook to then ask for that top bit.
https://github.com/tturocy/gambit/tree/sage_integration probably not necessary to have the link currently.
I think it gets lost here that although you are correct that such games are technically two matrices, they are nearly universally represented as one matrix with two elements in each position. I'm not sure how to resolve this, but it should be thought about. This comes up in the LaTeX method in particular, though also the documentation.
Similarly, one should think very carefully about the default string representation of the game being

{(0, 1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}

rather than some matrix-y thing. We have lots of ways to print stuff like that in tables and matrices in Sage. That doesn't mean that internally it can't be a dict, of course!

I just love that you are including the plots of the utility functions. This is so typical for pedagogy and will make this really useful. I'm cc:ing Greg Bard, who has done this in the past himself, for any comments he may have on this.
Input a single matrix creates zero-sum - then implicitly two players is assumed? But I bet we want to be able to eventually assume representation of at least three players, even if we can't solve them yet.
bonus/malus - I've never heard of a "malus" but I like it even if it isn't a word, it should be, perfect Latinate creation.
ALL METHODS must have documentation. Even private double underscore ones.
Where did the examples from _repr_ go? Same for payoff_matrices.
I have a similar question about adding players with default strategies as on the other ticket. What purpose does _generateutilities perform? (And why isn't it _generate_utilities?)
algorithm='enumeration' or not? You have in one spot ``"support enumeration"`` which sounds horrible.
Why is parser.py a separate file? Are you planning on adding more stuff here that is used in general in other types of games (i.e., not normal form)? Don't forget to doctest that too... Have fun! All this said, this is clearly very well-organized and I'm looking forward to seeing this in Sage. Naturally along with Gambit compatibility :)

comment:6

I just love that you are including the plots of the utility functions. This is so typical for pedagogy and will make this really useful. I'm cc:ing Greg Bard, who has done this in the past himself, for any comments he may have on this.

Actually, he's not on Trac, I guess, but I'll let him know.

comment:7

I'd written a response to this yesterday and then lost it by pressing the wrong button: woops! So here goes again: just my initial thoughts before I start working on it :)

Replying to @kcrisman:

It's always easier to nitpick than test, because I don't have to think about branches or start Sage. Plus, I can see it will really take some time to go through the representation/algorithm stuff. So here goes.

Dumb question:
from sage.misc.package import is_package_installed
Is that really necessary in all.py? It does make sense in the other files.

Will see if works without and remove (might be a relic from when we were figuring out what we were doing).

minor

+    Normal form games, also referred to as strategic form games are used to
+    model situations where agents/players make strategic choices the outcome
+    of which depends on the strategic choices of all players involved.

maybe a few commas here

+    Normal form games, also referred to as strategic form games, are used to
+    model situations where agents/players make strategic choices, the outcome
+    of which depends on the strategic choices of all players involved.

I'll let "modelled" pass since you are based in the UK ;-)

Not at all precious about it, will look through the rest of Sage and align the UK/US spelling :)

I'll let you figure these out
Amy prefers to player video games
Gambit has it's own Python api

Thanks.

You have things like game: :: several times. Typically Sage code where a colon would be appropriate before a doctest is just game:: even though I suppose you are right that it might not look as good in built doc.

Thanks, that's a simple one to fix: will do :)

In your opening discussion, there is a discrepancy over 1.0 and 1 in the results of the Battle of the Sexes, also with 3/4 versus 0.75. I don't know which is preferable.

I'll take a look, this might also be a relic with gambit as gambit output only as floats. I'll clear it up.

Sage should always be capitalized Sage not sage.

Woops.

You may want to switch to Python 3 formatting in your example of printing the Nash equilibria utilities.

I'll need to look in to what that is but will do.

By the way, both here and in #16331, I'm wondering whether a lot of the (great) documentation you have for the main games maybe belongs (also) in the initial docstring. The reason is that this is what is at the top of the html/pdf documentation. But maybe these are such short files that the main game appears at the top anyway. Though for this ticket the starting documentation is SO long I think that really a lot of it should be at the top - and hopefully there will be some easy way for someone at the command line or notebook to then ask for that top bit.

Not too sure I understand (apologies). Are you saying to move the docs we wrote in the library (before any code kicks in) in to the docs for NormalFormGame?

https://github.com/tturocy/gambit/tree/sage_integration probably not necessary to have the link currently.

Thanks (and sorry for not picking this up myself).

I think it gets lost here that although you are correct that such games are technically two matrices, they are nearly universally represented as one matrix with two elements in each position. I'm not sure how to resolve this, but it should be thought about. This comes up in the LaTeX method in particular, though also the documentation.

This was a long discussion. We wanted to allow for both inputs for two player games: a bi matrix as well as two matrices. At one point we were going to work on creating a bi matrix class (inheriting/copying the Sage matrix class) and this is currently an 'enhancement' issue on our github repo (https://github.com/theref/sage-game-theory/issues/52).

We decided to leave it as it is for now as I think to create a bi matrix class (and to get it right) is not something worth rushing.

I certainly wouldn't want to get rid of the option to input games as two matrices as I think I slightly disagree about how universal the bi-matrix representation is as you do find the two matrix representation in papers and text books. In fact it can be argued that it's (from a pedagogic) point of view a 'better' representation as it links easilier to ideas regarding the underlying linear programming approaches.

So in essence I'd like to leave it as it is for now but with a view (over the next year or so) to work on a nice bi-matrix class... What do you think?

Similarly, one should think very carefully about the default string representation of the game being
{(0, 1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}

This is in fact completely analogous to the gambit representation of games and is something we concentrated on (with a view to further gambit integration later on). We thought about the gambit representation quite critically and realised that it is actually the 'best' way when it comes to generalising to games with more than 2 players (which will hopefully at some point be implemented as alluded to in the docs). So again, I think this is worth keeping as it is (although very open to discussing it if I'm missing something).

rather than some matrix-y thing. We have lots of ways to print stuff like that in tables and matrices in Sage. That doesn't mean that internally it can't be a dict, of course!

I just love that you are including the plots of the utility functions. This is so typical for pedagogy and will make this really useful. I'm cc:ing Greg Bard, who has done this in the past himself, for any comments he may have on this.

Thanks, this is actually from the time you mentioned it in our first video call quite a while ago now :)

Input a single matrix creates zero-sum - then implicitly two players is assumed? But I bet we want to be able to eventually assume representation of at least three players, even if we can't solve them yet.

Yes but in that case the input structures would have to be 'gambit'-y like the one example of a 3 player game (which is not solved) in the docs.

bonus/malus - I've never heard of a "malus" but I like it even if it isn't a word, it should be, perfect Latinate creation.

I think it might be a French word (I went to high school there so I do that sometimes...).

ALL METHODS must have documentation. Even private double underscore ones.

On it :) (sorry for being sloppy/lazy)

Where did the examples from _repr_ go? Same for payoff_matrices.

Will look for them.

I have a similar question about adding players with default strategies as on the other ticket. What purpose does _generateutilities perform? (And why isn't it _generate_utilities?)

Will reflect on this.

algorithm='enumeration' or not? You have in one spot ``"support enumeration"`` which sounds horrible.

Not too sure I understand. 'support enumeration' is the actual name of the algorithm which is what we need to pass as an argument (so have shorted to enumeration) like we could also pass lrs. Would support_enumeration be any better?

Why is parser.py a separate file? Are you planning on adding more stuff here that is used in general in other types of games (i.e., not normal form)? Don't forget to doctest that too...

This was a separate file as we also need to parse the gambit output, so once I work on #16333 there will be another parsing method in there (and will indeed aim to do the same of other types of games further down the line). Will add doctests...

Have fun! All this said, this is clearly very well-organized and I'm looking forward to seeing this in Sage. Naturally along with Gambit compatibility :)

Thanks :) Will start working on it on my flight home.

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`692785b`	`Added tests and an explenation to generate_utilities`
`7fa190f`	`Added doctests and slightly refactored row_cond_dominance`
`353a2dc`	`tidied a test slightly`
`fbe0b0f`	`Added doctests to solve_indifference`
`d5b8f03`	`Made tests for indifference a bit more verbose`
`1303268`	`Added another test to is_NE`
`0d12841`	`minor refactoring`
`be6add6`	`minor minor refactoring`
`9febc45`	`Have added doctest to parser`
`ffa6d52`	`Changed formatting to python 3 style`

Changed commit from 33861c9 to ffa6d52

comment:9

Hi Karl, I've gone through and pretty much addressed all your queries, apart from the ones I mentioned above that I thought were better as they are (but very open to talk about it and figure out what is best).

Thanks!

comment:10

Hi all,

Been away from the laptop for a couple of months and was just wondering what's left to do?

Thanks, James

comment:11

Been away from the laptop for a couple of months and was just wondering what's left to do?

Needs review, largely!

Unfortunately, something isn't quite right on the git view online - see https://github.com/sagemath/sagetrac-mirror/blob/develop/src/sage?id=6800b2c2b7037ae7bf25c297fd139ee48a5ece10 and the "bad object" line for game_theory. See here and here for the actual files in question.

Anyway, a couple of minor things before I have time to check it out properly.

There are however a variety of such algorithms available in gambit, seems orphaned.
Overzealous deleting In the following we create the game and solve i:: and game. In fact degenerate games can cause problems for most algorithm:: and Here is a slightly larger gam::
Caps for exs?

   def payoff_matrices(self):
        r"""
        Returns 2 matrices representing the payoffs for each player.

        Examples ::

I'll be looking at this in more detail over the next few days as I have time.

comment:12

Parser comments.

Minor - this could be made slightly more professional-sounding. Also, double ticks for code markup; maybe even ``'lrs'`` if it is a string, I'm not sure about this.

    At present the only parser included is the for `lrs` algorithm however
    this will be expanded to `gambit` soon.

Since lrs is an optional package, will any of the doctests in the parser file need to be marked optional? I assume not, just checking. (Maybe the one using the subprocess stuff?)
Will those temp files really disappear or do you need to remove them? I just don't remember - we use the temp file name thing so it doesn't overwrite, but I can't remember if we need to remove them afterwards, though I believe we do.
Just out of curiosity, what does the fourth element of the stuff mean that you parse?

'2  0  1  2 \n', '1  1/2  1/2 -2 \n'

the first number is the player, the next two the strategy (does lrs only do two player, two-strategy games?) but what is the 2 and -2 here?

Could the creation of the p1_strategies be sped up slightly with something like

p2_strategies.append(sage_eval(k) for k in i.split() if k.index() !=1 or -1)

(this syntax is not right, I'm sure) ? Again, probably quite minor to even think about given the type of use case.

comment:13

Hmm, you'll want to amend src/doc/en/reference/game_theory/index.rst, I bet.

comment:14

Two issues from above I return to.

algorithm='enumeration' or not? You have in one spot "support enumeration" which sounds horrible.

Not too sure I understand. 'support enumeration' is the actual name of the algorithm which is what we need to pass as an argument (so have shorted to enumeration) like we could also pass lrs. Would support_enumeration be any better?

What I mean is that when you put something in quotes and double backticks, it looks like code. You can call it support enumeration and still use 'enumeration' as the algorithm keyword, but then you need to make it quite clear what the difference is. I agree that shorter is better in this case. No double backticks (as later in the doc), not a problem.

By the way, both here and in #16331, I'm wondering whether a lot of the (great) documentation you have for the main games maybe belongs (also) in the initial docstring. The reason is that this is what is at the top of the html/pdf documentation. But maybe these are such short files that the main game appears at the top anyway. Though for this ticket the starting documentation is SO long I think that really a lot of it should be at the top - and hopefully there will be some easy way for someone at the command line or notebook to then ask for that top bit.

Not too sure I understand (apologies). Are you saying to move the docs we wrote in the library (before any code kicks in) in to the docs for NormalFormGame?

What I mean is that you have some documentation in the class definition for NormalFormGame that probably can just go in the initial docstring at the very top of the file. After all, it's quite general stuff about what games and Nash equilibria are. This also applies to #16331, as I say, but perhaps somewhat less so since it will not be expanded in the near future.

Items new to this take on the actual file.

We can use Sage to find them and more importantly see if there is a - please have someone who knows commas go through this entire file. I don't need every Oxford comma, but the sentences are often quite run-on.
In the following section, you may need to clarify that you mean this as vector/matrix multiplication. Even though you then do that in Sage, someone who is just reading it and not necessarily looking at the code may get confused - especially those who come from a background where column vectors and row vectors are truly separate things, never to be mixed (as opposed to in Sage!).

    We can use Sage to compute the expected utility for any mixed strategy
    pair `(\sigma_1, \sigma_2)`. The payoff to player 1 is given by:

In playing strategy `i` is given by (`(Ay)_i`) perhaps once again a gentle reminder that you mean matrix times vector could be useful. Do you think I'm being too gentle on the reader?
Rock-Paper-Scissors-Lizard-Spock - I'm scared to ask... fun, but perhaps want to put a reference in for this non-standard example.
I am scared of the syntax sage: f.add_player(2). Am I adding the player named 2? Am I adding two new players? And why do I do this twice in a row? Using "gambit syntax" is nice but would need to be fully explained. By the way, this is the kind of thing that really does do better in the "top matter".
Can we add the name of a player, or is that a horrible idea? Just because it might eventually get confusing with lots of players.
A programmed example of a way to use the

        sage: threegame = NormalFormGame()
        sage: threegame.add_player(2)
        sage: threegame.add_player(2)
        sage: threegame.add_player(2)
        sage: threegame[0, 0, 0][0] = 3
        sage: threegame[0, 0, 0][1] = 1
        sage: threegame[0, 0, 0][2] = 4
...

syntax would be nice, just like we did in the other game theory tickets. Who is going to type all that in (accurately) by hand, anyway? So demonstrating it's possible to do it right with a loop or something is useful.

The airline example is cool (actually, really interesting) but really needs to be in top matter or at least somehow separated. Also, if there are two paragraphs, separate them with another newline.
In this same example, you have it that the best strategy is to say the stuff is worth two, but you have

[[(1, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0)]]

Doubtless this corresponds to 100% choosing the first strategy, but that is not clear since the way the problem is stated makes it sound like there are 99 strategies or something.

"In fact degenerate games can cause problems for most algorithm" - but what is the problem caused in the following example? It gives a solution that adds to 100% for each player...

comment:15

Before continuing, I just have to say that this is really exceptionally well-organized. Good work.

Moving on to the methods.

But what will happen to the deleted game? Will this raise an error if you try to do anything with it? (Maybe I'll find out later.)

            sage: prisoners_dilemma
            {(1, 0): [0, 5], (0, 0): [2, 2], (1, 1): [4, 4]}

Can you __setitem__ for an already-set item in the game? If not (for whatever reason), then this should be doctested. If yes, I guess this should be justified and doctested too.
Can you move that method to with the other dictionary-emulating methods? Not super-important but helpful to those reading code. __iter__ and __len__ strictly speaking are not about dict emulation but just emulation of iterables.
Usually __init__ is best at the very first. Am I missing something that the emulation ones are coming first?
I would have expected this to list the bimatrix entries. Instead I get a very boring list of the possible pure strategies.

            sage: for key in prisoners_dilemma:
            ....:     print key

Will length basically always be n times m in terms of the number of strategies? In which case do you really need all that extra stuff about utilities?

Generator function must be a list or nothing is not doctested.
generator != None or generator is not None? Just wondering which you intend here.
LaTeX method shows nothing interesting for games with more players:: - then you should probably use the ... like so:

\text{\texttt{<bound{ }method{ }NormalFormGame...[False,{ }False,{ }False]{\char`\}}>}}

or the like.

I still do not like return str(self.utilities) for the string rep. It should at least say, at the very least, that it is in fact a normal form game!!! Maybe "Normal Form Game with following utilities" or whatever.
One of the errors in the payoff matrices method is tested, the other isn't.
m1 = matrix(QQ, - oh, oh. But didn't you say that Gambit does floats? And what if people input floats? I'm just thinking of nasty things like people inputting 1/sqrt(2) as a probability, or ones where when they are coerced to rationals don't add up to 100%
I'd like to see an example with

sage: g._generate_utilities(True)

where it would actually destroy a utility. Myuh-ha-ha!

The line

Checks if ``utilities`` has been completed

doesn't seem to correspond to any errors, though.

These mixed strategies

[[(1, 0, 0, 0), (127/1212, 115/1212, 485/606)], [(0, 1, 0, 0), (0, 1/26, 25/26)]]

seem strange, but I assume correct - can you confirm they are exact answers?

The line

        This particular game has 3 Nash equilibria::

isn't backed up by

            sage: g.obtain_Nash(maximization=False)
            [[(1, 0, 0), (0, 1)]]

unless I'm misunderstanding the syntax. Where are the other two equilibria promised to the reader? This seems to happen in a few other examples. (Actually, I think that some copy-paste is at fault here, esp. since maximization=False but that isn't mentioned.)

The or a?

A function to return the Nash equilibrium for a game.

Should it be obtain_Nash or obtain_nash?
When you use tmp_filename() in the things themselves (not doctests) are there any other strange side-effects?
I feel like you tired (understandable!) in the _solve_enumeration doctests. Most of them should be tests and not examples in any case, I suppose. Here is the funniest of them, I actually laughed at this one.

        TESTS:

        Due to the nature of the linear equations solved in this algorithm
        some negative vectors can be returned. Here is a test that ensures
        this doesn't happen::

            sage: a = matrix([[-13, 59],
            ....:             [27, 86]])
            sage: b = matrix([[14, 6],
            ....:             [58, -14]])
            sage: c = NormalFormGame([a, b])

It sure doesn't happen! Since we never try to find said vectors :-)

Adding strategies should then have an example finishing it.

    If we do this and try and obtain the Nash equilibrium or view the payoff
    matrices(without specifying the utilities), an error is returned::

but it's never finished up.

What happens with a completely trivial matrix i.e. all payoffs are zero? Then all mixed strategies are optimal, I guess...

Remaining:

Making sure the _solve_enumeration actually is correct. I'm sure it is, I just haven't had time to look at it.
I will have to just trust you on the _Hrepresentation method.

Almost there!

Finally, as a general rule of thumb, if you have any pretty useful tests or examples which are in underscore methods (which won't show up in the reference manual) maybe repeat them elsewhere. I don't know if you do that, just mentioning it.

comment:16

Looking at the reference for support enumeration (page 103), I find a few final (hopefully!) questions. Most are probably due to my unfamiliarity with the details of this algorithm, though I think it is quite interesting as a strategy.

The algorithm for some reason sorts the support size profiles, but I don't see that in the code.
The algorithm definitely implies that there could be different numbers of pure strategies for each player, and your examples and potential_supports seem to suggest this, but then potential_support_pairs and how that is used seems to implicitly ... I don't know, it just doesn't smell right. E.g.

if len(pair[0]) == len(pair[1])

should really be comparing two different supports for player 1, according to the pseudocode in the paper, but here you are comparing a support from player 1 with one from player 2. Shouldn't you be comparing supports of the same size as the player 1 supports with respect to $A'_2$? However, I may be misunderstanding the algorithm.

Also, do you have to do all the construction of tuples and such or is there a more efficient way to go from the power set to the evaluation of the supports? Maybe there isn't.
Minor doc note: or does not have a dominated row: should have one more colon.
Just brainstorming - maybe in _row_cond_dominance one doesn't have to cycle through the product of rows and rows, but could check rows i and j for i>j and then immediately check for j>i... because as soon as one is dominated, you return False, and right now it's a weary n^2 but maybe you could make it n(n+1)/2 if you only check each pair once, but twice within the pair (if that makes sense).
Minor but made the code harder to understand:

for p2_strategy in range(self.players[1].num_strategies):
for i in range(self.players[0].num_strategies):

even though they fill exactly the same role. Same with

for p2_strategy in range(len(p2_support)):
for j in range(len(p1_support)):

Should _solve_indifference really return False, or maybe just [], when it isn't possible (since if foo: doesn't happen as long as foo is "empty" in its type)?
Would it help to formally do this as an LP with Sage LPs or is solve_right sufficient?
I just don't see how

linearsystem2[j, p2_strategy] = M1[p1_support[j]][p2_strategy] - M1[p1_support[j-1]][p2_strategy]

corresponds to the TGS, though somehow it must. (4.30) is essentially

linearsystem2[-1, p2_strategy] = 1

and _is_NE corresponds more or less to (4.28) and (4.29). I think

p1_payoffs = [sum(v * row[i] for i, v in enumerate(b)) for row in M1.rows()]
if p1_payoffs.index(max(p1_payoffs)) not in p1_support:

also helps correspond to (4.26) and/or (4.27) but I think that somehow you combined all these into solving the linear system and then checking, which is probably mathematically equivalent but I'm just having trouble keeping track of all the variables.

Along those lines, should it be all([a[i] > 0 for i in p1_support]) or all([a[i] >= 0 for i in p1_support])? Maybe if you already checked smaller supports then this would be degenerate... or maybe this is why they do the smaller supports (sort of) first in the algorithm.

Reviewer: Karl-Dieter Crisman

Author: Vince Knight, James Campbell

comment:18

James and I have just had a meeting about this and we're getting going on it! Will have something to you by the end of the week hopefully.

Thanks a lot for the extensive/detailed review (very helpful). Have also seen your reviews on the other tickets, will get to those when we're done with working on this one.

Last 10 new commits:

`79abde9`	`Have made great suggestion by Karl that means we check less things when going for conditional dominance`
`c62ddc1`	`Have added docs and comments to explain indifference method`
`b6bb1a2`	`Adding latex method`
`c23ff8a`	`Fixing some minor stye issues`
`fed02ff`	`Fixing commas and various other small details`
`aa61323`	`Have moved description of indifference condition`
`69e66b3`	`Moving docs from class to front matter`
`53aed36`	`Fixing some docbuil errors`
`651c081`	`Fixing slight error in docs - about to push to trac`
`9e14ff2`	`Changing ticks in parser`

Changed commit from ffa6d52 to 9e14ff2

comment:20

Before I start: thank you very much for such a detailed and rigorous review! Great to know that the code is being looked at so closely. It's taken me quite a while to go through it all but I think I've addressed everything. Will respond part by part, in particular highlighting points where I haven't just gone with your suggestion (obviously delighted to discuss).

Replying to @kcrisman:

Been away from the laptop for a couple of months and was just wondering what's left to do?

Needs review, largely!

Unfortunately, something isn't quite right on the git view online - see https://github.com/sagemath/sagetrac-mirror/blob/develop/src/sage?id=6800b2c2b7037ae7bf25c297fd139ee48a5ece10 and the "bad object" line for game_theory. See here and here for the actual files in question.

Anyway, a couple of minor things before I have time to check it out properly.

There are however a variety of such algorithms available in gambit, seems orphaned.

Overzealous deleting In the following we create the game and solve i:: and game. In fact degenerate games can cause problems for most algorithm:: and Here is a slightly larger gam::

Caps for exs?
   def payoff_matrices(self):
        r"""
        Returns 2 matrices representing the payoffs for each player.

        Examples ::

Have fixed this.

I'll be looking at this in more detail over the next few days as I have time.

Replying to @kcrisman:

Parser comments.

Minor - this could be made slightly more professional-sounding. Also, double ticks for code markup; maybe even ``'lrs'`` if it is a string, I'm not sure about this.
    At present the only parser included is the for `lrs` algorithm however
    this will be expanded to `gambit` soon.

Have changed wording and also ticks but I'm not sure if it's quite what you meant.

Since lrs is an optional package, will any of the doctests in the parser file need to be marked optional? I assume not, just checking. (Maybe the one using the subprocess stuff?)

This was indeed an oversight on our part: have added the optional tests.

Will those temp files really disappear or do you need to remove them? I just don't remember - we use the temp file name thing so it doesn't overwrite, but I can't remember if we need to remove them afterwards, though I believe we do.

We have checked: they disappear.

Just out of curiosity, what does the fourth element of the stuff mean that you parse?
'2  0  1  2 \n', '1  1/2  1/2 -2 \n'
the first number is the player, the next two the strategy (does lrs only do two player, two-strategy games?) but what is the 2 and -2 here?

They correspond to the utility of the other player.

Could the creation of the p1_strategies be sped up slightly with something like
p2_strategies.append(sage_eval(k) for k in i.split() if k.index() !=1 or -1)
(this syntax is not right, I'm sure) ? Again, probably quite minor to even think about given the type of use case.

I thought about this for a while and felt that in fact this looked less readable. I don't think speed is terribly troublesome here. If you feel strongly about this I'm happy to change though.

Replying to @kcrisman:

Hmm, you'll want to amend src/doc/en/reference/game_theory/index.rst, I bet.

Done: thanks.

Replying to @kcrisman:

Two issues from above I return to.

algorithm='enumeration' or not? You have in one spot "support enumeration" which sounds horrible.

Not too sure I understand. 'support enumeration' is the actual name of the algorithm which is what we need to pass as an argument (so have shorted to enumeration) like we could also pass lrs. Would support_enumeration be any better?

What I mean is that when you put something in quotes and double backticks, it looks like code. You can call it support enumeration and still use 'enumeration' as the algorithm keyword, but then you need to make it quite clear what the difference is. I agree that shorter is better in this case. No double backticks (as later in the doc), not a problem.

Cool.

By the way, both here and in #16331, I'm wondering whether a lot of the (great) documentation you have for the main games maybe belongs (also) in the initial docstring. The reason is that this is what is at the top of the html/pdf documentation. But maybe these are such short files that the main game appears at the top anyway. Though for this ticket the starting documentation is SO long I think that really a lot of it should be at the top - and hopefully there will be some easy way for someone at the command line or notebook to then ask for that top bit.

Not too sure I understand (apologies). Are you saying to move the docs we wrote in the library (before any code kicks in) in to the docs for NormalFormGame?

What I mean is that you have some documentation in the class definition for NormalFormGame that probably can just go in the initial docstring at the very top of the file. After all, it's quite general stuff about what games and Nash equilibria are. This also applies to #16331, as I say, but perhaps somewhat less so since it will not be expanded in the near future.

This is one of the last commits: I've moved most of the docs from the NormalFormGame to the front matter. I'm not sure this is perfect but I didn't want to repeat the docs in two different places to avoid confusion: let me know if this isn't quite right.

Items new to this take on the actual file.

We can use Sage to find them and more importantly see if there is a - please have someone who knows commas go through this entire file. I don't need every Oxford comma, but the sentences are often quite run-on.

I have asked a couple of people and also paid close attention myself. I hope it's ok.

In the following section, you may need to clarify that you mean this as vector/matrix multiplication. Even though you then do that in Sage, someone who is just reading it and not necessarily looking at the code may get confused - especially those who come from a background where column vectors and row vectors are truly separate things, never to be mixed (as opposed to in Sage!).
    We can use Sage to compute the expected utility for any mixed strategy
    pair `(\sigma_1, \sigma_2)`. The payoff to player 1 is given by:

Have added this in, in various places.

In playing strategy `i` is given by (`(Ay)_i`) perhaps once again a gentle reminder that you mean matrix times vector could be useful. Do you think I'm being too gentle on the reader?

Not at all: better to be too gentle. Have added this in.

Rock-Paper-Scissors-Lizard-Spock - I'm scared to ask... fun, but perhaps want to put a reference in for this non-standard example.

It's actually an episode from a TV show: have added in a url link (students usually find this amusing).

I am scared of the syntax sage: f.add_player(2). Am I adding the player named 2? Am I adding two new players? And why do I do this twice in a row? Using "gambit syntax" is nice but would need to be fully explained. By the way, this is the kind of thing that really does do better in the "top matter".

This is adding a player with 2 strategies. Doing it twice in a row is because we're adding two players. Tried to think of a way to make it more verbose but couldn't come to a better conclusion than this but very open to any suggestions.

Can we add the name of a player, or is that a horrible idea? Just because it might eventually get confusing with lots of players.

We actually came to the conclusion that this wasn't a great idea. Not sure when it would be used and differs from gambit syntax but happy to discuss if you feel strongly about it.

A programmed example of a way to use the
        sage: threegame = NormalFormGame()
        sage: threegame.add_player(2)
        sage: threegame.add_player(2)
        sage: threegame.add_player(2)
        sage: threegame[0, 0, 0][0] = 3
        sage: threegame[0, 0, 0][1] = 1
        sage: threegame[0, 0, 0][2] = 4
...
syntax would be nice, just like we did in the other game theory tickets. Who is going to type all that in (accurately) by hand, anyway? So demonstrating it's possible to do it right with a loop or something is useful.

Have added an example with a function that generates the utilities.

The airline example is cool (actually, really interesting) but really needs to be in top matter or at least somehow separated. Also, if there are two paragraphs, separate them with another newline.

In this same example, you have it that the best strategy is to say the stuff is worth two, but you have
[[(1, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0)]]
Doubtless this corresponds to 100% choosing the first strategy, but that is not clear since the way the problem is stated makes it sound like there are 99 strategies or something.

Have added another sentence highlighting that this is a 'smaller' example.

"In fact degenerate games can cause problems for most algorithm" - but what is the problem caused in the following example? It gives a solution that adds to 100% for each player...

Have added more of an explanation.

Replying to @kcrisman:

Before continuing, I just have to say that this is really exceptionally well-organized. Good work.

Moving on to the methods.

But what will happen to the deleted game? Will this raise an error if you try to do anything with it? (Maybe I'll find out later.)
            sage: prisoners_dilemma
            {(1, 0): [0, 5], (0, 0): [2, 2], (1, 1): [4, 4]}

You're not quite deleting a game but a utility. It will cause an error of the game being incomplete if you tried to use it. This is just to make it act like a dictionary.

Can you __setitem__ for an already-set item in the game? If not (for whatever reason), then this should be doctested. If yes, I guess this should be justified and doctested too.

Yes you can: have added a doctest.

Can you move that method to with the other dictionary-emulating methods? Not super-important but helpful to those reading code. __iter__ and __len__ strictly speaking are not about dict emulation but just emulation of iterables.

__iter__ kind of is relevant to the dictionaries as we want the iteration to behave like a dictionary (by iterating over keys). Have moved __setitem though as you suggest and __len__ is now just at the end of those methods.

Usually __init__ is best at the very first. Am I missing something that the emulation ones are coming first?

This was an oversight: __init__ is now first.

I would have expected this to list the bimatrix entries. Instead I get a very boring list of the possible pure strategies.
            sage: for key in prisoners_dilemma:
            ....:     print key

This goes back to wanting a game to behave like a dictionary (which in turn goes back to wanting gambit like syntax): have changed it though so it prints things out a bit nicer.

Will length basically always be n times m in terms of the number of strategies? In which case do you really need all that extra stuff about utilities?

This is future proofed for games with more than 2 players (in which case n times m won't necessarily make sense).

Generator function must be a list or nothing is not doctested.

Have added doctest.

generator != None or generator is not None? Just wondering which you intend here.

Have fixed (gone for is not None).

LaTeX method shows nothing interesting for games with more players:: - then you should probably use the ... like so:
\text{\texttt{<bound{ }method{ }NormalFormGame...[False,{ }False,{ }False]{\char`\}}>}}
or the like.

Have gone with your suggestion.

I still do not like return str(self.utilities) for the string rep. It should at least say, at the very least, that it is in fact a normal form game!!! Maybe "Normal Form Game with following utilities" or whatever.

Have added "Normal Form Game".

One of the errors in the payoff matrices method is tested, the other isn't.

Have added test.

m1 = matrix(QQ, - oh, oh. But didn't you say that Gambit does floats? And what if people input floats? I'm just thinking of nasty things like people inputting 1/sqrt(2) as a probability, or ones where when they are coerced to rationals don't add up to 100%

Our plan is to leave this as is and let the gambit ticket take care of it. When we have the gambit integration we will simply return an error when someone tries to use the Gambit algorithms with a matrix in QQ. This will imply that users will need to make sure they have the correct input. We had implemented a preprocessor but felt that this hid what was going on so feel that it's best to just return an error (and document).

I'd like to see an example with
sage: g._generate_utilities(True)
where it would actually destroy a utility. Myuh-ha-ha!

Done :)

The line
Checks if ``utilities`` has been completed
doesn't seem to correspond to any errors, though.

This corresponds to all the errors throughout when a game is created without a full utility profile. For example we have lines like (in obtain_Nash):

if not self._is_complete():
   raise ValueError("utilities have not been populated")

These mixed strategies
[[(1, 0, 0, 0), (127/1212, 115/1212, 485/606)], [(0, 1, 0, 0), (0, 1/26, 25/26)]]
seem strange, but I assume correct - can you confirm they are exact answers?

They were in fact incorrect but have now fixed: answers are definitely correct now.

The line
        This particular game has 3 Nash equilibria::
isn't backed up by
            sage: g.obtain_Nash(maximization=False)
            [[(1, 0, 0), (0, 1)]]
unless I'm misunderstanding the syntax. Where are the other two equilibria promised to the reader? This seems to happen in a few other examples. (Actually, I think that some copy-paste is at fault here, esp. since maximization=False but that isn't mentioned.)

This was a copy and past error: I think I caught them all.

The or a?

A function to return the Nash equilibrium for a game.

Fixed.

Should it be obtain_Nash or obtain_nash?

Not entirely sure: I felt a bit better going with Nash... I would like to keep Nash if that's not a problem.

When you use tmp_filename() in the things themselves (not doctests) are there any other strange side-effects?

None that we have noticed (have checked as thoroughly as possible).

I feel like you tired (understandable!) in the _solve_enumeration doctests. Most of them should be tests and not examples in any case, I suppose. Here is the funniest of them, I actually laughed at this one.
        TESTS:
    Due to the nature of the linear equations solved in this algorithm
    some negative vectors can be returned. Here is a test that ensures
    this doesn't happen::

        sage: a = matrix([[-13, 59],
        ....:             [27, 86]])
        sage: b = matrix([[14, 6],
        ....:             [58, -14]])
        sage: c = NormalFormGame([a, b])
}}} It sure doesn't happen! Since we never try to find said vectors :-)

Have added that missing line (which actually tries to find them) and an explanation also.

Adding strategies should then have an example finishing it.
    If we do this and try and obtain the Nash equilibrium or view the payoff
    matrices(without specifying the utilities), an error is returned::
but it's never finished up.

Have added that in.

What happens with a completely trivial matrix i.e. all payoffs are zero? Then all mixed strategies are optimal, I guess...

This is in fact an example of a degenerate game: have added that to the docs.

Remaining:

Making sure the _solve_enumeration actually is correct. I'm sure it is, I just haven't had time to look at it.

Have added docs that hopefully clarify (will go in to details below).

I will have to just trust you on the _Hrepresentation method.

Very happy to document/explain further if that's helpful but very confident this is correct (it has been heavily tested).

Almost there!

Finally, as a general rule of thumb, if you have any pretty useful tests or examples which are in underscore methods (which won't show up in the reference manual) maybe repeat them elsewhere. I don't know if you do that, just mentioning it.

Wrote a new one and copied it to the front matter.

Replying to @kcrisman:

Looking at the reference for support enumeration (page 103), I find a few final (hopefully!) questions. Most are probably due to my unfamiliarity with the details of this algorithm, though I think it is quite interesting as a strategy.

This confusion is partly our fault: the algorithm we used is a combination of something from 'mas' (the pruning of conditionally dominated strategies). Have added docs and also will clarify further below.

The algorithm for some reason sorts the support size profiles, but I don't see that in the code.

This sorts it because the algorithm from 'mas' is interested in finding an equilibrium (not necessarily all of them). The way the potential pairs are created are in fact sorted but in essence as we need to test them all: it's not terribly important.

The algorithm definitely implies that there could be different numbers of pure strategies for each player, and your examples and potential_supports seem to suggest this, but then potential_support_pairs and how that is used seems to implicitly ... I don't know, it just doesn't smell right. E.g.
if len(pair[0]) == len(pair[1])
should really be comparing two different supports for player 1, according to the pseudocode in the paper, but here you are comparing a support from player 1 with one from player 2. Shouldn't you be comparing supports of the same size as the player 1 supports with respect to $A'_2$? However, I may be misunderstanding the algorithm.

This is because the algorithm doesn't take in to account a result from 'Algorithmic Game Theory' (referenced in docs) which proves that for non-degenerate games supports have to be the same size (this is almost 'by definition').

Also, do you have to do all the construction of tuples and such or is there a more efficient way to go from the power set to the evaluation of the supports? Maybe there isn't.

We could not think of a better way.

Minor doc note: or does not have a dominated row: should have one more colon.

Have added.

Just brainstorming - maybe in _row_cond_dominance one doesn't have to cycle through the product of rows and rows, but could check rows i and j for i>j and then immediately check for j>i... because as soon as one is dominated, you return False, and right now it's a weary n^2 but maybe you could make it n(n+1)/2 if you only check each pair once, but twice within the pair (if that makes sense).

Really helpful suggestion: thanks! Have fixed this!

Minor but made the code harder to understand:
for p2_strategy in range(self.players[1].num_strategies):
for i in range(self.players[0].num_strategies):
even though they fill exactly the same role. Same with
for p2_strategy in range(len(p2_support)):
for j in range(len(p1_support)):

Have tried to clarify as suggested: let me know if it still isn't quite right.

Should _solve_indifference really return False, or maybe just [], when it isn't possible (since if foo: doesn't happen as long as foo is "empty" in its type)?

Returning [] wouldn't be quite right from the mathematical point of view (empty set as opposed to a set that doesn't exist): False seemed to make more sense to us. Obviously wouldn't make a different from the point of view of the actual algorithm so let me know if you feel strongly about it.

Would it help to formally do this as an LP with Sage LPs or is solve_right sufficient?

The way this is being run (using a basic version of indifference) does not require an LP as it's all being reduced to a simple linear system.

I just don't see how
linearsystem2[j, p2_strategy] = M1[p1_support[j]][p2_strategy] - M1[p1_support[j-1]][p2_strategy]
corresponds to the TGS, though somehow it must. (4.30) is essentially
linearsystem2[-1, p2_strategy] = 1
and _is_NE corresponds more or less to (4.28) and (4.29). I think
p1_payoffs = [sum(v * row[i] for i, v in enumerate(b)) for row in M1.rows()]
if p1_payoffs.index(max(p1_payoffs)) not in p1_support:
also helps correspond to (4.26) and/or (4.27) but I think that somehow you combined all these into solving the linear system and then checking, which is probably mathematically equivalent but I'm just having trouble keeping track of all the variables.

I have added a lot more explanation as to how this works to the docs. I've also added that new explanation to the docs for the unhidden obtain_Nash method although I'm not sure it's useful there (potentially more confusing for the general user who won't care?). Let me know if that helps.

Along those lines, should it be all([a[i] > 0 for i in p1_support]) or all([a[i] >= 0 for i in p1_support])? Maybe if you already checked smaller supports then this would be degenerate... or maybe this is why they do the smaller supports (sort of) first in the algorithm.

We need the strict inequality to verify that the support condition isn't being violated.

Thanks so much for the detailed review! (Will try and get to 16331 soon before the end of the week.)

comment:21

Returning [] wouldn't be quite right from the mathematical point of view (empty set as opposed to a set that doesn't exist): False seemed to make more sense to us. Obviously wouldn't make a different from the point of view of the actual algorithm so let me know if you feel strongly about it.

My suggestion would be to return None; this is what we do for crystals for a similar situation. AFAIK, there is no standard (or other similar case for that matter) in Sage about this.

comment:22

Wow, thank you so much for the detailed responses! This will take some time to go through, so it may take a few days to get to - but it's a high priority, for sure.

comment:23

I don't think I'll get to everything in one comment, but assume that if I don't mention it it's either okay or I'm still getting to it.

Parser comments.

Minor - this could be made slightly more professional-sounding. Also, double ticks for code markup; maybe even ``'lrs'`` if it is a string, I'm not sure about this.
    At present the only parser included is the for `lrs` algorithm however
    this will be expanded to `gambit` soon.
Have changed wording and also ticks but I'm not sure if it's quite what you meant.

No. What you changed it to is

-    At present the only parser included is for 'lrs' algorithm however
-    this is actively being expanded to 'gambit'.
+    At present the only parser included is for `lrs` algorithm however
+    this is actively being expanded to `gambit`.

but what we need is for `lrs` or the previous 'lrs' to become ``'lrs'``. Notice the double backticks (typeset as code) and the single quote because, well, it needs single quotes because it's a string (such as in the example sage: matching_pennies.obtain_Nash(algorithm='lrs')). That said, it probably can be kept 'lrs' in some contexts, I think it's just especially important in places like

    1. ``lrs`` (requires lrs)
    2. ``enumeration``

where not having the quotes could mean people will type in something nasty and wrong.

Here is a dumb comment - you have between gambit and sage. but then it should be Sage. Trivial, I know, I apologize but I just happened to see it.

LaTeX method shows nothing interesting for games with more players:: - then you should probably use the ... like so:
\text{\texttt{<bound{ }method{ }NormalFormGame...[False,{ }False,{ }False]{\char`\}}>}}
or the like.
Have gone with your suggestion.

Yikes! I see now I was assuming too much information. What I meant by that is that the LaTeX method is fine, but that in doctesting it one can use three periods in a row to substitute for arbitrary sequences. So keep the original LaTeX method, but add ... in the middle of it so that the doctest is actually legible and it's clear what it's testing for.

More to come.

comment:24

Since lrs is an optional package, will any of the doctests in the parser file need to be marked optional? I assume not, just checking. (Maybe the one using the subprocess stuff?)

This was indeed an oversight on our part: have added the optional tests.

Usually our practice is to mark only the doctest that would actually fail without the optional package. (After all, testing the other stuff is worthwhile.) Am I correct that only the stuff depending on process = Popen(['nash', g1_name, g2_name], stdout=PIPE) needs to be optional?

algorithm='enumeration' or not? You have in one spot "support enumeration" which sounds horrible.

Not too sure I understand. 'support enumeration' is the actual name of the algorithm which is what we need to pass as an argument (so have shorted to enumeration) like we could also pass lrs. Would support_enumeration be any better?

What I mean is that when you put something in quotes and double backticks, it looks like code. You can call it support enumeration and still use 'enumeration' as the algorithm keyword, but then you need to make it quite clear what the difference is. I agree that shorter is better in this case. No double backticks (as later in the doc), not a problem.

Cool.

You still have ``enumeration`` instead of ``"enumeration"`` at one point, though you do have ``"lrs"`` correctly there.

-    playing strategy `i` is given by (`(Ay)_i`)::
+    playing strategy `i` is given by the matrix/vector multiplication:
+    (`(Ay)_i`)::

And even after you move it, it is confusing. Why a colon before the colons? What is i? I know but the reader may not.

More trivialities:

Should dictionary like interface perhaps have a hyphen instead of a space?
Similarly, A game with 1 equilibria - I think the singular is equilibrium.
initiating probably should be initializing, unless this is secret society?
The sentence

However, if one writes down a smaller number than the other, this smaller

probably needs a blank line in front of it or the documentation will look like a humongous paragraph. I think I mentioned this before.

At present the algorithms for the computation of equilibria only solve 2 player - "solves"

sage: p += plot((A * vector([y, 1 - y]))[1], y, 0, 1, color='red', legend_label='$u_1(r_2, (y, 1-y))$')

but typically one shows the plot (or allows the user to) when using this to make a point. Maybe just add ; p to the end of that line.

Thinking aloud: Should

"Normal Form Game with the following utilities: {}"

instead be

"Normal Form Game with the following utilities:\n{}"

I don't know if Sage often has two-line string representations, though.

I'm a bit scared by the following.

-        sage: g.obtain_Nash()
-        [[(1, 0, 0), (1, 0, 0)], [(0, 1, 0), (0, 1, 0)], [(0, 0, 1), (0, 0, 1)]]
+        sage: g.obtain_Nash(algorithm='enumeration')
+        [[(1, 0, 0), (1, 0, 0)]]

Shouldn't lrs and enumeration give the same Nash equilibria?

Minor but made the code harder to understand:
for p2_strategy in range(self.players[1].num_strategies):
for i in range(self.players[0].num_strategies):
even though they fill exactly the same role. Same with
for p2_strategy in range(len(p2_support)):
for j in range(len(p1_support)):
Have tried to clarify as suggested: let me know if it still isn't quite right.

Hmm, I kind of meant the opposite - shouldn't j be a p1_strategy and so forth? Perhaps I'm misunderstanding this. For stuff like this, variable names that mean something are crucial. Plus, the new code still mixes letters and strategys.

These mixed strategies seem strange, but I assume correct - can you confirm they are exact answers?

They were in fact incorrect but have now fixed: answers are definitely correct now.

Well, I have no independent way to check that but hopefully yes!

I am scared of the syntax sage: f.add_player(2). Am I adding the player named 2? Am I adding two new players? And why do I do this twice in a row? Using "gambit syntax" is nice but would need to be fully explained. By the way, this is the kind of thing that really does do better in the "top matter".

This is adding a player with 2 strategies. Doing it twice in a row is because we're adding two players. Tried to think of a way to make it more verbose but couldn't come to a better conclusion than this but very open to any suggestions.

Maybe at the very least in situations like

        sage: g = NormalFormGame()
        sage: g.add_player(2)
        sage: g.add_player(2)
        sage: g.add_player(2)  # Creating a game with three players

you could, early in the docs, say instead

        sage: g = NormalFormGame()
        sage: g.add_player(2)  # adding first player with two strategies
        sage: g.add_player(2)  # adding second player with two strategies
        sage: g.add_player(2)  # Creating a game with three players

or something along those lines.

I would have expected this to list the bimatrix entries. Instead I get a very boring list of the possible pure strategies.
            sage: for key in prisoners_dilemma:
            ....:     print key
This goes back to wanting a game to behave like a dictionary (which in turn goes back to wanting gambit like syntax): have changed it though so it prints things out a bit nicer.

Well, it doesn't print things nicer, just the doctest does. So I guess what you are saying is that the keys must be pure strategy pairs to comply with gambit?

In this same example, you have it that the best strategy is to say the stuff is worth two, but you have
[[(1, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0)]]
Doubtless this corresponds to 100% choosing the first strategy, but that is not clear since the way the problem is stated makes it sound like there are 99 strategies or something.
Have added another sentence highlighting that this is a 'smaller' example.

I still don't understand, so for sure the reader won't. You have to tell the reader what the output means, since they do not see the number TWO in the output and if they are not a programmer they won't recognize it from the matrices. I think here you understand the code so well that it is just obvious to you.

Should it be obtain_Nash or obtain_nash?

Not entirely sure: I felt a bit better going with Nash... I would like to keep Nash if that's not a problem.

Given that Sage usually lowercases even proper names most of the time (such as Schlegel projection or Conway polynomials or Schonheim bound) I think we need to go with obtain_nash. Especially because in programming there are kind of two conventions - either camelCase or camel_case, but not camel_Case and that is what it looks like, even if that is not the intent.

Getting closer...

comment:25

Returning [] wouldn't be quite right from the mathematical point of view (empty set as opposed to a set that doesn't exist): False seemed to make more sense to us. Obviously wouldn't make a different from the point of view of the actual algorithm so let me know if you feel strongly about it.

My suggestion would be to return None; this is what we do for crystals for a similar situation. AFAIK, there is no standard (or other similar case for that matter) in Sage about this.

Hmm, maybe that is better indeed.

comment:26

More random bits. Looking very good, though.

+Here is a game being constructed using gambit syntax (note that a
+``NormalFormGame`` object acts like a dictionary with strategy tuples as
+keys and payoffs as their values)::

I think that if you make it clear that they are pure strategy tuples I will be a lot happier with this syntax.

Proceedings of the national academy of sciences

I think PNAS is capitalized, but I could be wrong. Interesting place for a math paper, incidentally, you don't get too many in there!

I just have to point out about the RPSLS

The topic of this article may not meet Wikipedia's general notability guideline.

:-) But maybe then http://www.samkass.com/theories/RPSSL.html is a better, if more brittle, reference. At least it does have the CC license, phew! Otherwise maybe you couldn't use it ;-)

comment:27

Okay, back to the algorithm. Here was one thing I definitely was confused by before.

Equivalently we can consider consecutive rows of A (instead of all pairs of strategies).

Huh? I distinctly remember that part of the code, but I don't see it in the references. So maybe this is just some very basic linear systems thing I am not remembering, but if you can clear it up for me I'd be grateful.

Along these lines, you then need to change

where `A` has been modified to only contain the row corresponding to `S(\rho_1)`

where `A` has been modified to only contain the rows corresponding to `S(\rho_1)`)

(since there is a necessary parenthesis (oh, WHY do the Brits call them brackets when brackets are square? (truly, I don't know))).

Minor but made the code harder to understand:

Have tried to clarify as suggested: let me know if it still isn't quite right.

Hmm, I kind of meant the opposite - shouldn't j be a p1_strategy and so forth? Perhaps I'm misunderstanding this. For stuff like this, variable names that mean something are crucial. Plus, the new code still mixes letters and strategys.

Oh, now I get it (thanks to your improved exposition and CUP's kind provision of a free download of AGT). These are maybe to distinguish between using all strategies and just the ones in the truncated list of ones in the support?

Or if not, then I stick with my original request.

By the way, you can just move the comments like this

# Coefficients of linear system that ensure indifference between two consecutive strategies of the support of p1

to the line immediately preceding, to ensure good readability.

I note that in the built doc for some reason there is documentation for sage.game_theory.normal_form_game.PIPE. I couldn't tell you how to remove it but it does seem odd.

So now one can move to the testing phase!

comment:28

Since lrs is an optional package, will any of the doctests in the parser file need to be marked optional? I assume not, just checking. (Maybe the one using the subprocess stuff?)

This was indeed an oversight on our part: have added the optional tests.

Usually our practice is to mark only the doctest that would actually fail without the optional package.

Though be sure to do ./sage -t --optional=all or --optional=sage,lrs in that event, as I just found out, not having done any optional tests in a while...

comment:29

Sorry for the mountain, but getting it all done at once is better for my workflow...

I get the following output in the notebook.

Normal Form Game with the following                     utilities: {(0,
1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}

Note the very long space. I think this is because of

+        return "Normal Form Game with the following \
+                    utilities: {}".format(self.utilities)

and so it kept all those spaces, since this is a string.

comment:30

Okay, now testing commences. I am primarily testing whether the two algorithms give the same output. I am also trying to compare output with various third-party online software, just to make sure no horrible goofs.

sage: N = NormalFormGame([matrix(2,[0,-1,-2,-1]),matrix(2,[1,0,0,2])])
sage: N.obtain_Nash(algorithm='enumeration')
[[(1, 0), (1, 0)]]
sage: N.obtain_Nash(algorithm='lrs')
[[(2/3, 1/3), (0, 1)], [(0, 1), (0, 1)], [(1, 0), (1, 0)]]

This one is degenerate because one column of the row player's matrix is all the same, but I wonder why enumeration doesn't at least get the two pure equilibria? Is it possible to warn about degenerate ones in the code, or would that indeed be too hard? Maybe that should be implemented at the algorithm level... but at least the situation where a column of the row player or row of the column player have two of the same number could be checked for. So far, that is all the discrepancies I get.

Or maybe that's for an upgrade ticket!

Here is something I don't like. In all cases (including when gambit is added), the return type from obtain_nash/obtain_Nash should be the same. Well, it sort of is.

sage: N = NormalFormGame([matrix(2,[2,-3,0,-1]),matrix(2,[0,1,2,-2])])
sage: N.obtain_Nash(algorithm='enumeration')                          
[[(4/5, 1/5), (1/2, 1/2)]]
sage: N.obtain_Nash(algorithm='lrs')                                  
[[(4/5, 1/5), (1/2, 1/2)]]
sage: N.obtain_Nash(algorithm='enumeration') == N.obtain_Nash(algorithm='lrs') 
False
sage: type(N.obtain_Nash(algorithm='lrs')[0][0])
<type 'tuple'>
sage: type(N.obtain_Nash(algorithm='enumeration')[0][0])
<type 'sage.modules.vector_rational_dense.Vector_rational_dense'>

Umm. This is because you solved a linear system, and that returns a vector. However, I'm not sure what the right return type is - because with gambit presumably the return will be a non-rational vector or something. Maybe better to return all as tuples? Or all as vectors?

An argument for vectors is to easily always do this

sage: N.obtain_Nash(algorithm='enumeration')[0][0]*matrix(2,[2,-3,0,-1])*N.obtain_Nash(algorithm='enumeration')[0][1]
-1/2
sage: vector(N.obtain_Nash(algorithm='lrs')[0][0])*matrix(2,[2,-3,0,-1])*vector(N.obtain_Nash(algorithm='lrs')[0][1])

without having to put things in vectors.

An argument against is that one might not want the additional structure of a vector - after all, a (mixed) strategy is really more of a discrete probability distribution.

But the return types should be as close as possible to each other, anyway.

sage: N = NormalFormGame([matrix(2,[7,-8,-4,-8,7,0]),matrix(2,[-9,-1,-8,3,2,3])])
sage: N.obtain_Nash(algorithm='lrs')[[(0, 1), (0, 0, 1)]]
sage: N.obtain_Nash(algorithm='enumeration')
[]

Okay, I get it, degenerate. But why doesn't enumeration at least return an equilibrium?

Here's another one. I am baffled by these outputs (just showing the matrices and results).

[-7 -5  5]
[ 5  5  3]
[ 1 -6  1]
[ -9   7   9]
[  6  -2  -3]
[ -4   6 -10]
[[(0, 1, 0), (1, 0, 0)], [(1/3, 2/3, 0), (1/7, 0, 6/7)], [(1, 0, 0), (0, 0, 1)]]  #enum
[[(0, 1, 0), (0, 0, 1)], [(1/3, 2/3, 0), (0, 1/6, 5/6)], [(1, 0, 0), (1/7, 0, 6/7)]]  #lrs

In particular, what is up with [(0, 1, 0), (0, 0, 1)]? If row plays middle and column plays right, then row should move to top and/or column should move to left or middle. I buy [(0, 1, 0), (1, 0, 0)]. Am I reading the matrices wrong now that they are 3x3? Note that the LSE online version of lrs online gives most of these equilibria, but not [(0, 1, 0), (0, 0, 1)]. Hopefully I'm just interpreting something wrong, though.

Otherwise I am pretty happy, this really does seem to give good output in most cases and the algorithms agree where desired. Lots of very minor things to fix above but this will be a robust addition to Sage, thanks for working so hard on it.

comment:32

Awesome: thanks so much for the ridiculously brilliant review. Will get right on this and hopefully have something towards mid next week.

comment:33

(By 'brilliant': I mean rigorous and comprehensive.)

Changed commit from 9e14ff2 to 8775f12

Last 10 new commits:

`939c52a`	`Adding explenation to gambit approach of adding players`
`266b87f`	`Renaming obtain_Nash to obtain_nash`
`c937eae`	`Adding more explanation to airline example`
`936634e`	`Returning None instead of False for row coonditional dominance`
`11b8efc`	`Fixing PNAS capitalisation and detail about pure strategy`
`420db98`	`Variables are more verbose in construction of linear system`
`66a2e91`	`Changing link for RPSLS`
`b1c5302`	`Fixing str method whilst adhering to PEP8`
`9fab733`	`Returning None in correct place`
`8775f12`	`Typo sage -> Sage`

comment:35

Replying to @kcrisman:

Ok so I actually think you've found a bug (in your testing section) so I'm spending some time on that over the next couple of days. In the meantime I addressed the various other issues so thought I might as well push those now.

I don't think I'll get to everything in one comment, but assume that if I don't mention it it's either okay or I'm still getting to it.

Parser comments.

Minor - this could be made slightly more professional-sounding. Also, double ticks for code markup; maybe even ``'lrs'`` if it is a string, I'm not sure about this. {{{ At present the only parser included is the for lrs algorithm however this will be expanded to gambit soon. }}}

Have changed wording and also ticks but I'm not sure if it's quite what you meant.

No. What you changed it to is
-    At present the only parser included is for 'lrs' algorithm however
-    this is actively being expanded to 'gambit'.
+    At present the only parser included is for `lrs` algorithm however
+    this is actively being expanded to `gambit`.
but what we need is for `lrs` or the previous 'lrs' to become ``'lrs'``. Notice the double backticks (typeset as code) and the single quote because, well, it needs single quotes because it's a string (such as in the example sage: matching_pennies.obtain_Nash(algorithm='lrs')). That said, it probably can be kept 'lrs' in some contexts, I think it's just especially important in places like
    1. ``lrs`` (requires lrs)
    2. ``enumeration``
where not having the quotes could mean people will type in something nasty and wrong.

Believe I have now addressed this.

Here is a dumb comment - you have between gambit and sage. but then it should be Sage. Trivial, I know, I apologize but I just happened to see it.

Changed.

LaTeX method shows nothing interesting for games with more players:: - then you should probably use the ... like so: {{{ \text{\texttt{<bound{ }method{ }NormalFormGame...[False,{ }False,{ }False]{\char`}}>}} }}} or the like.

Have gone with your suggestion.

Yikes! I see now I was assuming too much information. What I meant by that is that the LaTeX method is fine, but that in doctesting it one can use three periods in a row to substitute for arbitrary sequences. So keep the original LaTeX method, but add ... in the middle of it so that the doctest is actually legible and it's clear what it's testing for.

I understand now :) Have fixed.

Replying to @kcrisman:

Since lrs is an optional package, will any of the doctests in the parser file need to be marked optional? I assume not, just checking. (Maybe the one using the subprocess stuff?)

This was indeed an oversight on our part: have added the optional tests.

Usually our practice is to mark only the doctest that would actually fail without the optional package. (After all, testing the other stuff is worthwhile.) Am I correct that only the stuff depending on process = Popen(['nash', g1_name, g2_name], stdout=PIPE) needs to be optional?

One or two others needed to stay optional but yes this has been addressed.

algorithm='enumeration' or not? You have in one spot "support enumeration" which sounds horrible. Not too sure I understand. 'support enumeration' is the actual name of the algorithm which is what we need to pass as an argument (so have shorted to enumeration) like we could also pass lrs. Would support_enumeration be any better? What I mean is that when you put something in quotes and double backticks, it looks like code. You can call it support enumeration and still use 'enumeration' as the algorithm keyword, but then you need to make it quite clear what the difference is. I agree that shorter is better in this case. No double backticks (as later in the doc), not a problem.

Cool.

You still have ``enumeration`` instead of ``"enumeration"`` at one point, though you do have ``"lrs"`` correctly there.

Have fixed this.

-    playing strategy `i` is given by (`(Ay)_i`)::
+    playing strategy `i` is given by the matrix/vector multiplication:
+    (`(Ay)_i`)::
And even after you move it, it is confusing. Why a colon before the colons? What is i? I know but the reader may not.

Have added more explenation.

More trivialities:

Should dictionary like interface perhaps have a hyphen instead of a space?

Done.

Similarly, A game with 1 equilibria - I think the singular is equilibrium.

Done.

initiating probably should be initializing, unless this is secret society?

Yup: done :)

The sentence
However, if one writes down a smaller number than the other, this smaller
probably needs a blank line in front of it or the documentation will look like a humongous paragraph. I think I mentioned this before.

Apologies: done.

At present the algorithms for the computation of equilibria only solve 2 player - "solves"

Unless I'm making a grammatical mistake (which I might well be) I don't think that's correct? 'The algorithms solve 2 player games'?

sage: p += plot((A * vector([y, 1 - y]))[1], y, 0, 1, color='red', legend_label='$u_1(r_2, (y, 1-y))$')
but typically one shows the plot (or allows the user to) when using this to make a point. Maybe just add ; p to the end of that line.

Have fixed (wasn't sure if tests would no longer pass but they do).

Thinking aloud: Should
"Normal Form Game with the following utilities: {}"
instead be
"Normal Form Game with the following utilities:\n{}"
I don't know if Sage often has two-line string representations, though.

I have left it as is for now as I haven't seen many two-line string representations.

I'm a bit scared by the following.
-        sage: g.obtain_Nash()
-        [[(1, 0, 0), (1, 0, 0)], [(0, 1, 0), (0, 1, 0)], [(0, 0, 1), (0, 0, 1)]]
+        sage: g.obtain_Nash(algorithm='enumeration')
+        [[(1, 0, 0), (1, 0, 0)]]
Shouldn't lrs and enumeration give the same Nash equilibria?

This might be part of the potential bug and I need to address. In a sense it's ok because the algorithm 'doesn't make sense for degenerate games' but I think something is wrong with pure strategy NE which enumeration should find.

Minor but made the code harder to understand: {{{ for p2_strategy in range(self.players[1].num_strategies): for i in range(self.players[0].num_strategies): }}} even though they fill exactly the same role. Same with {{{ for p2_strategy in range(len(p2_support)): for j in range(len(p1_support)): }}}

Have tried to clarify as suggested: let me know if it still isn't quite right.

Hmm, I kind of meant the opposite - shouldn't j be a p1_strategy and so forth? Perhaps I'm misunderstanding this. For stuff like this, variable names that mean something are crucial. Plus, the new code still mixes letters and strategys.

I agree, in fact I think I've gotten myself confused with what you were asking now. It's clear now and will mention more in comment later on.

These mixed strategies seem strange, but I assume correct - can you confirm they are exact answers?

They were in fact incorrect but have now fixed: answers are definitely correct now.

Well, I have no independent way to check that but hopefully yes!

I am scared of the syntax sage: f.add_player(2). Am I adding the player named 2? Am I adding two new players? And why do I do this twice in a row? Using "gambit syntax" is nice but would need to be fully explained. By the way, this is the kind of thing that really does do better in the "top matter".

This is adding a player with 2 strategies. Doing it twice in a row is because we're adding two players. Tried to think of a way to make it more verbose but couldn't come to a better conclusion than this but very open to any suggestions.

Maybe at the very least in situations like
        sage: g = NormalFormGame()
        sage: g.add_player(2)
        sage: g.add_player(2)
        sage: g.add_player(2)  # Creating a game with three players
you could, early in the docs, say instead
        sage: g = NormalFormGame()
        sage: g.add_player(2)  # adding first player with two strategies
        sage: g.add_player(2)  # adding second player with two strategies
        sage: g.add_player(2)  # Creating a game with three players
or something along those lines.

Have added as you suggest throughout (for all similar examples).

I would have expected this to list the bimatrix entries. Instead I get a very boring list of the possible pure strategies. {{{ sage: for key in prisoners_dilemma: ....: print key }}}

This goes back to wanting a game to behave like a dictionary (which in turn goes back to wanting gambit like syntax): have changed it though so it prints things out a bit nicer.

Well, it doesn't print things nicer, just the doctest does. So I guess what you are saying is that the keys must be pure strategy pairs to comply with gambit?

Yes.

In this same example, you have it that the best strategy is to say the stuff is worth two, but you have {{{ [[(1, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0)]] }}} Doubtless this corresponds to 100% choosing the first strategy, but that is not clear since the way the problem is stated makes it sound like there are 99 strategies or something.

Have added another sentence highlighting that this is a 'smaller' example.

I still don't understand, so for sure the reader won't. You have to tell the reader what the output means, since they do not see the number TWO in the output and if they are not a programmer they won't recognize it from the matrices. I think here you understand the code so well that it is just obvious to you.

I've added more explenation.

Should it be obtain_Nash or obtain_nash?

Not entirely sure: I felt a bit better going with Nash... I would like to keep Nash if that's not a problem.

Given that Sage usually lowercases even proper names most of the time (such as Schlegel projection or Conway polynomials or Schonheim bound) I think we need to go with obtain_nash. Especially because in programming there are kind of two conventions - either camelCase or camel_case, but not camel_Case and that is what it looks like, even if that is not the intent.

Have fixed throughout.

Getting closer...

More to come.

Replying to @kcrisman:

Returning [] wouldn't be quite right from the mathematical point of view (empty set as opposed to a set that doesn't exist): False seemed to make more sense to us. Obviously wouldn't make a different from the point of view of the actual algorithm so let me know if you feel strongly about it.

My suggestion would be to return None; this is what we do for crystals for a similar situation. AFAIK, there is no standard (or other similar case for that matter) in Sage about this.

Hmm, maybe that is better indeed.

Have gone with None.

Replying to @kcrisman

More random bits. Looking very good, though.
+Here is a game being constructed using gambit syntax (note that a
+``NormalFormGame`` object acts like a dictionary with strategy tuples as
+keys and payoffs as their values)::
I think that if you make it clear that they are pure strategy tuples I will be a lot happier with this syntax.

Have clarified this.

Proceedings of the national academy of sciences
I think PNAS is capitalized, but I could be wrong. Interesting place for a math paper, incidentally, you don't get too many in there!

Have capitalized.

I just have to point out about the RPSLS

The topic of this article may not meet Wikipedia's general notability guideline. :-) But maybe then http://www.samkass.com/theories/RPSSL.html is a better, if more brittle, reference. At least it does have the CC license, phew! Otherwise maybe you couldn't use it ;-)

Changed the reference.

Replying to @kcrisman:

Okay, back to the algorithm. Here was one thing I definitely was confused by before.

Equivalently we can consider consecutive rows of A (instead of all pairs of strategies).

Huh? I distinctly remember that part of the code, but I don't see it in the references. So maybe this is just some very basic linear systems thing I am not remembering, but if you can clear it up for me I'd be grateful.

This isn't documented in the references but is a small linear system trick. I haven't changed the docs but here's the idea (if you think it needs to go in just let me know):

We want to find a strategy such that u(x,s) = u for all s for some u: ie all the pure strategies must have the same utility against that particular mixed strategy. In practice we don't actually care about the value of u so to set up the linear system it's just as easy to say that u(x,s_1)=u(x,s_2) for all s_1, s_2. What we're doing here in our algorithm is creating a chain of equality where we have consecutive pairs of strategies: u(x,s_1)=u(x,s_2), u(x,s_2)=u(x,s_3), ... u(x,x_m)=u(x,s_1) (the last equality there isn't really needed). Does that help? Do you think more is needed in the docs? (If you do, I'm happy to put something in but feel that it's perhaps not needed - happy to be wrong).

Along these lines, you then need to change
where `A` has been modified to only contain the row corresponding to `S(\rho_1)`
to
where `A` has been modified to only contain the rows corresponding to `S(\rho_1)`)
(since there is a necessary parenthesis (oh, WHY do the Brits call them brackets when brackets are square? (truly, I don't know))).

Fixed.

Minor but made the code harder to understand: Have tried to clarify as suggested: let me know if it still isn't quite right. Hmm, I kind of meant the opposite - shouldn't j be a p1_strategy and so forth? Perhaps I'm misunderstanding this. For stuff like this, variable names that mean something are crucial. Plus, the new code still mixes letters and strategys. Oh, now I get it (thanks to your improved exposition and CUP's kind provision of a free download of AGT). These are maybe to distinguish between using all strategies and just the ones in the truncated list of ones in the support?

Or if not, then I stick with my original request.

The equations of are linear system correspond to strategy pairs so I've now changed this to be more verbose.

By the way, you can just move the comments like this
# Coefficients of linear system that ensure indifference between two consecutive strategies of the support of p1
to the line immediately preceding, to ensure good readability.

Done.

I note that in the built doc for some reason there is documentation for sage.game_theory.normal_form_game.PIPE. I couldn't tell you how to remove it but it does seem odd.

I have no idea what to do about this and/or how it has come about... Will continue to investigate unless someone has a good suggestion?

So now one can move to the testing phase!

Replying to @kcrisman:

Sorry for the mountain, but getting it all done at once is better for my workflow...

I get the following output in the notebook.
Normal Form Game with the following                     utilities: {(0,
1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}
Note the very long space. I think this is because of
+        return "Normal Form Game with the following \
+                    utilities: {}".format(self.utilities)
and so it kept all those spaces, since this is a string.

Was trying to stick to PEP8 but looking at that it was very clumsily done: have addressed now.

Replying to @kcrisman:

Okay, now testing commences. I am primarily testing whether the two algorithms give the same output. I am also trying to compare output with various third-party online software, just to make sure no horrible goofs.
sage: N = NormalFormGame([matrix(2,[0,-1,-2,-1]),matrix(2,[1,0,0,2])])
sage: N.obtain_Nash(algorithm='enumeration')
[[(1, 0), (1, 0)]]
sage: N.obtain_Nash(algorithm='lrs')
[[(2/3, 1/3), (0, 1)], [(0, 1), (0, 1)], [(1, 0), (1, 0)]]
This one is degenerate because one column of the row player's matrix is all the same, but I wonder why enumeration doesn't at least get the two pure equilibria? Is it possible to warn about degenerate ones in the code, or would that indeed be too hard? Maybe that should be implemented at the algorithm level... but at least the situation where a column of the row player or row of the column player have two of the same number could be checked for. So far, that is all the discrepancies I get.

Or maybe that's for an upgrade ticket!

Here is something I don't like. In all cases (including when gambit is added), the return type from obtain_nash/obtain_Nash should be the same. Well, it sort of is.
sage: N = NormalFormGame([matrix(2,[2,-3,0,-1]),matrix(2,[0,1,2,-2])])
sage: N.obtain_Nash(algorithm='enumeration')
[[(4/5, 1/5), (1/2, 1/2)]]
sage: N.obtain_Nash(algorithm='lrs')
[[(4/5, 1/5), (1/2, 1/2)]]
sage: N.obtain_Nash(algorithm='enumeration') == N.obtain_Nash(algorithm='lrs')
False
sage: type(N.obtain_Nash(algorithm='lrs')[0][0])
<type 'tuple'>
sage: type(N.obtain_Nash(algorithm='enumeration')[0][0])
<type 'sage.modules.vector_rational_dense.Vector_rational_dense'>
Umm. This is because you solved a linear system, and that returns a vector. However, I'm not sure what the right return type is - because with gambit presumably the return will be a non-rational vector or something. Maybe better to return all as tuples? Or all as vectors?

An argument for vectors is to easily always do this
sage: N.obtain_Nash(algorithm='enumeration')[0][0]*matrix(2,[2,-3,0,-1])*N.obtain_Nash(algorithm='enumeration')[0][1]
-1/2
sage: vector(N.obtain_Nash(algorithm='lrs')[0][0])*matrix(2,[2,-3,0,-1])*vector(N.obtain_Nash(algorithm='lrs')[0][1])
without having to put things in vectors.

An argument against is that one might not want the additional structure of a vector - after all, a (mixed) strategy is really more of a discrete probability distribution.

But the return types should be as close as possible to each other, anyway.

I agree: I'm likely to go with tuples but will think about it.

sage: N = NormalFormGame([matrix(2,[7,-8,-4,-8,7,0]),matrix(2,[-9,-1,-8,3,2,3])])
sage: N.obtain_Nash(algorithm='lrs')[[(0, 1), (0, 0, 1)]]
sage: N.obtain_Nash(algorithm='enumeration')
[]
Okay, I get it, degenerate. But why doesn't enumeration at least return an equilibrium?

Here's another one. I am baffled by these outputs (just showing the matrices and results).
[-7 -5  5]
[ 5  5  3]
[ 1 -6  1]
[ -9   7   9]
[  6  -2  -3]
[ -4   6 -10]
[[(0, 1, 0), (1, 0, 0)], [(1/3, 2/3, 0), (1/7, 0, 6/7)], [(1, 0, 0), (0, 0, 1)]]  #enum
[[(0, 1, 0), (0, 0, 1)], [(1/3, 2/3, 0), (0, 1/6, 5/6)], [(1, 0, 0), (1/7, 0, 6/7)]]  #lrs
In particular, what is up with [(0, 1, 0), (0, 0, 1)]? If row plays middle and column plays right, then row should move to top and/or column should move to left or middle. I buy [(0, 1, 0), (1, 0, 0)]. Am I reading the matrices wrong now that they are 3x3? Note that the LSE online version of lrs online gives most of these equilibria, but not [(0, 1, 0), (0, 0, 1)]. Hopefully I'm just interpreting something wrong, though.

Otherwise I am pretty happy, this really does seem to give good output in most cases and the algorithms agree where desired. Lots of very minor things to fix above but this will be a robust addition to Sage, thanks for working so hard on it.

As I said above I think you have actually found a bug in the algorithm here. My hunch is that it's something to do with pruning so will take a look at that: your examples are going to serve as tests and will be incorporated in. Thank you very much for spotting this.

comment:36

As I said above I think you have actually found a bug in the algorithm here. My hunch is that it's something to do with pruning so will take a look at that: your examples are going to serve as tests and will be incorporated in. Thank you very much for spotting this.

You're very welcome; I really have a lot of motivation to encouraging more people in voting/choice/strategy to start using a standard tool.

Also, I should point out that there are three sorts of things I noticed with this.

Places where it was degenerate and 'enumeration' didn't give as many pure equilibria (in one case, none). Perhaps this is a bug in enumeration, as you say.
The fact that a certain type of degenerate case is very easy to recognize from the form of the matrices and could conceivably be checked for. That is probably a followup ticket.
One example where it was possibly degenerate but where 'lrs' inside of Sage gave a pure strategy which is not a NE, and which is not returned by the LSE online lrs service (which does return all the pure strategies 'enumeration' does in this case). So perhaps we are using lrs incorrectly.

I'll wait to review the other changes until you have this and the tuple thing sorted out, though I'm not worried about them :)

comment:37

For the PIPE thing, it might be (for whatever strange reason) added to the doc because of the lazy import. Perhaps just import it (and Popen) where it is necessary since there are only two places it is used.

comment:38

For the PIPE thing, it might be (for whatever strange reason) added to the doc because of the lazy import. Perhaps just import it (and Popen) where it is necessary since there are only two places it is used.

You know, I thought about that. But are there any other places this happens with lazy imports? It's not like this module doesn't lazy import some other stuff, but I don't remember ever seeing something like this before.

comment:39

Replying to @kcrisman:

You know, I thought about that. But are there any other places this happens with lazy imports? It's not like this module doesn't lazy import some other stuff, but I don't remember ever seeing something like this before.

I don't know of any other place where we've lazily imported a (standard?) python module, so in that way it's special.

comment:40

You know, I thought about that. But are there any other places this happens with lazy imports? It's not like this module doesn't lazy import some other stuff, but I don't remember ever seeing something like this before.

I don't know of any other place where we've lazily imported a (standard?) python module, so in that way it's special.

Ah, that does make sense.

Vincent, you can easily try that out by changing the import and then doing

./sage -b; ./sage -docbuild reference/game_theory html

and seeing if it's gone. However, I just tried to build it (without any changes yet, in fact not even including the latest changes here) and got UNABLE TO IMPORT MODULE for the doc (built!), with no content! So I am really confused now.

comment:41

Replying to @kcrisman:

You know, I thought about that. But are there any other places this happens with lazy imports? It's not like this module doesn't lazy import some other stuff, but I don't remember ever seeing something like this before.

I don't know of any other place where we've lazily imported a (standard?) python module, so in that way it's special.

Ah, that does make sense.

Vincent, you can easily try that out by changing the import and then doing
./sage -b; ./sage -docbuild reference/game_theory html
and seeing if it's gone. However, I just tried to build it (without any changes yet, in fact not even including the latest changes here) and got UNABLE TO IMPORT MODULE for the doc (built!), with no content! So I am really confused now.

Thanks both: I'll take a look at this and see if I can sort it out.

For info: I've fixed the enumeration bug. It was actually one of those 'neat' ones where something we assumed would be a quicker way of doing something was in fact incorrect in the particular case of degenerate games (nothing to do with the pruning). Just taking a look at the lrs issue: I assume it's a problem with the parser. Will push when it's all done :) (And hopefully PIPE docs disappear).

Last 10 new commits:

`b432676`	`Have added another test for pure equilibria - it passes`
`d7d73bf`	`Have rewritten tests so now all pass`
`8888cbc`	`Adding a test`
`f160aa2`	`Adding test that fails for lrs`
`12d864c`	`Have added tests that check that have correct H representation for game that is causing errors`
`1096bc3`	`Have test showing that pure lrs is outputting correct solution`
`050a576`	`Have test that fails - this will fix the parser`
`70c5837`	`Parser now working correctly, need to rewrite some tests before refactoring`
`9967e78`	`Re written tests`
`c7e42b7`	`Changing all eq to output tuples, also sorting so output is comparable`

Changed commit from 8775f12 to c7e42b7

comment:43

Replying to @kcrisman:

As I said above I think you have actually found a bug in the algorithm here. My hunch is that it's something to do with pruning so will take a look at that: your examples are going to serve as tests and will be incorporated in. Thank you very much for spotting this.

You're very welcome; I really have a lot of motivation to encouraging more people in voting/choice/strategy to start using a standard tool.

Also, I should point out that there are three sorts of things I noticed with this.

Places where it was degenerate and 'enumeration' didn't give as many pure equilibria (in one case, none). Perhaps this is a bug in enumeration, as you say.

I have addressed this: it was a genuine bug where we were trying to be quick (which worked for non degenerate games) but we were in effect incorrect. Have added tests as well.

The fact that a certain type of degenerate case is very easy to recognize from the form of the matrices and could conceivably be checked for. That is probably a followup ticket.

I would prefer to have this as a follow up ticket (but can already start lining up a student to work on it!).

One example where it was possibly degenerate but where 'lrs' inside of Sage gave a pure strategy which is not a NE, and which is not returned by the LSE online lrs service (which does return all the pure strategies 'enumeration' does in this case). So perhaps we are using lrs incorrectly.

This was also a bug but this time a bit more of a clumsy one. Our parser was assuming a certain format. This has been fixed now (more tests added).

I'll wait to review the other changes until you have this and the tuple thing sorted out, though I'm not worried about them :)

I have also addressed the tuples/vectors issue. I've gone with tuples and also sorted the output of both algorithms so this way the algorithms do give the same output (even taking ordering in to account).

I am afraid though that I don't seem to have the PIPE doc build locally. Am I looking in the wrong place? I ran ./sage -b; ./sage -docbuild reference/game_theory html (Note that I had to run a make doc-clean) with no problems and when I go to src/doc/output/html/en/reference/game_theory/sage/game_theory I only have two html files: 'cooperative_game.html' and 'normal_form_game.html'.

If I'm looking in the wrong please please let me know...

comment:45

Wow, this is all great work. Good catch on the correct place to put None! A couple now super-minor things.

With this wording

Here is a test that failed during development::

Maybe that's a bit too pessimistic, just "another test" is fine, or in the updated version something like

Testing against an error in `check_NE`::

and similarly in other situations.

I have a feeling this one is also optional? But I didn't get an error.

+            sage: print lrs_output[5:-4]

A typo that means this won't ever be tested...

+            sage: N.obtain_nash(algorithm='lrs')  # optional t- lrs

This one just tests that it exists, not the solutions (though presumably this example has now gotten lots of traction!)

+            sage: A = matrix(3, [-7, -5,  5, 5,  5,  3,  1, -6,  1])
+            sage: B = matrix(3, [-9, 7, 9, 6, -2, -3, -4, 6, -10])
+            sage: N = NormalFormGame([A, B])

Can you confirm that what went wrong with the parser is the following: lrs returns equilibria in the form of several possible player 2 strategies for each player 1 strategy, but you just assumed that each player 2 strategy corresponded to a different player 1 strategy? That's what the change in code looks like.
You need this test fixed (easy):

sage -t src/sage/game_theory/normal_form_game.py
**********************************************************************
File "src/sage/game_theory/normal_form_game.py", line 150, in sage.game_theory.normal_form_game
Failed example:
    p += plot((A * vector([y, 1 - y]))[1], y, 0, 1, color='red', legend_label='$u_1(r_2, (y, 1-y))$'); p
Expected nothing
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************

In built doc, apparently `i`th disagrees with Sage's Sphinxification and gives it indigestion. Changing it to `i` th fixes things, but I get that this might not be desirable. Unfortunately, :math:`i`th doesn't give what we want either.
Also, apparently lazy importing PIPE was indeed what caused it to be built for me in the documentation.

But I think that's it! Commendable work. Now we just have to get the rest of this game theory stuff working, including getting gambit to build right...

sagemath / sage

Game Theory: Build class for normal form games as well as ability to obtain Nash equilibria #16954