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

drvinceknight commented 10 years ago

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

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 10 years ago

comment:1

(being curious)

kcrisman commented 10 years ago

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

Changed author from Vince Knight to none

drvinceknight commented 10 years ago

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

comment:4

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

drvinceknight commented 10 years ago

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

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 #16332, #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 commented 10 years ago

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 #16332, #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 commented 10 years ago

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

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

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

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

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?

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

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

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

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Include class for 2 by 2 normal form games.
+Include class for 2 player normal form games.

 A method to solve these games will be built (this is the main difficulty). 3 approaches will be considered:

drvinceknight commented 10 years ago

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

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

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

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

Dependencies: #16466,

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

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!

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

Branch: u/jcampbell/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria

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

Commit: 40b8b16

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

Last 10 new commits:

`1df4bfb`	`creates conditional dominance`
`633bee9`	`change something back`
`18c294b`	`Pushing failed test`
`46e8e7a`	`Simplified tests for valid NE in enum`
`6ff97fa`	`adds quick docstring to gambit game`
`b19f406`	`More docs at beginning`
`9b284d7`	`Added some docs`
`b5f47f5`	`Added links to gambit website everywhere`
`066a15a`	`Merge branch '16333' of https://github.com/theref/sage-game-theory into 16333`
`40b8b16`	`Merge branch '16333' into t/16333/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria`

drvinceknight commented 10 years ago

comment:22

Hi!

James has just pushed a pretty substantial piece of work. This creates a NormalFormGame class that brings with it 3 algorithms to compute equilibria:

LCP (a gambit algorithm)
lrs
A bespoke support enumeration algorithm (this is the slowest of algorithms but allows users to find equilibria if the above two packages aren't installed).

There is also a lot of documentation that has been written (and it builds! :)). Finally, if it's of interest we're actively continuously testing this by generating random games and trying all 3 algorithms. You can find a bunch of plots (and the raw data) here: https://github.com/theref/sage-game-theory.

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

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

`c7867f6`	`fixes bug if gambit not installed`
`2fb6131`	`Merge branch '16333' into t/16333/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria`

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

Changed commit from 40b8b16 to 2fb6131

drvinceknight commented 10 years ago

Changed branch from u/jcampbell/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria to u/vinceknight/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria

kcrisman commented 10 years ago

Changed commit from 2fb6131 to bce8e4b

kcrisman commented 10 years ago

comment:27

Hi! I don't see anything at https://github.com/theref/sage-game-theory except the readme, which I am pretty sure is not what it was earlier in the summer.

Also, have you tested this with and without gambit installed? (I'm having difficult finding the code right now because of some broken links on Trac as well, so my apologies.)

New commits:

`f4f0c3b`	`Got rid of documentation about scaling in LCP`
`b976815`	`Start getting rid of scaler`
`3bcfd98`	`Have removed scaler, docs not passing`
`fdc5b1e`	`Tests now pass`
`5c265aa`	`Have error raising when games are not in correct format for LCP`
`fe32168`	`Have an example of scaling`
`8a31fb1`	`Fixed missing web links`
`716ff55`	`Added optional tag for some tests`
`bce8e4b`	`Removed some white space`

kcrisman commented 10 years ago

comment:28

Very broad comments:

The following file seems unhelpful - src/sage/game_theory/installing_gambit.md

    mv gambit-14.0.2.tar.gz SAGE_ROOT/upstream
    cd SAGE_ROOT
    ./sage -i gambit

would that even work without #16466?

old.py is always a frightening name for a file in a professional package ;-) Maybe there is a more updated version of this stuff coming? I don't see anything from August, for instance.

kcrisman commented 10 years ago

Changed dependencies from #16466, to #16466

drvinceknight commented 10 years ago

comment:29

I'm having to do this on my phone as my laptop has just died which is a bit of a nightmare as I'm at my mother's all weekend so won't be able to work on this like I was hoping!

Re github, if you click on the branches you can see that we've set the landing page to be the read me branch with nothing in it. If you look at branch 16333 you'll see the relevant code for this ticket. If you look through the issues on there also you'll see that James and I tried to document this whole process so any decisions that were not obvious are on there :)

Re with and without gambit: this was tricky to test as 'uninstalling' an optional Sage package proved to be difficult. We did however test on various machines with and without Gambit installed and I'm pretty sure that it works just fine. If it doesn't it's just that we ran out of Gambit-less machines and made a tweak that might be missing a try except statement. So it would be an easy fix but we certainly tried our best (and I'm almost 100% sure we succeeded) to make sure that Gambit is not a requirement but an enhancement.

Replying to @kcrisman:

Very broad comments:

The following file seems unhelpful - src/sage/game_theory/installing_gambit.md
    mv gambit-14.0.2.tar.gz SAGE_ROOT/upstream
    cd SAGE_ROOT
    ./sage -i gambit
would that even work without #16466?

That is in fact there to help if anyone wanted to get Gambit working prior to 16466 being fixed (which it needs to be) and approved. It would/should work if the instructions are followed (I tested this on my own machine). We thought that this is mainly useful for devs/reviewers.

old.py is always a frightening name for a file in a professional package ;-) Maybe there is a more updated version of this stuff coming? I don't see anything from August, for instance.

Yeah old.py should be deleted (I'll call that a lazy relic). A part from that issue this is pretty much just waiting for a review (I've been too busy with other things this month to bug people :)).

Thanks again, and really sorry if I'm unable to work on things immediately. Currently having my heart broken by a flashing hard disk error...

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

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

2176905 Removing old.py

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

Changed commit from bce8e4b to 2176905

