File: app.alg.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 (344 lines) | stat: -rw-r--r-- 7,320 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<HTML
><HEAD
><TITLE
>Reference: Algorithms to Compute Nash Equilibria</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.59"><LINK
REL="HOME"
TITLE="Gambit"
HREF="gambit.html"><LINK
REL="PREVIOUS"
TITLE="Categorical listing of functions"
HREF="gcl.funccat.html"><LINK
REL="NEXT"
TITLE="EnumMixedSolve"
HREF="app.alg.enummixed.html"></HEAD
><BODY
CLASS="APPENDIX"
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="gcl.funccat.html"
>&#60;&#60;&#60; Previous</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="app.alg.enummixed.html"
>Next &#62;&#62;&#62;</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="APPENDIX"
><H1
><A
NAME="APP.ALG"
>Reference: Algorithms to Compute Nash Equilibria</A
></H1
><P
>This appendix is an overview of the literature on computing
Nash equilibria in finite games.  The focus here is on detailing the
essentials of the theory for the user who wants to compute equilibria, 
and to document the implementations of the algorithms provided in
Gambit.  The interested user should consult McKelvey and McLennan's
survey article [<SPAN
CLASS="CITATION"
><A
HREF="bib.html#MCKMCL96"
>McKMcL96</A
></SPAN
>],
plus the references
therein and the <A
HREF="bib.html"
>bibliography</A
> of this manual for more information.
    </P
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="APP.ALG.START"
>Tips on getting started</A
></H1
><P
>Gambit has a number of algorithms to find Nash equilibria.  The
appropriate algorithm to use depends on a number of factors, most
importantly, the number of players in the game, and the number of
equilibria you want to find.  </P
><P
>Before computing equilibria, you may wish to eliminate
dominated strategies.  The smaller the number of strategies the
algorithm must consider, 
the faster any algorithm will run.  However, dominance
elimination can itself be computationally intensive, especially if
domination by mixed strategies (for the normal form) is considered,
or if dominance elimination is done on a large extensive form.
<P
></P
><UL
><LI
><P
>If you want to find more than one, or all Nash equilibria of a game,
then you may first successively eliminate strongly dominated
strategies.  Any equilibrium of the original game will also be an
equilibrium of the reduced game.</P
></LI
><LI
><P
>If you just want to find <I
CLASS="EMPHASIS"
>one</I
> Nash equilibrium,
you can first successively eliminate <I
CLASS="EMPHASIS"
>weakly</I
>
dominated strategies.  Elimination of weakly dominated strategies may
eliminate some Nash equilibria of the original game, so it should not
be used if you want to find multiple Nash equilibria, but any Nash
equilibrium to the reduced game will be an equilibrium to the original
game, so it can be used if you only want to find one equilibrium.</P
></LI
></UL
></P
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="APP.ALG.START.COMMON"
>Common algorithm parameters</A
></H2
><P
>There are a few parameters which are common among several algorithms.</P
></DIV
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="APP.ALG.START.PURE"
>Pure strategy equilibria</A
></H2
><P
>The <A
HREF="app.alg.enumpure.html"
>EnumPureSolve</A
> algorithm can be used to enumerate
all of the pure strategy equilibria for both extensive and normal form
games.  </P
></DIV
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="APP.ALG.START.ZEROSUM"
>Two Person Constant Sum Games</A
></H2
><P
>For two person constant sum normal form games, the minimax theorem
applies.  The set of Nash equilibria is a convex set, and the problem
of finding Nash equilibria can be formulated as a linear program.  The 
<A
HREF="app.alg.lp.html"
>LpSolve</A
> algorithm
will solve a constant sum game using this approach.</P
></DIV
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="APP.ALG.START.2P"
>Two Person Games</A
></H2
><P
>For two person nonzero sum games, the problem of finding Nash
equilibria can be formulated as a linear complementarity problem, and
exact solutions can be found as long as computations are done in
rationals.  The <A
HREF="app.alg.lcp.html"
>LcpSolve</A
>
algorithm solves a two person game
using this approach.  Note that this algorithm can also be used
directly on an extensive form game, where it implements the Koller,
Megiddo, von Stengel sequence form
[<SPAN
CLASS="CITATION"
><A
HREF="bib.html#KOLMEGSTE94"
>KolMegSte94</A
></SPAN
>].</P
><P
>For a two person game the <A
HREF="app.alg.enummixed.html"
>EnumMixedSolve</A
> algorithm
will enumerate all of the extreme points of the components of the set
of Nash equilibria, and hence can be used to find <I
CLASS="EMPHASIS"
>all</I
> Nash
equilibria.  </P
></DIV
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="APP.ALG.START.NP"
>Games With More Than Two Players</A
></H2
><P
>For n-person normal form games, with n greater than two, the
<A
HREF="app.alg.polenum.html"
>PolEnumSolve</A
> algorithm will find all Nash
equilibria. The PolEnum algorithm may be computationally infeasible on
large games.  Thus other algorithms are also available for finding one
or a sample of Nash equilibria.  Since Nash equilibria can be
irrational, the algorithms to locate one equilibrium will only find
approximations (to machine accuracy) of Nash equilibria.</P
><P
><A
HREF="app.alg.simpdiv.html"
>SimpDivSolve</A
>SimpDivSolve is guaranteed to locate one
equilibrium for an n-person normal form game.  This algorithm can be
very slow on some games.  Hence two other algorithms are also
implemented, <A
HREF="app.alg.qre.html"
>QreSolve</A
>
and <A
HREF="app.alg.liap.html"
>LiapSolve</A
>.  These
algorithms can also be used to search for multiple equilibria (with no
guarantee that all have been found), and to search for equilibria
close to a given starting point.</P
></DIV
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="APP.ALG.START.SEQUENTIAL"
>Sequential Equilibria</A
></H2
><P
>Sequential equilibria are equilibria that prescribe optimal behavior
at any information set of the extensive form, given a consistent
assessment of beliefs.  See [<SPAN
CLASS="CITATION"
><A
HREF="bib.html#KREWIL82"
>KreWil82</A
></SPAN
>].  
<A
HREF="app.alg.qre.html"
>QreSolve</A
> on extensive form games
is guaranteed to converge to a sequential equilibrium.</P
></DIV
></DIV
></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="gcl.funccat.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="app.alg.enummixed.html"
>Next &#62;&#62;&#62;</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Categorical listing of functions</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
>&nbsp;</TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>EnumMixedSolve</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>