Make list of built-in normal form games

kcrisman commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

comment:2

Or algebras or crystals Samus :P.

drvinceknight commented 9 years ago

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 commented 9 years ago

Commit: c343ff4

drvinceknight commented 9 years ago

Branch: u/vinceknight/catalog_of_games

drvinceknight commented 9 years ago

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 commented 9 years ago

comment:6

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

kcrisman commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

Author: vinceknight, jcampbell

kcrisman commented 9 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from c343ff4 to d097599

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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 commented 9 years ago

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

d3dfe940-4ef4-4242-81e0-6916cce90212 commented 9 years ago

Changed keywords from none to days64

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from d097599 to 9d979d4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

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 commented 9 years ago

comment:20

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

I was thinking more like http://www.gametheory.net/dictionary/games/GameofChicken.html

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.

Then better to plan for the future, eh?

Minor, many very minor points because I have nothing else to complain about:

an often used v -> An often used v
There is a single Nash equilibria -> There is a single Nash equilibrium
There are several other instances of this, I believe, e.g.

+    A coordination game is a particular type of game where the pure Nash
+    equilibria

so please be careful on the plural/singular here.

if the defining inequality is not -> if the defining inequalities are not
I think most of the things like

Return a Battle of the Sexes game

should be

Return a Battle of the Sexes game.

Chicken: Anti coordination game: Normal Form Game seems not to jive with the usual Battle of the sexes - Coordination game: Normal Form Game format. I don't know that I like either but I understand the dilemma here.
Game theory question.

+    An anti coordination game is a particular type of game where the pure Nash
+    equilibria is for the players to pick different strategies (or equivalent)
+    strategies.

What does that mean - do they pick different ones or not? I have a feeling you cut and pasted from CoordinationGame here.

The numbers for HawkDove and Pigs seem somewhat arbitrary. Maybe they could at least be scaled (optionally)? What do you think?
like a Hawk of a Dove. -> like a Hawk or a Dove.
The numbers don't work out right for Pigs without additional explanation. See here where it's explained a bit better why 3.5 and 1.5 means the subservient pig gets 1/3 of the food! I was stumped by that for a while.
Return a Matching pennies game -> Return a Matching Pennies game
Don't forget the web link for RPSLS like you did elsewhere
both players naming the smallest possible value -> both players naming the smallest possible value.
The following paragraph is too far indented.

+        Note that this command can be used to create travellers dilemma for a
+         different maximum value of the luggage. Below is an implementation
+        with a maximum value of 5::
+

Rock crushes scissors -> Rock crushes Scissors

kcrisman commented 9 years ago

Reviewer: Karl-Dieter Crisman

drvinceknight commented 9 years ago

comment:21

