\[ \text{Nash equilibrium} \quad + \quad \text{Polyhedral homotopy} \]

Start from the very very basic...

A "game" is a strategic interaction involving multiple "players", where each player's outcome depends on the choices of all players.

A\B	💎	📜	✂️
💎	0	-1	+1
📜	+1	0	-1
✂️	-1	+1	0

Normal form game

Pure vs mixed strategies

Mixed strategy: assignment of probabilities for pure strategies.

Totally mixed strategy: assignment of positive probabilities.

\[ \begin{aligned} \text{A's payoff} &= (\;0\;) \cdot a_1 \class{highlight}{\frac{1}{3}} + (-1) \cdot a_1 \class{highlight}{\frac{1}{3}} + (+1) \cdot a_1 \class{highlight}{\frac{1}{3}} \\ &+ (+1) \cdot a_2 \class{highlight}{\frac{1}{3}} + (\;0\;) \cdot a_2 \class{highlight}{\frac{1}{3}} + (-1) \cdot a_2 \class{highlight}{\frac{1}{3}} \\ &+ (-1) \cdot a_3 \class{highlight}{\frac{1}{3}} + (+1) \cdot a_3 \class{highlight}{\frac{1}{3}} + (\;0\;) \cdot a_3 \class{highlight}{\frac{1}{3}} \class{highlight}{=0} \end{aligned} \]

No way A can improve it.

Nash equilibrium: strategies $(a_1,a_2,a_3)$ and $(b_1,b_2,b_3)$ where neither can increase payoff by changing their strategy unilaterally.
J. Nash. Equilibrium points in n-person games. Proc. Natl. Acad. Sci. 36, 48-49 (1950).

$A,B,C$ play a non-cooperative game. Each have 2 pure strategies.

Three mixed strategies \[ \begin{aligned} A &: (a_1,a_2) \\ B &: (b_1,b_2) \\ C &: (c_1,c_2) \end{aligned} \] with \[ \begin{aligned} a_1 + a_2 &= 1 \\ b_1 + b_2 &= 1 \\ c_1 + c_2 &= 1 \\ \end{aligned} \]

Player A's view

There are 8 situations:

• A choose #1, B choose #1, C choose #1 ("111") Payoff: $A_{111}$
• A choose #1, B choose #1, C choose #2 ("112") Payoff: $A_{112}$
• A choose #1, B choose #2, C choose #1 ("121") Payoff: $A_{121}$
• A choose #1, B choose #2, C choose #2 ("122") Payoff: $A_{122}$
• A choose #2, B choose #1, C choose #1 ("211") Payoff: $A_{211}$
• ......
• ......
• A choose #2, B choose #2, C choose #2 ("222") Payoff: $A_{222}$

Payoff arrays

\[ B_{ijk} \; := \; \text{The payoff for situation } (ijk) \text{ for B} \]

\[ C_{ijk} \; := \; \text{The payoff for situation } (ijk) \text{ for C} \]

The game is encoded in $2 \times 2 \times 2$ arrays $A,B,C$.

Player A's payoff

\[ \text{The probability for } (ijk) \;=\; a_i \, b_j \, c_k \]

Payoff: \[ \begin{aligned} A_{111} a_1 b_1 c_1 &+ A_{112} a_1 b_1 c_2 + A_{121} a_1 b_2 c_1 + A_{122} a_1 b_2 c_2 + \\ A_{211} a_2 b_1 c_1 &+ A_{212} a_2 b_1 c_2 + A_{221} a_2 b_2 c_1 + A_{222} a_2 b_2 c_2 \end{aligned} \]

\[ \begin{aligned} \text{Player A's payoff} &= \sum_{i,j,k=1}^2 A_{ijk} \, a_i \, b_j \, c_k \\ \text{Player B's payoff} &= \sum_{i,j,k=1}^2 B_{ijk} \, a_i \, b_j \, c_k \\ \text{Player C's payoff} &= \sum_{i,j,k=1}^2 C_{ijk} \, a_i \, b_j \, c_k \end{aligned} \]

There are two aspects: The algebraic and the combinatorial.

\[ \sum_{i,j,k=1}^2 A_{ijk} \, a_i \, b_j \, c_k \ge \sum_{i,j,k=1}^2 A_{ijk} \, \class{highlight}{\overline{a}_i} \, b_j \, c_k \quad\text{for any } (\class{highlight}{\overline{a}_1},\class{highlight}{\overline{a}_2}) \in \Delta \]

In particular, this is true for $(1,0)$ and $(0,1)$.

\[ \begin{aligned} \alpha &= \sum_{i,j,k=1}^2 A_{ijk} \, a_i \, b_j \, c_k & \alpha &\ge \sum_{j,k=1}^2 A_{\class{highlight}{1}jk} \, b_j \, c_k \\ && \alpha &\ge \sum_{j,k=1}^2 A_{\class{highlight}{2}jk} \, b_j \, c_k \end{aligned} \]

Real solutions with $a_1,a_2,b_1,b_2,c_1,c_2 > 0$ correspond to totally mixed Nash equilibria.

\[ \overline{A}_{jk} = \text{Difference in payoff between two choices} \]

6 equations in 6 unknowns (payoff variables eliminated).

Real solutions with $a_1,a_2,b_1,b_2,c_1,c_2 > 0$ correspond to
totally mixed Nash equilibria.

Question: How to compute totally mixed Nash equilibria (in general) ?

Approach:

• Compute all nonzero complex solutions ($\mathbb{C}^*$-solutions)
• Numerical homotopy method (continuous deformation)
• Polyhedral homotopy of Huber & Sturmfels

Totally mixed Nash equilibria are defined by the equations \[ 0 = \overline{A}_{11} \, b_1 c_1 + \overline{A}_{12} \, b_1 c_2 + \overline{A}_{21} \, b_2 c_1 + \overline{A}_{22} \, b_2 c_2 \] \[ \begin{aligned} 0 &= \overline{B}_{11} a_1 c_1 + \overline{B}_{12} a_1 c_2 + \overline{B}_{21} a_2 c_1 + \overline{B}_{22} a_2 c_2 \\ 0 &= \overline{C}_{11} a_1 b_1 + \overline{C}_{12} a_1 b_2 + \overline{C}_{21} a_2 b_1 + \overline{C}_{22} a_2 b_2 \\ 1 &= a_1 + a_2 \\ 1 &= b_1 + b_2 \\ 1 &= c_1 + c_2 \end{aligned} \]

Harsanyi. Oddness of the number of equilibrium points: A new proof. Int. J. Game Theory 2, 235-250 (1973).

We consider the generic version

\[ \begin{aligned} 0 &= \class{highlight}{\overline{A}_{11}} \, b_1 c_1 + \class{highlight}{\overline{A}_{12}} \, b_1 c_2 + \class{highlight}{\overline{A}_{21}} \, b_2 c_1 + \class{highlight}{\overline{A}_{22}} \, b_2 c_2 \\ 0 &= \class{highlight}{\overline{B}_{11}} a_1 c_1 + \class{highlight}{\overline{B}_{12}} a_1 c_2 + \class{highlight}{\overline{B}_{21}} a_2 c_1 + \class{highlight}{\overline{B}_{22}} a_2 c_2 \\ 0 &= \class{highlight}{\overline{C}_{11}} a_1 b_1 + \class{highlight}{\overline{C}_{12}} a_1 b_2 + \class{highlight}{\overline{C}_{21}} a_2 b_1 + \class{highlight}{\overline{C}_{22}} a_2 b_2 \\ 1 &= a_1 + a_2 \\ 1 &= b_1 + b_2 \\ 1 &= c_1 + c_2 \end{aligned} \]

where highlight coefficients are randomly perturbed.

We considered the homotopy function $H: (\mathbb{C}^*)^6 \times [0,1] \to \mathbb{C}^6$, and the "paths" defined by $H = 0$. This is the polyhedral homotopy.

Complication: Near $t=0$, the paths escapes $(\mathbb{C}^*)^6$.

Can we "describe" the local behavior of the paths as $t \to 0$ ?

That means \[ H( \boldsymbol{a}_1(t), \boldsymbol{a}_2(t), \boldsymbol{b}_1(t), \boldsymbol{b}_2(t), \boldsymbol{c}_1(t), \boldsymbol{c}_2(t), t ) = 0 \]

Define \[ \mathbf{v} = \begin{bmatrix} \frac{\alpha_1}{m}, \frac{\alpha_2}{m}, \frac{\beta_1}{m}, \frac{\beta_2}{m}, \frac{\gamma_1}{m}, \frac{\gamma_2}{m}, 1 \end{bmatrix} \in \mathbb{Q}^6 \times \mathbb{Q} \]

Then \[ \operatorname{init}_{\mathbf{v}} H ( a_1, a_2, b_1, b_2, c_1, c_2, 1 ) = \mathbf{0} \] i.e., the leading coefficients form a $\mathbb{C}^*$-zero of the initial system.

Initial systems

\[ f(\mathbf{x}) = \sum_{\mathbf{a} \in S} \, c_{\mathbf{a}} \mathbf{x}^{\mathbf{a}} \quad\longrightarrow\quad \operatorname{init}_{\mathbf{v}} f = \sum_{\mathbf{a} \in (S)_{\mathbf{v}}} \, c_{\mathbf{a}} \mathbf{x}^{\mathbf{a}} \] where $(S)_\mathbf{v}$ is the subset of $S$ on which $\langle \cdot, \mathbf{v} \rangle$ is minimized.

\[ f = c_{00} \color{purple}{x^0 y^0} + c_{10} \color{green}{x^2 y^0} + c_{22} \color{blue}{x^2 y^2} + c_{12} \color{red}{x^1 y^2} \]

\[ \operatorname{init}_{\mathbf{v}} f(x,y) = c_{00} \color{purple}{x^0 y^0} \]

\[ \operatorname{init}_{\mathbf{v}} f(x,y) = c_{00} \color{purple}{x^0 y^0} + c_{12} \color{red}{x^1 y^2} \]

\[ \operatorname{init}_{\mathbf{v}} \begin{bmatrix} f_1 \\ \vdots \\ f_n \end{bmatrix} = \begin{bmatrix} \operatorname{init}_{\mathbf{v}} f_1 \\ \vdots \\ \operatorname{init}_{\mathbf{v}} f_n \end{bmatrix} \]

Recall that from the assumption we derived \[ \operatorname{init}_{\mathbf{v}} H ( a_1, a_2, b_1, b_2, c_1, c_2, 1 ) = \mathbf{0} \]

This requires very special $\mathbf{v}$.

For a "bad" choice of $\mathbf{v}$, $\operatorname{init}_{\mathbf{v}} H = \mathbf{0} \; \to$ \[ \begin{aligned} \class{lowlowlight}{ 0 } &= \class{highlight}{\overline{A}_{11} \, b_1 c_1 } + \class{lowlowlight}{ \overline{A}_{12} \, b_1 c_2 } + \class{lowlowlight}{ \overline{A}_{21} \, b_2 c_1 } + \class{lowlowlight}{ \overline{A}_{22} \, b_2 c_2 } \\ \class{lowlowlight}{ 0 } &= \class{highlight}{ \overline{B}_{11} \,a_1 c_1 } + \class{lowlowlight}{ \overline{B}_{12} \,a_1 c_2 } + \class{lowlowlight}{\overline{B}_{21} \,a_2 c_1 } + \class{lowlowlight}{\overline{B}_{22} \,a_2 c_2 } \\ \class{lowlowlight}{ 0 } &= \class{highlight}{ \overline{C}_{11} \,a_1 b_1 } + \class{lowlowlight}{\overline{C}_{12} \,a_1 b_2 } + \class{lowlowlight}{\overline{C}_{21} \,a_2 b_1 } + \class{lowlowlight}{ \overline{C}_{22} \,a_2 b_2 } \\ \class{lowlowlight}{1} &= \class{highlight}{ a_1 } + \class{lowlowlight}{a_2} \\ \class{lowlowlight}{1} &= \class{highlight}{ b_1 } + \class{lowlowlight}{b_2 } \\ \class{lowlowlight}{1} &= \class{highlight}{c_1} + \class{lowlowlight}{ c_2} \end{aligned} \]

$\operatorname{init}_{\mathbf{v}} H = \mathbf{0} \; \to$ has no solution in $(\mathbb{C}^*)^6$.

For one "good" choice of $\mathbf{v}$, $\operatorname{init}_{\mathbf{v}} H = \mathbf{0} \; \to$ \[ \begin{aligned} \class{lowlowlight}{0} &= \class{highlight}{ \overline{A}_{11} \, b_1 c_1 } + \class{lowlowlight}{\overline{A}_{12} \, b_1 c_2 } + \class{lowlowlight}{\overline{A}_{21} \, b_2 c_1 } + \class{highlight}{ \overline{A}_{22} \, b_2 c_2 } \\ \class{lowlowlight}{0} &= \class{lowlowlight}{\overline{B}_{11} \,a_1 c_1 } + \class{highlight}{ \overline{B}_{12} \,a_1 c_2 } + \class{lowlowlight}{\overline{B}_{21} \,a_2 c_1 } + \class{highlight}{ \overline{B}_{22} \,a_2 c_2 } \\ \class{lowlowlight}{0} &= \class{highlight}{ \overline{C}_{11} \,a_1 b_1 } + \class{highlight}{ \overline{C}_{12} \,a_1 b_2 } + \class{lowlowlight}{\overline{C}_{21} \,a_2 b_1 } + \class{lowlowlight}{\overline{C}_{22} \,a_2 b_2 } \\ \class{lowlowlight}{0} &= \class{highlight}{ a_1 } + \class{lowlowlight}{a_2} - \class{highlight}{1} \\ \class{lowlowlight}{0} &= \class{highlight}{ b_1 } + \class{lowlowlight}{b_2 } - \class{highlight}{1} \\ \class{lowlowlight}{0} &= \class{highlight}{ c_1} + \class{lowlowlight}{c_2} - \class{highlight}{1} \end{aligned} \]

• A system of binomials
• Has a solution in $(\mathbb{C}^*)^6$

\[ \text{``Good''} \;\Longrightarrow\; \mathbf{v} \in \bigcap_{i=1}^6 \mathbb{V}(\operatorname{Trop}(h_i)) \]

Another "good" choice of $\mathbf{v}$, $\operatorname{init}_{\mathbf{v}} H = \mathbf{0} \; \to$

• Also a system of binomials
• Also has one solution in $(\mathbb{C}^*)^6$

Exactly 2 "good" choices. They produce binomial systems

and

Their $\mathbb{C}^*$-solutions give us leading coefficients. Starting points of the "solution paths" can be computed.

Starting points of the "solution paths" can be computed.

"Tracking" these paths lead to two (totally mixed) Nash equilibria. Problem solved!

Revisiting our assumption

Why is this true?

• Newton-Puiseux Theorem
• Local Uniformizer
• Local Parametrization Theorem

Polyhedral homotopy for totally mixed Nash equilibria

Huber & Sturmfels. A polyhedral method for solving sparse polynomial systems. Math Comput 64, 1541-1555 (1995).

\[ \left\{ \begin{aligned} \class{lowlowlight}{0} &= \class{highlight}{ \overline{A}_{11} \, b_1 c_1 } + \class{lowlowlight}{\overline{A}_{12} \, b_1 c_2 } + \class{lowlowlight}{\overline{A}_{21} \, b_2 c_1 } + \class{highlight}{ \overline{A}_{22} \, b_2 c_2 } \\ \class{lowlowlight}{0} &= \class{lowlowlight}{\overline{B}_{11} \,a_1 c_1 } + \class{highlight}{ \overline{B}_{12} \,a_1 c_2 } + \class{lowlowlight}{\overline{B}_{21} \,a_2 c_1 } + \class{highlight}{ \overline{B}_{22} \,a_2 c_2 } \\ \class{lowlowlight}{0} &= \class{highlight}{ \overline{C}_{11} \,a_1 b_1 } + \class{highlight}{ \overline{C}_{12} \,a_1 b_2 } + \class{lowlowlight}{\overline{C}_{21} \,a_2 b_1 } + \class{lowlowlight}{\overline{C}_{22} \,a_2 b_2 } \\ \class{lowlowlight}{0} &= \class{highlight}{ a_1 } + \class{lowlowlight}{a_2} - \class{highlight}{1} \\ \class{lowlowlight}{0} &= \class{highlight}{ b_1 } + \class{lowlowlight}{b_2 } - \class{highlight}{1} \\ \class{lowlowlight}{0} &= \class{highlight}{ c_1} + \class{lowlowlight}{c_2} - \class{highlight}{1} \end{aligned} \right. \] \[ \left\{ \begin{aligned} \class{lowlowlight}{ 0 } &= \class{highlight}{ \overline{A}_{11} \, b_1 c_1 } + \class{lowlowlight}{\overline{A}_{12} \, b_1 c_2 } + \class{highlight}{ \overline{A}_{21} \, b_2 c_1 } + \class{lowlowlight}{\overline{A}_{22} \, b_2 c_2 } \\ \class{lowlowlight}{ 0 } &= \class{lowlowlight}{\overline{B}_{11} \,a_1 c_1 } + \class{lowlowlight}{\overline{B}_{12} \,a_1 c_2 } + \class{highlight}{ \overline{B}_{21} \,a_2 c_1 } + \class{highlight}{ \overline{B}_{22} \,a_2 c_2 } \\ \class{lowlowlight}{ 0 } &= \class{lowlowlight}{\overline{C}_{11} \,a_1 b_1 } + \class{highlight}{\overline{C}_{12} \,a_1 b_2 } + \class{highlight}{ \overline{C}_{21} \,a_2 b_1 } + \class{lowlowlight}{ \overline{C}_{22} \,a_2 b_2 } \\ \class{lowlowlight}{0} &= \class{highlight}{ a_1 } + \class{lowlowlight}{a_2} - \class{highlight}{1} \\ \class{lowlowlight}{0} &= \class{highlight}{ b_1 } + \class{lowlowlight}{b_2 } - \class{highlight}{1} \\ \class{lowlowlight}{ 0 } &= \class{highlight}{c_1} + \class{lowlowlight}{ c_2} - \class{highlight}{1} \end{aligned} \right. \]

Standard numerical "path trackers" can track these paths and produce totally mixed Nash equilibria.

Polyhedral homotopy method

Huber & Sturmfels. A polyhedral method for solving sparse polynomial systems. Math Comput 64, 1541-1555 (1995).

For a system of $n$ (Laurent) polynomials $F$

in $n$ variables $\mathbf{x} = (x_1,\ldots,x_n)$, where

• $\mathbf{x}^{\mathbf{a}} = x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ denotes a monomial
• $S_i$ is the support of $f_i$
• $c_{\mathbf{a}}$'s are nonzero complex coefficients...

the polyhedral homotopy method of Huber and Sturmfels is an efficient and stable numerical method for compute all $\mathbb{C}^*$-zeros.

For generic coefficients, all $\mathbb{C}^*$-solutions to $F = \mathbf{0}$ are isolated, and the total number is the BKK bound $\operatorname{MVol}(\operatorname{Newt}(f_1),\ldots,\operatorname{Newt}(f_n))$.

• $H$ is continuous
• $H(\mathbf{x},1) \equiv F(\mathbf{x})$
• As $t$ varies between 1 and 0, $H$ "deforms" the target system $F$

For generic coefficients, $\mathbb{C}^*$-solutions to $H = \mathbf{0}$ also move continuously forming "solution paths".

How to start ?

Near $t=0$, the paths may escape $(\mathbb{C}^*)^n$, but they have Puiseux series expansions \[ x_i = t^{\class{highlight}{\frac{\alpha_i}{m}}}(y_i + o(t)) \quad\text{for } i = 1,\ldots,n \]

The "exponent" vector \[ \begin{bmatrix} \class{highlight}{\frac{\alpha_1}{m}} & \cdots & \class{highlight}{\frac{\alpha_n}{m}} & 1 \end{bmatrix} \]

is a common inner normal vector of $n$ edges of the Newton polytopes of \[ h_i (\mathbf{x},t) = \sum_{\mathbf{a} \in S_i} c_{\mathbf{a}} \mathbf{x}^{\mathbf{a}} t^{\omega_i(\mathbf{a})} \quad\text{for } i = 1,\ldots,n \]

And the leading coefficients $y_1,\ldots,y_n$ satisfies \[ \operatorname{init}_{\mathbf{v}} (y_1,\ldots,y_n,1) = \mathbf{0}. \]

These initial systems are generically binomial systems and can be solved directly and efficiently. Path trackers can then take over......

Root counting

\[ \begin{aligned} 0 &= \overline{A}_{11} \, b_1 c_1 + \overline{A}_{12} \, b_1 c_2 + \overline{A}_{21} \, b_2 c_1 + \overline{A}_{22} \, b_2 c_2 \\ 0 &= \overline{B}_{11} \,a_1 c_1 + \overline{B}_{12} \,a_1 c_2 + \overline{B}_{21} \,a_2 c_1 + \overline{B}_{22} \,a_2 c_2 \\ 0 &= \overline{C}_{11} \,a_1 b_1 + \overline{C}_{12} \,a_1 b_2 + \overline{C}_{21} \,a_2 b_1 + \overline{C}_{22} \,a_2 b_2 \\ 1 &= a_1 + a_2 \\ 1 &= b_1 + b_2 \\ 1 &= c_1 + c_2 \end{aligned} \]

What is the generic root count?

Why 2 ?

Bernshtein-Kushnirenko-Khovanskii (BKK) bound

• $\operatorname{MVol}$ denotes the mixed volume function,
• $\operatorname{Newt}(f_i)$ is the Newton polytope of $f_i$, i.e., the convex hull of the exponent vectors in $f_i$ as points in $\mathbb{R}^n$.

This "BKK" bound is also the maximum number of isolated $\mathbb{C}^*$-solutions such a system can have for any choice of coefficients.

(This is the number of paths the polyhedral homotopy has to trace.)

Mixed volume

\[ \text{Minkowski sum: } A + B := \{ a + b \mid a \in A, b \in B \} \]

\[ \text{MVol}(A,B) = \text{Coef. of}\quad \lambda_1 \lambda_2 \quad \text{in}\quad \operatorname{vol}(\lambda_1 A + \lambda_2 B) \]

2-dimensional case

$\text{MVol}(A,B)$ is the coefficient of $\lambda_1 \lambda_2$ in $ \text{vol}(\lambda_1 A + \lambda_2 B) $

\[ \operatorname{MVol}(A,B) = \operatorname{vol}(A+B) - \text{vol}(A) - \text{vol}(B) \]

This formula can be generalized to higher dimensional (polarization formula), but this is not how we compute mixed volume in practice.

BKK bound for Nash equilibria

McKelvey, & McLennan. The Maximal Number of Regular Totally Mixed Nash Equilibria. J. Econ. Theory 72, 411-425

This maximum number can be attained by counting only the real Nash equilibria with $p_k^{(i)} \in (0,1)$.

The 3-player-2-strategies case

($n=3, d_i=2$) BKK bound equals the number of partitions \[ \{ a, b, c \} = B_1 \cup B_2 \cup B_3 \] such that $|B_1| = |B_2| = |B_3| = 1$

• $a \not\in B_1$
• $b \not\in B_2$
• $c \not\in B_3$

(Coincide with the number of derangements in this special case)

There are only two possibilities: \[ \begin{aligned} B_1 &= \{ c \} && & B_1 &= \{ b \} \\ B_2 &= \{ a \} &&\text{and} & B_2 &= \{ c \} \\ B_3 &= \{ b \} && & B_3 &= \{ a \} \end{aligned} \]

There are exactly 2 totally mixed Nash equilibria.