#18536: Solvers for constant sum games
-------------------------------------+-------------------------------------
Reporter: ptigwe | Owner:
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-6.8
Component: game theory | Resolution:
Keywords: Game Theory, | Merged in:
Gambit, Zero-sum game Constant | Reviewers: Karl-Dieter Crisman
Sum Game, Normal Form Games | Work issues:
Authors: Tobenna P. Igwe | Commit:
Report Upstream: N/A | 60efdc7f823c8aa64ac176addcd376f1f571b09d
Branch: | Stopgaps:
u/ptigwe/gt_extension |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by kcrisman):
I cannot figure out how to get the changes in the doc built, it's
maddening. I'll have to assume it's okay and I didn't miss anything.
The following could be improved, it really looks pretty meager. Not
necessarily for this ticket, as definitely pre-existing - Vince, I'll
blame you for this :)
{{{
class NormalFormGame(SageObject, MutableMapping):
r"""
An object representing a Normal Form Game. Primarily used to compute
the
Nash Equilibria.
INPUT:
- ``generator`` - Can be a list of 2 matrices, a single matrix or left
blank.
"""
}}}
It should at least tell how to get to more documentation from there.
The following
{{{
+ p = MixedIntegerLinearProgram(maximization=False, solver=solver)
+ y = p.new_variable(nonnegative=True)
+ v = p.new_variable(nonnegative=False)
+ p.add_constraint(self.payoff_matrices()[0] * y - v[0] <= 0)
+ p.add_constraint(matrix([[1] * strategy_sizes[0]]) * y == 1)
+ p.set_objective(v[0])
}}}
looks good though I would prefer to use maximization and swap that first
constraint or whatever is appropriate, but presumably this is the industry
standard to minimize.
So... is the reason for doing this only for constant-sum games because
it's only known to be in P for them? Is it potentially still faster even
for non-constant-sum games?
Doctests pass.
I think it's worth pointing out somewhere in the documentation that the LP
approach will give ''one'' NE but not ''all'' of them, should there be
more than one. (Constant-sum games can have more than one NE, right? I
guess the trivial game is an example.)
--
Ticket URL: <http://trac.sagemath.org/ticket/18536#comment:13>
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.
