Two Algorithms for Computing Exact and Approximate Nash Equilibria in Bimatrix Games

In this paper, we first devise two algorithms to determine whether or not a bimatrix game has a strategically equivalent zero-sum game. If so, we propose an algorithm that computes the strategically equivalent zero-sum game. If a given bimatrix game is not strategically equivalent to a zero-sum game, we then propose an approach to compute a zero-sum game whose saddle-point equilibrium can be mapped to a well-supported approximate Nash equilibrium of the original game. We conduct extensive numerical simulation to establish the efficacy of the two algorithms.

Authors and Affiliations

1. The Ohio State University, Columbus, OH, 43210, USA

   Jianzong Pi & Abhishek Gupta

2. United States Military Academy, West Point, NY, 10996, USA

   Joseph L. Heyman

Corresponding author

Correspondence to Jianzong Pi .

Editors and Affiliations

1. Czech Technical University, Prague, Czech Republic

   Branislav Bošanský

2. Carnegie Mellon University, Pittsburgh, PA, USA

   Cleotilde Gonzalez

3. Johannes Kepler University Linz, Linz, Austria

   Stefan Rass

4. Singapore Management University, Singapore, Singapore

   Arunesh Sinha

A Some Auxiliary Results on \(\mathcal M_{m\times n}(\mathbb {R})\)

This appendix is based on Appendix A.1.1 of [12].

Theorem 6

For matrix \(M \in \mathbb R^{m\times n}\) with \(\texttt {rank}({M}) = r\). Let \(M_1 = M\), and

Define rank 1 matrices \(W_k := \boldsymbol{\mathbf {v}}_k \boldsymbol{\mathbf {u}}_k^\mathsf {T}= w_k^{-1}M_k\boldsymbol{\mathbf {x}}_k \boldsymbol{\mathbf {y}}_k^\mathsf {T}M_k\). Then, for any \(j > k\), \(\boldsymbol{\mathbf {v}}_k \not \in \texttt {ColSpan}(M_j)\) and \(\boldsymbol{\mathbf {u}}_k \not \in \texttt {ColSpan}(M_j^\mathsf {T})\).

Proof

By (2), we have \(M_{k+1} = M - \sum _{i=1}^{k}W_i = \sum _{i = k+1}^r W_i\). Then, [23, p. 69] implies \(\texttt {rank}({M_{k+1}}) = \texttt {rank}({M_k}) - 1\). Hence the result is proved.    \(\square \)

Theorem 7

If a matrix \(A \in \mathbb R^{m\times n}\) and \(A \not \in \mathcal M_{m\times n}(\mathbb R)\), then \(\mathcal {WZ}(A) \ne \emptyset \)

Proof

We can write \(A = M + \sum _{i=1}^k \boldsymbol{\mathbf {v}}_i \boldsymbol{\mathbf {u}}_i^\mathsf {T}\), where

1. (a)

   \(k = \texttt {rank}({A}) - \texttt {rank}({M})\),

2. (b)

   \(M = \boldsymbol{\mathbf {1}}_m\boldsymbol{\mathbf {u}}_o^\mathsf {T}+ \boldsymbol{\mathbf {v}}_0 \boldsymbol{\mathbf {1}}_n^\mathsf {T}\in \mathcal M_{m\times n}(\mathbb R)\), so \(\texttt {rank}({M}) \le 2\),

3. (c)

   For any \(i \in \{1, \dots , k\}\), \(\boldsymbol{\mathbf {v}}_i \not \in \texttt {ColSpan}(M)\) and \(\boldsymbol{\mathbf {u}}_i \not \in \texttt {ColSpan}(M^\mathsf {T})\),

4. (d)

   \(\left\{ \boldsymbol{\mathbf {v}}_i\right\} _{i = 1}^k\) and \(\left\{ \boldsymbol{\mathbf {u}}_i\right\} _{i = 1}^k\) are linearly independent.

Let \(\boldsymbol{\mathbf {w}}_0 = \boldsymbol{\mathbf {1}}_m\) and \(\boldsymbol{\mathbf {z}}_0 = \boldsymbol{\mathbf {1}}_n\), and construct orthogonal vectors such that

After the iteration, we have that

The last step is because \( \boldsymbol{\mathbf {w}}_i^\mathsf {T}\boldsymbol{\mathbf {v}}_j = \boldsymbol{\mathbf {u}}_j^\mathsf {T}\boldsymbol{\mathbf {z}}_i = 0 \) for any \(j < i\).    \(\square \)

Lemma 5

For any matrix \(M\in \mathcal {M}_{m\times n}(\mathbb {R})\):

1. 1.

   If \(\texttt {rank}({M})=2\), then \(\boldsymbol{\mathbf {1}}_m\in \texttt {ColSpan}(M)\) and \(\boldsymbol{\mathbf {1}}_n\in \texttt {ColSpan}(M^\mathsf {T})\). In addition, for all \(\boldsymbol{\mathbf {x}},\boldsymbol{\mathbf {y}}\) such that \(M\boldsymbol{\mathbf {x}}=\boldsymbol{\mathbf {1}}_m\),\(M^\mathsf {T}\boldsymbol{\mathbf {y}}=\boldsymbol{\mathbf {1}}_n\),\(\boldsymbol{\mathbf {1}}_n^\mathsf {T}\boldsymbol{\mathbf {x}}=0\),\(\boldsymbol{\mathbf {1}}_m^\mathsf {T}\boldsymbol{\mathbf {y}}=0\).

