lrsnash(1)

1LRSNASH(1)                        lrslib 7.2                        LRSNASH(1)
2
3
4

NAME

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

SYNOPSIS

9       lrsnash  [options...] [input-file]
10
11       lrsnash1 [options...] [input-file]
12
13       lrsnash2 [options...] [input-file]
14
15       nashdemo
16
17       options:
18           -v, --verbose         Prints a trace of the solution process
19           -d, --debug           Dumps lots of information for debugging
20           -p, --printgame       Prints the payoff matrix for the game
21           -s, --standard        Promise that input files have standard
22       structure
23           -o, --outfile <file>  Send output to <file>
24           -h, --help            Prints this text
25            Short options can be grouped, as in '-ps' and '-do out.txt'
26
27
28

DESCRIPTION

30       These C programs are distributed as part of the lsrslib[2] package and
31       must be compiled with it.
32
33       Alice has a payoff matrix A and Bob has a playoff matrix B, both of
34       dimension m by n.  Alice assigns probabilities x to the rows and Bob y
35       to the columns.  Alice receives payoff x^T A y and Bob receives x^T B
36       y.  A Nash equilibriam occurs for pairs x,y for which neither player
37       can improve their expected payoff by unilateraly changing strategies.
38
39
40       lrsnash is an application of lrs for finding Nash-equilibria in
41       2-person matrix games using a method described in [1]. It uses GMP
42       exact extended precision arithmetic.
43
44       lrsnash1 is the same as lrsnash except that it uses 64 bit exact
45       arithmetic and terminates if overflow is detected.  It is about 3-4
46       times faster.
47
48       lrsnash2 is the same as lrsnash except that it uses 128 bit exact
49       arithmetic and terminates if overflow is detected.  It is about twice
50       as fast. It requires a C compiler with __int128 support (eg. gcc v.
51       4.6.0 or later).
52
53       nashdemo is a simple template for lrsnash.  It builds two 3x4 matrices
54       A and B and computes their equilibria.
55
56       The running time may be significantly different depending on the order
57       of the two matrices in the input. For large problems it may be
58       advantageous to run lrsnash twice in parallel with the matrices in
59       different orders.  There is also a more complex legacy input format
60       recognized by lrsnash that is described in [1].
61
62

FILE FORMATS

64       The input file consists of two integers m and n on line 1 followed by
65       two mxn payoff matrices A and B:
66
67        m n
68        A          (row by row)
69        B          (row by row)
70
71

EXAMPLE

73       The input file game  has two 3x2 payoff matrices:
74
75        %cat game
76
77        3 2
78
79        0 6
80        2 5
81        3 3
82
83        1 0
84        0 2
85        4 3
86
87        % lrsnash game
88
89        2  1/3  2/3  4
90        1  2/3  1/3  0  2/3
91
92        2  2/3  1/3  3
93        1  0  1/3  2/3  8/3
94
95        2  1  0  3
96        1  0  0  1  4
97
98        *Number of equilibria found: 3
99        *Player 1: vertices=5 bases=5 pivots=8
100        *Player 2: vertices=3 bases=1 pivots=8
101
102       Interpretation There are 3 Nash equilibria. For the first one:
103
104        2  1/3  2/3  4
105       Bob(player 2) plays column 1 and 2 with probablilities y=(1/3, 2/3) and
106       the payoff to Alice(player 1) is 4.
107
108        1  2/3  1/3  0  2/3
109       Alice plays rows 1,2,3 with probabilities x=(2/3, 1/3, 0) and the
110       payoff to Bob is 2/3.
111
112

NOTES

114       1.  D. Avis, G. Rosenberg, R. Savani, B. von Stengel, Enumeration of
115           Nash Equilibria for Two-Player Games, Economic Theory 42(2009) 9-37
116
117       2.  User's guide for lrslib
118           http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html
119

AUTHORS

121       David Avis and Terje Lensberg
122