#16954: Game Theory: Build class for normal form games as well as ability to
obtain
Nash equilibria
-------------------------------------+-------------------------------------
Reporter: vinceknight | Owner:
Type: enhancement | Status: needs_work
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 | 8775f12e2644129b2a790ad91f37b853a273d2b6
Branch: | Stopgaps:
u/vinceknight/mainly_fixes_to_docs |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by vinceknight):
Replying to [comment:23 kcrisman]:
Ok so I actually think you've found a bug (in your testing section) so I'm
spending some time on that over the next couple of days.
In the meantime I addressed the various other issues so thought I might as
well push those now.
> I don't think I'll get to everything in one comment, but assume that if
I don't mention it it's either okay or I'm still getting to it.
>
> ----
> > > 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.
>
> No. What you changed it to is
> {{{
> #!diff
> - At present the only parser included is for 'lrs' algorithm however
> - this is actively being expanded to 'gambit'.
> + At present the only parser included is for `lrs` algorithm however
> + this is actively being expanded to `gambit`.
> }}}
> but what we need is for {{{`lrs`}}} or the previous {{{'lrs'}}} to
become {{{``'lrs'``}}}. Notice the double backticks (typeset as code) and
the single quote because, well, it needs single quotes because it's a
string (such as in the example {{{sage:
matching_pennies.obtain_Nash(algorithm='lrs')}}}). That said, it probably
can be kept {{{'lrs'}}} in some contexts, I think it's just especially
important in places like
> {{{
> 1. ``lrs`` (requires lrs)
> 2. ``enumeration``
> }}}
> where not having the quotes could mean people will type in something
nasty and wrong.
Believe I have now addressed this.
>
> ----
>
> Here is a dumb comment - you have {{{between gambit and sage.}}} but
then it should be {{{Sage}}}. Trivial, I know, I apologize but I just
happened to see it.
Changed.
>
> > > * ` 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.
>
> Yikes! I see now I was assuming too much information. What I meant by
that is that the LaTeX method is fine, but that in ''doctesting'' it one
can use three periods in a row to substitute for arbitrary sequences. So
keep the original LaTeX method, but add ... in the middle of it so that
the doctest is actually legible and it's clear what it's testing for.
I understand now :) Have fixed.
Replying to [comment:24 kcrisman]:
> > > * 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.
>
> Usually our practice is to mark ''only'' the doctest that would actually
fail without the optional package. (After all, testing the other stuff is
worthwhile.) Am I correct that only the stuff depending on {{{process =
Popen(['nash', g1_name, g2_name], stdout=PIPE)}}} needs to be optional?
One or two others needed to stay optional but yes this has been addressed.
>
>
> ----
>
> > > > > 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.
> >
> You ''still'' have {{{``enumeration``}}} instead of
{{{``"enumeration"``}}} at one point, though you do have {{{``"lrs"``}}}
correctly there.
>
Have fixed this.
> ----
>
> {{{
> #!diff
> - playing strategy `i` is given by (`(Ay)_i`)::
> + playing strategy `i` is given by the matrix/vector multiplication:
> + (`(Ay)_i`)::
> }}}
> And even after you move it, it is confusing. Why a colon before the
colons? What is {{{i}}}? I know but the reader may not.
Have added more explenation.
>
> ----
>
> More trivialities:
> * Should {{{dictionary like interface}}} perhaps have a hyphen instead
of a space?
Done.
> * Similarly, {{{A game with 1 equilibria}}} - I think the singular is
{{{equilibrium}}}.
Done.
> * {{{initiating}}} probably should be {{{initializing}}}, unless this
is secret society?
Yup: done :)
> * The sentence
> {{{
> However, if one writes down a smaller number than the other, this
smaller
> }}}
> probably needs a blank line in front of it or the documentation will
look like a humongous paragraph. I think I mentioned this before.
Apologies: done.
> * {{{At present the algorithms for the computation of equilibria only
solve 2 player}}} - "solves"
Unless I'm making a grammatical mistake (which I might well be) I don't
think that's correct? 'The algorithms solve 2 player games'?
> ----
> {{{
> sage: p += plot((A * vector([y, 1 - y]))[1], y, 0, 1, color='red',
legend_label='$u_1(r_2, (y, 1-y))$')
> }}}
> but typically one shows the plot (or allows the user to) when using this
to make a point. Maybe just add {{{; p}}} to the end of that line.
Have fixed (wasn't sure if tests would no longer pass but they do).
> ----
>
> Thinking aloud: Should
> {{{
> "Normal Form Game with the following utilities: {}"
> }}}
> instead be
> {{{
> "Normal Form Game with the following utilities:\n{}"
> }}}
> I don't know if Sage often has two-line string representations, though.
I have left it as is for now as I haven't seen many two-line string
representations.
>
> ----
>
> I'm a bit scared by the following.
> {{{
> #!diff
> - sage: g.obtain_Nash()
> - [[(1, 0, 0), (1, 0, 0)], [(0, 1, 0), (0, 1, 0)], [(0, 0, 1),
(0, 0, 1)]]
> + sage: g.obtain_Nash(algorithm='enumeration')
> + [[(1, 0, 0), (1, 0, 0)]]
> }}}
> Shouldn't lrs and enumeration give the same Nash equilibria?
This might be part of the potential bug and I need to address. In a sense
it's ok because the algorithm 'doesn't make sense for degenerate games'
but I think something is wrong with pure strategy NE which enumeration
should find.
>
> ----
>
> > > * 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.
> >
> Hmm, I kind of meant the opposite - shouldn't `j` be a `p1_strategy` and
so forth? Perhaps I'm misunderstanding this. For stuff like this,
variable names that mean something are crucial. Plus, the new code still
mixes letters and `strategy`s.
I agree, in fact I think I've gotten myself confused with what you were
asking now. It's clear now and will mention more in comment later on.
>
> ----
>
> > > * These mixed strategies
> > > 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.
> >
> Well, I have no independent way to check that but hopefully yes!
>
> ----
> > > * 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.
> >
> Maybe at the very least in situations like
> {{{
> sage: g = NormalFormGame()
> sage: g.add_player(2)
> sage: g.add_player(2)
> sage: g.add_player(2) # Creating a game with three players
> }}}
> you could, early in the docs, say instead
> {{{
> sage: g = NormalFormGame()
> sage: g.add_player(2) # adding first player with two strategies
> sage: g.add_player(2) # adding second player with two
strategies
> sage: g.add_player(2) # Creating a game with three players
> }}}
> or something along those lines.
Have added as you suggest throughout (for all similar examples).
>
> ----
> > > * 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.
> >
> Well, it doesn't print things nicer, just the doctest does. So I guess
what you are saying is that the keys must be pure strategy pairs to comply
with gambit?
Yes.
>
> ----
> > > * 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.
> >
> I still don't understand, so for sure the reader won't. You have to
tell the reader what the output ''means'', since they do not see the
number TWO in the output and if they are not a programmer they won't
recognize it from the matrices. I think here you understand the code so
well that it is just obvious to you.
I've added more explenation.
>
> ----
>
> > > * 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.
> >
> Given that Sage usually lowercases even proper names most of the time
(such as Schlegel projection or Conway polynomials or Schonheim bound) I
think we need to go with `obtain_nash`. Especially because in programming
there are kind of two conventions - either `camelCase` or `camel_case`,
but not `camel_Case` and that is what it looks like, even if that is not
the intent.
Have fixed throughout.
>
>
> ----
>
> Getting closer...
>
> ----
> More to come.
Replying to [comment:25 kcrisman]:
> >> 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.
> > My suggestion would be to return None; this is what we do for crystals
for a similar situation. AFAIK, there is no standard (or other similar
case for that matter) in Sage about this.
> Hmm, maybe that is better indeed.
Have gone with `None`.
Replying to [comment:26 kcrisman]
> More random bits. Looking very good, though.
>
> ----
>
> {{{
> +Here is a game being constructed using gambit syntax (note that a
> +``NormalFormGame`` object acts like a dictionary with strategy tuples
as
> +keys and payoffs as their values)::
> }}}
> I think that if you make it clear that they are '''pure''' strategy
tuples I will be a lot happier with this syntax.
>
Have clarified this.
> ----
>
> {{{
> Proceedings of the national academy of sciences
> }}}
> I think PNAS is capitalized, but I could be wrong. Interesting place
for a math paper, incidentally, you don't get too many in there!
Have capitalized.
>
> ----
>
> I just have to point out about the RPSLS
> > The topic of this article may not meet Wikipedia's general notability
guideline.
> :-) But maybe then http://www.samkass.com/theories/RPSSL.html is a
better, if more brittle, reference. At least it does have the CC license,
phew! Otherwise maybe you couldn't use it ;-)
Changed the reference.
Replying to [comment:27 kcrisman]:
> Okay, back to the algorithm. Here was one thing I definitely was
confused by before.
> > Equivalently we can consider consecutive rows of A (instead of all
pairs of strategies).
> Huh? I distinctly remember that part of the code, but I don't see it in
the references. So maybe this is just some very basic linear systems
thing I am not remembering, but if you can clear it up for me I'd be
grateful.
This isn't documented in the references but is a small linear system
trick.
I haven't changed the docs but here's the idea (if you think it needs to
go in just let me know):
We want to find a strategy such that u(x,s) = u for all s for some u: ie
all the pure strategies must have the same utility against that particular
mixed strategy.
In practice we don't actually care about the value of u so to set up the
linear system it's just as easy to say that u(x,s_1)=u(x,s_2) for all s_1,
s_2.
What we're doing here in our algorithm is creating a chain of equality
where we have consecutive pairs of strategies: u(x,s_1)=u(x,s_2),
u(x,s_2)=u(x,s_3), ... u(x,x_m)=u(x,s_1) (the last equality there isn't
really needed).
Does that help? Do you think more is needed in the docs? (If you do, I'm
happy to put something in but feel that it's perhaps not needed - happy to
be wrong).
>
> Along these lines, you then need to change
> {{{
> where `A` has been modified to only contain the row corresponding to
`S(\rho_1)`
> }}}
> to
> {{{
> where `A` has been modified to only contain the rows corresponding to
`S(\rho_1)`)
> }}}
> (since there is a necessary parenthesis (oh, WHY do the Brits call them
brackets when brackets are square? (truly, I don't know))).
Fixed.
>
> > > > * Minor but made the code harder to understand:
> > > Have tried to clarify as suggested: let me know if it still isn't
quite right.
> > Hmm, I kind of meant the opposite - shouldn't `j` be a `p1_strategy`
and so forth? Perhaps I'm misunderstanding this. For stuff like this,
variable names that mean something are crucial. Plus, the new code still
mixes letters and `strategy`s.
> Oh, ''now'' I get it (thanks to your improved exposition and CUP's kind
provision of [http://blog.oddhead.com/2007/09/17/computational-aspects-of-
prediction-markets-book-chapter-and-extended-bibliography/ a free download
of AGT]). These are maybe to distinguish between using ''all'' strategies
and just the ones in the truncated list of ones in the support?
>
> Or if not, then I stick with my original request.
The equations of are linear system correspond to strategy pairs so I've
now changed this to be more verbose.
>
> By the way, you can just move the comments like this
> {{{
> # Coefficients of linear system that ensure indifference between two
consecutive strategies of the support of p1
> }}}
> to the line immediately preceding, to ensure good readability.
Done.
>
> I note that in the built doc for some reason there is documentation for
`sage.game_theory.normal_form_game.PIPE`. I couldn't tell you how to
remove it but it does seem odd.
I have no idea what to do about this and/or how it has come about... Will
continue to investigate unless someone has a good suggestion?
>
> ----
>
> So now one can move to the testing phase!
Replying to [comment:29 kcrisman]:
> Sorry for the mountain, but getting it all done at once is better for my
workflow...
>
> I get the following output in the notebook.
> {{{
> Normal Form Game with the following utilities: {(0,
> 1): [1, 1], (1, 0): [0, 0], (0, 0): [3, 2], (1, 1): [2, 3]}
> }}}
> Note the very long space. I think this is because of
> {{{
> + return "Normal Form Game with the following \
> + utilities: {}".format(self.utilities)
> }}}
> and so it kept all those spaces, since this is a string.
Was trying to stick to PEP8 but looking at that it was very clumsily done:
have addressed now.
Replying to [comment:30 kcrisman]:
> Okay, now testing commences. I am primarily testing whether the two
algorithms give the same output. I am also trying to compare output with
various third-party online software, just to make sure no horrible goofs.
>
> ----
>
> {{{
> sage: N = NormalFormGame([matrix(2,[0,-1,-2,-1]),matrix(2,[1,0,0,2])])
> sage: N.obtain_Nash(algorithm='enumeration')
> [[(1, 0), (1, 0)]]
> sage: N.obtain_Nash(algorithm='lrs')
> [[(2/3, 1/3), (0, 1)], [(0, 1), (0, 1)], [(1, 0), (1, 0)]]
> }}}
> This one is degenerate because one column of the row player's matrix is
all the same, but I wonder why enumeration doesn't at least get the two
''pure'' equilibria? Is it possible to warn about degenerate ones in the
code, or would that indeed be too hard? Maybe that should be implemented
at the algorithm level... but at least the situation where a column of the
row player or row of the column player have two of the same number could
be checked for. So far, that is all the discrepancies I get.
>
> Or maybe that's for an upgrade ticket!
>
> ----
>
> Here is something I don't like. In all cases (including when gambit is
added), the return type from `obtain_nash/obtain_Nash` should be the same.
Well, it sort of is.
> {{{
> sage: N = NormalFormGame([matrix(2,[2,-3,0,-1]),matrix(2,[0,1,2,-2])])
> sage: N.obtain_Nash(algorithm='enumeration')
> [[(4/5, 1/5), (1/2, 1/2)]]
> sage: N.obtain_Nash(algorithm='lrs')
> [[(4/5, 1/5), (1/2, 1/2)]]
> sage: N.obtain_Nash(algorithm='enumeration') ==
N.obtain_Nash(algorithm='lrs')
> False
> sage: type(N.obtain_Nash(algorithm='lrs')[0][0])
> <type 'tuple'>
> sage: type(N.obtain_Nash(algorithm='enumeration')[0][0])
> <type 'sage.modules.vector_rational_dense.Vector_rational_dense'>
> }}}
> Umm. This is because you solved a linear system, and that returns a
vector. However, I'm not sure what the right return type is - because
with gambit presumably the return will be a non-rational vector or
something. Maybe better to return all as tuples? Or all as vectors?
>
> An argument for vectors is to easily ''always'' do this
> {{{
> sage:
N.obtain_Nash(algorithm='enumeration')[0][0]*matrix(2,[2,-3,0,-1])*N.obtain_Nash(algorithm='enumeration')[0][1]
> -1/2
> sage:
vector(N.obtain_Nash(algorithm='lrs')[0][0])*matrix(2,[2,-3,0,-1])*vector(N.obtain_Nash(algorithm='lrs')[0][1])
> }}}
> without having to put things in vectors.
>
> An argument against is that one might not ''want'' the additional
structure of a vector - after all, a (mixed) strategy is really more of a
discrete probability distribution.
>
> But the return types should be as close as possible to each other,
anyway.
I agree: I'm likely to go with tuples but will think about it.
>
> ----
> {{{
> sage: N =
NormalFormGame([matrix(2,[7,-8,-4,-8,7,0]),matrix(2,[-9,-1,-8,3,2,3])])
> sage: N.obtain_Nash(algorithm='lrs')[[(0, 1), (0, 0, 1)]]
> sage: N.obtain_Nash(algorithm='enumeration')
> []
> }}}
> Okay, I get it, degenerate. But why doesn't enumeration at least return
''an'' equilibrium?
>
> ----
>
> Here's another one. I am baffled by these outputs (just showing the
matrices and results).
> {{{
> [-7 -5 5]
> [ 5 5 3]
> [ 1 -6 1]
> [ -9 7 9]
> [ 6 -2 -3]
> [ -4 6 -10]
> [[(0, 1, 0), (1, 0, 0)], [(1/3, 2/3, 0), (1/7, 0, 6/7)], [(1, 0, 0), (0,
0, 1)]] #enum
> [[(0, 1, 0), (0, 0, 1)], [(1/3, 2/3, 0), (0, 1/6, 5/6)], [(1, 0, 0),
(1/7, 0, 6/7)]] #lrs
> }}}
> In particular, what is up with `[(0, 1, 0), (0, 0, 1)]`? If row plays
middle and column plays right, then row should move to top and/or column
should move to left or middle. I buy `[(0, 1, 0), (1, 0, 0)]`. Am I
reading the matrices wrong now that they are 3x3? Note that the
[http://banach.lse.ac.uk/ LSE online version of lrs online] gives most of
these equilibria, but not `[(0, 1, 0), (0, 0, 1)]`. Hopefully I'm just
interpreting something wrong, though.
>
> ----
>
> Otherwise I am pretty happy, this really does seem to give good output
in most cases and the algorithms agree where desired. Lots of very minor
things to fix above but this will be a robust addition to Sage, thanks for
working so hard on it.
As I said above I think you have actually found a bug in the algorithm
here. My hunch is that it's something to do with pruning so will take a
look at that: your examples are going to serve as tests and will be
incorporated in. **Thank you very much for spotting this.**
--
Ticket URL: <http://trac.sagemath.org/ticket/16954#comment:35>
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.
