A Regret-Based Algorithm for Computing All Pure Nash Equilibria for Noncooperative Games in Normal Form

H. W. Corley

Center on Stochastic Modeling, Optimization, & Statistics (COSMOS), University of Texas at Arlington, Arlington, USA.

DOI: 10.4236/tel.[phone]                

Abstract

The concept of a pure Nash equilibrium (NE) for a noncooperative game is simpler than that of a mixed NE, which always exists. However, pure NEs probably have more practical significance even though such a game may not have a pure NE. An efficient algorithm is presented here to determine whether an n-person game in normal form has a pure NE and, if so, to obtain all NEs. This algorithm uses the notion of regret, and the payoff matrix (PM) is transformed into a regret matrix (RM)—a loss matrix with an intuitive interpretation. The RM has the property that an action profile of the PM is a pure NE if and only if (0,· · ·,0) is the corresponding element of the RM. The computational complexity of the algorithm is O(N) in the number of individual utilities N in the PM, and so it is substantially faster than a total enumeration.

Keywords

Pure Nash Equilibria, Algorithm for Pure Nash Equilibria, Regret Matrix, Pareto Nash Equilibrium

1. Introduction

In a Nash equilibrium (NE) for an n-person game, every player has a strategy that maximizes his payoff for the other n− 1 players’ strategies. In other words, no player can unilaterally change his strategy in an NE (i.e., with no change of strategy by the other players) and improve his payoff. This stability is the reason an NE is termed an equilibrium. The NE thus models selfish behavior in which each player wants to maximize his payoff for any given set of strategies for the other players. Nash’s fundamental result for a game with a finite number of actions for each player was that every n-person noncooperative game has an equilibrium in mixed strategies, though perhaps not in pure strategies. It should be recalled that a mixed strategy for a player is an assignment of probability to each of the player’s possible actions, with a pure strategy being a special case where one action has a probability of 1 and the rest have probabilities of zero. The joint mixed strategies for the players then determine expected payoffs for each player.

The NE has found application in fields as diverse as economics (Myerson, 1999), computing (Chen, 2015), evolutionary biology (Kastampolidou & Andronikos, 2020), medicine (Zhang, Shan, Gao, & Jia, 2019), psychology (DeDreu, Giacomantonio, Giffin, & Vecchiato, 2019), and artificial intelligence (Fragkos, Tsiropoulou, & Papavassiliou, 2020). The efficient computation of an NE has thus been considerably studied. Most work, however, has focused on the computational complexity for finding mixed NEs, whose existence is guaranteed by Nash’s existence theorem (Nash, 1951). Despite this fact, it remains unknown whether a mixed NE can be computed in polynomial time. However, Papadimitriou (1994) has defined the complexity class PPAD to include this problem, and Daskalakis, Christos, and Papadimitriou (2009) have shown that the computation of a mixed NE is PPAD-complete.

In addition to the computational difficulties associated with mixed strategies, their interpretation is controversial. For example, both von Neumann & Morgenstern (1944) and later Nash (1953) considered a randomizing process an essential part of a mixed strategy, a requirement that Aumann (1985) and Rubinstein (1991) considered problematic since the reasons and methods for the players randomizing their decisions were not specified. Aumann and Brandenburger (1995) later viewed a Nash equilibrium as an equilibrium in beliefs, rather than actions. More recently, Nahhas and Corley (2018) interpreted mixed strategies as the allocation of resources.

However, the principal advantage of mixed strategies seems to be theoretical. They provide NEs when none exist in pure strategies and allow for the development of a rich mathematical theory. Nonetheless, practitioners are frequently ambivalent towards mixed strategies due to the lack of a consistent interpretation and to the current difficulty (if not impossibility) of computing them except for relatively small games.

On the other hand, pure NEs are not guaranteed to exist. Though conceptually simpler than mixed NEs, the associated computations appear even more difficult (Gottlob, Greco, & Scarcello, 2005). In general, determining whether a finite game has a pure Nash is known to be tractable in normal form but NP-complete in other representations such as graphical form (Gottlob, Greco, & Scarcello, 2005). Recent algorithms for determining whether an n-person game in normal form has a pure NE and, if so, for determining all NEs, have been developed in (Buttler & Akchurina, 2013), (Barrios, Luna, & Balcazar, 2016), and (Zaman, Elsayed, Ray, & Sarkerr, 2018), for example. In contrast to these previous approaches, the algorithm presented here uses the concept of regret, which is essentially an opportunity cost, and a regret matrix.