drvinceknight commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,11 +1 @@
-Include class for 2 player normal form games.
-
-A method to solve these games will be built (this is the main difficulty). 3 approaches will be considered:
-
-1. Write implementation of lrs nash algorithm in cython;
-2. Liaise with lrs library
-3. Use Gambit (this approach will be investigated)
-
-A summer student at Cardiff University will be working on this during Summer 2014.
-
-Should be efficient to code in pure python/cython.
+Build on other tickets (#16954 and #16466) to allow for the use of Gambit as an option when calculating Nash Equilibria.

kcrisman commented 9 years ago

comment:32

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.

This is now #17392.

kcrisman commented 9 years ago

comment:33

Ping. No worries if this won't be coming soon, but just checking in.

drvinceknight commented 9 years ago

comment:34

I'm basically ready to start moving on this: waiting for #16466 to be merged in to develop. Completely realise that we could get going without waiting on that but am just not completely confident in my ability to not make a mess. Once it's in develop I'll branch from that and it'll be ready to rock n roll! :) (A lot of the code is ready, it'll just take some time making sure docs and tests are up to standard).

kcrisman commented 9 years ago

comment:35

Okay, #16466 is merged.

drvinceknight commented 9 years ago

comment:36

Replying to @kcrisman:

Okay, #16466 is merged.

Yup: way ahead of you :) Really is just waiting on me finding a spare day over the break to tidy everything up and double check a couple of things (the parser is re-written, tests are re-written etc...). If it's not pushed by the end of the week (am working on a revisions to a paper) it certainly will be by the end of the christmas break.

drvinceknight commented 9 years ago

comment:37

Have just pushed this. Note that I've left the gambit_docs.py as a separate set of docs.

Last 10 new commits:

`720c44c`	`removes imports from init`
`f62c915`	`removes unnecessary import from solve_LCP`
`e28ba7d`	`added a test for _gambit_game`
`4f760d8`	`at_startup = True for is_package_installed`
`a48759f`	`Merge branch 'develop' of https://github.com/sagemath/sage into 16333`
`fa5f6e7`	`Have removed extra parsing that changed format type in certain cases for gambit output`
`6bfc5be`	`Using try/except instead of checking if package is installed on startup`
`46ae1a7`	`Tweaking some tests`
`93cba7f`	`Removing an error in docs`
`9e1c104`	`Have added gambit as a standalone package documentation`

drvinceknight commented 9 years ago

Changed branch from u/vinceknight/game_theory__build_class_for_normal_form_games_as_well_as_ability_to_obtain_nash_equilibria to u/vinceknight/gambit_integration

drvinceknight commented 9 years ago

Changed commit from 2176905 to 9e1c104

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:38

Hello Vince ! It would be really cool if you made your branch a bit more 'reviewer-friendly'. Right now it seems to follow the development history, but you want this to be re-read by somebody and it would be nice to not have a commit that fixes a bug introduced in a previous commit.

With git, you can very easily merge commits together, as part of the rebase command. Try something like that:

Checkout your branch, and type 'git checkout -b rebased_version'. This, to make sure that we do not touch your old branch so nothing can go wrong.
'git rebase -i develop'. This will 'replay' all your commits on top of the latest develop version. It will open a text editor, and you will see how easy it is to merge two commits, or reorder them.

At the end of this procedure, the branch rebased_version will be on top of the latest develop version, and its history should be cleaner. You can call 'git rebase -i develop' several times if needed.

Hope that will help.

Nathann

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

comment:39

p.s.: do you use 'tig' ? It is a text-mode viewer for tig branches. It helps a LOT. If you don't use it already, download it and type 'tig' in Sage's source directory.

drvinceknight commented 9 years ago

comment:40

Replying to @nathanncohen:

Hello Vince ! It would be really cool if you made your branch a bit more 'reviewer-friendly'. Right now it seems to follow the development history, but you want this to be re-read by somebody and it would be nice to not have a commit that fixes a bug introduced in a previous commit.

Yeah, sorry: this was the subject of a long discussion on another thread... Will fix it now (or at least try to: rebase is a thing I can't pretend to understand). :)

With git, you can very easily merge commits together, as part of the rebase command. Try something like that:

Checkout your branch, and type 'git checkout -b rebased_version'. This, to make sure that we do not touch your old branch so nothing can go wrong.

'git rebase -i develop'. This will 'replay' all your commits on top of the latest develop version. It will open a text editor, and you will see how easy it is to merge two commits, or reorder them.

At the end of this procedure, the branch rebased_version will be on top of the latest develop version, and its history should be cleaner. You can call 'git rebase -i develop' several times if needed.

Hope that will help.

Yeah that looks really helpful, thanks!

Nathann

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

Changed commit from 9e1c104 to 3d22981

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

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

`ef2d0c2`	`Changing name of gambit file to avoid import error`
`4dbc0eb`	`Have added gambit as a standalone package for documentation`
`2497775`	`Have parser documented and tested for the gambit LCP output`
`d598036`	`Have added lots of tests that fail`
`3d22981`	`Have integrated gambit in Sage - all tests pass`

drvinceknight commented 9 years ago

comment:43

I KNOW KUNG-FU!!! :)

(Or I've made a complete mess)

Thanks for that initial explanation of rebase @nathanncohen. So ridiculously powerful! :) I am 75% confident that I've used it correctly (which is way above the 5% I've gotten to the previous 3 times I've braved the rebase command).

drvinceknight commented 9 years ago

comment:44

No: it looks like I've managed to make a mess (the messages don't match what they were supposed to do). I thought I had checked, apologies - will fix and get back to you all :)

sagemath / sage

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