File: bif.polenumsolve.html

package info (click to toggle)
gambit-doc 0.97.0-1
links: PTS
area: main
in suites: etch, etch-m68k, lenny, sarge, squeeze
size: 1,344 kB
sloc: makefile: 19; sh: 10
file content (298 lines) | stat: -rw-r--r-- 5,388 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<HTML
><HEAD
><TITLE
>PolEnumSolve</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.59"><LINK
REL="HOME"
TITLE="Gambit"
HREF="gambit.html"><LINK
REL="UP"
TITLE="Built-in functions"
HREF="c2106.html#GCL.BUILTIN"><LINK
REL="PREVIOUS"
TITLE="Plus"
HREF="bif.plus.html"><LINK
REL="NEXT"
TITLE="PossibleNashSupports"
HREF="bif.possiblenashsupports.html"></HEAD
><BODY
CLASS="REFENTRY"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="NAVHEADER"
><TABLE
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
>Gambit: Software Tools for Game Theory</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="bif.plus.html"
>&#60;&#60;&#60; Previous</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="bif.possiblenashsupports.html"
>Next &#62;&#62;&#62;</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><H1
><A
NAME="BIF.POLENUMSOLVE"
>PolEnumSolve</A
></H1
><DIV
CLASS="REFNAMEDIV"
><A
NAME="AEN5422"
></A
><H2
>Name</H2
>PolEnumSolve&nbsp;--&nbsp;Computes Nash equilibria by enumerating solutions to polynomial equations</DIV
><DIV
CLASS="REFSYNOPSISDIV"
><A
NAME="AEN5425"
></A
><H2
>Synopsis</H2
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="SYNOPSIS"
>PolEnumSolve[support-&#62;NFSUPPORT, {stopAfter-&#62;0}, {nEvals&#60;-&#62;0}, 
             {time&#60;-&#62;0.000000}, {traceFile&#60;-&#62;(Output)}, {traceLevel-&#62;0}, 
             {singularSupps&#60;-&#62;{  }}, {recurse-&#62;True}] =: LIST(MIXED)
PolEnumSolve[support-&#62;EFSUPPORT, {asNfg-&#62;False}, {stopAfter-&#62;0}, 
             {nEvals&#60;-&#62;0}, {time&#60;-&#62;0.000000}, {traceFile&#60;-&#62;(Output)}, 
             {traceLevel-&#62;0}, {singularSupps&#60;-&#62;{  }}, 
             {recurse-&#62;True}] =: LIST(BEHAV)</PRE
></TD
></TR
></TABLE
></DIV
><DIV
CLASS="REFSECT1"
><A
NAME="AEN5427"
></A
><H2
>Description</H2
><P
><TT
CLASS="FUNCTION"
>PolEnumSolve</TT
>
solves for all totally mixed Nash equilibrium on <TT
CLASS="PARAMETER"
><I
>support</I
></TT
>.
If
<TT
CLASS="PARAMETER"
><I
>recurse</I
></TT
> is <TT
CLASS="LITERAL"
>True</TT
>, the algorithm iterates through all
sub-supports of <TT
CLASS="PARAMETER"
><I
>support</I
></TT
> to find the full support equilibria on
each sub-support.  Supports with singular solutions are reported in
<TT
CLASS="PARAMETER"
><I
>singularSupps</I
></TT
>.  These supports are skipped by the algorithm
when determined to have singular solutions.</P
><P
>On each sub-support, the algorithm starts with a cube containing the
space of possible solutions and proceeds recursively.  The recursion
step begins with a subcube.  The subcube is discarded if the cube is
irrelevant in the sense of lying outside the space of possible
solutions.  Otherwise a modified Newton's method is used to search for
a solution in the subcube.  In the event that such a solution is
found, Taylor's series information at the solution is used to inquire
whether the solution is necessarily the unique solution in the
subcube.  If Newton's method leaves the subcube before finding a
solution, Taylor's series information at the center is used to inquire
whether we can be sure that the subcube contains no solutions.  If
neither of these procedures resolves the issue, the subcube is
subdivided and this recursion is performed on each smaller subcube.</P
><P
>The following optional parameters may be used to modify the behavior
of the algorithm:
<P
></P
><UL
><LI
><P
><TT
CLASS="PARAMETER"
><I
>stopAfter</I
></TT
> By default, all equilibria are found.  This parameter may
be used to specify a maximum number of equilibria to be found.</P
></LI
><LI
><P
><TT
CLASS="PARAMETER"
><I
>asNfg</I
></TT
> Only applicable to the extensive form version.  By default,
this is <TT
CLASS="LITERAL"
>False</TT
>.  If it is specified to be <TT
CLASS="LITERAL"
>True</TT
>, the
extensive form game is solved by recursively converting its marked
subgames into normal form, solving, and reconstructing the solution as
a behavior profile.</P
></LI
><LI
><P
><TT
CLASS="PARAMETER"
><I
>singularSupps</I
></TT
>:
Returns a list of the supports which have singular solutions. </P
></LI
><LI
><P
><TT
CLASS="PARAMETER"
><I
>recurse</I
></TT
>: Recurses to find totally mixed equilibria on all
subsupports of <TT
CLASS="PARAMETER"
><I
>support</I
></TT
>.</P
></LI
></UL
></P
></DIV
><DIV
CLASS="REFSECT1"
><A
NAME="AEN5454"
></A
><H2
>See also</H2
><P
><A
HREF="bif.possiblenashsupports.html"
>PossibleNashSupports</A
>.</P
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="bif.plus.html"
>&#60;&#60;&#60; Previous</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="gambit.html"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="bif.possiblenashsupports.html"
>Next &#62;&#62;&#62;</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Plus</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="c2106.html#GCL.BUILTIN"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>PossibleNashSupports</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>