Make list of built-in normal form games

[kcrisman]

In #16333 comment:13, the idea arises of having built-in normal form games for pedagogical (or other) purposes, similarly to in our discrete math areas.

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  

There are quite a few such games out there in the literature that would be assumed as 'standard'.

CC: @drvinceknight @nathanncohen

Component: game theory

Keywords: days64

Author: Vince Knight, James Campbell

Branch: 6ec7195

Reviewer: Karl-Dieter Crisman, Travis Scrimshaw

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

[drvinceknight]

comment:1

Oh!!! love this idea, I'd actually forgotten so thanks for opening the ticket! I'll take a careful look through the way this has been done for graphs and matroids and happy to have a go.

[tscrim]

comment:2

Or algebras or crystals Samus :P.

[drvinceknight]

Last 10 new commits:

d7c095a	Merge branch 'catalog' of github.com:theref/sage-game-theory into catalog
d1eda11	RPS complete
e79d97c	Rock Paper Scissors Lizard Spock now added
7d26c92	adds Stag Hunt
667b710	Fixing merge conflicts and tweaking some things
fb47923	Adding the game of chicken
4956e85	Fixing slight error in docs for travellers game
d97483d	Adding travellers dilemma game
cd4ae37	Changig order of strategies in travellers dilemma example to be consistent
c343ff4	Re-ordering documentation for GT

[drvinceknight]

Commit: c343ff4

[drvinceknight]

Branch: u/vinceknight/catalog_of_games

[drvinceknight]

comment:5

James and I have just finished working on this assuming we're on the right path.
Everything is well tested and documented (we think) but let us know (or indeed let us know if you can think of any games that we're missing).

(We decided to follow how things were done for matroids as closely as possible.)

[kcrisman]

comment:6

I've been very busy lately but I do plan to put this on my docket, looking forward to it!

[kcrisman]

comment:7

Okay, I looked at this for all of two minutes and have the following non-mathematical comments.

• Many of these are very standard in the literature. There should be normative references, whether to an undergraduate text like Straffin or to some other source, such as RAND corp. whitepapers or whatever.
• Many of these games will have many different "versions" in the literature - for instance, your numbers for PD are quite unorthodox, as they are positive :-) Maybe there should be way to specify the actual numbers for each, as they have a standard form in some sense (one could check for these).
• There are a number of evolutionary biology games that are quite interesting that have parameters, and indeed parameters show up in many advanced treatments of such games. Not sure how this is a useful comment but anyway I think having parameters is a "good thing". I like Mesterton-Gibbons' treatment of this (AMS STML volume 11).
• Finally, there are some comprehensive listings by e.g. Rapaport et al., Fishburn and Kilgour, and Robinson and Goforth, which might be interesting to include here (or some later ticket) for 2x2 normal form games "types".

[drvinceknight]

comment:8

Many of these are very standard in the literature. There should be normative references, whether to an undergraduate text like Straffin or to some other source, such as RAND corp. whitepapers or whatever.

Cool, will add references throughout (see later comments).

Many of these games will have many different "versions" in the literature - for instance, your numbers for PD are quite unorthodox, as they are positive :-)

Very help to change it, perhaps once I go through and grab references for each I'll just go with on of the many possible ones (if you are particularly against this one I'll make sure I pick a different one).

Maybe there should be way to specify the actual numbers for each, as they have a standard form in some sense (one could check for these).

So would your idea for the PD for example, be to have a default standard (as mentioned above) but that one could pass a set of arguments?

So for example one could pass the RSTP values (see 'Canonical PD payoff matrix' here: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma). I suppose the thing with the PD is that RSTP notation is pretty common and conventional, in all honesty I am not sure they are for some of the others but will investigate.

Each game could have an initialisation test that checks if the values obey the defining inequalities. Let me know if that was what you're thinking and I'll go ahead and get working on it :)

There are a number of evolutionary biology games that are quite interesting that have parameters, and indeed parameters show up in many advanced treatments of such games. Not sure how this is a useful comment but anyway I think having parameters is a "good thing". I like Mesterton-Gibbons' treatment of this (AMS STML volume 11).

Yeah, not at all against this idea (RSTP is certainly very common and used).

Finally, there are some comprehensive listings by e.g. Rapaport et al., Fishburn and Kilgour, and Robinson and Goforth, which might be interesting to include here (or some later ticket) for 2x2 normal form games "types".

I'd suggest this be a further ticket as it could actually be something that is added to the normal form game class so that we could for example (a much simpler 'type') just be able to check if any game is symmetric.

[kcrisman]

comment:9

So for example one could pass the RSTP values (see 'Canonical PD payoff matrix' here: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma). I suppose the thing with the PD is that RSTP notation is pretty common and conventional, in all honesty I am not sure they are for some of the others but will investigate.

Yes, exactly. And if there is no conventional standard, just don't do it and then others could propose a standard as an enhancement.

Each game could have an initialisation test that checks if the values obey the defining inequalities. Let me know if that was what you're thinking and I'll go ahead and get working on it :)

Yes.

[drvinceknight]

Author: vinceknight, jcampbell

[kcrisman]

