#18536: Solvers for constant sum games
-------------------------------------+-------------------------------------
Reporter: ptigwe | Owner:
Type: enhancement | Status: needs_work
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 | a24c7dd1ebd473b679fe070c173e7c824138e3d2
Branch: | Stopgaps:
u/ptigwe/gt_extension |
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by ptigwe):
> 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.
OK. I was planning on opening a ticket, towards the end of GSOC, which
would address the documentation as a whole. In the mean time, changes to
the documentation would be based on changes made to the code.
> 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?
Yeah.
> Is it potentially still faster even for non-constant-sum games?
Not sure if you are asking about using the LP for non-constant-sum games
or the general classification of finding a Nash in a general game. In case
if it was a bit of both:
* LP's aren't guaranteed to find a Nash equilibrium in a two player non-
constant-sum game.
* Finding a Nash is PPAD-complete. Even the problem of approximation is
hard.
> Doctests pass.
That's Good.
> 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.)
OK.
--
Ticket URL: <http://trac.sagemath.org/ticket/18536#comment:17>
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.
