#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:
Authors: | Work issues:
Report Upstream: N/A | Commit:
Branch: | ffa6d525b5e6681687642d9efc80037884823e30
u/vinceknight/16954 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by 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.
* The algorithm for some reason sorts the support size profiles, but I
don't see that in the code.
* 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.
* 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.
* Minor doc note: ` or does not have a dominated row:` should have
one more colon.
* 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).
* 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)):
}}}
* 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)?
* Would it help to formally do this as an LP with Sage LPs or is
`solve_right` sufficient?
* 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.
* 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/16954#comment:16>
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.
