lrsnash(1)

✨ lrsnash — the manual page, bestie edition 💅

okay so. you're in the lrslib section of the manual (lrslib 7.3), and this is the page for lrsnash — the tool that finds Nash equilibria in 2-person games. it's giving game theory main character energy and i'm obsessed 🎀

---

🌸 Name 🌸

lrsnash: compute Nash-equibria in 2-person games. no cap, that's the whole job description.

---

✨ Synopsis ✨

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

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

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

nashdemo

options:

• -v, --verbose — prints a trace of the solution process. it literally narrates its own journey 🫶
• -d, --debug — dumps lots of information for debugging. like, a lot a lot. 💀
• -p, --printgame — prints the payoff matrix for the game
• -s, --standard — promise that input files have standard structure (you're pinky-promising here, bestie 🤝)
• -o, --outfile <file> — send output to <file>
• -h, --help — prints this text

short options can be grouped, as in '-ps' and '-do out.txt' — cute and efficient, we love to see it ✨

---

💖 Description 💖

these C programs are distributed as part of the lsrslib[2] package and must be compiled with it. like, they don't do the solo thing. they come as a set 🔥

so here's the setup: 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. iconic behaviour honestly 👑

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 — precision queen, no rounding drama 💅

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. speed demon energy ⚡

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). fancy 💅

nashdemo is a simple template for lrsnash. it builds two 3x4 matrices A and B and computes their equilibria. a lil demo, a lil appetizer 🍓

heads up bestie: 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. slay 💅

---

🎀 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 — absolute legends, fr fr 💜

---

💜 See also 💜

lrslib(5)

---

okay that's the whole page bestie, you're fully caught up 🫶 this was lrsnash(1) from lrslib 7.3, dated January 2024 (version 2024.1.31) — go forth and find some equilibria, no one can stop you now ✨💖🎀