Game Theory: build capacity to use gambit to solve Normal Form Games.

[drvinceknight]

Build on other tickets (#16954 and #16466) to allow for the use of Gambit as an option when calculating Nash Equilibria.

Depends on #16466

Component: game theory

Keywords: Normal Form Games

Author: Vince Knight, James Campbell

Branch: 07b0bab

Reviewer: Jeroen Demeyer, Karl-Dieter Crisman

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

[nathanncohen]

comment:1

(being curious)

[kcrisman]

comment:2

Putting to no listed component because truly non fits. Also, author is really for actual author of any changes (which may well be vinceknight! but isn't yet).

[kcrisman]

Changed author from Vince Knight to none

[drvinceknight]

comment:3

Thanks kcrisman: that all makes a lot more sense than what I had put down. I'll go check if you have changed the other related tickets and if not will change myself.

[kcrisman]

comment:4

Here is a relevant paper: http://math.berkeley.edu/~datta/msprojectreport.pdf

[drvinceknight]

comment:5

Replying to @kcrisman:
Here is a link to the lrs page (which has relevant papers there): http://cgm.cs.mcgill.ca/~avis/C/lrslib/USERGUIDE.html

This is what I would think as best way to go (as stated in Gambit FAQ: lrs is more robust) but that paper (pointed out by kcrisman) which points at Gambit will be super useful to evaluate the best way to go.

[kcrisman]

comment:6

This is what I would think as best way to go (as stated in Gambit FAQ: lrs is more robust) but that paper (pointed out by kcrisman) which points at Gambit will be super useful to evaluate the best way to go.

Where is this FAQ? I couldn't find it easily.

---

Thinking out loud below:

• lrs seems to just be about polytopes - useful, to be sure, but I'm just wondering whether reinventing the entire rest of the Gambit wheel is a great idea. For instance, Gambit's McKelvey was THE McKelvey. How much of lrs do we really need for finding equilibria, as opposed to all the other many things one does in game theory?
• However, Gambit doesn't talk about cooperative or matching game theory (tickets Game Theory: Build capacity to calculate Shapley value of cooperative games. #16332, Game Theory: Build capacity to solve matching games in to Sage. #16331)
• Maybe it would be worth talking to the Gambit folks directly about how/whether any common work would be useful? Especially if we could both use the same formats (if they are useful formats) - having a common base would be very valuable, especially as other software doesn't seem to have gotten into a standard format or even into game theory at all.

[drvinceknight]

comment:7

Replying to @kcrisman:

This is what I would think as best way to go (as stated in Gambit FAQ: lrs is more robust) but that paper (pointed out by kcrisman) which points at Gambit will be super useful to evaluate the best way to go.

Where is this FAQ? I couldn't find it easily.

---

Thinking out loud below:

• lrs seems to just be about polytopes - useful, to be sure, but I'm just wondering whether reinventing the entire rest of the Gambit wheel is a great idea. For instance, Gambit's McKelvey was THE McKelvey. How much of lrs do we really need for finding equilibria, as opposed to all the other many things one does in game theory?
• However, Gambit doesn't talk about cooperative or matching game theory (tickets Game Theory: Build capacity to calculate Shapley value of cooperative games. #16332, Game Theory: Build capacity to solve matching games in to Sage. #16331)
• Maybe it would be worth talking to the Gambit folks directly about how/whether any common work would be useful? Especially if we could both use the same formats (if they are useful formats) - having a common base would be very valuable, especially as other software doesn't seem to have gotten into a standard format or even into game theory at all.

Yeah all fair comments: I'll get in touch with the Gambit folk (they're a very short drive from where I am) and see what they think. It was my understanding that lrs 'kind of' exists within Sage already as some sort of 'extra library'? Is that something I've made up? I think I've seen it somewhere...

With regards to matching games and cooperative games they basically involve very straightforward algorithms so I was just thinking of coding those in Sage itself. A combination of cython and python should do the trick and one of those would be a nice warm up exercise for my student. If we decide to go the Gambit way we can still have all these things side by side I suppose?

[kcrisman]

comment:8

Yeah all fair comments: I'll get in touch with the Gambit folk (they're a very short drive from where I am) and see what they think. It was my understanding that lrs 'kind of' exists within Sage already as some sort of 'extra library'? Is that something I've made up? I think I've seen it somewhere...

I've commented on your old sage-support thread on this. Also a very interesting sage-devel thread on this is out there.

With regards to matching games and cooperative games they basically involve very straightforward algorithms so I was just thinking of coding those in Sage itself. A combination of cython and python should do the trick and one of those would be a nice warm up exercise for my student. If we decide to go the Gambit way we can still have all these things side by side I suppose?

