WorksComputer Science
On Existence and Computational Complexity of Quasi-strict Equilibria
Abstract
Quasi-strict Nash equilibrium, introduced by Harsanyi in 1973, is the Nash equilibrium refinement that requires every pure best response to be played with positive probability. Norde established that any bimatrix game admits a quasi-strict Nash equilibrium. We give a substantially simpler proof of this result that in particular avoids an intricate limit argument used in the final step of the proof by Norde. Our existence proof allows us to positively resolve the outstanding open question of PPAD membership of the problem of computing a quasi-strict Nash equilibrium, thereby settling its precise complexity. In games with three or more players, a quasi-strict Nash equilibrium is not guaranteed to exist, leading to the natural problem of deciding the existence of a quasi-strict Nash equilibrium in a given strategic form game. We show that this problem is -complete, strengthening a previous NP-hardness result.
Introduction
The fundamental theorem of Nash establishes that every finite strategic form game admits a Nash equilibrium in mixed strategies [25], i.e. a mixed-strategy profile in which every player’s strategy is a best response to the strategies of the other players. Nash equilibrium refinements impose additional requirements with the aim of capturing certain desirable properties. In this work we are concerned with the notion of quasi-strict Nash equilibria introduced by Harsanyi [13], which simply requires each player to play each pure best response to the strategies of the other players with positive probability. In subsequent work Harsanyi [14 Theorem 2] proved that in almost all finite strategic form games all Nash equilibria are in fact quasi-strict equilibria. In general, however, quasi-strict equilibria are not guaranteed to exist in games with 3 or more players [32 Fig 3.4.1] and when they do exist they may necessarily assign positive probability to dominated pure strategies even in bimatrix games [32 Fig 2.1.1]. On the other hand, as shown by Squires [31], from any quasi-strict equilibrium one can construct sets satisfying the axioms introduced by Cubitt and Sugden [7] as formal conditions for justifiable play, making them very interesting from an axiomatic point of view.
Norde proved that quasi-strict equilibria exist in all bimatrix games [26]. A fundamental technical challenge in proving this result is that it is not possible to express the set of quasi-strict equilibria as the set of fixed points given by the fixed point theorems of Brouwer [4] and Kakutani [16], simply because these are closed sets which the set of quasi-strict equilibria may fail to be. This does of course not rule out expressing a closed subset of the quasi-strict equilibria as a set of fixed points, but it is not clear how to do that in a general way. Norde overcomes the obstacles presented by a direct fixed point formulation by several means. First, for each set of pure strategies of player 2, a generalized permutahedron is constructed in the relative interior of the face of the strategy simplex of player 2 defined by , chosen to approximate this relative interior sufficiently well. On each such set , a continuous best-response function for player 1 is constructed and a corresponding best-response function for player 2 defined using projection and a scaling of the payoffs by a large positive constant . A continuous function is then defined as a weighted combination of the functions to which Brouwer’s fixed point theorem applies. Finally, it is proved that limit points of fixed points of the functions , as tends to infinity, can form the strategy of player 1 in a quasi-strict equilibrium.
In this work we are interested in quasi-strict equilibria from the viewpoint of computational complexity. The seminal work of Papadimitriou [28] introduced the complexity class PPAD to capture total search problems whose totality is given by directed parity arguments. These include, in particular, search problems arising from path-following procedures underlying computational versions of Sperner’s lemma and Lemke’s algorithm. Using these, Papadimitriou showed that the problems of computing a Nash equilibrium of bimatrix games and of computing an -approximate Nash equilibrium in a strategic form game belong to PPAD. Later, the celebrated works of Daskalakis, Goldberg, and Papadimitriou [8] and Chen, Deng, and Teng [6] proved that these problems are in fact PPAD-complete.
The PPAD-hardness of computing a Nash equilibrium of a bimatrix game trivially implies PPAD-hardness of computing a quasi-strict equilibrium in bimatrix games. Brandt and Fischer [1] gave a polynomial time algorithm for finding a quasi-strict equilibrium in two-player zero-sum games and symmetric multiplayer games in which every player has exactly two pure strategies. The precise complexity of computing a quasi-strict equilibrium in bimatrix games remained an outstanding open problem. Our main result is settling this question by proving that the problem belongs to PPAD.
Theorem 1. Computing a quasi-strict Nash equilibrium of a bimatrix game is PPAD-complete.
On the way to proving our result we first develop an alternative proof of Norde’s existence theorem. This proof relies primarily on simplicial complexes and simplicial maps and allows us to bypass the technically involved arguments employed in Norde’s proof. Our proof also follows a more natural structure of treating each player symmetrically. More specifically, for each player we consider the polyhedral complex defined by the best-response regions and refine it to a simplicial complex by taking geometric realizations of the order complexes of its face posets. In addition to this, we also consider the barycentric subdivisions of each strategy simplex, giving for each player two simplicial complexes with the same underlying space. On these we define natural simplicial maps defined in terms of the support of the strategy defined by the vertex and the set of pure best replies to the strategy defined by the vertex. These are combined to form a single continuous self-map on the set of mixed strategy profiles using radial projection of a translation of the given strategy profile in a way similar to the existence proof of Nash equilibria by Nash [25]. Finally, by examining the inclusion relations among faces, we show how to extract a quasi-strict Nash equilibrium directly from a fixed point of .
To prove our PPAD-membership result we make use of the notion of polynomial piecewise linear fixed point problems, as defined and used by Etessami and Yannakakis [EY10] in their characterization of PPAD by the search problems given by the piecewise linear fragment of the general complexity class FIXP. An instance of a polynomial piecewise linear fixed point problem is given by a continuous self-map of a nonempty compact convex domain , divided in polyhedral cells on which is linear. The domain is given by a set of linear inequalities with rational coefficients computable from and the linear function, which must be defined by a rational matrix and vector, of a given cell containing a point must be computable in polynomial time by an oracle algorithm that can perform linear comparison queries of the form with rational-valued and .
To use this notion requires us to make our existence proof effective. In particular, for refining the polyhedral complex defined by the best-response regions we define the interior points chosen of each face implicitly by solutions of linear programs. This allows them to be computed in polynomial time whenever they are needed, which in turn allows us to implement the necessary oracle algorithm in polynomial time.
To make the self-map piecewise linear we also replace the radial projection by Euclidean projection. The same change of the type of projection was previously used by Etessami and Yannakakis [EY10] in their characterization of the set of Nash equilibria as fixed points of continuous functions defined without use of division.
Our second result is concerned with games with three or more players, where a quasi-strict Nash equilibrium is not guaranteed to exist. This naturally leads to the decision problem of deciding existence of a quasi-strict Nash equilibrium in a given strategic form game. From the definition of quasi-strict equilibria it is immediate to see that this problem belongs to the complexity class which is the complexity class associated with the decision problem for the existential theory of the reals. Brandt and Fischer [1] proved that the problem is NP-hard by adapting a construction of McLennan and Tourky [21] used for proving NP-completeness for other decision problems about Nash equilibria. We show that the problem is in fact -hard, thereby settling the complexity of the problem.
Theorem 2. For every fixed , deciding whether an -player game in strategic form with rational payoffs admits a quasi-strict Nash equilibrium is -complete, even for zero-sum games.
The proof is based on -hardness of deciding whether the minmax value of player 1 in a 3-player game is at most 0, which, importantly for our purposes, holds even when a certain useful property of the payoff functions is satisfied, which in particular enables player 1 to ensure that the minmax value is at least 0, and under a promise that a minmax value of 0, when possible, may be ensured by fully mixed strategies of player 2 and player 3 [Han19]. We follow the definition of a corresponding zero-sum game used by Berthelsen and Hansen [2] to prove -completeness for other decision problems about Nash equilibria in multi-player zero-sum games. Similarly to proofs of these results, our reduction simply gives each player a new strategy in this game and we define payoffs that ensure that the resulting game has a quasi-strict equilibrium if and only if the minmax value of player 1 in the original game is 0.
Related work
A substantial body of research studies the computational complexity of computing various notions of Nash equilibrium refinements. We shall here focus on strategic form games. Nash equilibrium refinements that are guaranteed to exist naturally inherit the computational hardness of computing any Nash equilibrium, i.e. the PPAD-completeness of computing a Nash equilibrium in bimatrix games [8, 6] and the FIXP-completeness of computing a Nash equilibrium in multiplayer games [EY10].
Classic equilibrium refinements defined to take the possibility of players making mistakes into account are the notions of perfect equilibria due to Selten [29] and proper equilibria due to Myerson [24]. Perfect equilibria in two-player games coincide with a Nash equilibrium wherein neither strategy is dominated. This means that a perfect equilibrium in two-player zero-sum games may be found in polynomial time using linear programming. For bimatrix games computing a perfect equilibrium belongs to PPAD, as a consequence of the complementary pivoting algorithm for computing perfect equilibria in two-player extensive form games by von Stengel, van den Elzen, and Talman [VSvdET02]. For multiplayer games Etessami, Hansen, Miltersen and Sørensen [EHMS14] showed that the problem belongs to , i.e. that the problem of computing a strategy profile that is -close to a perfect equilibrium for a given belongs to FIXP. All these results were subsequently strengthened to the same results for proper equilibria [24]. A polynomial time algorithm for zero-sum games was given by Miltersen and Sørensen [20], Sørensen [30] proved the problem to be in PPAD for bimatrix games, and Hansen and Lund [15] proved the problem to belong to for multiplayer games. Thus for two-player games, the complexity of finding a perfect or proper equilibrium is the same as the complexity of finding a quasi-strict equilibrium. This is not the case for games with three or more players, simply because a quasi-strict equilibrium may fail to exist.
Another interesting Nash equilibrium refinement is the notion of test-set equilibrium due to Milgrom and Mollner [19]. For two-player games, every proper equilibrium is a test-set equilibrium, and every test-set equilibrium is a perfect equilibrium [19 Proposition 1], which means that computing a test-set equilibrium can be done in polynomial time for two-player zero-sum games and belongs to PPAD for bimatrix games. But, similarly to quasi-strict equilibria, a test-set equilibrium may fail to exist in games with three or more players [19 Figure 1].
Preliminaries
For our existence proof we make use of fundamental topological notions, where we generally follow the terminology of Munkres [22, 23]. For polyhedral complexes we adopt the definition of Björner [Bjö95]. The concepts and results we need have natural geometric interpretations, which we illustrate by example using a bimatrix game.
For , we let denote the set and let denote the standard -simplex given by
A point can be viewed as a probability distribution on and we define .
Definition 1 (Two-player Bimatrix games and Quasi-strict Nash Equilibria). Let be the set of pure strategies of player 1 and be the set of pure strategies of player 2. We let and denote the mixed strategies of player 1 and player 2, respectively. A bimatrix game is given by a pair of matrices specifying payoffs of player 1 and player 2, respectively. For the matrix and probability vector , the set
is the set of pure best responses of player 1 to strategy . For the matrix and probability vector , the set
is the set of pure best responses of player 2 to strategy . A Nash equilibrium is a pair of mixed strategies satisfying
A quasi-strict Nash equilibrium further requires that
When considering the computational problem of finding an equilibrium, the payoff matrices are defined on the rational number field . The following example is adapted from [26], with a modified payoff matrix for player 2. For clarity, we denote player 1’s pure action by and player 2’s pure action by , rather than using the notation .
Example 1. Consider the bimatrix game with payoff matrices
The best-response relations and subdivide the strategy simplices and , respectively. As illustrated by the calculation, each closed best-response region is a polytope. For example, write , where and . Player 1’s pure action is the unique best response precisely when
Then, and imply . For , where and , the choice gives
Figure 1. Best-response partitions induced by on (left) and on (right).
Definition 2 (Simplex and Simplicial Complex). Let be an affinely independent point set in . The -simplex spanned by these points is the set of all points such that
where and for each . For each point in the simplex, the coefficients are uniquely determined. They are called the barycentric coordinates of with respect to . A simplicial complex in is a collection of simplices in such that:
Every face of a simplex of is in .
The intersection of any two simplices of is a face of each of them.
Example 2. In Example 1, the best-response regions on , together with all their faces, form a simplicial complex. On , the best-response regions are quadrilaterals, so their subdivision is not simplicial.
Thus, the best-response subdivisions are in general not simplicial complexes. To facilitate the construction of a continuous self-map, we use topological tools to obtain a finer subdivision that is a simplicial complex. This construction is described in [Bjö95, §9.3, §12.2] and also appears as an exercise in [23 §3, Ex. 4].
Definition 3 (Polytopes and polyhedral complexes). A convex polytope is a bounded subset of which is the solution set of a finite number of linear equalities and inequalities. Any nonempty subset obtained by changing some of the inequalities to equalities is a face of .
A polyhedral complex is a finite collection of convex polytopes in such that:
Every face of a polytope of is in .
The intersection of any two polytopes of is a face of each of them.
Example 3. In Example 1, the closed best-response regions on , together with all their nonempty faces, form a polyhedral complex. The best-response regions on could be also considered as a polyhedral complex.
Definition 4 (Face poset and order complex). Let be a polyhedral complex. Its face poset
consists of its faces ordered by inclusion.
For a finite poset , the order complex is the abstract simplicial complex on vertex set whose -simplices are the -element chains
In particular, the simplices correspond to chains of faces
Example 4. In Example 1, each maximal chain in the face poset has the form
consisting of a vertex, an incident edge, and a two-dimensional polytope. It defines a 2-simplex in the corresponding order complex.
Write for the interior of in its affine hull. For each face , fix a single point
The same selected point is used whenever occurs in a chain. Set
We use the following standard results without proof; see [Bjö95, §12.2].
Proposition 1. The collection is a simplicial complex with the same underlying space as :
Example 5. In Example 1, let
denote the closed best-response regions. Let and consist of all their nonempty faces, respectively. For each face , take to be the average of its vertices and realize each chain by
This gives barycentric subdivisions of the best-response complexes. By Proposition 1, their underlying spaces are and , respectively.
Figure 2. Barycentric subdivisions of the best-response complexes on (left) and (right). Colors indicate the original best-response regions.
Definition 5 (Simplicial map). Let and be simplicial complexes, and let
be a map. Suppose that whenever span a simplex of , their images are vertices of a simplex of .
Define on each simplex by
The map is called the simplicial map induced by the vertex map .
We have the following fundamental property of simplicial maps.
Proposition 2. The simplicial map induced by a vertex map satisfying the above condition is well-defined and continuous.
Example 6. For the game in Example 1, where , give the target strategy simplex its barycentric subdivision. On the vertices of the source subdivision in Example 5, define
Thus each vertex is sent to the barycenter of the face spanned by its pure best responses. Along a face chain, the best-response sets are nested in reverse order, so the image vertices span a simplex in the target subdivision. Extending affinely over each source simplex gives a simplicial map .
Let , and let be the barycenters of the faces in the chain
Their best-response sets are , , and , respectively, so the vertex rule gives
Extending affinely maps the shaded simplex to the shaded target simplex.
Figure 3. A simplicial map . The shaded simplices correspond under .
Additionally, we need some basic properties of product spaces from [22 Theorem 18.2, Theorem 18.4 and Theorem 26.7].
Proposition 3. The following hold:
Let and be polytopes. The function is continuous if and only if the coordinate functions and are continuous.
Let be continuous. Then the function is continuous.
For two simplices and , the product is a nonempty compact convex subset of .
Next, we introduce related complexity classes and tools needed. A polynomial-time search reduction consists of polynomial-time computable maps and such that, for every instance of the source problem and every solution of the target instance , the output is a solution of . The class PPAD consists of total search problems reducible to End-of-Line. Given an implicitly represented directed graph with indegree and outdegree at most one and a specified source, find another endpoint [28].
We apply the general class defined by Etessami and Yannakakis [EY10] for fixed-point problems with piecewise-linear, polynomial-time computable functions, without constructing the underlying End-of-Line graph. Here, piecewise linearity is understood with respect to a suitable polyhedral subdivision, which need not be compatible with the simplicial complexes used in our construction.
Definition 6 (Polynomial piecewise-linear fixed-point problems). For each instance , let
be a continuous self-map of a nonempty compact convex domain . This defines a polynomial piecewise-linear fixed-point problem if the following hold:
is a polytope defined by a set of linear inequalities. And coefficients can be computed from in polynomial time.
There is a collection of hyperplanes dividing into polyhedral regions on each of which is affine. For each cell, the coefficients of its affine formula, as well as those of each dividing hyperplane, are rational numbers with encoding lengths polynomial in uniformly.
There is a polynomial-time algorithm that interacts with a linear-comparison oracle for the point . Each query asks whether with rational input and , and may depend on the answers to previous queries. If , the algorithm outputs No; otherwise, it outputs a rational matrix and a rational vector specifying the local affine formula applicable at , so that .
The following exact fixed-point theorem is due to Etessami and Yannakakis [EY10, Theorem 5.2].
Theorem 3. For every instance of a polynomial piecewise-linear fixed-point problem, there exists a rational fixed point s.t. and its encoding length is polynomial in . The search problem of computing such an exact rational fixed point belongs to PPAD.
Thus, to apply Theorem 3, we will construct a continuous self-map satisfying Definition 6 and give a polynomial-time procedure that transforms each polynomial-size rational fixed point into a quasi-strict Nash equilibrium.
Our existence proof of quasi-strict equilibrium uses radial projection in a similar way to the existence proof of Nash [25] by Brouwer’s fixed point theorem, which does not give a piecewise linear self-map. We thus replace the radial projection by Euclidean projection to obtain this, which may be computed as follows. This may be computed in a simple way as shown in by a piecewise linear algebraic circuit as shown in the proof of [EY10, Lemma 4.6], and adapted in the following lemma.
Lemma 1 (Euclidean projection). For , let be its coordinates in decreasing order, and define
and for each ,
Then is the unique real number satisfying
This projection maps into , and is continuous and piecewise linear. Moreover, there is a polynomial-time algorithm with access to a linear-comparison oracle that outputs the local affine formula with input .
The complexity class used in our result about multiplayer games is the class . Its canonical complete problem, the existential theory of the reals (ETR), asks whether a sentence of the form
is true, where is a quantifier-free formula with equalities and inequalities involving polynomials with rational coefficients. One may think of as an analogue of NP, and ETR as an analogue of SAT. It is easy to see that . Canny proved that in [5].1
We use the minmax hardness theorem in 3-player games given by Hansen [Han19, Theorem 1] to establish -hardness. We use the specific formulation given in [2 Definition 1 and Proposition 3] and restated below (without the additional promise that one may assume in the case of the minmax value being 0).
Theorem 4. Let be a three-player game with pure strategy sets , , and a rational valued payoff function of player 1. Suppose and
Define
It is then -hard to decide whether under the promise that the game meets one of the following conditions:
;
, and there exist full-support strategies and such that for every .
Existence of quasi-strict Nash equilibria in bimatrix games
We use the notation introduced in the preliminary section. The best-response regions are
Let consist of all nonempty faces of the nonempty , and let consist of all nonempty faces of the nonempty . If , their intersection is obtained in both regions by imposing the equality , so it is a face of both. Consequently, is a polyhedral complex with . The same argument gives .
For each and , fix points
Using the construction from the preliminary section, set
By Proposition 1, these are simplicial complexes and
For each nonempty , define
This is the barycenter of the face of . Let be the barycentric subdivision of . Its vertices are the points , and a set of these vertices spans a simplex exactly when their indexing sets form a chain under inclusion. Moreover,
Theorem 5 (Norde [26]). Every bimatrix game has a quasi-strict Nash equilibrium.
Proof. We construct four simplicial maps as follows:
All these maps send vertices of the simplicial complex (or ) to vertices of the simplicial complex (or ). We verify that whenever vertices span a simplex of , their images span a simplex of . Then we use the same notation for their continuous extensions:
If , then
To prove the first inclusion, suppose that but . Then and . Since , there exists such that every point in the affine hull of at distance less than from belongs to . Moreover, , so the point lies in this affine hull. Choose sufficiently small and then . This contradicts . Therefore .
For the second inclusion, take any . By the definition of , we have . Thus is nonempty and belongs to . Since and belong to the polyhedral complex , their nonempty intersection is a face of . Moreover, . A proper face of cannot contain a point of . We obtain and then . It implies that and .
These arguments are identical for ,
Let . By the definition of , there is a face chain
in such that
Set . By Equation (3),
Hence the corresponding faces of satisfy
Their barycenters are precisely
By the definition of , these barycenters therefore span a simplex:
Similarly, we have
The corresponding faces of form a face chain, whose barycenters are . Thus
The same argument applies to and on each simplex of . By Proposition 2, the four vertex maps extend to continuous simplicial maps.
Following Nash’s modification in the proof of [25], define
For each , define the modified strategies
Both vectors have nonnegative coordinates summing to one. Thus these formulas define a map
The coordinate projections and the four simplicial maps are continuous by Proposition 3, so all the functions and are continuous. Hence is continuous. By Proposition 3, is nonempty, compact, and convex. Since is a continuous self-map, Brouwer’s fixed-point theorem gives a fixed point .
One can show
At the fixed point, the first equation in Equation (5) gives
, for vanishes outside . Then we have
Consequently, there exists such that
and therefore . Since , the fixed-point equation yields
It follows that, for every ,
We obtain
for . The same argument applied to the second equation in Equation (5) gives .
The last step is to extract quasi-strict Nash equilibria from the above fixed point . Choose the unique minimal simplices of and containing and , respectively. Each point lies in the relative interior of its chosen simplex. These simplices correspond to the face chains
We can write the points in barycentric coordinates
where for and for , with and . Rewrite Equation (6) with Equation (2),
We claim that is a quasi-strict Nash equilibrium. By Definition 1, verify the conditions
The first condition holds by Equation (3) and Equation (4). and are the largest index sets, respectively. It follows that they are identical as Equation (7) holds.
To verify the second condition, notice that Equation (8) implies that and have the same set of maximizing indices,
These sets are precisely and , respectively, since they are the smallest sets in the corresponding chains, each is uniform on , and all weights are strictly positive. Hence
Thus is a quasi-strict Nash equilibrium.
Complexity of quasi-strict Nash equilibria in bimatrix games
We now make the construction in Theorem 5 effective. Recall the four simplicial maps , , , from Equation (2) and replace Nash modification by the EY modification in Lemma 1. Denote the EY modification by . For , set
Define by
By Lemma 1, is a continuous self-map of .
Lemma 2. A fixed point of implies and .
Proof. First observe that
Indeed, if , every vertex with a positive coefficient in a barycentric representation of has zero th coordinate. By Equation (2), its image under also has zero th coordinate. Affine interpolation therefore gives . The argument for is identical.
Suppose that is a fixed point of . Since , the coordinates of sum to one. The candidate in the definition of is therefore zero, so .
For every , the fixed-point equation gives
and hence
For , the support property above gives . Consequently,
Every term on the right is nonnegative. Since , it follows that and for all . Thus . Applying the same argument to the second component gives .
Recall Equation (1). In topology, a standard choice of a relative-interior point for each face is its barycenter, defined as the average of its vertices, as illustrated in Example 5. For our purposes, however, computing this average by enumerating the vertices can be inefficient. A polytope in defined by linear inequalities may have exponentially many vertices. Moreover, the barycenter plays no special role in our construction, so we instead use linear programming to compute a relative-interior point.
Lemma 3. For , let
Given these index sets, a rational point can be computed in polynomial time. The same holds for .
Proof. Select as the smallest index in the set and solve
Since is a face of , the zero-coordinate and payoff-tie equalities recorded by and cut out within . The remaining inequalities are strict on , so the optimal value satisfies . Consequently, the -component of every optimal solution lies in . Using a fixed deterministic LP algorithm [18, 17] selects the same point whenever the same face occurs, with polynomial running time and output encoding length. The construction for is analogous, using in place of .
To obtain our membership result, we verify the three conditions in Definition 6. The first is immediate. For the second condition, start with the property of function composition.
Lemma 4. For each input instance , let and be composable continuous maps, with all dimensions polynomially bounded in . If both maps satisfy the second condition of Definition 6, then their composition satisfies the second condition as well.
Proof. On a cell of , write . Substituting into a dividing hyperplane for gives
If , this equation introduces no new dividing hyperplane. Take all original dividing hyperplanes for , together with all nontrivial hyperplanes obtained by the above substitutions over all cells of . This finite collection divides the domain of into polyhedral regions on each of which a fixed affine formula for applies and its image lies in a region with a fixed affine formula for . If these formulas are and , respectively, then
Each new coefficient is a sum of at most the intermediate dimension plus one terms, each of which is a product of at most two original coefficients. Since the intermediate dimension and the encoding lengths of the original coefficients are polynomially bounded in , so are the encoding lengths of all new coefficients. Finally, is continuous because and are continuous. Since it is affine on each of the polyhedral regions constructed above, it is piecewise linear.
We now verify the second condition in Definition 6. Recall the function we used in Equation (9)
Let denote the input game. Choose the points and for every and using Lemma 3. It admits that their rational coordinates have a polynomial encoding length of . Select any -simplex of , and set the matrix . This matrix is invertible, for these points are affinely independent and for each valid . Let the matrices and contain the corresponding vertex images under and , respectively. Formally,
Then, the local formulas are
The entries of and are either zero or reciprocals of positive integers at most . Since the entries of have polynomial encoding length, standard bounds for rational matrix inversion imply the same for . The same argument applies to and on a -simplex . Therefore, the coefficients of local formulas and have polynomial size.
Each -simplex and -simplex can be described by
The union of dividing hyperplanes in above two sets represents the dividing hyperplanes of the cell in the space . These coefficients of dividing hyperplanes have polynomial size as well. Thus, both maps and meet the second condition in Definition 6.
For , we index the affine pieces by the coordinates retained after thresholding. For an input , let . This set is nonempty, and the threshold equation gives
Thus fixing fixes an affine expression for the threshold.
For each nonempty , consider the region
On this region, the vector
is nonnegative and sums to one, so it is indeed the output of by uniqueness of the threshold. Consequently, is affine on , including its boundary, and these regions cover .
The required dividing hyperplanes are obtained from the nontrivial equations over all such . Their coefficients and those of the affine formulas have encoding length , hence polynomial in . Thus satisfies the second condition of Definition 6. The argument for is identical.
Using Lemma 4, the composition maps and also meet the second condition in Definition 6. Taking the union of the dividing hyperplane collections for the two composition maps gives regions on which both affine formulas apply. Concatenating these formulas also satisfies the second condition.
Next is to locate simplices of and containing and respectively, using only linear comparisons in the original input. Once these simplices are known, the required affine formula follows from Equation (10) and Lemma 1.
Lemma 5. Given a rational bimatrix game , there exists a polynomial-time algorithm with access to a linear-comparison oracle for that outputs No if . Otherwise, it returns the local formula .
Proof. Write and consider the two parts separately by setting the coefficients corresponding to the other one to zero in each query. Test the constraints of . If any test fails, reject. Recall the best-response regions are
Use the oracle to locate a concrete pair of polytopes s.t. and . Since each has an explicit rational inequality description of polynomial encoding length, a strong optimization oracle for can be implemented in polynomial time by rational linear programming. Hence, for every nonempty , its dimension can be computed in polynomial time by [11 Lemma 6.5.3 and Remark 6.5.4(b)]. We can always choose the polytopes such that and since the full-dimensional regions must cover . Otherwise, the union of these closed sets would leave a full-dimensional open set in covered only by finitely many lower-dimensional regions, which is impossible. The same holds for the regions in .
For the selected region , first compute its label sets by linear programming:
These computations use only the explicit inequality description of . Given these labels, apply Lemma 3 to obtain the prescribed point . The labels and interior point for are computed analogously.
Then we need to compute the corresponding -simplex in and the corresponding -simplex in , respectively. Equivalently, compute two sets of points and such that and . We next show how to compute recursively. Set , , and . The initial label sets are and .
At stage , we maintain a polytope , its label sets and , its prescribed relative-interior point , and a matrix defining target point . In each stage, first test whether . We can compare them directly using oracle for the first stage. As shown later, this test can also be achieved using linear comparisons in the original input for other stages.
If , consider the ray
Let be its first intersection with a facet of , and choose that facet as , breaking ties by a fixed ordering.
To find this intersection, we first determine the facets of from its label sets and . Fix , and consider the inequalities
These are the inequalities in the label-based description of that are not identically tight on . For each such inequality , form
and retain if is nonempty and . These tests can be performed in polynomial time by rational linear programming. Let be the resulting set of functions. Every facet of is represented by at least one function in . Each is homogeneous linear, is nonnegative on , and satisfies , since .
For , if the corresponding facet intersects with the ray, substituting the ray into gives
We have
Choosing another , if it also intersects with the ray, we can compare
Otherwise, if the ray also misses the supporting hyperplane , then . It is also possible that the ray meets this hyperplane outside , possibly outside , while . In this case, before reaching that intersection at , the ray must meet some facet with defining function at a parameter . By the same comparison,
Hence such an intersection outside cannot yield the minimum ratio. Thus the first facet encountered is obtained by choosing that minimizes , breaking ties by the fixed ordering.
To implement these comparisons using only linear queries in the original input , store the target points as
where is a rational matrix with polynomial size and . The vectors and points are used only as symbolic quantities. The algorithm explicitly stores the rational matrix , rather than the numerical values of , , or . Initially, . The facet comparison becomes
which is a linear comparison in the original . After selecting , the intersection is exactly
We therefore preserve the representation by setting
Moreover, based on above analysis. Writing , update the matrix by
Thus, , which is a rational matrix. Not hard to verify that has polynomial size for each and thus has polynomial size for each . Additionally, since is a point in . We obtain .
To update the labels of the selected facet, delete coordinates identical to zero in and add new best-response actions in by linear programming,
Using the updated labels, apply Lemma 3 to compute the prescribed point .
If , complete the remaining face chain by choosing facets according to the fixed ordering and applying the same label updates and interior-point computations. No further target points are needed, and all subsequent barycentric coefficients are zero.
We now address the issue above. Determining whether using a linear-comparison oracle for the original input is equivalent to determining whether , which just uses linear comparisons.
The resulting complete face chain determines an -simplex
containing . The correctness can be proved by induction since for each valid . The same argument applies to .
Based on the above analysis, the local formulas of all four simplicial maps can be determined by (10). Execute the Euclidean projection algorithm of Lemma 1 on our formula
Each comparison becomes
which is also a linear comparison in the original input. The resulting local formula for is obtained in polynomial time. This concludes our proof.
Theorem 1. Computing a quasi-strict Nash equilibrium of a bimatrix game is PPAD-complete.
Proof. For hardness, use PPAD-completeness of computing a bimatrix Nash equilibrium by [6].
For membership, using Theorem 3, we can obtain a fixed point of , which is rational and can be computed in PPAD. Execute the algorithm in Lemma 5 on input . Since the input is rational, the oracle is no longer needed and all linear comparisons can be finished in polynomial time. As the intermediate result of the algorithm, we have and , together with and defined in (10). Compute the barycentric coordinates as follows
Select
As the proof of Theorem 5 shows, is a quasi-strict Nash equilibrium.
Complexity of deciding whether quasi-strict Nash equilibria exist
Theorem 2. For every fixed , deciding whether an -player game in strategic form with rational payoffs admits a quasi-strict Nash equilibrium is -complete, even for zero-sum games.
Proof. Containment in for general-sum games is straightforward. Namely, let denote the expected payoff if player chooses action from action set . Introduce a real variable to denote the best-response payoff of player and a vector of real variables to denote the strategy. We can construct an existential formula
It uses only polynomial equalities and inequalities.
For hardness, take an instance of Theorem 4. Construct a three-player game with action sets
Define its payoffs in the following form, where player 1 selects the matrix, player 2 selects the row, and player 3 selects the column. The first matrix applies to any , with in its block and all other displayed payoff vectors are constant on their blocks. Every payoff vector sums to zero.
The construction adds one action per player and uses only the original payoff entries, their negatives, and , so its size and encoding length are polynomial in the input size.
Suppose first that . Choose the full-support strategies supplied by the promise. Let be uniform on , and set
where the last coordinate corresponds to the additional action. It’s easy to check that all three strategies are valid. Moreover,
The first equation follows from for each . For the second equation, assigns equal probabilities to each pair , so every original action of player 2 has expected payoff zero. The action yields payoff . The last equation holds because , so every action of player 3 has payoff zero. Thus is a quasi-strict Nash equilibrium of , for
Conversely, let be a quasi-strict Nash equilibrium of . We first show that . If , player 3’s action has positive payoff, while every original action has payoff zero. Hence player 3 plays with probability one. Player 1’s action then yields zero, while every original action yields , so player 1 plays with probability one. But player 2’s action now yields , while every original action yields zero, contradicting .
Since , every action of player 3 has payoff zero. QSNE requires full support on . Suppose, for a contradiction, that . Player 1’s action yields payoff zero. QSNE therefore requires player 1’s equilibrium payoff to be strictly positive. Since player 3’s payoff is zero and the game is zero-sum, player 2’s equilibrium payoff must be strictly negative. However, when , player 2 can obtain zero by switching to , which is a valuable deviation. This contradicts the Nash equilibrium condition, so .
Define two normalized vectors
Since is played with positive probability and yields payoff zero, for each pair , we have
The condition in Theorem 4 implies for every and then . We have therefore proved, on the promised instances,
This establishes -hardness for three-player zero-sum games.
Given any fixed , add players, each with a single action and constant zero payoff, and leave the original payoffs independent of these players. This preserves the existence of quasi-strict Nash equilibria and the zero-sum property, completing the proof.
AI methodology
ChatGPT-6 Astra was used to assist in developing the proofs, and in particular provided a correction to the step of the proof that recovers a quasi-strict equilibrium from a fixed point. This tool was also used to assist in writing the paper and preparing the figures. The authors have verified all proofs and naturally take full responsibility for all mathematical claims given in the paper.
Acknowledgements
Kristoffer Arnsfelt Hansen and Xinhao Nie were supported by the Independent Research Fund Denmark under grant no. 10.46540/4283-00272B. This work was also supported in part by a grant of access to OpenAI models through the ChatGPT for Academic Researchers program.
References
- [1]Felix Brandt and Felix Fischer. On the hardness and existence of quasi-strict equilibria. In Burkhard Monien and Ulf-Peter Schroeder, editors, Algorithmic Game Theory, pages 291–302, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. 2, 3DOI
- [2]Marie Louisa Tølbøll Berthelsen and Kristoffer Arnsfelt Hansen. On the computational complexity of decision problems about multi-player Nash equilibria. Theory of Computing Systems, 66(3):519–545, 2022. 3, 9
- [4]L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71:97–115, 1911. 1
- [5]John Canny. Some algebraic and geometric computations in PSPACE. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 460–467, 1988. 9DOI
- [6]Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM (JACM), 56(3):1–57, 2009. 2, 3, 19arxiv.org/abs/0704.1678
- [7]Robin P. Cubitt and Robert Sugden. Rationally justifiable play and the theory of non-cooperative games. The Economic Journal, 104(425):798–803, 1994. 1DOI
- [8]Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a Nash equilibrium. Communications of the ACM, 52(2):89–97, 2009. 2, 3
- [11]M. Grötschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics. Springer Berlin Heidelberg, 2012. 16
- [13]John C. Harsanyi. Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points. International journal of game theory, 2(1):1–23, 1973. 1
- [14]John C. Harsanyi. Oddness of the number of equilibrium points: A new proof. International journal of game theory, 2(1):235–250, 1973. 1
- [15]Kristoffer Arnsfelt Hansen and Troels Bjerre Lund. Computational complexity of proper equilibrium. In Proceedings of the 2018 ACM Conference on Economics and Computation, EC ’18, pages 113–130, New York, NY, USA, 2018. ACM. 3DOI
- [16]Shizuo Kakutani. A generalization of Brouwer’s fixed point theorem. Duke Mathematical Journal, 8(3):457–459, 1941. 1DOI
- [17]Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302–311, 1984. 14
- [18]Leonid G. Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, 20(1):53–72, 1980. 14DOI
- [19]Paul Milgrom and Joshua Mollner. Equilibrium selection in auctions and high stakes games. Econometrica, 86(1):219–261, 2018. 4DOI
- [20]Peter Bro Miltersen and Troels Bjerre Sørensen. Computing proper equilibria of zero-sum games. In Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29–31, 2006. Proceedings, volume 4630 of Lecture Notes in Computer Science, pages 200–211. Springer, 2007. 3DOI
- [21]Andrew McLennan and Rabee Tourky. Simple complexity from imitation games. Games and Economic Behavior, 68(2):683–688, 2010. 3DOI
- [22]J.R. Munkres. Topology. Featured Titles for Topology. Prentice Hall, Incorporated, 2000. 4, 8
- [23]J.R. Munkres. Elements Of Algebraic Topology. Textbooks in Mathematics. CRC Press, 2018. 4, 5
- [24]R. B. Myerson. Refinements of the Nash equilibrium concept. International Journal of Game Theory, 15:133–154, 1978. 3DOI
- [25]John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286–295, 1951. 1, 2, 9, 12
- [26]Henk Norde. Bimatrix games have quasi-strict equilibria. Mathematical Programming, 85(1):35, 1999. 1, 4, 10DOI
- [27]OpenAI. Existential–universal real sentences in the counting hierarchy. OpenAI Math Release preprint OAI:Existential-universal-real-sentences-in-the-counting-hierarchy-October-4-2026, 2026. 9
- [28]Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):498–532, 1994. 2, 8DOI
- [29]Reinhard Selten. A reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4:25–55, 1975. 3DOI
- [30]Troels Bjerre Sørensen. Computing a proper equilibrium of a bimatrix game. In Boi Faltings, Kevin Leyton-Brown, and Panos Ipeirotis, editors, ACM Conference on Electronic Commerce, EC ’12, pages 916–928. ACM, 2012. 3DOI
- [31]David Squires. Impossibility theorems for normal form games. Theory and Decision, 44(1):67–81, 1998. 1DOI
- [32]Eric van Damme. Stability and Perfection of Nash Equilibria. Springer-Verlag, Berlin, Heidelberg, 2nd edition, 1991. 1