The use of a regret matrix in single-agent decision making is surveyed in (Yager, 2004), (Taha, 2017) , and (Mishra & Tsionas, 2020). For games, regret has been used in (Deligkas, Fearnley, Savani, & Spirakis, 2017), (Zhang, Chen, & Chang, 2020), (Farina, Kroer, & Sandholm, 2019), and the references therein, but apparently not as applied here. Utilizing regret, we present here an efficient algorithm for computing a pure NE for a normal form game. Normal form is the most fundamental representation of a game (Daskalakis & Leyton-Brown, 2009) since all other representations of finite games, such as extensive form, can be encoded in it.

Consider now the game $G_n=\left(I,{\left(S_i\right)}_{i\in N},{\left(u_i\right)}_{i\in N}\right)$ in normal form, where $I=\left\{1,\cdots ,n\right\}$ is the set of players, $S_i$ is the finite set of $m_i\ge 2$ actions (i.e., pure strategies) for player i, and $u_i\left(s\right)$ is the utility of player i for an action profile $s=\left(s_1,\cdots ,s_n\right)\in {{\displaystyle \times }}_{j\in I}{S}_j=S$. The NE is defined as follows, where an incomplete strategy profile $s_{-i}=\left(s_1,\cdots ,s_{i-1},s_{i+1},\cdots ,s_n\right)$ denotes a member of $S_{-i}={{\displaystyle \times }}_{j\in I\backslash \left\{i\right\}}{S}_j$. With this notation and terminology, an NE for $G_n$ is now defined.

Definition 1. The action profile $s^{*}$ is an NE of $G_n$ if and only if

$u_i\left(s^{*}\right)=\underset{s_i\in S_i}{\max }{u}_i\left(s_i,s_{-i}^{*}\right),$ for all $i\in I$. (1)

In Section 2 we define the regret matrix (RM) corresponding to the payoff matrix (PM) for $G_n$ and prove that a joint action $s^{*}$ is a NE if and only if $\left(0,\cdots ,0\right)$ is the corresponding entry of the RM. In Section 3 the approach of Section 2 is formalized as an algorithm to obtain all NEs for $G_n$ if any exist. In Section 4 a simple computational example is presented for n = 3.

2. The Regret Matrix

The regret function $r_i$ is defined as a transformation of player i’s payoffs to losses for a given action profile $s=\left(s_i,s_{-i}\right)$.

Definition 2. For the game $G_n$, the regret incurred by any player i for $s=\left(s_i,s_{-i}\right)$ is

$r_i\left(s\right)=\underset{t_i\in S_i}{\max }{u}_i\left(t_i,s_{-i}\right)-u_i\left(s_i,s_{-i}\right)$ for all $i\in I$. (2)

The regret incurred by player i for an action profile $\left(s_i,s_{-i}\right)$ is thus the difference between the best payoff that player i can obtain for fixed $s_{-i}$ and the payoff that player i will obtain for $\left(s_i,s_{-i}\right)$. The following result is needed for the algorithm.

Result 1. The pure strategy profile $s^{*}$ is a NE for the game $G_n$ if and only if the $r_i\left(s^{*}\right)=0$ for all $i\in I$.

Proof. The strategy profile $s^{*}$ is an NE for $G_n$ if and only if $s^{*}$ satisfies (1) of Definition 1. But (1) holds if and only if $r_i\left(s^{*}\right)=0$ in (2) for all $i\in I$.

We next define the regret matrix (RM) of $G_n$.

Definition 3. The regret (RM) of $G_n$ is the matrix obtained from its PM by replacing $\left(u_1\left(s\right),\cdots \text{,}{u}_n\left(s\right)\right)$ with $\left(r_1\left(s\right),\cdots ,r_n\left(s\right)\right)$ for all $s\in S$.

The associated game ${\hat{G}}_n=\left(N,{\left(S_i\right)}_{i\in N},{\left(r_i\right)}_{i\in N}\right)$ with payoff matrix RM is not equivalent to $G_n$ in the sense of Myerson (1991) but has the same NEs. The regret matrix provides an efficient approach for determining if a pure NE exists and, if so, obtaining them.

3. The Algorithm

Consider a game $G_n$ as above, and denote the j^th strategy of player i by $s_i^j\in S_i,j=1,\cdots ,m_i$. The following pseudocode describes the algorithm PURECOMP for obtaining the set of pure NEs for $G_n$ from its RM.

$1\leftarrow i,1\leftarrow j$

While $i\le n$ do

While $j\le m_i$ do

From (2), compute $r_i\left(s_i^j,s_{-i}\right)$ for all $s_{-i}\in S_{-i}$. (3)