Thanks very much for this Karl. Things are a bit crazy right now (marking and a conference I'm helping organise coming up) but will get to it asap!

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 9d979d4 to 1bc47e8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`68d543b`	`Merge branch 'develop' into catalog`
`c6c0ff4`	`Fixing incorrect inequality in the doc for anti coord`
`7bb07bd`	`Parametrized Game of Chicken`
`6f7ce43`	`Tweaking the representation of named games.`
`a9f55b9`	`Various minor things`
`96b9c84`	`Removing text about equivalent strategies`
`a3dac3b`	`Have parametrized Hawk Dove.`
`6848245`	`Rewording the game of pigs.`
`a347fc6`	`Compartmentalising normal form game catalog.`
`1bc47e8`	`Making sure documentation builds.`

drvinceknight commented 9 years ago

comment:23

Replying to @kcrisman:

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

I was thinking more like http://www.gametheory.net/dictionary/games/GameofChicken.html

Cool, have changed this so that there is an extra inequality that makes the Game of Chicken a particular type of Anti Coordination game.

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.

Then better to plan for the future, eh?

Yup: have changed this so that the behaviour is now:

normal_form_games.Chicken()

So you simply type normal_form_games. and tab completion brings up all the names normal form games. I'm not sure if this is the best way: what do you think? I tried to get game_theory.normal_form_games to work but could not actually get that to work...

Minor, many very minor points because I have nothing else to complain about:

an often used v -> An often used v

Done.

There is a single Nash equilibria -> There is a single Nash equilibrium

There are several other instances of this, I believe, e.g.
+    A coordination game is a particular type of game where the pure Nash
+    equilibria
so please be careful on the plural/singular here.

Thanks: I think I have picked these all up.

if the defining inequality is not -> if the defining inequalities are not

Done.

I think most of the things like
Return a Battle of the Sexes game
should be
Return a Battle of the Sexes game.

Done all these.

Chicken: Anti coordination game: Normal Form Game seems not to jive with the usual Battle of the sexes - Coordination game: Normal Form Game format. I don't know that I like either but I understand the dilemma here.

I have changed things so that the colon : is only used prior to the utilities but otherwise the - is used to seperate different names. So for example:

Battle of the sexes - Coordination game - Normal Form Game with the following utilities: {(0, 1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}

I think I prefer this but let me know.

Game theory question.
+    An anti coordination game is a particular type of game where the pure Nash
+    equilibria is for the players to pick different strategies (or equivalent)
+    strategies.
What does that mean - do they pick different ones or not? I have a feeling you cut and pasted from CoordinationGame here.

What I meant was that the strategies might not be called the same/different thing but that they would be equivalent to the same/different thing. I've removed this in both places in case that's more clear.

The numbers for HawkDove and Pigs seem somewhat arbitrary. Maybe they could at least be scaled (optionally)? What do you think?

I have completely parametrized HawkDove, let me know what you think :)

As far as scaling Pigs, certainly could do this but the equilibrium would be the same so I'm not sure it's really worth doing. If you would really like it to be done though just let me know (it just seems a bit artificial to me as the equilibria is in pure strategies).

like a Hawk of a Dove. -> like a Hawk or a Dove.

Done.

The numbers don't work out right for Pigs without additional explanation. See here where it's explained a bit better why 3.5 and 1.5 means the subservient pig gets 1/3 of the food! I was stumped by that for a while.

I have added more explanation and changed the game to go with that blog post. As the blog post refers to the same book I have not referenced it but am not sure if that's appropriate.

Return a Matching pennies game -> Return a Matching Pennies game

Done.

Don't forget the web link for RPSLS like you did elsewhere

Done.

both players naming the smallest possible value -> both players naming the smallest possible value.

Done.

The following paragraph is too far indented.

+        Note that this command can be used to create travellers dilemma for a
+         different maximum value of the luggage. Below is an implementation
+        with a maximum value of 5::
+

Thanks: fixed.

Rock crushes scissors -> Rock crushes Scissors

Done.

I have also made sure that the docs build and look ok on my end but let me know if I've managed to not do that correctly. Thanks again for your time and help :)

kcrisman commented 9 years ago

comment:25

Awesome. I won't have time this week (a day and a half gone to jury duty) but next week should be fine. Why not ask on sage-devel about game_theory.normal_form_games or the like? I think Sage should have a reasonably unified policy on the growing set of lists of examples anyway.

tscrim commented 9 years ago

comment:26

FYI, we've done subcatalogs for crystals; take a look at the catalog files in combinat/crystals. (Edit: not categories...catalogs :P)

drvinceknight commented 9 years ago

comment:27

Replying to @tscrim:

FYI, we've done subcatalogs for crystals; take a look at the catalog files in combinat/crystals. (Edit: not categories...catalogs :P)

That's super helpful Travis, will get that going and push in time for when you have a moment Karl :)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`6b126cf`	`Have catalog working as wanted`
`41babbc`	`Tests pass - need to work on docs.`
`a3ee259`	`Tidying the documentation`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 1bc47e8 to a3ee259

drvinceknight commented 9 years ago

comment:29

Have this working so that the catalog behaves as:

sage: game_theory.normal_form_games.
game_theory.normal_form_games.AntiCoordinationGame  game_theory.normal_form_games.MatchingPennies       game_theory.normal_form_games.RPSLS
game_theory.normal_form_games.BattleOfTheSexes      game_theory.normal_form_games.NormalFormGame        game_theory.normal_form_games.StagHunt
game_theory.normal_form_games.Chicken               game_theory.normal_form_games.Pigs                  game_theory.normal_form_games.TravellersDilemma
game_theory.normal_form_games.CoordinationGame      game_theory.normal_form_games.PrisonersDilemma      game_theory.normal_form_games.matrix
game_theory.normal_form_games.HawkDove              game_theory.normal_form_games.RPS                   game_theory.normal_form_games.sign

I've tidied up the documentation and also moved some files around in the hope of future proofing for further games types. :)

drvinceknight commented 9 years ago

comment:30

Also, in 41babbc an abstract from an email I was writing somehow managed to sneak in to the docstrings, it gets taken straight back out in a3ee259. My clumsy mistake, just mentioning it in case you go through the commits and are confused :)

