We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is
complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) …

The rank of a bimatrix game (A, B) is defined as rank (A+ B). Computing a Nash equilibrium
(NE) of a rank-0, ie, zero-sum game is equivalent to linear programming (von Neumann'28 …

Proceedings of the forty-seventh annual ACM symposium on Theory of Computing: On the
Complexity of Nash Equilibria in Anonymous Page 1 On the Complexity of Nash Equilibria in …

In view of the apparent intractability of constructing Nash Equilibria (NE in short) in
polynomial time, even for bimatrix games, understanding the limitations of the …

PPAD refers to a class of computational problems for which solutions are guaranteed to exist
due to a specific combinatorial principle. The most wellknown such problem is that of …

Finding a Nash equilibrium in a two-player normal form game (2-Nash) is one of the most
extensively studied problems within mathematical economics as well as theoretical …

A polymatrix game is a multi-player game over n players, where each player chooses a pure
strategy from a list of its own pure strategies. The utility of each player is a sum of payoffs it …

We revisit the complexity of deciding, given a bimatrix game, whether it has a Nash
equilibrium with certain natural properties; such decision problems were early known to be …

In this work we present a simple quadratic formulation for the problem of computing Nash
equilibria in symmetric bimatrix games, inspired by the well-known formulation of …

We investigate the complexity of finding Nash equilibria in which the strategy of each player
is uniform on its support set. We show that, even for a restricted class of win–lose bimatrix …