An overview of Gambit
=====================

What is Gambit?
---------------

Gambit is a set of software tools for doing computation on finite,
noncooperative games. These comprise a graphical interface for
interactively building and analyzing general games in extensive or
strategy form; a number of command-line tools for computing Nash
equilibria and other solution concepts in games; and, a set of file
formats for storing and communicating games to external tools.

A brief history of Gambit
-------------------------

The Gambit Project was founded in the mid-1980s by Richard McKelvey at
the California Institute of Technology. The original implementation
was written in BASIC, with a simple graphical interface. This code was
ported to C around 1990 with the help of Bruce Bell, and was
distributed publicly as version 0.13 in 1991 and 1992.

A major step in the evolution of Gambit took place with the awarding
of the NSF grants in 1994, with McKelvey and Andrew McLennan as
principal investigators, and `Theodore Turocy <http://www.gambit-project.org/turocy>`__ as the head programmer.
The grants sponsored a complete rewrite of Gambit in C++. The
graphical interface was made portable across platforms through the use
of the wxWidgets library (`http://www.wxwidgets.org
<http://www.wxwidgets.org>`__). Version 0.94 of Gambit was released in
the late summer of 1994, version 0.96 followed in 1999, and version
0.97 in 2002. During this time, many students at Caltech and Minnesota
contributed to the effort by programming, testing, and/or documenting.
These include, alphabetically, Bruce Bell, Anand Chelian, Matthew
Derer, Nelson Escobar, Ben Freeman, Eugene Grayver, Todd Kaplan, Geoff
Matters, Brian Trotter, Michael Vanier, Roberto Weber, and Gary Wu.

Over the same period, Bernhard von Stengel, of the London School of
Economics, made significant contributions in the implementation of the
sequence form methods for two-player extensive games, and for
contributing his "clique" code for identification of equilibrium
components in two-player strategic games, as well as other advice
regarding Gambit's implementation and architecture.

Development since the mid-2000s has focused on two objectives. First,
the graphical interface was reimplemented and modernized, with the
goal of following good interaction design principles, especially in
regards to easing the learning curve for users new to Gambit and new
to game theory.  Second, the internal architecture of Gambit was
refactored to increase interoperability between the tools provided by
Gambit and those written independently. 

Gambit is proud to have participated in the Google Summer of Code
program in the summers of 2011 and 2012 as a mentoring organization.
The Python API, which became part of Gambit from Gambit 13, was
developed during these summers, thanks in particular to the work 
of Stephen Kunath and Alessandro Andrioni.


Key features of Gambit
----------------------

Gambit has a number of features useful both for the researcher and the
instructor:

**Interactive, cross-platform graphical interface.** All Gambit
features are available through the use of a graphical interface, which
runs under multiple operating systems: Windows, various flavors of
Un*x (including Linux), and Mac OS X. The interface offers flexible
methods for creating extensive and strategic games. It offers an
interface for running algorithms to compute Nash equilibria, and for
visualizing the resulting profiles on the game tree or table, as well
as an interactive tool for analyzing the dominance structure of
actions or strategies in the game. The interface is useful for the
advanced researcher, but is intended to be accessible for students
taking a first course in game theory as well.

**Command-line tools for computing equilibria.** More advanced
applications often require extensive computing time and/or the ability
to script computations. All algorithms in Gambit are packaged as
individual, command-line programs, whose operation and output are
configurable.

**Extensibility and interoperability.** The Gambit tools read and
write file formats which are textual and documented, making them
portable across systems and able to interact with external tools. It
is therefore straightforward to extend the capabilities of Gambit by,
for example, implementing a new method for computing equilibria,
reimplementing an existing one more efficiently, or creating tools to
programmatically create, manipulate, and transform games, or for
econometric analysis on games.


Limitations of Gambit
---------------------

Gambit has a few limitations that may be important in some
applications. We outline them here.

**Gambit is for finite games only.** Because of the mathematical
structure of finite games, it is possible to write many general-
purpose routines for analyzing these games. Thus, Gambit can be used
in a wide variety of applications of game theory. However, games that
are not finite, that is, games in which players may choose from a
continuum of actions, or in which players may have a continuum of
types, do not admit the same general-purpose methods.