2. 2.

   If \(\texttt {rank}({M})=1\), then either \(\boldsymbol{\mathbf {1}}_m\in \texttt {ColSpan}(M)\), or \(\boldsymbol{\mathbf {1}}_n\in \texttt {ColSpan}(M^\mathsf {T})\) or both \(\boldsymbol{\mathbf {1}}_m\in \texttt {ColSpan}(M)\) and \(\boldsymbol{\mathbf {1}}_n\in \texttt {ColSpan}(M^\mathsf {T})\).

Proof

For Claim 1, \(\boldsymbol{\mathbf {1}}_m\in \texttt {ColSpan}(M)\) and \(\boldsymbol{\mathbf {1}}_n\in \texttt {ColSpan}(M^\mathsf {T})\) follows directly from \(\texttt {rank}({M})=2\). In addition, \(M\in \mathcal {M}_{m\times n}(\mathbb {R})\) and \(\texttt {rank}({M})=2\) implies that there exists \(\boldsymbol{\mathbf {v}}\ne \boldsymbol{\mathbf {0}}_n\) and \(\boldsymbol{\mathbf {u}}\ne \boldsymbol{\mathbf {0}}_m\) such that \(M=\boldsymbol{\mathbf {1}}_m\boldsymbol{\mathbf {u}}^\mathsf {T}+\boldsymbol{\mathbf {v}}\boldsymbol{\mathbf {1}}_n^\mathsf {T}\). Also since \(\texttt {rank}({M})=2\), we have that for all \(a\in \mathbb {R}\), \(\boldsymbol{\mathbf {v}}\ne a\boldsymbol{\mathbf {1}}_m\) since \(\boldsymbol{\mathbf {v}}\) and \(\boldsymbol{\mathbf {1}}_m\) must be linearly independent. Then, for all \(\boldsymbol{\mathbf {x}}\) such that \(M\boldsymbol{\mathbf {x}}=\boldsymbol{\mathbf {1}}_m\) we have that:

This implies \((\boldsymbol{\mathbf {1}}_n^\mathsf {T}\boldsymbol{\mathbf {x}})\boldsymbol{\mathbf {v}}=(1-\boldsymbol{\mathbf {u}}^\mathsf {T}\boldsymbol{\mathbf {x}})\boldsymbol{\mathbf {1}}_m\). Further, \(\boldsymbol{\mathbf {v}}\ne a\boldsymbol{\mathbf {1}}_m\) implies that the equation above is satisfied if and only if \(\boldsymbol{\mathbf {1}}_n^\mathsf {T}\boldsymbol{\mathbf {x}}=0\) and \(\boldsymbol{\mathbf {u}}^\mathsf {T}\boldsymbol{\mathbf {x}}=1\). To prove that for all \(\boldsymbol{\mathbf {y}}\) such that \(M^\mathsf {T}\boldsymbol{\mathbf {y}}=\boldsymbol{\mathbf {1}}_n\), \(\boldsymbol{\mathbf {1}}_m^\mathsf {T}\boldsymbol{\mathbf {y}}=0\) apply the same technique to \(M^\mathsf {T}\).

Claim 2 follows directly from \(\texttt {rank}({M})=1\).    \(\square \)

Lemma 6

For any matrix \(F\in \mathbb {R}^{m\times n}\), if there exists i, j such that \(F_{(i)}=\boldsymbol{\mathbf {0}}_n^\mathsf {T}\) and \(F^{(j)}=\boldsymbol{\mathbf {0}}_m\) then \(F\in \mathcal {M}_{m\times n}(\mathbb {R})\) if and only if \(F=\boldsymbol{\mathbf {0}}_{m\times n}\).

Proof

Clearly \(F=\boldsymbol{\mathbf {0}}_{m\times n}\) implies that \(F\in \mathcal {M}_{m\times n}(\mathbb {R})\) and that for all i, j \(F_{(i)}=\boldsymbol{\mathbf {0}}_n^\mathsf {T}\) and \(F^{(j)}=\boldsymbol{\mathbf {0}}_m\). Now, consider the forward direction and suppose that \(F\in \mathcal {M}_{m\times n}(\mathbb {R})\). Then from the definition of \(\mathcal {M}_{m\times n}(\mathbb {R})\), we have that \(\texttt {rank}({F})\le 2\). We will show that \(\texttt {rank}({F})=0\). \(F_{(i)}=\boldsymbol{\mathbf {0}}_n^\mathsf {T}\) implies that \(\boldsymbol{\mathbf {1}}_m\notin \texttt {ColSpan}(M)\) and \(F^{(j)}=\boldsymbol{\mathbf {0}}_m\) implies that \(\boldsymbol{\mathbf {1}}_n\notin \texttt {ColSpan}(M^\mathsf {T})\). Then, by Lemma 5 \(\texttt {rank}({F})\ne 1,2\). Therefore, \(\texttt {rank}({F})=0\) and \(F=\boldsymbol{\mathbf {0}}_{m\times n}\).    \(\square \)

Reprints and permissions

© 2021 Springer Nature Switzerland AG

Policies and ethics