'\" t
.\"     Title: nash
.\"    Author: [FIXME: author] [see http://docbook.sf.net/el/author]
.\" Generator: DocBook XSL Stylesheets v1.79.1 <http://docbook.sf.net/>
.\"      Date: 01/14/2019
.\"    Manual: lrslib 0.42b
.\"    Source: July 2009
.\"  Language: English
.\"
.TH "NASH" "1" "01/14/2019" "July 2009" "lrslib 0\&.42b"
.\" -----------------------------------------------------------------
.\" * Define some portability stuff
.\" -----------------------------------------------------------------
.\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.\" http://bugs.debian.org/507673
.\" http://lists.gnu.org/archive/html/groff/2009-02/msg00013.html
.\" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
.ie \n(.g .ds Aq \(aq
.el       .ds Aq '
.\" -----------------------------------------------------------------
.\" * set default formatting
.\" -----------------------------------------------------------------
.\" disable hyphenation
.nh
.\" disable justification (adjust text to left margin only)
.ad l
.\" -----------------------------------------------------------------
.\" * MAIN CONTENT STARTS HERE *
.\" -----------------------------------------------------------------
.SH "NAME"
nash \- find nash equilibria of two person noncooperative games
.SH "SYNOPSIS"
.HP \w'\fBsetupnash\ input\ game1\&.ine\ game2\&.ine\fR\ 'u
\fBsetupnash input game1\&.ine game2\&.ine\fR
.HP \w'\fBsetupnash2\ input\ game1\&.ine\ game2\&.ine\fR\ 'u
\fBsetupnash2 input game1\&.ine game2\&.ine\fR
.HP \w'\fBnash\ game1\&.ine\ game2\&.ine\fR\ 'u
\fBnash game1\&.ine game2\&.ine\fR
.HP \w'\fB2nash\ game1\&.ine\ game2\&.ine\fR\ 'u
\fB2nash game1\&.ine game2\&.ine\fR
.SH "DESCRIPTION"
.PP
All Nash equilibria (NE) for a two person noncooperative game are computed using two interleaved reverse search vertex enumeration steps\&. The input for the problem are two m by n matrices A,B of integers or rationals\&. The first player is the row player, the second is the column player\&. If row i and column j are played, player 1 receives Ai,j
and player 2 receives Bi,j\&. If you have two or more cpus available run 2nash instead of nash as the order of the input games is immaterial\&. It runs in parallel with the games in each order\&. (If you use nash, the program usually runs faster if m is <= n , see below\&.) The easiest way to use the program nash or 2nash is to first run setupnash or ( setupnash2 see below ) on a file containing:\ \&
.sp
.if n \{\
.RS 4
.\}
.nf
  m n
  matrix A
  matrix B
  
.fi
.if n \{\
.RE
.\}
.sp
eg\&. the file game is for a game with m=3 n=2:
.sp
.if n \{\
.RS 4
.\}
.nf
  3 2

  0 6
  2 5
  3 3
  
  1 0
  0 2
  4 3
  
.fi
.if n \{\
.RE
.\}
.sp

.sp
.if n \{\
.RS 4
.\}
.nf
  % setupnash game game1 game2
  
.fi
.if n \{\
.RE
.\}
.sp
produces two H\-representations, game1 and game2, one for each player\&. To get the equilibria, run
.sp
.if n \{\
.RS 4
.\}
.nf
  %  nash game1  game2
  
.fi
.if n \{\
.RE
.\}
.sp
or
.sp
.if n \{\
.RS 4
.\}
.nf
  %  2nash game1  game2
  
.fi
.if n \{\
.RE
.\}
.PP
Each row beginning 1 is a strategy for the row player yielding a NE with each row beginning 2 listed immediately above it\&.The payoff for player 2 is the last number on the line beginning 1, and vice versa\&. Eg: first two lines of output: player 1 uses row probabilities 2/3 2/3 0 resulting in a payoff of 2/3 to player 2\&.Player 2 uses column probabilities 1/3 2/3 yielding a payoff of 4 to player 1\&. If both matrices are nonnegative and have no zero columns, you may instead use setupnash2:
.sp
.if n \{\
.RS 4
.\}
.nf
  % setupnash2 game game1 game2
.fi
.if n \{\
.RE
.\}
.sp
Now the polyhedra produced are polytopes\&. The output\ \& of nash in this case is a list of unscaled probability vectors x and y\&. To normalize, divide each vector by v = 1^T x and u=1^T y\&.u and v are the payoffs to players 1 and 2 respectively\&. In this case, lower bounds on the payoff functions to either or both players may be included\&. To give a lower bound of r on the payoff for player 1 add the options to file game2\ \& (yes that is correct!)To give a lower bound of r on the payoff for player 2 add the options to file game1
.sp
.if n \{\
.RS 4
.\}
.nf
  minimize
  0 1 1 \&.\&.\&. 1 \ \&\ \& (n entries to begiven)
  bound \ \& 1/r;\ \&\ \&  ( note: reciprocal of r)
.fi
.if n \{\
.RE
.\}
.sp
If you do not wish to use the 2\-cpu program 2nash, please read the following\&. If m is greater than n then nash usually runs faster by transposing the players\&. This is achieved by running:
.sp
.if n \{\
.RS 4
.\}
.nf
 %  nash game2  game1
.fi
.if n \{\
.RE
.\}
.sp
If you wish to construct the game1 and game2 files by hand, see the
\m[blue]\fBlrslib user manual\fR\m[]\&\s-2\u[1]\d\s+2
.SH "SEE ALSO"
.PP
For information on
\fIH\-representation\fR
file formats, see the man page for lrslib or the
\m[blue]\fBlrslib user manual\fR\m[]\&\s-2\u[2]\d\s+2
.SH "NOTES"
.IP " 1." 4
lrslib user manual
.RS 4
\%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Nash%20Equilibria
.RE
.IP " 2." 4
lrslib user manual
.RS 4
\%http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#File%20Formats
.RE