$r_i\left(s_i^j,s_{-i}\right)\leftarrow u_i\left(s_i^j,s_{-i}\right)$ for all $s_{-i}\in S_{-i}$

End While

End While

$P={\displaystyle \cup \left\{s\in S:r_i\left(s\right)=0,i=1,\cdots ,n\right\}}$.

The set of pure NEs of $G_n$ is P, which may be empty. From (3) the computational complexity of PURECOMP is $O\left(N\right)$, where $N=n{\displaystyle \underset{i\in I}{\prod }{m}_i}$ is the size of the input to the game. It is the number of individual utilities $u_i\left(s\right),i=1,\cdots ,n$ of the n players for all possible action profiles $s\in S$. In particular, for $m=m_i,i=1,\cdots ,n$, then $N=n{m}^n$. PURECOMP is thus linear in the input size. It should be noted, however, that the input size itself is exponential in the number of players. On the other hand, for example, Daskalakis and Leyton-Brown (2009) propose an enumeration using Definition 1 with complexity

$O\left({\left[{\displaystyle \underset{i\in I}{\prod }{m}_i}\right]}^2\right)$, which is at least $O\left(2^n{\displaystyle \underset{i\in I}{\prod }{m}_i}\right)$ because $m_i\ge 2$ for all $i\in I$. But $O\left(2^n{\displaystyle \underset{i\in I}{\prod }{m}_i}\right)>O\left(n{\displaystyle \underset{i\in I}{\prod }{m}_i}\right)$ for $n\ge 1$ since $2^n{\displaystyle \underset{i\in I}{\prod }{m}_i}/n{\displaystyle \underset{i\in I}{\prod }{m}_i}=2^n/n$, and so PURECOM is considerably faster.

4. Example

For n = 3 we use the notation of Section 3 with $m_1=m_2=m_3=2$ and consider the game $G_3$ with the PM of Table 1 below. The RM for $G_3$ is then obtained from the PM via PURECOMP and shown in Table 2. The unique pure NE for $G_3$ is $s^{*}=\left(s_1^1,s_2^2,s_3^2\right)$ with associated payoffs $\left(u_1\left(s^{*}\right),\cdots \text{,}{u}_n\left(s^{*}\right)\right)=\left(3,5,1\right)$.

Table 1. PM for G₃.

Table 2. RM forG₃.

5. Conclusion

An algorithm PURECOM was presented here to determine whether an n-person game in normal form has a pure NE and, if so, to obtain all NEs. In PURECOM the payoff matrix is transformed into a regret matrix. The RM has the property that an action profile of the PM is a pure NE if and only if $\left(0,\cdots ,0\right)$ is the corresponding element of the RM. The computational complexity of the algorithm is $O\left(N\right)$ in the number of elements N of the PM, which is $2^n/n$ times faster than a complete enumeration.

PURECOM thus makes two contributions. First, it determines a pure NE by implementing the intuition that an equilibrium should not cause regret for any player. This approach undoubtedly has pedagogical applications. Second, it gives a computational procedure for determining all pure NEs, if any exist, for games with normal form. PURECOM is unlikely to be improved except for payoff matrices with special structure such as certain symmetries.

Conflicts of Interest

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

References

