6 Player Poker, Nash Equilibria, and Algorithms
https://science.sciencemag.org/content/365/6456/885.full
This article discusses the algorithmic implications of Nash equilibria. An important problem in computer science is the idea of discovering polynomial time algorithms to solve problems. However, it is often not possible to discover polynomial algorithms (these are called NP Hard problems). In the context of game theory, this applies to “two player zero-sum” games, or games where there is one winner (+1) and one loser (-1). For all games in which an algorithm was developed to find a Nash equilibria for two player zero-sum games, it has been possible to discover one in polynomial time. But what happens for games that are not in this standard format?
An example of a game that has been shown to have no polynomial time algorithm for finding Nash equilibria is six player poker. This result is surprising, as it seems like games far more complex in their rule sets have AI algorithms that are guaranteed to win. For example, there have been bots programmed to play against professional DotA (a multiplayer MOBA game) players. The state space of this game is seemingly infinite; every single action can change the next move. In poker, there is a finite number of possibilities (although it is a large finite number) yet it still is hard to achieve algorithms that can detect Nash equilibria.
However, this doesn’t mean it’s impossible for an AI to win a game of six player poker; in fact, the bots that have played against professionals still consistently defeat others despite not having a strong theoretical guarantee on victory. This is because the basic principles of Nash equilibria and general game theory still apply to more complex systems. The only reason these algorithms are significantly more complex and still have no theoretical guarantees is because of the number of players, which correlates to the number of nodes in the graph (or in the case of most games, a tree).
In conclusion, as we learned in class, every game does result in a Nash equilibrium – but that doesn’t always mean that the Nash equilibrium is easy to find in reasonable time. In fact, it is often very computationally intensive to find a Nash equilibrium. Sometimes, human intuition is better than any computer algorithm ever can be.