Ubuntu Manpage: lrsnash: Compute Nash-equibria in 2-person games.

NAME

       lrsnash:   Compute Nash-equibria in 2-person games.

SYNOPSIS

       lrsnash  [options...] [input-file]

       lrsnash1 [options...] [input-file]

       lrsnash2 [options...] [input-file]

       nashdemo

       options:
           -v, --verbose         Prints a trace of the solution process
           -d, --debug           Dumps lots of information for debugging
           -p, --printgame       Prints the payoff matrix for the game
           -s, --standard        Promise that input files have standard structure
           -o, --outfile <file>  Send output to <file>
           -h, --help            Prints this text
            Short options can be grouped, as in '-ps' and '-do out.txt'

DESCRIPTION

These C programs are distributed as part of the lsrslib[2] package and must be compiled
with it.

Alice has a payoff matrix A and Bob has a playoff matrix B, both of dimension m by n.
Alice assigns probabilities x to the rows and Bob y to the columns. Alice receives payoff
x^T A y and Bob receives x^T B y. A Nash equilibriam occurs for pairs x,y for which
neither player can improve their expected payoff by unilateraly changing strategies.

lrsnash is an application of lrs for finding Nash-equilibria in 2-person matrix games
using a method described in [1]. It uses GMP exact extended precision arithmetic.

lrsnash1 is the same as lrsnash except that it uses 64 bit exact arithmetic and terminates
if overflow is detected. It is about 3-4 times faster.

lrsnash2 is the same as lrsnash except that it uses 128 bit exact arithmetic and
terminates if overflow is detected. It is about twice as fast. It requires a C compiler
with __int128 support (eg. gcc v. 4.6.0 or later).

nashdemo is a simple template for lrsnash. It builds two 3x4 matrices A and B and
computes their equilibria.

The running time may be significantly different depending on the order of the two matrices
in the input. For large problems it may be advantageous to run lrsnash twice in parallel
with the matrices in different orders. There is also a more complex legacy input format
recognized by lrsnash that is described in [1].

FILE FORMATS

       The input file consists of two integers m and n on line 1 followed by two mxn payoff
       matrices A and B:

        m n
        A          (row by row)
        B          (row by row)

EXAMPLE

       The input file game  has two 3x2 payoff matrices:

        %cat game

        3 2

        0 6
        2 5
        3 3

        1 0
        0 2
        4 3

        % lrsnash game

        2  1/3  2/3  4
        1  2/3  1/3  0  2/3

        2  2/3  1/3  3
        1  0  1/3  2/3  8/3

        2  1  0  3
        1  0  0  1  4

        *Number of equilibria found: 3
        *Player 1: vertices=5 bases=5 pivots=8
        *Player 2: vertices=3 bases=1 pivots=8

       Interpretation There are 3 Nash equilibria. For the first one:

        2  1/3  2/3  4
       Bob(player 2) plays column 1 and 2 with probablilities y=(1/3, 2/3) and the payoff to
       Alice(player 1) is 4.

        1  2/3  1/3  0  2/3
       Alice plays rows 1,2,3 with probabilities x=(2/3, 1/3, 0) and the payoff to Bob is 2/3.

NOTES

       1.  D. Avis, G. Rosenberg, R. Savani, B. von Stengel, Enumeration of Nash Equilibria for
           Two-Player Games, Economic Theory 42(2009) 9-37

       2.  User's guide for lrslib
           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html

AUTHORS

       David Avis and Terje Lensberg