Oh, of course. And it will be very useful to have a "one-stop shop" for this. Just trying to figure things out.

[drvinceknight]

comment:9

Replying to @kcrisman:

Yeah all fair comments: I'll get in touch with the Gambit folk (they're a very short drive from where I am) and see what they think. It was my understanding that lrs 'kind of' exists within Sage already as some sort of 'extra library'? Is that something I've made up? I think I've seen it somewhere...

I've commented on your old sage-support thread on this. Also a very interesting sage-devel thread on this is out there.

Thanks! I'll take a closer look.

With regards to matching games and cooperative games they basically involve very straightforward algorithms so I was just thinking of coding those in Sage itself. A combination of cython and python should do the trick and one of those would be a nice warm up exercise for my student. If we decide to go the Gambit way we can still have all these things side by side I suppose?

Oh, of course. And it will be very useful to have a "one-stop shop" for this. Just trying to figure things out.

Yeah it's really helpful (and appreciated) to talk this over with you :)

[theref]

comment:10

We've been in contact with the man from Gambit and he seems quite keen on potentially being included in Sage. He appears to be fairly familiar with Sage and understands that some things may need to be tidied up before it becomes a standard package.

[kcrisman]

comment:11

We've been in contact with the man from Gambit and he seems quite keen on potentially being included in Sage. He appears to be fairly familiar with Sage and understands that some things may need to be tidied up before it becomes a standard package.

Great - and in any case it would have to start as optional. But that isn't a total hurdle, as one could have wrapper classes or stand-alone, depending on what Gambit actually does. I'm most interested in compatibility - it would be nice for there to be a standard format for representing things, you know?

[theref]

comment:12

But that isn't a total hurdle, as one could have wrapper classes or stand-alone, depending on what Gambit actually does.

I like the idea of having wrapper classes that could make use of Sage's ability to show things in an aesthetically pleasing way, anything involving latex would be great for example.

it would be nice for there to be a standard format for representing things, you know?

I agree, gambit actually uses its own .efg and .nfg file formats for representing games with the aim of them being easily readable by humans. Given that there isn't much else out there they may become a standard themselves.

[kcrisman]

comment:13

Originally posted on the wrong ticket...

---

I really like the idea you had here:

with normal form games, we might have a prebuilt Matching Pennies game that the user could load,

Yes! Just like

sage: graphs.[tab]
graphs.Balaban10Cage
graphs.Balaban11Cage
graphs.BalancedTree
graphs.BarbellGraph
graphs.BidiakisCube
graphs.BiggsSmithGraph
graphs.BishopGraph
graphs.BrinkmannGraph
<snip>
sage: matroids.[tab]
matroids.AG               matroids.Uniform          matroids.named_matroids
matroids.CompleteGraphic  matroids.Wheel            
matroids.PG               matroids.Whirl            

This would be awesome, a built-in library one could explore of basic examples.

[drvinceknight]

comment:15

Replying to @kcrisman:

We've been in contact with the man from Gambit and he seems quite keen on potentially being included in Sage. He appears to be fairly familiar with Sage and understands that some things may need to be tidied up before it becomes a standard package.

Great - and in any case it would have to start as optional. But that isn't a total hurdle, as one could have wrapper classes or stand-alone, depending on what Gambit actually does. I'm most interested in compatibility - it would be nice for there to be a standard format for representing things, you know?

Yeah completely agree. Structure is something we're going to be carefully thinking about over the next week or two. I'm hoping we get to meet with Ted (Gambit) to talk about stuff.

I don't suppose @kcrisman that you would have a spare 15 minutes for us to chat (via hangout or something) just to get your thoughts? Perhaps when we have an initial/draft architecture written down we could talk? We want to make sure we future proof things as much as possible and also that we're thinking of the right stuff... Completely understand that you are busy and really appreciate the time you're giving on here so no problem if that doesn't work :)

(I replied to the email I got about this on my phone with this message about 2 hours ago hoping it would automagically appear here but that doesn't look like it happened)

[drvinceknight]

comment:16

Replying to @theref:

But that isn't a total hurdle, as one could have wrapper classes or stand-alone, depending on what Gambit actually does.

I like the idea of having wrapper classes that could make use of Sage's ability to show things in an aesthetically pleasing way, anything involving latex would be great for example.

it would be nice for there to be a standard format for representing things, you know?

I agree, gambit actually uses its own .efg and .nfg file formats for representing games with the aim of them being easily readable by humans. Given that there isn't much else out there they may become a standard themselves.

The LaTeX representation of things will be minor tweaks I imagine. It's all about making sure we get the general structure of Gambit games and 'our games' aligned so that we can talk to 'Gambit' in the right way... We won't rush this: important to get it right.

[kcrisman]

comment:17

I don't suppose @kcrisman that you would have a spare 15 minutes for us to chat (via hangout or something) just to get your thoughts? Perhaps when we have an initial/draft architecture written down we could talk? We want to make sure we future proof things as much as possible and also that we're thinking of the right stuff... Completely understand that you are busy and really appreciate the time you're giving on here so no problem if that doesn't work :)

