## table of contents

- bookworm 0.71b-2
- testing 0.71b-2.1+b1
- unstable 0.73-2
- experimental 0.73-1

lrsnash(1) | lrslib 7.3 | lrsnash(1) |

## 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

## Authors¶

David Avis and Terje Lensberg

## See also¶

**lrslib**(5)

2024.1.31 | January 2024 |