Nash Equilibrium of a Fixed-Sum Two-Player Game

Yoshihiro Tanaka

Faculty of Economics, Hokkaido University, Sapporo, Japan.

DOI: 10.4236/ajcm.2024.143017                

Abstract

It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems known as PPAD (Polynomial Parity Argument on Directed graphs), for which no polynomial-time solution methods are known, even for two-player games. This paper demonstrates that in fixed-sum two-player games (including zero-sum games), the Nash equilibrium forms a convex set, and has a unique expected payoff. Furthermore, these equilibria are Pareto optimal. Additionally, it is shown that the Nash equilibrium of fixed-sum two-player games can theoretically be found in polynomial time using the principal-dual interior point method, a solution method of linear programming.

Keywords

Nash Equilibrium, Fixed-Sum Two-Player Game, Principal-Dual Interior Point Method

1. Introduction

It has been well-established since Nash’s work [1] that the Nash equilibrium exists in mixed strategies for strategic games. However, the computational complexity of finding Nash equilibria belongs to the class of PPAD (Polynomial Parity Argument for Directed graphs) complete [2], for which no polynomial-time solution method is known, particularly for general, non-zero-sum games.

Bowling et al. [3] solved the Nash equilibrium for Poker—an incomplete information game and a repeated two-player zero-sum game—using an approximate computation method.

Monderer and Shapley [4] revealed that potential games consistently have Nash equilibria in pure strategies. Additionally, Moulin [5] and Friedman [6] examined the properties of Nash equilibrium in mixed strategies for non-zero-sum two-player games when the games are strictly competitive.

It is well-known that a zero-sum two-player game can be formulated as a pair of linear programming problems. Although linear programming problems are generally solved efficiently using the Simplex method, which moves along the vertices of the feasible polyhedron, there are rare instances where problems cannot be solved in polynomial time. To address this, various interior-point methods, which traverse the interior of the feasible polyhedron, have been developed since the mid-1980s. Among these, the primal-dual interior-point method, proposed by Kojima et al. [7] and others, which simultaneously solves both the primal and dual problems, is considered a powerful approach.

This study first indicates that for a fixed-sum two-player game, the Nash equilibrium can be efficiently solved in polynomial time using the principal-dual interior point method for linear programming. Furthermore, the study reveals that the Nash equilibrium forms a convex set in the mixed strategy for fixed-sum two-player games and that all Nash equilibria yield unique expected payoffs. Elementary computational experiments demonstrate the correctness of the methods presented.

2. Formulation

The Nash equilibrium is defined as $\left(\overline{x},\overline{y}\right)\in {\text{Δ}}^{m-1}\times {\text{Δ}}^{n-1}$ (where ${\text{Δ}}^d$ denotes a d-simplex), which satisfies

${\overline{x}}^{\text{T}}A\overline{y}\ge x^{\text{T}}A\overline{y}$, $\forall x\in {\text{Δ}}^{m-1}$ (1)

${\overline{x}}^{\text{T}}B\overline{y}\ge {\overline{x}}^{\text{T}}By$, $\forall y\in {\text{Δ}}^{n-1}$ ,

for the non-zero-sum two-player game $\left(A,B\right)$ , where A and B are the payoff matrices of the two players.

Generally, the computational complexity of finding Nash equilibria belongs to a class of PPAD complete [2], for which no polynomial-time solution method is known, even in two-person games.

The fixed-sum two-player game, including the zero-sum two-player games, can be formalized as a linear programming problem, which can be solved in polynomial time.

We convert a fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ , where p is the sum of the payoffs of the two players, and $E=\left(e_{ij}\right)$ , $e_{ij}=1$ , $i=1,\cdots ,m$ , $j=1,\cdots ,n$ , to a zero-sum two-player game $\left(A,-A\right)$ , by subtracting $\frac{p}{2}$ from all the entries. Let x and y denote the mixed strategy of player 1 and player 2, respectively, and 1 be the vector ${\left(1,\cdots ,1\right)}^{\text{T}}$ .

Nash equilibrium is also referred to as “equilibrium,” particularly in the zero-sum two-player games.

In a zero-sum game $\left(A,-A\right)$ , player 2’s maximin strategy is equivalent to their minimax strategy.

The maximin strategy for player 1 is defined as

$\begin{array}{l}\underset{x,v_1}{\text{maximize}}{v}_1\\ \text{subject}\text{to}{A}^{\text{T}}x\ge v_1{1}_n\\ {\displaystyle {\sum }_{i=1}^m{x}_i}=1,x_i\ge 0,i=1,\cdots ,m,\end{array}$ (2)

where x represents a mixed strategy.