Changed author from vinceknight, jcampbell to Vincent Knight, James Campbell

[sagetrac-git]

Changed commit from c343ff4 to d097599

[sagetrac-git]

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

78510d6	Have written new tests for Prisoners Dilemma
6c33d2c	17392: Adding generalised form of PD
e7bca58	Adding generic coordination game
f862b3e	Rewriting battle of the sexes as a coordination game
e139b40	Change repr of battle of the sexes
08466bd	Some bugs and writing stag hunt as a coordination game
f48c729	Have a generic anti coordination game
c8a1dd4	Fixing test after changing PD
d097599	Adding references for a variety of games

[drvinceknight]

comment:13

Hi Karl.

I'm pushing the latest set of work I've done on this. I still need to get more references. I am currently at Sage Days 64 so that will have to wait till I get back to my text books in Cardiff but thought I'd push this as it is as I've parametrised a variety of games.

One important change is the ability to create a generic Coordination and Anti Coordination game so that the Battle of the Sexes for example is a particular case of the first.

Let me know what you think (but aware that I need to throw more references in).

[theref]

Changed keywords from none to days64

[sagetrac-git]

Changed commit from d097599 to 9d979d4

[sagetrac-git]

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

fd6f156	adds reference for Travellers Dilemma
4e05c46	Adding journal info for reference
a9bb53d	Working on referencing
8d2ff3c	Merge branch 'develop' into catalog
d7bb533	reference for hawk-dove
c0029e0	Merge branch 'catalog' of https://github.com/theref/sage-game-theory into catalog
d752a13	changes hawk-dove to match reference
3bd15b8	Merge branch 'catalog' of github.com:theref/sage-game-theory into catalog
e4f9a7d	Have references for all games
9d979d4	Reorganising references

[drvinceknight]

comment:17

I think this is now ready. A lot of references and almost everything is dependent on parameters (or a type of game that is dependent on parameters).

There will always be more games that could be added but let us know if you think there's any that really should be in this ticket :)

[kcrisman]

comment:18

A quick read-through says great and thorough work. There are a few typos and I will want to check my sources as well to make sure we are agreeing on the standard definitions for some of the games (and I may not be able to do that for some time given my current duties) but in general this will be a great resource and I wish I were teaching game theory so I could! Also, I would parametrize Chicken if it were me, but maybe this isn't typically a parametrized game form?

Oh, and I am agnostic on where the tab-completion happens, but since game_theory covers more than non-cooperative game theory I wonder about that - maybe game_theory.normal_form_games.[tab], though that is cumbersome-ish (only -ish because of tab-completion in the first place). Of course, you all have implemented the entire thing so maybe it doesn't matter... but if CGT or some more standard cooperative stuff "examples" get implemented then it could be useful to separate those catalogs. Particularly for combinatorial game theory there is likewise a standard set of basic examples (like Nim) and I wonder about confusion there, which can't happen in graph or matroid catalogs.

[drvinceknight]

comment:19

A quick read-through says great and thorough work. There are a few typos and I will want to check my sources as well to make sure we are agreeing on the standard definitions for some of the games (and I may not be able to do that for some time given my current duties) but in general this will be a great resource and I wish I were teaching game theory so I could!

That's great: thanks. Apologies for the typos and no rush: I understand how busy we all are :)
I expect you will have some references that give differing parameters. If so just let us know and we'll tweak and include your reference text also.

Also, I would parametrize Chicken if it were me, but maybe this isn't typically a parametrized game form?

We have coded this as a particular type of anti-coordination game so it is in some aspects already parametrized. Let me know what you think...

Oh, and I am agnostic on where the tab-completion happens, but since game_theory covers more than non-cooperative game theory I wonder about that - maybe game_theory.normal_form_games.[tab], though that is cumbersome-ish (only -ish because of tab-completion in the first place). Of course, you all have implemented the entire thing so maybe it doesn't matter... but if CGT or some more standard cooperative stuff "examples" get implemented then it could be useful to separate those catalogs. Particularly for combinatorial game theory there is likewise a standard set of basic examples (like Nim) and I wonder about confusion there, which can't happen in graph or matroid catalogs.