[1]	Aumann, R. (1985). What Is Game Theory Trying to Accomplish? In K. Arrow, & S. Honkapohja (Eds.), Frontiers of Economics (pp. 5-46). Oxford: Blackwell.
[2]	Aumann, R., & Brandenburger, A. (1995) Epistemic Conditions for Nash Equilibrium. Econometrica, 63, 1161-1180. https://doi.org/10.2307/2171725
[3]	Barrios, O., Luna, D., & Balcazar, L. (2016) Design of an Efficient Algorithm to Find Pure Nash Equilibria on Strategic Games. IEEE Latin America Transactions, 14, 320-324. https://doi.org/10.1109/TLA.2016.7430096
[4]	Buttler, J., & Akchurina, N. (2013) Nash Equilibria in Normal Games via Optimization Methods. European Control Conference (ECC), Zurich, 17-19 July 2013, 724-729. https://doi.org/10.23919/ECC.2013.6669658
[5]	Chen, X. (2015). Decentralized Computation Offloading Game for Mobile Cloud Computing. IEEE Transactions on Parallel and Distributed Systems, 26, 974-983. https://doi.org/10.1109/TPDS.2014.2316834
[6]	Daskalakis, C., & Leyton-Brown, K. (2009). A Computational Perspective on Game-Theoretic Solution Concepts: A Tutorial. 10th ACM Conference on Electronic Commerce, CA: Stanford University, 6-10 July 2009. http://www.sigecom.org/ec09/slides/Equilibrium-Computation-Tutorial.pdf
[7]	Daskalakis, C., Christos, P., & Papadimitriou, H. (2009). The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing, 39, 195-259. https://doi.org/10.1137/070699652
[8]	DeDreu, C., Giacomantonio, M., Giffin, M., & Vecchiato, G. (2019). Psychological Constraints on Aggressive Predation in Economic Contests. Journal of Experimental Psychology: General, 148, 1767-1781. https://doi.org/10.1037/xge0000531
[9]	Deligkas, A., Fearnley, J., Savani, R., & Spirakis, P. (2017) Computing Approximate Nash Equilibria in Polymatrix Games. Algorithmica, 77, 487-514. https://doi.org/10.1007/s00453-015-0078-7
[10]	Farina, G., Kroer, C., & Sandholm, T. (2019). Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions. 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, 8-14 December 2019, 11 p. http://papers.nips.cc/paper/8764-optimistic-regret-minimization-for-extensive-form-games-via-dilated-distance-generating-functions.pdf
[11]	Fragkos, G., Tsiropoulou, E., & Papavassiliou, S. (2020). Artificial Intelligence Enabled Distributed Edge Computing for Internet of Things Applications. 2020 16th International Conference on Distributed Computing in Sensor Systems (DCOSS), Marina del Rey, 450-457. https://doi.org/10.1109/DCOSS49796.2020.00077
[12]	Gottlob, G., Greco, G., & Scarcello, F. (2005). Pure Nash Equilibria: Hard and Easy Games. Journal of Artificial Intelligence Research, 24, 357-406. https://doi.org/10.1613/jair.1683
[13]	Kastampolidou, K., & Andronikos, T. (2020). A Survey of Evolutionary Games in Biology. Advances in Experimental Medicine and Biology, 1194, 253-261. https://doi.org/10.1007/978-3-030-32622-7_23
[14]	Mishra, A., & Tsionas, M. (2020). A Minimax Regret Approach to Decision Making under Uncertainty. Journal of Agricultural Economics, 71, 698-718. https://doi.org/10.1111/1477-9552.12370
[15]	Myerson, R. (1991). Game Theory: Analysis of Conflict. Cambridge, MA: Harvard University Press.
[16]	Myerson, R. (1999). Nash Equilibrium and the History of Economic Theory. Journal of Economic Literature, 37, 1067-1082. https://doi.org/10.1257/jel.37.3.1067
[17]	Nahhas, A., & Corley, H. (2018). An Alternative Interpretation of Mixed Strategies in n-Person Normal Form Games via Resource Allocation. Theoretical Economics Letters, 8, 1854-1868. https://doi.org/10.4236/tel.[phone]
[18]	Nash, J. (1951). Non-Cooperative Games. The Annals of Mathematics, 54, 286-295. https://doi.org/10.2307/1969529
[19]	Nash, J. (1953). Two-Person Cooperative Games. Econometrica, 21, 128-140. https://doi.org/10.2307/1906951
[20]	Papadimitriou, H. (1994). On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Journal of Computer and System Sciences, 48, 498-532. https://doi.org/10.1016/S0022-0000(05)80063-7
[21]	Rubinstein, A. (1991). Comments on the Interpretation of Game Theory. Econometrica, 59, 909-924.
[22]	Taha, H. (2017). Operations Research: An Introduction (10th ed.). London: Pearson.
[23]	Von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton, NJ: Princeton University Press.
[24]	Yager, R. (2004). Decision Making Using Minimization of Regret. International Journal of Approximate Reasoning, 36, 109-128. https://doi.org/10.1016/j.ijar.2003.10.003
[25]	Zaman, F., Elsayed, S., Ray, T., & Sarkerr, R. (2018). Evolutionary Algorithms for Finding Nash Equilibria in Electricity Markets. IEEE Transactions on Evolutionary Computation, 22, 536-549. https://doi.org/10.1109/TEVC.2017.2742502
[26]	Zhang, S., Shan, G., Gao, H., & Jia, T. (2019). Rheumatoid Arthritis Analysis by Nash Equilibrium Game Analysis. Journal of Medical Imaging and Health Informatics, 9, 1382-1385. https://doi.org/10.1166/jmihi.2019.2760
[27]	Zhang, Y., Chen, T., & Chang, S. (2020). Existence of Solution to n-Person Non-Cooperative Games and Minimax Regret Equilibria with Set Payoffs. Applicable Analysis. https://doi.org/10.1080/00036811.2020.1813723