The maximin strategy for player 2 is:

$\begin{array}{l}\underset{y,v_2}{\text{maximize}}{v}_2\\ \text{subject}\text{to}\left(-A\right)y\ge v_2{1}_m\\ {\displaystyle {\sum }_{i=1}^n{y}_i}=1,y_i\ge 0,i=1,\cdots ,n,\end{array}$

where y represents a mixed strategy.

Specifically,

$\begin{array}{l}\underset{y,v_2}{\text{minimize}}-v_2\\ \text{subject}\text{to}Ay\le v_2{1}_m\\ {\displaystyle {\sum }_{i=1}^n{y}_i}=1,y_i\ge 0,i=1,\cdots ,n,\end{array}$ (3)

which is known as the minimax strategy.

Therefore, the Nash equilibrium $\left(\overline{x},\overline{y}\right)$ is obtained by solving linear programming problems (2) and (3).

Theorem 1. For a fixed-sum two-person game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ , there exists a Nash equilibrium $\left(\overline{x},\overline{y}\right)$ , which is the solution to the linear programming problems (2) and (3), and can be obtained in polynomial time in $m,n$ . In this case, the payoffs of the two players are $\left({\overline{x}}^{\text{T}}A\overline{y}+\frac{p}{2},\frac{p}{2}-{\overline{x}}^{\text{T}}A\overline{y}\right)$.

Proof. First, we show that $\left(\overline{x},{\overline{v}}_1\right)$ , the solution of (2), and $\left(\overline{y},{\overline{v}}_2\right)$ , the solution of (3), exist for the zero-sum two-player game $\left(A,-A\right)$ .

(2) is similar to

$\begin{array}{l}\underset{x,{\xi }_1,{\xi }_2}{\text{minimize}}{\xi }_1-{\xi }_2\\ \text{subject}\text{to}{A}^{\text{T}}x+\left({\xi }_1-{\xi }_2\right)1_n\ge 0\\ 1_m^{\text{T}}x\ge 1\\ -1_m^{\text{T}}x\ge -1\\ x_i\ge 0,i=1,\cdots ,m,{\xi }_1,{\xi }_2\ge 0.\end{array}$ (4)

The duality problem of (4) can be expressed as

$\begin{array}{l}\underset{y,{\eta }_1,{\eta }_2}{\text{maximize}}{\eta }_1-{\eta }_2\\ \text{subject}\text{to}Ay+\left({\eta }_1-{\eta }_2\right)1_m\le 0\\ -1_n^{\text{T}}y\le -1\\ 1_n^{\text{T}}y\le 1\\ y_i\ge 0,i=1,\cdots ,n,{\eta }_1,{\eta }_2\ge 0.\end{array}$ (5)

(3) is also a dual problem of (2) by considering that $v_2=-\left({\eta }_1-{\eta }_2\right)$ . Note that (4) has a bounded optimal solution $\left(\overline{x},\overline{\xi }\right)$ because $\overline{x}\in {\Delta }^{m-1}$ . Therefore, from the strong duality theorem of linear programming, there exist bounded solutions $\left(\overline{x},\overline{\xi }\right)$ and $\left(\overline{y},\overline{\eta }\right)$ , and $\left(-{\overline{v}}_1=\right){\overline{\xi }}_1-{\overline{\xi }}_2={\overline{\eta }}_1-{\overline{\eta }}_2\left(={\overline{v}}_2\right)$ , i.e. ${\overline{v}}_1+{\overline{v}}_2=0$ .

Noting that

$x^{\text{T}}\left(\frac{p}{2}E\right)y=\frac{p}{2}$ , $\forall x\in {\text{Δ}}^{m-1}$ , $\forall y\in {\text{Δ}}^{n-1}$ ,

we have (1) is the same as

${\overline{x}}^{\text{T}}\left(A+\frac{p}{2}E\right)\overline{y}\ge x^{\text{T}}\left(A+\frac{p}{2}E\right)\overline{y}$, $\forall x\in {\text{Δ}}^{m-1}$

${\overline{x}}^{\text{T}}\left(\frac{p}{2}E-A\right)\overline{y}\ge {\overline{x}}^{\text{T}}\left(\frac{p}{2}E-A\right)y$, $\forall y\in {\text{Δ}}^{n-1}$ .

Thus, the Nash equilibrium $\left(\overline{x},\overline{y}\right)$ of the zero-sum two-player game also serves as a Nash equilibrium for the fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ , and can be obtained by solving the linear programming problem (2) and (3).

The linear programming problem can be solved using polynomial time methods such as those discussed in [8], which validates this approach.

