#16954: Game Theory: Build class for normal form games as well as ability to
obtain
Nash equilibria
-------------------------------------+-------------------------------------
Reporter: vinceknight | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: game theory | Resolution:
Keywords: Game Theory, | Merged in:
Normal Form Games | Reviewers: Karl-Dieter Crisman
Authors: Vince Knight, | Work issues:
James Campbell | Commit:
Report Upstream: N/A | 9e14ff21121029f311b53d608b6a6d826ff2af88
Branch: | Stopgaps:
u/vinceknight/finishedresponsetobigreview|
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vinceknight):
Before I start: thank you very much for such a detailed and rigorous
review! Great to know that the code is being looked at so closely. It's
taken me quite a while to go through it all but I think I've addressed
everything. Will respond part by part, in particular highlighting points
where I haven't just gone with your suggestion (obviously delighted to
discuss).
Replying to [comment:11 kcrisman]:
> > Been away from the laptop for a couple of months and was just
wondering what's left to do?
> Needs review, largely!
>
> Unfortunately, something isn't quite right on the git view online - see
http://git.sagemath.org/sage.git/tree/src/sage?id=6800b2c2b7037ae7bf25c297fd139ee48a5ece10
and the "bad object" line for `game_theory`. See
[http://git.sagemath.org/sage.git/tree/src/sage/game_theory/normal_form_game.py?h=ffa6d525b5e6681687642d9efc80037884823e30
here] and
[http://git.sagemath.org/sage.git/tree/src/sage/game_theory/parser.py?h=ffa6d525b5e6681687642d9efc80037884823e30&id=9febc45b5fee55e695f4942688baf51396cb5693
here] for the actual files in question.
>
> Anyway, a couple of minor things before I have time to check it out
properly.
> * ` There are however a variety of such algorithms available in
gambit,` seems orphaned.
> * Overzealous deleting `In the following we create the game and solve
i::` and `game. In fact degenerate games can cause problems for most
algorithm::` and `Here is a slightly larger gam::`
> * Caps for exs?
> {{{
> def payoff_matrices(self):
> r"""
> Returns 2 matrices representing the payoffs for each player.
>
> Examples ::
> }}}
Have fixed this.
>
> I'll be looking at this in more detail over the next few days as I have
time.
Replying to [comment:12 kcrisman]:
> Parser comments.
> * Minor - this could be made slightly more professional-sounding.
Also, double ticks for code markup; maybe even {{{``'lrs'``}}} if it is a
string, I'm not sure about this.
> {{{
> At present the only parser included is the for `lrs` algorithm
however
> this will be expanded to `gambit` soon.
> }}}
Have changed wording and also ticks but I'm not sure if it's quite what
you meant.
> * Since `lrs` is an optional package, will any of the doctests in the
parser file need to be marked optional? I assume not, just checking.
(Maybe the one using the subprocess stuff?)
This was indeed an oversight on our part: have added the optional tests.
> * Will those temp files really disappear or do you need to remove them?
I just don't remember - we use the temp file name thing so it doesn't
overwrite, but I can't remember if we need to remove them afterwards,
though I believe we do.
We have checked: they disappear.
> * Just out of curiosity, what does the fourth element of the stuff mean
that you parse?
> {{{
> '2 0 1 2 \n', '1 1/2 1/2 -2 \n'
> }}}
> the first number is the player, the next two the strategy (does lrs
only do two player, two-strategy games?) but what is the 2 and -2 here?
They correspond to the utility of the other player.
> * Could the creation of the `p1_strategies` be sped up slightly with
something like
> {{{
> p2_strategies.append(sage_eval(k) for k in i.split() if k.index() !=1 or
-1)
> }}}
> (this syntax is not right, I'm sure) ? Again, probably quite minor
to even think about given the type of use case.
I thought about this for a while and felt that in fact this looked less
readable. I don't think speed is terribly troublesome here. If you feel
strongly about this I'm happy to change though.
Replying to [comment:13 kcrisman]:
> Hmm, you'll want to amend `src/doc/en/reference/game_theory/index.rst`,
I bet.
Done: thanks.
Replying to [comment:14 kcrisman]:
> Two issues from above I return to.
> > > algorithm='enumeration' or not? You have in one spot ``"support
enumeration"`` which sounds horrible.
> > Not too sure I understand. 'support enumeration' is the actual name of
the algorithm which is what we need to pass as an argument (so have
shorted to enumeration) like we could also pass lrs. Would
support_enumeration be any better?
> What I mean is that when you put something in quotes and double
backticks, it looks like code. You can call it support enumeration and
still use `'enumeration'` as the algorithm keyword, but then you need to
make it quite clear what the difference is. I agree that shorter is
better in this case. No double backticks (as later in the doc), not a
problem.
Cool.
> > > By the way, both here and in #16331, I'm wondering whether a lot of
the (great) documentation you have for the main games maybe belongs (also)
in the initial docstring. The reason is that this is what is at the top of
the html/pdf documentation. But maybe these are such short files that the
main game appears at the top anyway. Though for this ticket the starting
documentation is SO long I think that really a lot of it should be at the
top - and hopefully there will be some easy way for someone at the command
line or notebook to then ask for that top bit.
> > Not too sure I understand (apologies). Are you saying to move the docs
we wrote in the library (before any code kicks in) in to the docs for
NormalFormGame?
> What I mean is that you have some documentation in the class definition
for `NormalFormGame` that probably can just go in the initial docstring at
the very top of the file. After all, it's quite general stuff about what
games and Nash equilibria are. This also applies to #16331, as I say, but
perhaps somewhat less so since it will not be expanded in the near future.
This is one of the last commits: I've moved most of the docs from the
NormalFormGame to the front matter. I'm not sure this is perfect but I
didn't want to repeat the docs in two different places to avoid confusion:
let me know if this isn't quite right.
>
> Items new to this take on the actual file.
> * `We can use Sage to find them and more importantly see if there is a`
- ''please'' have someone who knows commas go through this entire file. I
don't need every Oxford comma, but the sentences are often quite run-on.
I have asked a couple of people and also paid close attention myself. I
hope it's ok.
> * In the following section, you may need to clarify that you mean this
as vector/matrix multiplication. Even though you then do that in Sage,
someone who is just reading it and not necessarily looking at the code may
get confused - especially those who come from a background where column
vectors and row vectors are truly separate things, never to be mixed (as
opposed to in Sage!).
> {{{
> We can use Sage to compute the expected utility for any mixed
strategy
> pair `(\sigma_1, \sigma_2)`. The payoff to player 1 is given by:
> }}}
Have added this in, in various places.
> * In {{{playing strategy `i` is given by (`(Ay)_i`)}}} perhaps once
again a gentle reminder that you mean matrix times vector could be useful.
Do you think I'm being too gentle on the reader?
Not at all: better to be too gentle. Have added this in.
> * `Rock-Paper-Scissors-Lizard-Spock` - I'm scared to ask... fun, but
perhaps want to put a reference in for this non-standard example.
It's actually an episode from a TV show: have added in a url link
(students usually find this amusing).
> * I am scared of the syntax `sage: f.add_player(2)`. Am I adding the
player named `2`? Am I adding two new players? And why do I do this
''twice'' in a row? Using "gambit syntax" is nice but would need to be
fully explained. By the way, this is the kind of thing that really does
do better in the "top matter".
This is adding a player with 2 strategies. Doing it twice in a row is
because we're adding two players. Tried to think of a way to make it more
verbose but couldn't come to a better conclusion than this but very open
to any suggestions.
> * Can we add the ''name'' of a player, or is that a horrible idea?
Just because it might eventually get confusing with lots of players.
We actually came to the conclusion that this wasn't a great idea. Not sure
when it would be used and differs from gambit syntax but happy to discuss
if you feel strongly about it.
> * A programmed example of a way to use the
> {{{
> sage: threegame = NormalFormGame()
> sage: threegame.add_player(2)
> sage: threegame.add_player(2)
> sage: threegame.add_player(2)
> sage: threegame[0, 0, 0][0] = 3
> sage: threegame[0, 0, 0][1] = 1
> sage: threegame[0, 0, 0][2] = 4
> ...
> }}}
> syntax would be nice, just like we did in the other game theory
tickets. Who is going to type all that in (accurately) by hand, anyway?
So demonstrating it's possible to do it right with a loop or something is
useful.
Have added an example with a function that generates the utilities.
> * The airline example is cool (actually, really interesting) but really
needs to be in top matter or at least somehow separated. Also, if there
are two paragraphs, separate them with another newline.
> * In this same example, you have it that the best strategy is to say
the stuff is worth two, but you have
> {{{
> [[(1, 0, 0, 0, 0, 0, 0, 0, 0), (1, 0, 0, 0, 0, 0, 0, 0, 0)]]
> }}}
> Doubtless this corresponds to 100% choosing the first strategy, but
that is not clear since the way the problem is stated makes it sound like
there are 99 strategies or something.
Have added another sentence highlighting that this is a 'smaller' example.
> * "In fact degenerate games can cause problems for most algorithm" -
but what is the problem caused in the following example? It gives a
solution that adds to 100% for each player...
Have added more of an explanation.
Replying to [comment:15 kcrisman]:
> Before continuing, I just have to say that this is really exceptionally
well-organized. Good work.
>
> ----
>
> Moving on to the methods.
> * But what will happen to the deleted game? Will this raise an error
if you try to do anything with it? (Maybe I'll find out later.)
> {{{
> sage: prisoners_dilemma
> {(1, 0): [0, 5], (0, 0): [2, 2], (1, 1): [4, 4]}
> }}}
You're not quite deleting a game but a utility. It will cause an error of
the game being incomplete if you tried to use it. This is just to make it
act like a dictionary.
> * Can you {{{__setitem__}}} for an already-set item in the game? If
not (for whatever reason), then this should be doctested. If yes, I guess
this should be justified and doctested too.
Yes you can: have added a doctest.
> * Can you move that method to with the other dictionary-emulating
methods? Not super-important but helpful to those reading code.
{{{__iter__}}} and {{{__len__}}} strictly speaking are not about dict
emulation but just emulation of iterables.
`__iter__` kind of is relevant to the dictionaries as we want the
iteration to behave like a dictionary (by iterating over keys). Have moved
`__setitem` though as you suggest and `__len__` is now just at the end of
those methods.
> * Usually {{{__init__}}} is best at the very first. Am I missing
something that the emulation ones are coming first?
This was an oversight: `__init__` is now first.
> * I would have expected this to list the bimatrix entries. Instead I
get a very boring list of the possible pure strategies.
> {{{
> sage: for key in prisoners_dilemma:
> ....: print key
> }}}
This goes back to wanting a game to behave like a dictionary (which in
turn goes back to wanting gambit like syntax): have changed it though so
it prints things out a bit nicer.
> Will length basically always be n times m in terms of the number of
strategies? In which case do you really need all that extra stuff about
utilities?
This is future proofed for games with more than 2 players (in which case n
times m won't necessarily make sense).
> * `Generator function must be a list or nothing` is not doctested.
Have added doctest.
> * `generator != None` or `generator is not None`? Just wondering which
you intend here.
Have fixed (gone for `is not None`).
> * ` LaTeX method shows nothing interesting for games with more
players::` - then you should probably use the `...` like so:
> {{{
> \text{\texttt{<bound{ }method{ }NormalFormGame...[False,{ }False,{
}False]{\char`\}}>}}
> }}}
> or the like.
Have gone with your suggestion.
> * I still do not like ` return str(self.utilities)` for the string rep.
It should at least say, at the very least, that it is in fact a normal
form game!!! Maybe "Normal Form Game with following utilities" or
whatever.
Have added "Normal Form Game".
> * One of the errors in the payoff matrices method is tested, the other
isn't.
Have added test.
> * `m1 = matrix(QQ,` - oh, oh. But didn't you say that Gambit does
floats? And what if people input floats? I'm just thinking of nasty
things like people inputting `1/sqrt(2)` as a probability, or ones where
when they are coerced to rationals don't add up to 100%
Our plan is to leave this as is and let the gambit ticket take care of it.
When we have the gambit integration we will simply return an error when
someone tries to use the Gambit algorithms with a matrix in QQ. This will
imply that users will need to make sure they have the correct input. We
had implemented a preprocessor but felt that this hid what was going on so
feel that it's best to just return an error (and document).
> * I'd like to see an example with
> {{{
> sage: g._generate_utilities(True)
> }}}
> where it would actually destroy a utility. Myuh-ha-ha!
Done :)
> * The line
> {{{
> Checks if ``utilities`` has been completed
> }}}
> doesn't seem to correspond to any errors, though.
This corresponds to all the errors throughout when a game is created
without a full utility profile.
For example we have lines like (in `obtain_Nash`):
if not self._is_complete():
raise ValueError("utilities have not been populated")
> * These mixed strategies
> {{{
> [[(1, 0, 0, 0), (127/1212, 115/1212, 485/606)], [(0, 1, 0, 0), (0, 1/26,
25/26)]]
> }}}
> seem strange, but I assume correct - can you confirm they are
''exact'' answers?
They were in fact incorrect but have now fixed: answers are definitely
correct now.
> * The line
> {{{
> This particular game has 3 Nash equilibria::
> }}}
> isn't backed up by
> {{{
> sage: g.obtain_Nash(maximization=False)
> [[(1, 0, 0), (0, 1)]]
> }}}
> unless I'm misunderstanding the syntax. Where are the other two
equilibria promised to the reader? This seems to happen in a few other
examples. (Actually, I think that some copy-paste is at fault here, esp.
since `maximization=False` but that isn't mentioned.)
This was a copy and past error: I think I caught them all.
> * The or a?
> {{{
> A function to return the Nash equilibrium for a game.
> }}}
Fixed.
> * Should it be `obtain_Nash` or `obtain_nash`?
Not entirely sure: I felt a bit better going with `Nash`... I would like
to keep Nash if that's not a problem.
> * When you use `tmp_filename()` in the things themselves (not doctests)
are there any other strange side-effects?
None that we have noticed (have checked as thoroughly as possible).
> * I feel like you tired (understandable!) in the `_solve_enumeration`
doctests. Most of them should be tests and not examples in any case, I
suppose. Here is the funniest of them, I actually laughed at this one.
> {{{
> TESTS:
>
> Due to the nature of the linear equations solved in this
algorithm
> some negative vectors can be returned. Here is a test that
ensures
> this doesn't happen::
>
> sage: a = matrix([[-13, 59],
> ....: [27, 86]])
> sage: b = matrix([[14, 6],
> ....: [58, -14]])
> sage: c = NormalFormGame([a, b])
> }}}
> It sure doesn't happen! Since we never try to find said vectors :-)
Have added that missing line (which actually tries to find them) and an
explanation also.
> * Adding strategies should then have an example finishing it.
> {{{
> If we do this and try and obtain the Nash equilibrium or view the
payoff
> matrices(without specifying the utilities), an error is returned::
> }}}
> but it's never finished up.
Have added that in.
> * What happens with a completely trivial matrix i.e. all payoffs are
zero? Then all mixed strategies are optimal, I guess...
This is in fact an example of a degenerate game: have added that to the
docs.
>
> ----
>
> Remaining:
> * Making sure the `_solve_enumeration` actually is correct. I'm sure
it is, I just haven't had time to look at it.
Have added docs that hopefully clarify (will go in to details below).
> * I will have to just trust you on the `_Hrepresentation` method.
Very happy to document/explain further if that's helpful but very
confident this is correct (it has been heavily tested).
>
> Almost there!
>
> Finally, as a general rule of thumb, if you have any pretty useful tests
or examples which are in underscore methods (which won't show up in the
reference manual) maybe repeat them elsewhere. I don't know if you do
that, just mentioning it.
Wrote a new one and copied it to the front matter.
Replying to [comment:16 kcrisman]:
> Looking at [http://www.masfoundations.org/mas.pdf the reference for
support enumeration] (page 103), I find a few final (hopefully!)
questions. Most are probably due to my unfamiliarity with the details of
this algorithm, though I think it is quite interesting as a strategy.
This confusion is partly our fault: the algorithm we used is a combination
of something from 'mas' (the pruning of conditionally dominated
strategies).
Have added docs and also will clarify further below.
> * The algorithm for some reason sorts the support size profiles, but I
don't see that in the code.
This sorts it because the algorithm from 'mas' is interested in finding an
equilibrium (not necessarily all of them).
The way the potential pairs are created are in fact sorted but in essence
as we need to test them all: it's not terribly important.
> * The algorithm definitely implies that there could be different
numbers of pure strategies for each player, and your examples and
`potential_supports` seem to suggest this, but then
`potential_support_pairs` and how that is used seems to implicitly ... I
don't know, it just doesn't smell right. E.g.
> {{{
> if len(pair[0]) == len(pair[1])
> }}}
> should really be comparing two different supports for player 1,
according to the pseudocode in the paper, but here you are comparing a
support from player 1 with one from player 2. Shouldn't you be comparing
supports of the same size as the player 1 supports with respect to $A'_2$?
However, I may be misunderstanding the algorithm.
This is because the algorithm doesn't take in to account a result from
'Algorithmic Game Theory' (referenced in docs) which proves that for non-
degenerate games supports have to be the same size (this is almost 'by
definition').
> * Also, do you have to do all the construction of tuples and such or is
there a more efficient way to go from the power set to the evaluation of
the supports? Maybe there isn't.
We could not think of a better way.
> * Minor doc note: ` or does not have a dominated row:` should
have one more colon.
Have added.
> * Just brainstorming - maybe in `_row_cond_dominance` one doesn't have
to cycle through the product of rows and rows, but could check rows `i`
and `j` for `i>j` and then immediately check for `j>i`... because as soon
as one is dominated, you return `False`, and right now it's a weary `n^2`
but maybe you could make it `n(n+1)/2` if you only check each pair once,
but twice within the pair (if that makes sense).
Really helpful suggestion: thanks! Have fixed this!
> * Minor but made the code harder to understand:
> {{{
> for p2_strategy in range(self.players[1].num_strategies):
> for i in range(self.players[0].num_strategies):
> }}}
> even though they fill exactly the same role. Same with
> {{{
> for p2_strategy in range(len(p2_support)):
> for j in range(len(p1_support)):
> }}}
Have tried to clarify as suggested: let me know if it still isn't quite
right.
> * Should `_solve_indifference` really return `False`, or maybe just
`[]`, when it isn't possible (since `if foo:` doesn't happen as long as
`foo` is "empty" in its type)?
Returning `[]` wouldn't be quite right from the mathematical point of view
(empty set as opposed to a set that doesn't exist): False seemed to make
more sense to us. Obviously wouldn't make a different from the point of
view of the actual algorithm so let me know if you feel strongly about it.
> * Would it help to formally do this as an LP with Sage LPs or is
`solve_right` sufficient?
The way this is being run (using a basic version of indifference) does not
require an LP as it's all being reduced to a simple linear system.
> * I just don't see how
> {{{
> linearsystem2[j, p2_strategy] = M1[p1_support[j]][p2_strategy] -
M1[p1_support[j-1]][p2_strategy]
> }}}
> corresponds to the TGS, though somehow it must. (4.30) is
essentially
> {{{
> linearsystem2[-1, p2_strategy] = 1
> }}}
> and `_is_NE` corresponds more or less to (4.28) and (4.29). I
''think''
> {{{
> p1_payoffs = [sum(v * row[i] for i, v in enumerate(b)) for row in
M1.rows()]
> if p1_payoffs.index(max(p1_payoffs)) not in p1_support:
> }}}
> also helps correspond to (4.26) and/or (4.27) but I think that
somehow you combined all these into solving the linear system and then
checking, which is probably mathematically equivalent but I'm just having
trouble keeping track of all the variables.
I have added a lot more explanation as to how this works to the docs.
I've also added that new explanation to the docs for the unhidden
`obtain_Nash` method although I'm not sure it's useful there (potentially
more confusing for the general user who won't care?). Let me know if that
helps.
> * Along those lines, should it be `all([a[i] > 0 for i in p1_support])`
or `all([a[i] >= 0 for i in p1_support])`? Maybe if you already checked
smaller supports then this would be degenerate... or maybe this is why
they do the smaller supports (sort of) first in the algorithm.
We need the strict inequality to verify that the support condition isn't
being violated.
---
Thanks so much for the detailed review!
(Will try and get to 16331 soon before the end of the week.)
--
Ticket URL: <http://trac.sagemath.org/ticket/16954#comment:20>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