Actually, today for the next couple hours would be good.

(I replied to the email I got about this on my phone with this message about 2 hours ago hoping it would automagically appear here but that doesn't look like it happened)

No, I don't think you can reply to Trac tickets that way. (Can you? I mean, it's possible you could...)

[theref]

Dependencies: #16466,

[theref]

comment:19

There is some discussion on Github about how we should model our Normal Form Game class. The main question being should we inherit from Gambit with methods written for other representation and algorithms, or should we inherit from SageObject and have different representations as different attributes.

The relevant issue can be found here. Please could people take a read through what has been said so far and any comments, all help is greatly appreciated!

[theref]

Branch: u/jcampbell/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria

[theref]

Commit: 40b8b16

[sagetrac-git]

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

aa3fc67

Fixing wording for LCP algorithm differences

[sagetrac-git]

Changed commit from 8f3cc37 to aa3fc67

[drvinceknight]

comment:64

Replying to @kcrisman:

Quite minor comments:

• # optional - LCP - should this be gambit?
• the output differs to the other algorithms - from the other ones?

Correct on both accounts. Both fixed now (thanks!).

I ended up wrapping presents long enough that I won't get to a final review until Monday, but on the surface it looks like everything is just fine, I just want to make sure there isn't some edge case in the parsing and that the equilibria are okay. I am really surprised I missed so many formatting things before - thanks, Jeroen!

Thanks both and if this waits till after Christmas it's not the end of the world :) Happy holidays both :)

[kcrisman]

comment:65

• # optional - LCP - should this be gambit?

There were two of these, one still is there ;-)

Thanks both and if this waits till after Christmas it's not the end of the world :) Happy holidays both :)

I have something else to take care of first but hope to get to it before the end of today.

[kcrisman]

comment:66

+It is also possible to generate a Normal Form Game from a gambit Game::
+

This would be a good place to refer to the gambit document or remind why there are all these ints.

is evidenced by the two algorithms returning different solutions::

Maybe better now is "the various algorithms"?

Finally, I think the parser is working fine but could use a little extra tlc if and when games with more than 2 players are implemented, as it is a very long series of things to parse for the reader (I mean the code like profile.append(tuple(gambitstrategy[previousplayerstrategylength: previousplayerstrategylength + len(player.strategies)]))) though I agree it should work correctly.

I don't see any other issues. Thanks for breaking all of these tickets apart! It really made it a lot easier to get figured out.

[sagetrac-git]

Changed commit from aa3fc67 to 0c6cc65

[sagetrac-git]

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

9b59a46	Fixed reference to just two algorithms
2533822	Have added link to gambit docs from norma form game docs at relevant point
0c6cc65	Merge branch 'u/vinceknight/gambit_integration' of git://trac.sagemath.org/sage into rebased_version

[drvinceknight]

comment:68

Replying to @kcrisman:

+It is also possible to generate a Normal Form Game from a gambit Game::
+

This would be a good place to refer to the gambit document or remind why there are all these ints.

I've added a pointer to the gambit documentation. Let me know if you think I've said too much/little.

is evidenced by the two algorithms returning different solutions::

Maybe better now is "the various algorithms"?

Yup: have put that in.

Finally, I think the parser is working fine but could use a little extra tlc if and when games with more than 2 players are implemented, as it is a very long series of things to parse for the reader (I mean the code like profile.append(tuple(gambitstrategy[previousplayerstrategylength: previousplayerstrategylength + len(player.strategies)]))) though I agree it should work correctly.

I agree, I'm hoping that future dev will further integrate all the gambit algorithms, as this happens the parser will be in turn expanded. The next thing I'll be working on is #17392 though :)

I don't see any other issues. Thanks for breaking all of these tickets apart! It really made it a lot easier to get figured out.

Thank you for all your help: I'm planning on finding time to try and review some tickets myself :)

[kcrisman]

comment:69

A few more things, largely about the gambit docs document.

• It's capitalized IPython, for whatever reason - the gambit docs thing is not correct that way, I missed it earlier.
• Here

The `python API documentation for gambit
<http://www.gambit-project.org/gambit14/pyapi.html>_` 

I think the syntax needs to put the underscore after the backtick.