In this case, the payoffs for the two players are $\left({\overline{x}}^{\text{T}}A\overline{y}+\frac{p}{2},\frac{p}{2}-{\overline{x}}^{\text{T}}A\overline{y}\right)$. □

Note that it is not always the case that $\overline{v}={\overline{v}}_1={\overline{v}}_2=0$ in any zero-sum two-player game $\left(A,-A\right)$ , as is evident from the case that ${\overline{v}}_1=1$ , ${\overline{v}}_2=-1$ when $A=E$ .

Consider the following definition:

Definition. A fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ is assumed to be symmetric if $A^{\text{T}}=-A$ .

Example 1. Rock-Paper-Scissors

$A=\left(\begin{array}{ccc}0& -1& 1\\ 1& 0& -1\\ -1& 1& 0\end{array}\right)$ , $\left({\overline{x}}^{\text{T}},{\overline{y}}^{\text{T}}\right)=\left(\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)\right)$, $\overline{v}=0$

Notably, in a symmetric fixed-sum two-player game, the condition $n=m$ holds by definition.

Competitions are typically symmetric zero-sum two-player games, such as Rock-Paper-Scissors, which represent a broad class of games.

In symmetric fixed-sum two-player games, solving only one linear programming problem is sufficient to obtain a Nash equilibrium solution.

Theorem 2. A symmetric fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ contains the Nash equilibrium $\left(\overline{x},\overline{x}\right)\in \left(\overline{x},\overline{y}\right)$ , where $\overline{x}$ contains the solution to the linear programming problem (2). In this case, the payoffs of both players are $\left(\frac{p}{2},\frac{p}{2}\right)$ .

Proof. In a symmetric fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ , $\left(\overline{x},{\overline{v}}_1\right)$ is the solution of (2) ($n=m$ ), and $\left(\overline{y},{\overline{v}}_2\right)$ is a solution of (3) ($n=m$ ).Note that (2) is a solution of the fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ , then (2) and (3) are equivalent for $A^{\text{T}}=-A$ . Thus, $\overline{y}=\overline{x}$ , since (2) and (3) are the same problem.

In this case, the payoffs of the two players are $\left({\overline{x}}^{\text{T}}A\overline{y}+\frac{p}{2},\frac{p}{2}-{\overline{x}}^{\text{T}}A\overline{y}\right)=\left({\overline{x}}^{\text{T}}A\overline{x}+\frac{p}{2},{\overline{x}}^{\text{T}}{A}^{\text{T}}\overline{x}+\frac{p}{2}\right)$. Now that ${\overline{x}}^{\text{T}}A\overline{x}={\overline{x}}^{\text{T}}{A}^{\text{T}}\overline{x}=0$, since ${\overline{x}}^{\text{T}}A\overline{x}+{\overline{x}}^{\text{T}}{A}^{\text{T}}\overline{x}=0$ and ${\left({\overline{x}}^{\text{T}}A\overline{x}\right)}^{\text{T}}={\overline{x}}^{\text{T}}{A}^{\text{T}}\overline{x}$. Hence, the payoffs are $\left(\frac{p}{2},\frac{p}{2}\right)$ . □

Many efficient general-purpose libraries, such as Python’s PuLP, that implement polynomial-time methods for linear programming problems exist. These methods can effectively handle large scale problems with tens of thousands of strategies.

The convexity of Nash equilibria in zero-sum two-player games was examined by Friedman [6] in strictly competitive games where $m=n$ .

This study extends the analysis to a more general setting.

Theorem 3. The Nash equilibrium of a finite-sum two-player game is a convex set of ${ℝ}^{m+n}$ and any solution of the Nash equilibrium determines the unique expected payoffs.

Proof. $\left(\begin{array}{c}x\\ v\end{array}\right)$ of (2), which satisfies $A^{\text{T}}x\le v{1}_n$ is a convex polyhedron in ${ℝ}^{m+1}$ . On the other hand, $\left\{x|x_i\ge 0,i=1,\cdots ,m,{\displaystyle {\sum }_i{x}_i}=1\right\}$ is ${\text{Δ}}_{m-1}\subset {ℝ}^{m+1}$ (($m-1$ )-simplex).

Their common part $S\subset {ℝ}^{m+1}$ is a bounded convex set in ${\text{Δ}}_{m-1}$ .

Therefore, as the solution set $P^{*}$ of (2) is the intersection of the convex set S and the support hyperplane $\left(0,\cdots ,0,1\right)\left(\begin{array}{c}x\\ v_1\end{array}\right)={\overline{v}}_1$ , it is a convex set in ${ℝ}^{m+1}$ .

Thus, $\overline{X}=\left\{x|\left(\begin{array}{c}x\\ {\overline{v}}_1\end{array}\right)\in P^{\text{*}}\right\}\subset {ℝ}^{m+1}$ is also a convex set.