James and I wondered about this one for a while and are also agnostic about it. I think it could be nice to have it as just game_theory.[tab] so that potentially we would get game_theory.Nim as well as game_theory.PrisonersDilemma but at the same time it might be more organised to seperate things out (in which case we should probably also rename the catalog.py file to normal_form_game_catalog.py. Let us know what you think: very happy either way.

[kcrisman]

comment:68

I think this solution is fine, though

+        sage: g = game_theory.normal_form_games.CoordinationGame(A=9,
+        ....:                                                    a=6,
+        ....:                                                    B=0,
+        ....:                                                    b=1,
+        ....:                                                    C=2,
+        ....:                                                    c=10,
+        ....:                                                    D=4,
+        ....:                                                    d=11)

starts looking a little longish. Was there a reason for doing that uniformly? You may also want to (briefly) mention somewhere convenient why you're doing this, or perhaps just where the utility dictionary is == to the game, which I wasn't expecting (since it's not a game, just a random dictionary) but is fine, as far as I care about it.

[drvinceknight]

comment:69

Replying to @kcrisman:

starts looking a little longish. Was there a reason for doing that uniformly?

Do you mean the multilines? That's mainly to stick with the 79 character limit, I noticed this for the larger games and then thought I should do it throughout. I agree that it looks pretty bad. I'm happy to leave as is (so that it fits with the 79 characters strictly) but perhaps the rule could be broken for some of the smaller dicts?

You may also want to (briefly) mention somewhere convenient why you're doing this, or perhaps just where the utility dictionary is == to the game, which I wasn't expecting (since it's not a game, just a random dictionary) but is fine, as far as I care about it.

So perhaps mention something a long the lines of:

sage: # Building a dictionary to test the required result
sage: # The order of the dictionary might differ on a given machine
sage: d = {...
sage: d == g

Let me know if that's what you mean?

Thanks again for your time with this Karl.

[kcrisman]

comment:70

starts looking a little longish. Was there a reason for doing that uniformly?

Do you mean the multilines? That's mainly to stick with the 79 character limit, I noticed this for the larger games and then thought I should do it throughout. I agree that it looks pretty bad. I'm happy to leave as is (so that it fits with the 79 characters strictly) but perhaps the rule could be broken for some of the smaller dicts?

I think only do it if you really go well beyond the limit. Or just continue the multiline in such a way that there are TWO lines and not EIGHT lines :)

You may also want to (briefly) mention somewhere convenient why you're doing this, or perhaps just where the utility dictionary is == to the game, which I wasn't expecting (since it's not a game, just a random dictionary) but is fine, as far as I care about it.

So perhaps mention something a long the lines of:

sage: # Building a dictionary to test the required result
sage: # The order of the dictionary might differ on a given machine
sage: d = {...
sage: d == g

Oh, not even that much - maybe just before the very first instance of this, preferably not within a specific function but at the module level, something like

We can construct a game::

    sage: construct a game
    sage: do something with it

When we test whether the game is actually the one in question, sometimes we will build a dictionary to test it, since this can be platform-dependent, like so::

    sage: d = {...
    sage: d == g
    True

And then the others are tacit.

[sagetrac-git]

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

7d5ae05	Adding an explanation of the dictionary test
1a9c835	Making the previous PEP8 adjustment look ok

[sagetrac-git]

Changed commit from 31ec186 to 1a9c835

[sagetrac-git]

Changed commit from 1a9c835 to 4210a63

[sagetrac-git]

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

4210a63

Making the previous PEP8 adjustment look ok

[drvinceknight]

comment:73

Ok Karl, I think this is ready now :) I've made the adjustments I believe you are suggesting :)

[kcrisman]

comment:74

Presumably irrelevant remarks:

+We can then immediately obtain the Nash equilibria for the game::

Of course, in that example there is only an equilibrium, though in general presumably not.

modelled

Dang Brits.

PEP8 looks fine. If this passes tests please set to positive review, unfortunately I have something else I need to do now.

[sagetrac-git]

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

2c111e2

Minor tweaks

[sagetrac-git]

Changed commit from 4210a63 to 2c111e2

[drvinceknight]

comment:76

Replying to @kcrisman:

Dang Brits.

Hehe :) My last commit addresses those two minor points.

PEP8 looks fine. If this passes tests please set to positive review, unfortunately I have something else I need to do now.

Cool: tests pass and docs build so am setting to positive review.

[tscrim]

comment:77

Sorry for not responding sooner, I've been busy moving out of my house and having to choose my time (and the past 17 hours, been traveling from SF to Korea). Here are my thoughts, not that they really count for much.

I try and keep to the 80 char/line limit, and what Vince did initially is the "best" practice according to PEP8. However, I side with Karl-Dieter on this in that it just looks ugly and it's worth it to consolidate the data and go past 80 char/line limit when it is easier to read.

However I do have an issue with this sentence:

+When we test whether the game is actually the one in question, sometimes we will
+build a dictionary to test it, since this can be platform-dependent, like so::

What is "this"? In particular, when I first read this, to me it seemed like the actual output could be different on different machines, whereas it is only the print representation of the dictionary used to model the game. Your change doesn't have to be as verbose as that (IMO), just change "this" to "the printed representation" or something like that.

Once you make that change, you can set this back to positive review on my behalf.

[drvinceknight]

comment:78

Replying to @tscrim:

However I do have an issue with this sentence:

+When we test whether the game is actually the one in question, sometimes we will
+build a dictionary to test it, since this can be platform-dependent, like so::

What is "this"? In particular, when I first read this, to me it seemed like the actual output could be different on different machines, whereas it is only the print representation of the dictionary used to model the game. Your change doesn't have to be as verbose as that (IMO), just change "this" to "the printed representation" or something like that.

Excellent point. Will change that asap. Thanks!

I hope your move went well!

[sagetrac-git]

Changed commit from 2c111e2 to 6ec7195

[sagetrac-git]

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

6ec7195

Clarifying text about testing dictionaries.

[vbraun]

Changed branch from u/vinceknight/catalog_of_games to 6ec7195

[jdemeyer]

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

[jdemeyer]

Changed commit from 6ec7195 to none