**Gambit is for noncooperative game theory only.** Gambit focuses on
the branch of game theory in which the rules of the game are written
down explicitly, and in which players choose their actions
independently. Gambit's analytical tools center primarily around Nash
equilibrium, and related concepts of bounded rationality such as
quantal response equilibrium. Gambit does not at this time provide any
representations of, or methods for, analyzing games written in
cooperative form. (It should be noted that some problems in
cooperative game theory do not suffer from the computational
complexity that the Nash equilibrium problem does, and thus
cooperative concepts could be an interesting future direction of
development.)

**Analyzing large games may become infeasible surprisingly quickly.**
While the specific formal complexity classes of computing Nash
equilibria and related concepts are still an area of active research,
it is clear that, in the typical case, the amount of time required to
compute equilibria increases rapidly in the size of the game. In other
words, it is quite easy to write down games which will take Gambit an
unacceptably long amount time to compute the equilibria of. There are
two ways to deal with this problem in practice. One way is to better
identify good heuristic approaches for guiding the equilibrium
computation process. Another way is to take advantage of known
features of the game to guide the process. Both of these approaches
are now becoming areas of active interest. While it will certainly not
be possible to analyze every game that one would like to, it is hoped
that Gambit will both contribute to these two areas of research, as
well as make the resulting methods available to both students and
practitioners.

Developers
----------

The principal developers of Gambit are:

* `Theodore Turocy <http://www.gambit-project.org/turocy>`__, 
  University of East Anglia: director.

* Richard D. McKelvey, California Institute of Technology: 
  project founder.

* Andrew McLennan, University of Queensland: co-PI during main 
  development, developer and maintainer of polynomial-based algorithms
  for equilibrium computation.

Much of the development of the main Gambit codebase took place in
1994-1996, under a grant from the National Science Foundation to the 
California Institute of Technology and the University of Minnesota 
(McKelvey and McLennan, principal investigators).

Others contributing to the development and distribution of Gambit
include:

* Bernhard von Stengel provided advice on implementation of 
  sequence form code, and contributed clique code

* Eugene Grayver developed the first version of the 
  graphical user interface.

* Gary Wu implemented an early scripting language interface for
  Gambit (since superseded by the Python API).

* Stephen Kunath and Alessandro Andrioni did extensive work to create
  the first release of the Python API.

* From Gambit 14, Gambit contains support for Action Graph Games
  [Jiang11]_.  This has been contributed by Navin Bhat, Albert Jiang,
  Kevin Leyton-Brown, and David Thompson, with funding support
  provided by a University Graduate Fellowship of the University
  of British Columbia, the NSERC Canada Graduate Scholarship, and a 
  Google Research Award to Leyton-Brown.

.. _section-downloading:

Downloading Gambit
------------------

Gambit operates on an annual release cycle roughly mirroring the
(northern hemisphere) academic year.  A new version is promoted to
stable/teaching each August; the major version number is equal to the
last two digits of the year in which the version becomes stable.

This document covers Gambit 15, which is the current stable
version as of October 2015.  The most recent release is 15.1.0. 
You can download it from
`Sourceforge
<http://sourceforge.net/projects/gambit/files/gambit15/15.1.0>`_.
Full source code is available, as are precompiled binaries for
Microsoft Windows and Mac OS X 10.8.

Older versions of Gambit can be downloaded from
`http://sourceforge.net/projects/gambit/files
<http://sourceforge.net/projects/gambit/files>`_.  Support for older
versions is limited.


Community
---------

The following mailing lists are available for those interested in the
use and further development of Gambit:

`gambit-announce@lists.sourceforge.net <http://lists.sourceforge.net/lists/listinfo/gambit-announce>`_
  Announcement-only mailing list for notifications of new releases of
  Gambit.

`gambit-users@lists.sourceforge.net <http://lists.sourceforge.net/lists/listinfo/gambit-users>`_
  General discussion forum for teaching and research users of Gambit.

`gambit-devel@lists.sourceforge.net <http://lists.sourceforge.net/lists/listinfo/gambit-devel>`_
  Discussion for those interested in devleoping or extending Gambit, 
  or using Gambit source code in other applications.

Bug reports
-----------

In the first instance, bug reports or feature requests should be
posted to the Gambit issue tracker, located at
`<http://github.com/gambitproject/gambit/issues>`_.

When reporting a bug, please be sure to include the following:

* The version(s) of Gambit you are using.  (If possible, it is helpful
  to know whether a bug exists in both the current stable/teaching and
  the current development/research versions.)
* The operating system(s) on which you encountered the bug.
* A detailed list of steps to reproduce the bug.  Be sure to include a
  sample game file or files if appropriate; it is often helpful to
  simplify the game if possible.