Similarly, $\overline{Y}=\left\{y|\left(\begin{array}{c}y\\ {\overline{v}}_2\end{array}\right)\in D^{*}\right\}\subset {ℝ}^{n+1}$ is also a convex set for the solution set $D^{*}$ of (3).

Thus, $\left(\begin{array}{c}\overline{x}\\ \overline{y}\end{array}\right)\in \overline{X}\times \overline{Y}\subset {ℝ}^{m+n}$ is a convex set.

As discussed in Theorem 1, $\overline{v}={\overline{v}}_1=-{\overline{v}}_2$ . Therefore, the expected payoff of each is uniquely determined. □

Example 2. Zero-sum two-player game

$A=\left(\begin{array}{ccc}0& -1& 1\\ 1& 0& -1\\ -1& -1& -1\end{array}\right)$ , $\left({\overline{x}}^{\text{T}},{\overline{y}}^{\text{T}}\right)=\left(\left(\frac{1}{3},\frac{2}{3},0\right),\left(0,\frac{2}{3},\frac{1}{3}\right)\right)$, and $\overline{v}=-\frac{1}{3}$

Example 3. Non-fixed-sum two-player game

$\left(A,B\right)=\left(\begin{array}{cc}\left(2,2\right)& \left(1,3\right)\\ \left(3,1\right)& \left(0,0\right)\end{array}\right)$ ,

$\left({\overline{x}}^{\text{T}},{\overline{y}}^{\text{T}}\right)\in \left\{\left(\left(1,0\right),\left(0,1\right)\right),\left(\left(\frac{1}{2},\frac{1}{2}\right),\left(\frac{1}{2},\frac{1}{2}\right)\right),\left(\left(0,1\right),\left(1,0\right)\right)\right\}$

The solution is not a convex set and $\left({\overline{v}}_1,{\overline{v}}_2\right)=\left\{\left(1,3\right),\left(\frac{3}{2},\frac{3}{2}\right),\left(3,1\right)\right\}$ , respectively.

In a fixed-sum two-player game, as specified in Theorem 3, the Nash equilibrium solution forms a convex set; however, it may not be unique (e.g., when $A=O$ ). However, in a zero-sum two-player game, by definition, any Nash equilibrium solution is Pareto optimal. Furthermore, Theorem 3 indicates that any solution has a unique expected payoff, making all Nash equilibria equally desirable.

3. Solving a Fixed-Sum Two-Player Game

In non-symmetric general finite-sum two-player games, solving the Nash equilibrium requires addressing both problems (2) and (3). Therefore, we consider applying the primal-dual interior point method, which has been extended for use in linear programming, convex programming, and positive semi-definite programming.

In the primal-dual interior point method (see [9]), the primal linear programming problem is formulated as

$\begin{array}{l}\underset{x}{\text{minimize}}{c}^{\text{T}}x\\ \text{subject}\text{to}Ax=b\\ x_i\ge 0,i=1,\cdots ,m,\end{array}$ (6)

where $c,x\in {ℝ}^n$ , A: $m\times n$ matrix, and $b\in {ℝ}^m$ . The dual problem to (6) is

$\begin{array}{l}\underset{y,z}{\text{maximize}}{b}^{\text{T}}y\\ \text{subject}\text{to}{A}^{\text{T}}y+z=c\\ z_i\ge 0,i=1,\cdots ,n,\end{array}$ (7)

where $y\in {ℝ}^m$ , $z\in {ℝ}^n$ . The duality gap is:

$x^{\text{T}}z=x^{\text{T}}\left(c-A^{\text{T}}y\right)=c^{\text{T}}x-{\left(Ax\right)}^{\text{T}}y=c^{\text{T}}x-b^{\text{T}}y$

The optimal solution $\left(x,y,z\right)$ of (6) and (7) is obtained as the solution of the following equations:

