When to Hold Em, When to Compete

Nash Equilibrium's use in Competitive Situations is re-examined, with hope for its use in competitive behavior situations.  We looked at it for that and found no golden egg, but it doesn't mean others couldn't find it.   A reexamination.   Complexity technical.  Just because optimum solutions are known to be probably impossibly hard, very good solutions are probably better than what we are doing today.

When to Hold 'Em    By CACM Staff 
Communications of the ACM, Vol. 61 No. 6, Pages 6-7
10.1145/3210585

Neil Savage deserves praise for his informative overview of recent computational results related to Nash equilibrium in his news story "Always Out of Balance" (Apr. 2018). I fully agree that the notion of Nash equilibrium does not always reflect how competitors behave in competitive situations, and that the fact that Nash equilibrium is provably computationally intractable makes it less useful than John Nash himself might have envisioned when he developed it. However, Savage also overstated (somewhat) the effect of intractability by claiming the intractability of computing Nash equilibrium necessitates researchers abandon this notion in favor of other competition-related ideas.

While looking for Nash equilibrium yields additional computational complexity, the decision-making problem is, in general, already computationally intractable (NP-hard) for non-competitive situations (such as when a company makes internal planning decisions). In doing so, a company would be looking for an optimal solution (such as one that would aim to help produce maximum profit), but computational optimization is, in general, NP-hard. Such computational intractability does not mean researchers have to abandon the idea of optimization and look for other ideas. Many real-life problems are NP-hard (such as robotic movement) and what makes working on them such an intellectual and computational challenge.

Indeed, there is no general feasible algorithm (unless P = NP), so computer scientists need to be creative when designing algorithms for specific practical problems.  .... " 

Vladik Kreinovich, EL Paso, TX, USA