• There are several things in single backticks (like `LCP`, but look for them, it's not the only one) that should be in double backticks ``LCP``.

Otherwise I think we are okay.

[kcrisman]

Changed reviewer from Jeroen Demeyer to Jeroen Demeyer, Karl-Dieter Crisman

[sagetrac-git]

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

70b61ab	Fixing capitalisation of ipython
cc282fb	Fixing syntax for hyperlink
c9f036a	Fixing syntaxing

[sagetrac-git]

Changed commit from 0c6cc65 to c9f036a

[drvinceknight]

comment:72

Sorry for the late reply to this: I've had a pretty nice internet fast :) Hope you all had a great holiday season and happy new year!

Replying to @kcrisman:

A few more things, largely about the gambit docs document.

• It's capitalized IPython, for whatever reason - the gambit docs thing is not correct that way, I missed it earlier.

Pretty sure I caught these now.

• Here

The `python API documentation for gambit
<http://www.gambit-project.org/gambit14/pyapi.html>_` 

Yup: have fixed.

I think the syntax needs to put the underscore after the backtick.

• There are several things in single backticks (like `LCP`, but look for them, it's not the only one) that should be in double backticks ``LCP``.

Looked for these and think there was just that one that I recognised. I did find various things in single back ticks but I think there done so correctly, I might well be confused by the syntax though: if you could point out one that is not right that should clarify what I'm misunderstanding and I'll go ahead and fix all the rest. (Apologies for not finding these, have built the docs and read through but think I'm just missing it).

Thanks again :)

Otherwise I think we are okay.

[kcrisman]

comment:73

Sorry for the late reply to this: I've had a pretty nice internet fast :)

A good idea! I also (nearly) did that.

• It's capitalized IPython, for whatever reason - the gambit docs thing is not correct that way, I missed it earlier.

Pretty sure I caught these now.

This commit actually makes it worse; it changes one IPython and then doesn't correctly fix an ipython. Why don't you back up to before that commit and fix them correctly - all should be first two letters caps, rest lowercase.

Looked for these and think there was just that one that I recognised.

I think you got 'em.

[kcrisman]

comment:74

Just had to check the look of the docs again. In addition to getting the IPython thing right (there are two total in the gambit docs and one in the normal form game file), I notice that in the gambit docs file

Here is how to use the ExternalEnumPureSolver

has ExternalEnumPureSolver in single backticks, but this makes it look like a math variable instead of code. I recommend double backticks or nothing; similarly for

If one really wants to use gambit directly in Sage (without using the NormalFormGame class as a wrapper)

Not sure why I didn't mention those before, I did see them.

[sagetrac-git]

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

f684012	Fixing incorrect optional tag
93bd1d6	Fixing wording for LCP algorithm differences
4e2afbd	Fixing syntaxing
b0142f5	Have fixed Ipython capitalisation
3a0b97e	Adding correct backticks

[sagetrac-git]

Changed commit from c9f036a to 3a0b97e

[drvinceknight]

comment:76

I think I caught everything although I made a slight mess with the rebase (Still learning... Will get it eventually) so apologies if the commits do not make the most sense. If it's confusing just let me know and I'll fix them.

[kcrisman]

comment:77

You unfortunately reverted or something the fix for one of the lcp optional tests (should be gambit):

+            sage: LCP_eqs == sorted(LCP_eqs)  # optional - LCP
+            True

Sorry, I shouldn't have asked you for some wacky thing, just trying to save a commit...

Otherwise all set!

[sagetrac-git]

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

8f3cc37	Fixing incorrect optional tag
aa3fc67	Fixing wording for LCP algorithm differences
0c6cc65	Merge branch 'u/vinceknight/gambit_integration' of git://trac.sagemath.org/sage into rebased_version
70b61ab	Fixing capitalisation of ipython
cc282fb	Fixing syntax for hyperlink
c9f036a	Fixing syntaxing
cc60552	Merge conflict
07b0bab	Have corrected optional test

[sagetrac-git]

Changed commit from 3a0b97e to 07b0bab

[drvinceknight]

comment:79

Replying to @kcrisman:

You unfortunately reverted or something the fix for one of the lcp optional tests (should be gambit):

+            sage: LCP_eqs == sorted(LCP_eqs)  # optional - LCP
+            True

Sorry, I shouldn't have asked you for some wacky thing, just trying to save a commit...

Not at all: I appreciate the opportunity to try and learn :) Haven't quite gotten it (this push is a single commit for example that seems to have grabbed more...) but I will!

Otherwise all set!

Awesome! The next thing will be that list of games :)

[vbraun]

Changed branch from u/vinceknight/gambit_integration to 07b0bab

[kcrisman]

Changed author from Vincent Knight, James Campbell to Vince Knight, James Campbell

[kcrisman]

Changed commit from 07b0bab to none

[kcrisman]

comment:82

Vince, I guess you are Vince from now on if we want to keep credit to the same individual :)