$\{\begin{array}{l}Xz=0\\ Ax=b\\ A^{\text{T}}y+z=c\\ x\ge 0,z\ge 0,\end{array}$ (8)

where $X=\text{diag}\left(x\right)$ .

The primal-dual interior point method considers the following system of equations

$\left(\begin{array}{c}Xz-v\\ Ax-b\\ A^{\text{T}}y+z-c\end{array}\right)=0$ .(9)

If we consider the Newton method as $v=v^k\to 0$ , the search direction is obtained as a solution of

$\left(\begin{array}{ccc}{Z}_k& 0& X_k\\ A& 0& 0\\ 0& A^{\text{T}}& I\end{array}\right)\left(\begin{array}{c}\text{Δ}{x}^k\\ \text{Δ}{y}^k\\ \text{Δ}{z}^k\end{array}\right)=-\left(\begin{array}{c}{X}_k{z}^k-v^k\\ A{x}^k-b\\ A^{\text{T}}{y}^k+z^k-c\end{array}\right)$ ,(10)

where $Z_k=\text{diag}\left(z_k\right)$ , $X_k=\text{diag}\left(x_k\right)$ .

Subsequently, the iteration process is

$\left(\begin{array}{c}{x}^{k+1}\\ y^{k+1}\\ z^{k+1}\end{array}\right)=\left(\begin{array}{c}{x}^k+{\alpha }_P^k\Delta x^k\\ y^k+{\alpha }_D^k\text{Δ}{y}^k\\ z^k+{\alpha }_D^k\text{ Δ}{z}^k\end{array}\right)$ ,(11)

where ${\alpha }_P^k$ and ${\alpha }_D^k$ are step widths.

The algorithm can be written as follows:

Algorithm PD

Input: $\left(x^0,y^0,z^0\right)$

Iteration ($k\ge 0$ )

1. Set $v^k$ and find the solution $\left(\text{Δ}{x}^k,\text{Δ}{y}^k,\text{Δ}{z}^k\right)$ of (10).

2. By (11), we obtain $\left(x^{k+1},y^{k+1},z^{k+1}\right)$ .

3. If the convergence condition is satisfied, then $K\leftarrow k$ . Stop.

4. $k\leftarrow k+1$ . Go to 1.

Output: $\left(x^K,y^K,z^K\right)$

Now let us consider its application to a fixed-sum two-player game.

We introduce a slack variable to (4).

$\begin{array}{l}\underset{x,{\xi }_1,{\xi }_2,s}{\text{minimize}}{\xi }_1-{\xi }_2\\ \text{subject}\text{to}\left(\begin{array}{cccc}{A}^{\text{T}}& 1_n& -1_n& -I_n\\ -1_m^{\text{T}}& 0& 0& 0\end{array}\right)\left(\begin{array}{c}x\\ {\xi }_1\\ {\xi }_2\\ s\end{array}\right)=\left(\begin{array}{c}0\\ ⋮\\ 0\\ -1\end{array}\right)\\ x_i\ge 0,i=1,\cdots ,m,{\xi }_1,{\xi }_2\ge 0,s_j\ge 0,j=1,\cdots ,n.\end{array}$ (12)

The dual problem to (12) is

$\begin{array}{l}\underset{y,\eta ,z}{\text{maximize}}-\eta \\ \text{subject}\text{to}\left(\begin{array}{cc}A& -1_m\\ 1_n^{\text{T}}& 0\\ -1_n^{\text{T}}& 0\\ -I_n& 0\end{array}\right)\left(\begin{array}{c}y\\ \eta \end{array}\right)+\mathcal{z}=\left(\begin{array}{c}0\\ ⋮\\ 0\\ 1\\ -1\\ 0\\ ⋮\\ 0\end{array}\right)\\ {\mathcal{z}}_i\ge 0,i=1,\cdots ,m+n+2.\end{array}$ (13)

We denote

$\mathcal{A}=\left(\begin{array}{cccc}{A}^{\text{T}}& 1_n& -1_n& -I_n\\ -1_m^{\text{T}}& 0& 0& 0\end{array}\right)$ , $\mathcal{x}=\left(\begin{array}{c}x\\ {\xi }_1\\ {\xi }_2\\ s\end{array}\right)$ , $b=\left(\begin{array}{c}0\\ ⋮\\ 0\\ -1\end{array}\right)$ , $\mathcal{y}=\left(\begin{array}{c}y\\ \eta \end{array}\right)$ , $c=\left(\begin{array}{c}0\\ ⋮\\ 0\\ 1\\ -1\\ 0\\ ⋮\\ 0\end{array}\right)$ . (14)

The necessary and sufficient conditions for the main problem (12) and the dual problem (13) to be optimal solutions are

$\{\begin{array}{l}\mathcal{X}\mathcal{z}=0\\ \mathcal{A}\mathcal{x}=b\\ {\mathcal{A}}^{\text{T}}\mathcal{y}+\mathcal{z}=c\\ \mathcal{x}\ge 0,\mathcal{z}\ge 0,\end{array}$ (15)

where $\mathcal{X}=\text{diag}\left(\mathcal{x}\right)$ , $\mathcal{x},\mathcal{z}\in {ℝ}^{\tilde{n}}$ , $\tilde{n}=m+n+2$ .

Therefore, the primal-dual interior point method can be applied.

We define L as a measure of the length of the input data [8], namely

$\begin{array}{l}L={\displaystyle {\sum }_{i,j}\lceil {\log }_2\left(\left|a_{ij}\right|+1\right)\rceil }+{\displaystyle {\sum }_i\lceil {\log }_2\left(\left|b_i\right|+1\right)\rceil }+{\displaystyle {\sum }_j\lceil {\log }_2\left(\left|c_j\right|+1\right)\rceil }\\ +\lceil {\log }_2\left(n+1\right)\rceil +\lceil {\log }_2\left(m+1\right)\rceil +\left(nm+n+m+1\right).\end{array}$ (16)

Theorem 4. The Nash equilibrium $\left(\overline{x},\overline{y}\right)$ of the fixed-sum two-player game can be obtained by solving (15) using the sequence tracking method of the primal-dual interior point method in $O\left(\sqrt{m+n}{L}^{\prime }\right)$ iterations, where $L^{\prime }$ is a measure of the length of the input data to (12).

Proof. In the sequence tracking method of Mizuno [10], which is part of the primal-dual interior point method, it has been proved that the solutions of the primal linear programming problem (6) and the dual problem (7) can be obtained in $O\left(\sqrt{n}L\right)$ iterations.

For the Nash equilibrium, the solutions of (12) and (13) can be obtained in $O\left(\sqrt{m+n}{L}^{\prime }\right)$ iterations, given that $n\leftarrow m+n+2$ . □

Considering that the computational effort of each iteration of the primal-dual interior point method primarily involves solving a simultaneous linear equation to determine the search direction, and given that this can be done in polynomial time, the Nash equilibrium $\left(\overline{x},\overline{y}\right)$ can be obtained in polynomial time.

4. Computational Results

The study performed elementary computational experiments on a fixed-sum two-player game $\left(A+\frac{p}{2}E,\frac{p}{2}E-A\right)$ . It solved the Nash equilibrium of the following example where A is not a skew-symmetric matrix.

Example 4. A fixed-sum two-player game

$\left(A+E,E-A\right)=\left(\begin{array}{ccc}\left(1,1\right)& \left(0,2\right)& \left(2,0\right)\\ \left(2,0\right)& \left(1,1\right)& \left(0,2\right)\\ \left(0,2\right)& \left(0,2\right)& \left(0,2\right)\end{array}\right)$

Note that $A=\left(\begin{array}{ccc}0& -1& 1\\ 1& 0& -1\\ -1& -1& -1\end{array}\right)$ : Example 2, where

$\left({\overline{x}}^{\text{T}},{\overline{y}}^{\text{T}}\right)=\left(\left(\frac{1}{3},\frac{2}{3},0\right),\left(0,\frac{2}{3},\frac{1}{3}\right)\right)$.

The primal-dual interior point methods discussed in the previous section include the affine scaling method, path-following method, potential reduction method, and others.

The primal-dual path following algorithm is used in this section for efficiency reasons (see [11]), and is coded in Python and executed on a Windows PC.

Consider the following system of equations:

$\left(\begin{array}{c}\mathcal{X}\mathcal{z}-v\\ \mathcal{A}\mathcal{x}-b\\ {\mathcal{A}}^{\text{T}}\mathcal{y}+\mathcal{z}-c\end{array}\right)=0$ (17)

This system of equations with $v=0$ satisfies all constraints (15) except the sign of $\mathcal{x}$ and $\mathcal{z}$ . Following Lustig et al. [12], the study employs $v=\sigma \mu 1_{\tilde{n}}$ , where $\sigma =0.01$ , which was determined in an ad hoc manner, and $\mu$ is set to $\mu =\frac{1}{\tilde{n}}{\displaystyle {\sum }_{i=1}^{\tilde{n}}{\mathcal{x}}_i{\mathcal{z}}_i}=\frac{1}{\tilde{n}}{\mathcal{x}}^{\text{T}}\mathcal{z}$ as the minimization of ${\Vert \mathcal{X}\mathcal{z}-\mu 1_{\tilde{n}}\Vert }^2$ .

Newton Direction $\left(\text{Δ}{\mathcal{x}}^k,\text{Δ}{\mathcal{y}}^k,\text{Δ}{\mathcal{z}}^k\right)$ is obtained by solving

$\left(\begin{array}{ccc}{\mathcal{Z}}_k& 0& {\mathcal{X}}_k\\ \mathcal{A}& 0& 0\\ 0& {\mathcal{A}}^{\text{T}}& I\end{array}\right)\left(\begin{array}{c}\text{Δ}{\mathcal{x}}^k\\ \text{Δ}{\mathcal{y}}^k\\ \text{Δ}{\mathcal{z}}^k\end{array}\right)=-\left(\begin{array}{c}{\mathcal{X}}_k{\mathcal{z}}^k-\sigma {\mu }^k{1}_{\tilde{n}}\\ \mathcal{A}{\mathcal{x}}^k-b\\ {\mathcal{A}}^{\text{T}}{\mathcal{y}}^k+{\mathcal{z}}^k-c\end{array}\right)$,(18)

where ${\mathcal{X}}_k=\text{diag}\left({\mathcal{x}}^k\right)$ and ${\mathcal{Z}}_k=\text{diag}\left({\mathcal{z}}^k\right)$ .

We denote the residuals for complementarity, linear constraints on the main problem, and linear constraints on the dual problem by $r_c$ , $r_p$ , and $r_d$ , respectively.

Then, the right-hand side of (18) can be expressed as

${\mathcal{Z}}_k\text{Δ}{\mathcal{x}}^k+{\mathcal{X}}_k\text{Δ}{\mathcal{z}}^k=r_c$

$\mathcal{A}\text{Δ}{\mathcal{x}}^k=r_p$

${\mathcal{A}}^{\text{T}}\text{Δ}{\mathcal{y}}^k+\text{Δ}{\mathcal{z}}^k=r_d$ .

This allows us to calculate the following in this order:

$\text{Δ}{\mathcal{y}}^k={\left(\mathcal{A}{\mathcal{Z}}_k^{-1}{\mathcal{X}}_k{\mathcal{A}}^{\text{T}}\right)}^{-1}\left(r_p-\mathcal{A}{\mathcal{Z}}_k^{-1}\left(r_c-{\mathcal{X}}_k{r}_d\right)\right)$

$\text{Δ}{\mathcal{z}}^k=r_d-{\mathcal{A}}^{\text{T}}\text{Δ}{\mathcal{y}}^k$ (19)

$\text{Δ}{\mathcal{x}}^k={\mathcal{Z}}_k^{-1}\left(r_c-{\mathcal{X}}_k\text{Δ}{\mathcal{z}}^k\right)$ .

A line search is performed using

${\alpha }_p^k=\underset{i}{\min }-\frac{{\mathcal{x}}_i^k}{\text{Δ}{\mathcal{x}}_i^k}$ , if $-\frac{{\mathcal{x}}_i^k}{\text{Δ}{\mathcal{x}}_i^k}<0$

${\alpha }_d^k=\underset{i}{\min }-\frac{{\mathcal{z}}_i^k}{\text{Δ}{\mathcal{z}}_i^k}$ , if $-\frac{{\mathcal{z}}_i^k}{\text{Δ}{\mathcal{z}}_i^k}<0$

${\alpha }^k=\min \left\{0.95{\alpha }_p^k,0.95{\alpha }_d^k,1\right\}$

so that

${\mathcal{x}}^k+{\alpha }^k\text{Δ}{\mathcal{x}}^k>0$

${\mathcal{z}}^k+{\alpha }^k\text{Δ}{\mathcal{z}}^k>0$ .

Subsequently, the iteration step is

$\left(\begin{array}{c}{\mathcal{x}}^{k+1}\\ {\mathcal{y}}^{k+1}\\ {\mathcal{z}}^{k+1}\end{array}\right)=\left(\begin{array}{c}{\mathcal{x}}^k\\ {\mathcal{y}}^k\\ {\mathcal{z}}^k\end{array}\right)+{\alpha }^k\left(\begin{array}{c}\text{Δ}{\mathcal{x}}^k\\ \text{Δ}{\mathcal{y}}^k\\ \text{Δ}{\mathcal{z}}^k\end{array}\right)$ (20)

The algorithm can be written as follows:

Algorithm 1

Input: ${\mathcal{x}}^0=1$ , ${\mathcal{y}}^0=0$ , ${\mathcal{z}}^0=1$

Iteration ($k\ge 0$ )

1. Set $v^k$ . Calculate the solution $\left(\text{Δ}{\mathcal{x}}^k,\text{Δ}{\mathcal{y}}^k,\text{Δ}{\mathcal{z}}^k\right)$ by (19).

2. By (20), we obtain $\left({\mathcal{x}}^{k+1},{\mathcal{y}}^{k+1},{\mathcal{z}}^{k+1}\right)$ .

3. If the convergence condition is satisfied, then $K\leftarrow k$ . Stop.

4. $k\leftarrow k+1$ . Go to 1.

Output: $\left({\mathcal{x}}^K,{\mathcal{y}}^K,{\mathcal{z}}^K\right)$

The following is a summary of the results of the study.

Table 1 summarizes the sequence $\left(x^k,y^k\right)$ generated by Algorithm 1 to solve the Nash equilibrium in Example 4.

Table 1. Solution by the principal-dual interior point method.

k	x1	x2	x3	y1	y2	y3
0	1.0	1.0	1.0	0.0	0.0	0.0
1	0.6623576	0.6623576	0.1415717	−0.1125475	0.7458808	0.3166667
2	0.4368808	0.5696124	0.0509516	−0.0040950	0.7077344	0.2938607
3	0.3520076	0.6394974	0.0180646	0.0008768	0.6956012	0.3024998
4	0.3330301	0.6650078	0.0030526	0.0002386	0.6716897	0.3278449
5	0.3332779	0.6665529	0.0002351	0.0000310	0.6669522	0.3329941
6	0.3333300	0.6666585	0.0000153	2.89E−6	0.6666822	0.3333133
7	0.3333332	0.6666661	9.39E−7	2.30E−7	0.6666675	0.3333322
8	0.3333333	0.6666666	5.54E−8	1.64E−8	0.6666671	0.3333333
9	0.3333333	0.6666667	3.20E−9	1.09E−9	0.6666667	0.3333333

Figure 1 presents the change in the dual gap at each iteration of the obtained sequence on a semi-logarithmic graph.

Figure 1. Duality gap for Example 4.

During the initial iterations for $k=1,2$ , although there is some influence from $\sigma$ , the logarithm of the duality gap gradually decreases with each iteration, albeit at a slow pace.

For $k\ge 3$ , we have

$\text{dual gap}=c^{\text{T}}{\mathcal{x}}^k-b^{\text{T}}{\mathcal{y}}^k=C\cdot {10}^{-1.2k}$ (C: constant)

relationship; hence, the sequence converges to the solution swiftly.

5. Conclusions

The study confirms that the Nash equilibrium of the fixed-sum two-player game forms a convex set. Additionally, all solutions within this set yield the unique expected payoffs.

The Nash equilibrium solution to the fixed-sum two-player game can be efficiently solved by using the primal-dual interior point method. This method solves the linear programming problems involved in polynomial time regarding the number of strategies, m and n.

In elementary computational experiments, the Nash equilibrium of the fixed-sum two-player game is efficiently determined using the primal-dual path following algorithm, a technique within the primal-dual interior point method.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Nash, J.F. (1950) Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences, 36, 48-49. https://doi.org/10.1073/pnas.36.1.48
[2]	Daskalakis, C., Goldberg, P.W. and Papadimitriou, C.H. (2009) The Complexity of Computing a Nash Equilibrium. Communications of the ACM, 52, 89-97. https://doi.org/10.1145/1461928.1461951
[3]	Bowling, M., Burch, N., Johanson, M. and Tammelin, O. (2015) Heads-Up Limit Hold’em Poker Is Solved. Science, 347, 145-149. https://doi.org/10.1126/science.1259433
[4]	Monderer, D. and Shapley, L.S. (1996) Potential Games. Games and Economic Behavior, 14, 124-143. https://doi.org/10.1006/game.1996.0044
[5]	Moulin, H. (1976) Cooperation in Mixed Equilibrium. Mathematics of Operations Research, 1, 273-286. https://doi.org/10.1287/moor.1.3.273
[6]	Friedman, J.W. (1983) On Characterizing Equilibrium Points in Two-Person Strictly Competitive Games. International Journal of Game Theory, 12, 245-247. https://doi.org/10.1007/BF01769094
[7]	Kojima, M., Mizuno, S. and Yoshise, A. (1989) A Primal-Dual Interior Point Algorithm for Linear Programming. In: Megiddo, N., Ed., Progress in Mathematical Programming, Interior Point and Related Methods, Springer, 29-47.
[8]	Griva, I., Nash, S.G. and Sofer, A. (2009) Linear and Nonlinear Optimization. 2nd Edition, SIAM. https://doi.org/10.1137/1.9780898717730
[9]	Mizuno, S. (1992) A Primal-Dual Interior Point Method for Linear Programming. Proceedings of the Institute of Statistical Mathematics, 40, 27-44. (In Japanese)
[10]	Mizuno, S. (1992) A New Polynomial Time Method for a Linear Complementarity Problem. Mathematical Programming, 56, 31-43. https://doi.org/10.1007/BF01580891
[11]	GitHub-Hideki105/Linear-Programming. https://github.com/Hideki105/linear-programming
[12]	Lustig, I.J., Marsten, R.E. and Shanno, D.F. (1991) Computation Experience with a Primal-Dual Interior Point Method for Linear Programming. Linear Algebra and Its Applications, 152, 191-222. https://doi.org/10.1016/0024-3795(91)90275-2