#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 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.
----
{{{
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/16954#comment:30>
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.