kcrisman commented 9 years ago

comment:31

Not sure why the branch name is red...

tscrim commented 9 years ago

comment:32

My guess is a merge conflict from #18127 (as beta5 was recently released).

drvinceknight commented 9 years ago

comment:33

Yup, just fixing it now :)

drvinceknight commented 9 years ago

comment:34

Just building to make sure but it's taking a little while...

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a3ee259 to 6cef68d

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

6cef68d Merge branch 'develop' into catalog

drvinceknight commented 9 years ago

comment:36

Something's not right.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

5de5031 Merge branch 'develop' into catalog

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 6cef68d to 5de5031

drvinceknight commented 9 years ago

comment:38

Ok I messed up some git-foo along the way. Not sure if this is a mess or not, let me know if it is and I'll do my best to figure it out. The merge conflict is fixed and otherwise everything else is as it was.

tscrim commented 9 years ago

comment:39

It looks like you merged in beta3 first and then beta4. However something seems wrong in your build/pkgs folder. Let's see if I remember my git-foo...try running:

git checkout build/pkgs develop

and see if that restores those files. You can run

git diff --name-status develop

to see the files which have changed from your version of develop.

drvinceknight commented 9 years ago

comment:40

I think I messed up with resolving the merge conflict. Have started again but this time rebasing on to develop. Just rebuilding and testing etc :)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`b006902`	`Tweaking the representation of named games.`
`db4d95d`	`Various minor things`
`b53a096`	`Removing text about equivalent strategies`
`4982c45`	`Have parametrized Hawk Dove.`
`88de208`	`Rewording the game of pigs.`
`15fbba2`	`Compartmentalising normal form game catalog.`
`d2d9794`	`Making sure documentation builds.`
`8b109ba`	`Have catalog working as wanted`
`e3b175c`	`Tests pass - need to work on docs.`
`e57758e`	`Tidying the documentation`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 5de5031 to e57758e

drvinceknight commented 9 years ago

comment:42

I rebased all the work for this ticket on to of the latest version of the develop branch. The earlier work has been squashed in to a single commit whilst the main work addressing Karl's comments has been left as a series of commits to try and be helpful and easier to review. Let me know if any of this has not made things simple :) Thanks again for your time.

tscrim commented 9 years ago

comment:43

Looks good from a git standpoint. I'd also change :math:`x + y` to simply `x + y` and .. math:: to .. MATH::.

You'll also note that because these are imported in the catalog:

from sage.game_theory.normal_form_game import NormalFormGame
from sage.matrix.constructor import matrix
from sage.functions.generalized import sign

I believe they appear under tab completion. To fix this, I'd add a

del matrix
del sign

at the end of the file.

I believe you're also importing at startup a good part of the game theory with the catalog. I'd change the import in all.py to

lazy_import('sage.game_theory', 'catalog', 'game_theory')

sagemath / sage

Make list of built-in normal form games #17392