betaFeedback

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 ∃R\exists\mathbb{R}-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 TT of pure strategies of player 2, a generalized permutahedron KTK_T is constructed in the relative interior of the face of the strategy simplex Δm\Delta_m of player 2 defined by TT, chosen to approximate this relative interior sufficiently well. On each such set KTK_T, a continuous best-response function fT:KT→Δnf_T: K_T \to\Delta_n for player 1 is constructed and a corresponding best-response function gT:Δn→KTg_T: \Delta_n \to K_T for player 2 defined using projection and a scaling of the payoffs by a large positive constant kk. A continuous function hk:Δm→Δmh_k: \Delta_m \to\Delta_m is then defined as a weighted combination of the functions fT∘gTf_T \circ g_T to which Brouwer’s fixed point theorem applies. Finally, it is proved that limit points of fixed points of the functions hkh_k, as kk 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 ε\varepsilon-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 TT 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 TT.

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 II of a polynomial piecewise linear fixed point problem is given by a continuous self-map FIF_I of a nonempty compact convex domain DID_I, divided in polyhedral cells on which FIF_I is linear. The domain DID_I is given by a set of linear inequalities with rational coefficients computable from II and the linear function, which must be defined by a rational matrix and vector, of a given cell containing a point xx must be computable in polynomial time by an oracle algorithm that can perform linear comparison queries of the form aTx≤ba^{\mathsf{T}}x \le b with rational-valued aa and bb.

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 ∃R\exists\mathbb{R} 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 ∃R\exists\mathbb{R}-hard, thereby settling the complexity of the problem.

Theorem 2. For every fixed n≥3n \ge3, deciding whether an nn-player game in strategic form with rational payoffs admits a quasi-strict Nash equilibrium is ∃R\exists\mathbb{R}-complete, even for zero-sum games.

The proof is based on ∃R\exists\mathbb{R}-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 ∃R\exists\mathbb{R}-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 FIXPa\mathrm{FIXP}_a, i.e. that the problem of computing a strategy profile that is ε\varepsilon-close to a perfect equilibrium for a given ε>0\varepsilon> 0 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 FIXPa\mathrm{FIXP}_a 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 k≥1k \ge1, we let [k][k] denote the set {1,…,k}\{1,\ldots,k\} and let Δk\Delta_k denote the standard (k−1)(k-1)-simplex given by

Δk:={z∈Rk:zi≥0 for all i∈[k], ∑i=1kzi=1}.\Delta_k := \left\{z \in\mathbb{R}^k : z_i \ge0 \text{ for all } i \in[k],\ \sum_{i=1}^{k} z_i = 1\right\}.

A point z∈Δkz \in\Delta_k can be viewed as a probability distribution on [k][k] and we define supp⁡(z)={i∈[k]:zi>0}\operatorname{supp}(z) = \{i \in[k] : z_i > 0\}.

Definition 1 (Two-player Bimatrix games and Quasi-strict Nash Equilibria). Let M:=[m]M := [m] be the set of pure strategies of player 1 and N:=[n]N := [n] be the set of pure strategies of player 2. We let x∈Δmx \in\Delta_m and y∈Δny \in\Delta_n denote the mixed strategies of player 1 and player 2, respectively. A bimatrix game is given by a pair I:=(A,B)I := (A, B) of matrices A,B∈Rm×nA, B \in\mathbb{R}^{m \times n} specifying payoffs of player 1 and player 2, respectively. For the matrix AA and probability vector yy, the set

BR1(y):={i∈M:i∈arg⁡max⁡j∈MejTAy}BR_1(y) := \{i \in M : i \in\arg\max_{j \in M} e_j^{\mathsf{T}}Ay\}

is the set of pure best responses of player 1 to strategy yy. For the matrix BB and probability vector xx, the set

BR2(x):={i∈N:i∈arg⁡max⁡j∈NxTBej}BR_2(x) := \{i \in N : i \in\arg\max_{j \in N} x^{\mathsf{T}}Be_j\}

is the set of pure best responses of player 2 to strategy xx. A Nash equilibrium is a pair of mixed strategies (x∗,y∗)(x^*, y^*) satisfying

supp⁡(x∗)⊆BR1(y∗)andsupp⁡(y∗)⊆BR2(x∗).\operatorname{supp}(x^*) \subseteq BR_1(y^*) \qquad\text{and} \qquad\operatorname{supp}(y^*) \subseteq BR_2(x^*).

A quasi-strict Nash equilibrium further requires that

supp⁡(x∗)=BR1(y∗)andsupp⁡(y∗)=BR2(x∗).\operatorname{supp}(x^*) = BR_1(y^*) \qquad\text{and} \qquad\operatorname{supp}(y^*) = BR_2(x^*).

When considering the computational problem of finding an equilibrium, the payoff matrices are defined on the rational number field Q\mathbb{Q}. The following example is adapted from [26], with a modified payoff matrix for player 2. For clarity, we denote player 1’s pure action ii by xix_i and player 2’s pure action jj by yjy_j, rather than using the notation eie_i.

Example 1. Consider the bimatrix game with payoff matrices

A=(−121100011),B=(100010001).A = \begin{pmatrix} -1 & 2 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}.

The best-response relations BR1BR_1 and BR2BR_2 subdivide the strategy simplices Δn\Delta_n and Δm\Delta_m, respectively. As illustrated by the calculation, each closed best-response region is a polytope. For example, write y=q1y1+q2y2+q3y3y=q_1y_1+q_2y_2+q_3y_3, where qi≥0q_i\geq0 and q1+q2+q3=1q_1+q_2+q_3=1. Player 1’s pure action x1x_1 is the unique best response precisely when

BR1(y)={1}⟺{−q1+2q2+q3>q1,−q1+2q2+q3>q2+q3BR_1(y)=\{1\}\Longleftrightarrow \begin{cases} -q_1+2q_2+q_3>q_1,\\ -q_1+2q_2+q_3>q_2+q_3 \end{cases}

Then, q2>q1q_2>q_1 and q1+q2≤1q_1+q_2\leq1 imply q1<12q_1<\frac{1}{2}. For x=p1x1+p2x2+p3x3x=p_1x_1+p_2x_2+p_3x_3, where pi≥0p_i\geq0 and p1+p2+p3=1p_1+p_2+p_3=1, the choice B=I3B=I_3 gives

BR2(x)=arg⁡max⁡j∈[3] pj.BR_2(x)=\underset{j\in[3]}{\arg\max}\ p_j.

Figure 1. Best-response partitions induced by BR1BR_1 on Δn\Delta_n (left) and BR2BR_2 on Δm\Delta_m (right).

Definition 2 (Simplex and Simplicial Complex). Let {a0,a1,…,an}\{a_0,a_1,\ldots,a_n\} be an affinely independent point set in Rn\mathbb{R}^n. The nn-simplex spanned by these points is the set of all points x∈Rnx\in\mathbb{R}^n such that

x=∑i=0ntiaix=\sum_{i=0}^{n}t_i a_i

where ∑i=0nti=1\sum_{i=0}^{n}t_i=1 and ti≥0t_i\geq0 for each ii. For each point xx in the simplex, the coefficients tit_i are uniquely determined. They are called the barycentric coordinates of xx with respect to a0,…,ana_0,\ldots,a_n. A simplicial complex KK in Rn\mathbb{R}^n is a collection of simplices in Rn\mathbb{R}^n such that:

  1. Every face of a simplex of KK is in KK.

  2. The intersection of any two simplices of KK is a face of each of them.

Example 2. In Example 1, the best-response regions on Δn\Delta_n, together with all their faces, form a simplicial complex. On Δm\Delta_m, 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 PP is a bounded subset of Rd\mathbb{R}^d 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 PP.

A polyhedral complex CC is a finite collection of convex polytopes in Rd\mathbb{R}^d such that:

  1. Every face of a polytope of C\mathcal{C} is in C\mathcal{C}.

  1. The intersection of any two polytopes of C\mathcal{C} is a face of each of them.

Example 3. In Example 1, the closed best-response regions on Δm\Delta_m, together with all their nonempty faces, form a polyhedral complex. The best-response regions on Δn\Delta_n could be also considered as a polyhedral complex.

Definition 4 (Face poset and order complex). Let C\mathcal{C} be a polyhedral complex. Its face poset

P(C)=(C,⊆)\mathcal{P}(\mathcal{C})=(\mathcal{C},\subseteq)

consists of its faces ordered by inclusion.

For a finite poset (P,⪯)(\mathcal{P},\preceq), the order complex is the abstract simplicial complex on vertex set P\mathcal{P} whose rr-simplices are the (r+1)(r+1)-element chains

F0≺F1≺⋯≺Fr.F_0\prec F_1\prec\cdots\prec F_r.

In particular, the simplices correspond to chains of faces

F0⊊F1⊊⋯⊊Fr,r≥0.F_0\subsetneq F_1\subsetneq\cdots\subsetneq F_r,\qquad r\geq0.

Example 4. In Example 1, each maximal chain in the face poset has the form

{v}⊊e⊊P,\{v\}\subsetneq e\subsetneq P,

consisting of a vertex, an incident edge, and a two-dimensional polytope. It defines a 2-simplex in the corresponding order complex.

Write relint⁡F\operatorname{relint} F for the interior of FF in its affine hull. For each face F∈CF\in\mathcal{C}, fix a single point

pF∈relint⁡F.p_F\in\operatorname{relint} F.

The same selected point pFp_F is used whenever FF occurs in a chain. Set

K(C,p)={conv⁡{pF0,…,pFr}:F0⊊⋯⊊Fr, Fi∈C, r≥0}.K(\mathcal{C},p)=\{\operatorname{conv}\{p_{F_0},\ldots,p_{F_r}\}:F_0\subsetneq\cdots\subsetneq F_r,\ F_i\in\mathcal{C},\ r\geq0\}.

We use the following standard results without proof; see [Bjö95, §12.2].

Proposition 1. The collection K(C,p)K(\mathcal{C},p) is a simplicial complex with the same underlying space as C\mathcal{C}:

∣K(C,p)∣=∣C∣.|K(\mathcal{C},p)|=|\mathcal{C}|.

Example 5. In Example 1, let

Qi={y∈Δn:i∈BR⁡1(y)},Pj={x∈Δm:j∈BR⁡2(x)}Q_i=\{y\in\Delta_n:i\in\operatorname{BR}_1(y)\},\qquad P_j=\{x\in\Delta_m:j\in\operatorname{BR}_2(x)\}

denote the closed best-response regions. Let Cn\mathcal{C}_n and Cm\mathcal{C}_m consist of all their nonempty faces, respectively. For each face FF, take bFb_F to be the average of its vertices and realize each chain by

F0⊊⋯⊊Fr⟼conv⁡{bF0,…,bFr}.F_0\subsetneq\cdots\subsetneq F_r\longmapsto\operatorname{conv}\{b_{F_0},\ldots,b_{F_r}\}.

This gives barycentric subdivisions of the best-response complexes. By Proposition 1, their underlying spaces are Δn\Delta_n and Δm\Delta_m, respectively.

Figure 2. Barycentric subdivisions of the best-response complexes on Δn\Delta_n (left) and Δm\Delta_m (right). Colors indicate the original best-response regions.

Definition 5 (Simplicial map). Let KK and LL be simplicial complexes, and let

f:K(0)→L(0)f: K^{(0)} \to L^{(0)}

be a map. Suppose that whenever v0,…,vrv_0,\ldots,v_r span a simplex of KK, their images f(v0),…,f(vr)f(v_0),\ldots,f(v_r) are vertices of a simplex of LL.

Define g:∣K∣→∣L∣g: |K| \to|L| on each simplex by

g(∑i=0rtivi)=∑i=0rtif(vi),ti≥0,∑i=0rti=1.g\left(\sum_{i=0}^{r}t_i v_i\right)=\sum_{i=0}^{r}t_i f(v_i), \qquad t_i\geq0,\qquad\sum_{i=0}^{r}t_i=1.

The map gg is called the simplicial map induced by the vertex map ff.

We have the following fundamental property of simplicial maps.

Proposition 2. The simplicial map g:∣K∣→∣L∣g: |K| \to|L| induced by a vertex map satisfying the above condition is well-defined and continuous.

Example 6. For the game in Example 1, where m=n=3m=n=3, give the target strategy simplex Δ3\Delta_3 its barycentric subdivision. On the vertices bFb_F of the source subdivision in Example 5, define

R1(bF)=1∣BR1(bF)∣∑i∈BR1(bF)xi,F∈Cn.R_1(b_F)=\frac{1}{|BR_1(b_F)|}\sum_{i\in BR_1(b_F)}x_i,\qquad F\in\mathcal{C}_n.

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 R1:Δ3→Δ3R_1:\Delta_3\to\Delta_3.

Let M=(y1+y2)/2M=(y_1+y_2)/2, and let q0,q1,q2q_0,q_1,q_2 be the barycenters of the faces in the chain

{M}⊊conv⁡{M,y3}⊊Q1.\{M\}\subsetneq\operatorname{conv}\{M,y_3\}\subsetneq Q_1.

Their best-response sets are {1,2,3}\{1,2,3\}, {1,3}\{1,3\}, and {1}\{1\}, respectively, so the vertex rule gives

r0=R1(q0)=x1+x2+x33,r1=R1(q1)=x1+x32,r2=R1(q2)=x1.r_0=R_1(q_0)=\frac{x_1+x_2+x_3}{3},\qquad r_1=R_1(q_1)=\frac{x_1+x_3}{2},\qquad r_2=R_1(q_2)=x_1.

Extending qi↦riq_i\mapsto r_i affinely maps the shaded simplex to the shaded target simplex.

Figure 3. A simplicial map R1:Δ3→Δ3R_1:\Delta_3\to\Delta_3. The shaded simplices correspond under qi↦riq_i\mapsto r_i.

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:

  1. Let X⊆RmX\subseteq\mathbb{R}^{m} and Y⊆RnY\subseteq\mathbb{R}^{n} be polytopes. The function f:X×Y→X×Yf:X\times Y\to X\times Y is continuous if and only if the coordinate functions f1:X×Y→Xf_1:X\times Y\to X and f2:X×Y→Yf_2:X\times Y\to Y are continuous.

  1. Let f:X→Rrf:X\to\mathbb{R}^{r} be continuous. Then the function f∘πX:X×Y→Rrf\circ\pi_X:X\times Y\to\mathbb{R}^{r} is continuous.

  1. For two simplices Δm\Delta_m and Δn\Delta_n, the product Δm×Δn\Delta_m\times\Delta_n is a nonempty compact convex subset of Rm+n\mathbb{R}^{m+n}.

Next, we introduce related complexity classes and tools needed. A polynomial-time search reduction consists of polynomial-time computable maps ff and gg such that, for every instance II of the source problem and every solution zz of the target instance f(I)f(I), the output g(I,z)g(I,z) is a solution of II. 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 II, let

FI:DI→DIF_I:D_I\to D_I

be a continuous self-map of a nonempty compact convex domain DID_I. This defines a polynomial piecewise-linear fixed-point problem if the following hold:

  1. DID_I is a polytope defined by a set of linear inequalities. And coefficients can be computed from II in polynomial time.

  1. There is a collection of hyperplanes dividing DID_I into polyhedral regions on each of which FIF_I 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 ∣I∣|I| uniformly.

  1. There is a polynomial-time algorithm that interacts with a linear-comparison oracle for the point xx. Each query asks whether a⊤x≤ba^{\top}x \le b with rational input aa and bb, and may depend on the answers to previous queries. If x∉DIx \notin D_I, the algorithm outputs No; otherwise, it outputs a rational matrix CC and a rational vector cc specifying the local affine formula applicable at xx, so that FI(x)=Cx+cF_I(x)=Cx+c.

The following exact fixed-point theorem is due to Etessami and Yannakakis [EY10, Theorem 5.2].

Theorem 3. For every instance II of a polynomial piecewise-linear fixed-point problem, there exists a rational fixed point xx s.t. FI(x)=xF_I(x)=x and its encoding length is polynomial in ∣I∣\lvert I\rvert. 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 z∈Rkz \in\mathbb{R}^{k}, let z(1)≥⋯≥z(k)z_{(1)} \ge\cdots\ge z_{(k)} be its coordinates in decreasing order, and define

tk(z)=max⁡1≤a≤k∑i=1az(i)−1a,t_k(z)=\max_{1\le a\le k}\frac{\sum_{i=1}^{a}z_{(i)}-1}{a},

and for each i∈[k]i\in[k],

zi↦max⁡{zi−tk(z),0}.z_i\mapsto\max\{z_i-t_k(z),0\}.

Then tk(z)t_k(z) is the unique real number tt satisfying

∑i=1kmax⁡{zi−t,0}=1.\sum_{i=1}^{k}\max\{z_i-t,0\}=1.

This projection maps Rk\mathbb{R}^{k} into Δk\Delta_k, 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 z∈Rkz\in\mathbb{R}^{k}.

The complexity class used in our result about multiplayer games is the class ∃R\exists\mathbb{R}. Its canonical complete problem, the existential theory of the reals (ETR), asks whether a sentence of the form

∃x1,…,xn∈R:φ(x1,…,xn)\exists x_1,\ldots,x_n\in\mathbb{R}:\varphi(x_1,\ldots,x_n)

is true, where φ\varphi is a quantifier-free formula with equalities and inequalities involving polynomials with rational coefficients. One may think of ∃R\exists\mathbb{R} as an analogue of NP, and ETR as an analogue of SAT. It is easy to see that NP⊆∃R\mathrm{NP}\subseteq\exists\mathbb{R}. Canny proved that ∃R⊆PSPACE\exists\mathbb{R}\subseteq\mathrm{PSPACE} in [5].1

We use the minmax hardness theorem in 3-player games given by Hansen [Han19, Theorem 1] to establish ∃R\exists\mathbb{R}-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 xi=yi≤1/2x_i=y_i\le1/2 in the case of the minmax value being 0).

Theorem 4. Let GG be a three-player game GG with pure strategy sets AA, XX, YY and a rational valued payoff function rr of player 1. Suppose A={ak+,ak−:k∈[t]}A = \{a_k^+, a_k^- : k \in[t]\} and

r(ak+,b,c)=−r(ak−,b,c)∀k∈[t], b∈X, c∈Y.r(a_k^+, b, c) = -r(a_k^-, b, c) \qquad\forall k \in[t],\ b \in X,\ c \in Y.

Define

V(G)=min⁡x∈ΔX, y∈ΔYmax⁡a∈Ar(a,x,y).V(G) = \min_{x \in\Delta_X,\, y \in\Delta_Y} \max_{a \in A} r(a,x,y).

It is then R\mathbb{R}-hard to decide whether V(G)=0V(G) = 0 under the promise that the game GG meets one of the following conditions:

  1. V(G)>0V(G) > 0;

  1. V(G)=0V(G) = 0, and there exist full-support strategies x∈ΔXx \in\Delta_X and y∈ΔYy \in\Delta_Y such that r(a,x,y)=0r(a,x,y) = 0 for every a∈Aa \in A.

Existence of quasi-strict Nash equilibria in bimatrix games

We use the notation introduced in the preliminary section. The best-response regions are

Qi={y∈Δn:i∈BR1(y)}={y∈Δn:(Ay)i≥(Ay)h for all h∈M},Q_i = \{y \in\Delta_n : i \in BR_1(y)\} = \{y \in\Delta_n : (Ay)_i \ge(Ay)_h \text{ for all } h \in M\},
Pj={x∈Δm:j∈BR2(x)}={x∈Δm:(BTx)j≥(BTx)ℓ for all ℓ∈N}.P_j = \{x \in\Delta_m : j \in BR_2(x)\} = \{x \in\Delta_m : (B^{\mathsf{T}}x)_j \ge(B^{\mathsf{T}}x)_\ell\text{ for all } \ell\in N\}.

Let Cn\mathcal{C}_n consist of all nonempty faces of the nonempty QiQ_i, and let Cm\mathcal{C}_m consist of all nonempty faces of the nonempty PjP_j. If Pj∩Pℓ≠∅P_j \cap P_\ell\ne\varnothing, their intersection is obtained in both regions by imposing the equality (BTx)j=(BTx)ℓ(B^{\mathsf{T}}x)_j = (B^{\mathsf{T}}x)_\ell, so it is a face of both. Consequently, Cm\mathcal{C}_m is a polyhedral complex with ∣Cm∣=Δm|\mathcal{C}_m| = \Delta_m. The same argument gives ∣Cn∣=Δn|\mathcal{C}_n| = \Delta_n.

For each F∈CmF \in\mathcal{C}_m and G∈CnG \in\mathcal{C}_n, fix points

pF∈relint⁡F,qG∈relint⁡G.(1)p_F \in\operatorname{relint} F,\qquad q_G \in\operatorname{relint} G. \tag*{(1)}

Using the construction from the preliminary section, set

Km=K(Cm,p),Kn=K(Cn,q).K_m = \mathcal{K}(\mathcal{C}_m,p),\qquad K_n = \mathcal{K}(\mathcal{C}_n,q).

By Proposition 1, these are simplicial complexes and

∣Km∣=Δm,∣Kn∣=Δn.|K_m| = \Delta_m,\qquad|K_n| = \Delta_n.

For each nonempty I⊆[k]I \subseteq[k], define

ℓk(I)=1∣I∣∑i∈Iei.\ell_k(I) = \frac{1}{|I|}\sum_{i \in I} e_i.

This is the barycenter of the face conv⁡{ei:i∈I}\operatorname{conv}\{e_i : i \in I\} of Δk\Delta_k. Let UkU_k be the barycentric subdivision of Δk\Delta_k. Its vertices are the points ℓk(I)\ell_k(I), and a set of these vertices spans a simplex exactly when their indexing sets form a chain under inclusion. Moreover,

∣Km∣=∣Um∣=Δm,∣Kn∣=∣Un∣=Δn.|K_m| = |U_m| = \Delta_m,\qquad|K_n| = |U_n| = \Delta_n.

Theorem 5 (Norde [26]). Every bimatrix game has a quasi-strict Nash equilibrium.

Proof. We construct four simplicial maps as follows:

S1(pF)=ℓm(supp⁡(pF)),R2(pF)=ℓn(BR2(pF)),S2(qG)=ℓn(supp⁡(qG)),R1(qG)=ℓm(BR1(qG)).(2)\begin{aligned} S_1(p_F)&=\ell_m(\operatorname{supp}(p_F)), & R_2(p_F)&=\ell_n(BR_2(p_F)),\\ S_2(q_G)&=\ell_n(\operatorname{supp}(q_G)), & R_1(q_G)&=\ell_m(BR_1(q_G)). \tag*{(2)} \end{aligned}

All these maps send vertices of the simplicial complex Km\mathcal{K}_m (or Kn\mathcal{K}_n) to vertices of the simplicial complex Um\mathcal{U}_m (or Un\mathcal{U}_n). We verify that whenever vertices span a simplex of K\mathcal{K}, their images span a simplex of U\mathcal{U}. Then we use the same notation for their continuous extensions:

S1:Δm→Δm,R2:Δm→Δn,S_1:\Delta_m\to\Delta_m,\qquad R_2:\Delta_m\to\Delta_n,
S2:Δn→Δn,R1:Δn→Δm.S_2:\Delta_n\to\Delta_n,\qquad R_1:\Delta_n\to\Delta_m.

If F⊆F′F\subseteq F', then

supp⁡(pF)⊆supp⁡(pF′),BR2(pF)⊇BR2(pF′).(3)\operatorname{supp}(p_F)\subseteq\operatorname{supp}(p_{F'}),\qquad BR_2(p_F)\supseteq BR_2(p_{F'}). \tag*{(3)}

To prove the first inclusion, suppose that i∈supp⁡(pF)i\in\operatorname{supp}(p_F) but i∉supp⁡(pF′)i\notin\operatorname{supp}(p_{F'}). Then (pF)i>0(p_F)_i>0 and (pF′)i=0(p_{F'})_i=0. Since pF′∈relint⁡F′p_{F'}\in\operatorname{relint} F', there exists δ>0\delta>0 such that every point in the affine hull of F′F' at distance less than δ\delta from pF′p_{F'} belongs to F′F'. Moreover, pF∈F⊆F′p_F\in F\subseteq F', so the point zε=pF′+ε(pF′−pF)z_\varepsilon=p_{F'}+\varepsilon(p_{F'}-p_F) lies in this affine hull. Choose ε>0\varepsilon>0 sufficiently small and then zε∈F′z_\varepsilon\in F'. This contradicts F′⊆ΔmF'\subseteq\Delta_m. Therefore supp⁡(pF)⊆supp⁡(pF′)\operatorname{supp}(p_F)\subseteq\operatorname{supp}(p_{F'}).

For the second inclusion, take any j∈BR2(pF′)j\in BR_2(p_{F'}). By the definition of PjP_j, we have pF′∈Pjp_{F'}\in P_j. Thus PjP_j is nonempty and belongs to Cm\mathcal{C}_m. Since F′F' and PjP_j belong to the polyhedral complex Cm\mathcal{C}_m, their nonempty intersection F′∩PjF'\cap P_j is a face of F′F'. Moreover, pF′∈(F′∩Pj)∩relint⁡F′p_{F'}\in(F'\cap P_j)\cap\operatorname{relint}F'. A proper face of F′F' cannot contain a point of relint⁡F′\operatorname{relint}F'. We obtain F′∩Pj=F′F'\cap P_j=F' and then F′⊆PjF'\subseteq P_j. It implies that pF∈F⊆F′⊆Pjp_F\in F\subseteq F'\subseteq P_j and j∈BR2(pF)j\in BR_2(p_F).

These arguments are identical for G⊆G′G\subseteq G',

supp⁡(qG)⊆supp⁡(qG′),BR1(qG)⊇BR1(qG′).(4)\operatorname{supp}(q_G)\subseteq\operatorname{supp}(q_{G'}),\qquad BR_1(q_G)\supseteq BR_1(q_{G'}). \tag*{(4)}

Let σ∈Km\sigma\in\mathcal{K}_m. By the definition of Km\mathcal{K}_m, there is a face chain

F0⊊⋯⊊FrF_0\subsetneq\cdots\subsetneq F_r

in Cm\mathcal{C}_m such that

σ=conv⁡{pF0,…,pFr}.\sigma=\operatorname{conv}\{p_{F_0},\ldots,p_{F_r}\}.

Set It=supp⁡(pFt)I_t=\operatorname{supp}(p_{F_t}). By Equation (3),

I0⊆⋯⊆Ir.I_0\subseteq\cdots\subseteq I_r.

Hence the corresponding faces of Δm\Delta_m satisfy

conv⁡{ei:i∈I0}⊆⋯⊆conv⁡{ei:i∈Ir}.\operatorname{conv}\{e_i:i\in I_0\}\subseteq\cdots\subseteq\operatorname{conv}\{e_i:i\in I_r\}.

Their barycenters are precisely

ℓm(It)=S1(pFt).\ell_m(I_t)=S_1(p_{F_t}).

By the definition of Um\mathcal{U}_m, these barycenters therefore span a simplex:

conv⁡{S1(pF0),…,S1(pFr)}∈Um.\operatorname{conv}\{S_1(p_{F_0}),\ldots,S_1(p_{F_r})\}\in\mathcal{U}_m.

Similarly, we have

BR2(pFr)⊆⋯⊆BR2(pF0).BR_2(p_{F_r})\subseteq\cdots\subseteq BR_2(p_{F_0}).

The corresponding faces of Δn\Delta_n form a face chain, whose barycenters are R2(pFt)R_2(p_{F_t}). Thus

conv⁡{R2(pF0),…,R2(pFr)}∈Un.\operatorname{conv}\{R_2(p_{F_0}),\ldots,R_2(p_{F_r})\}\in\mathcal{U}_n.

The same argument applies to S2S_2 and R1R_1 on each simplex of Kn\mathcal{K}_n. By Proposition 2, the four vertex maps extend to continuous simplicial maps.

Following Nash’s modification in the proof of [25], define

φ1i(x,y)=max⁡{0,(R1(y))i−(S1(x))i},i∈M,\varphi_{1i}(x,y)=\max\{0,(R_1(y))_i-(S_1(x))_i\},\quad i\in M,
φ2j(x,y)=max⁡{0,(R2(x))j−(S2(y))j},j∈N.\varphi_{2j}(x,y)=\max\{0,(R_2(x))_j-(S_2(y))_j\},\quad j\in N.

For each (x,y)∈Δm×Δn(x,y)\in\Delta_m\times\Delta_n, define the modified strategies

x′=x+∑i∈Mφ1i(x,y)ei1+∑i∈Mφ1i(x,y),y′=y+∑j∈Nφ2j(x,y)ej1+∑j∈Nφ2j(x,y).(5)x'=\frac{x+\sum_{i\in M}\varphi_{1i}(x,y)e_i}{1+\sum_{i\in M}\varphi_{1i}(x,y)},\qquad y'=\frac{y+\sum_{j\in N}\varphi_{2j}(x,y)e_j}{1+\sum_{j\in N}\varphi_{2j}(x,y)}. \tag*{(5)}

Both vectors have nonnegative coordinates summing to one. Thus these formulas define a map

T:Δm×Δn⟶Δm×Δn.T:\Delta_m\times\Delta_n\longrightarrow\Delta_m\times\Delta_n.

The coordinate projections and the four simplicial maps are continuous by Proposition 3, so all the functions φ1i\varphi_{1i} and φ2j\varphi_{2j} are continuous. Hence TT is continuous. By Proposition 3, Δm×Δn\Delta_m\times\Delta_n is nonempty, compact, and convex. Since TT is a continuous self-map, Brouwer’s fixed-point theorem gives a fixed point (xˉ,yˉ)(\bar{x},\bar{y}).

One can show

S1(xˉ)=R1(yˉ),S2(yˉ)=R2(xˉ).(6)S_1(\bar{x})=R_1(\bar{y}),\qquad S_2(\bar{y})=R_2(\bar{x}). \tag*{(6)}

At the fixed point, the first equation in Equation (5) gives

φ1i(xˉ,yˉ)=xˉi∑h∈Mφ1h(xˉ,yˉ).\varphi_{1i}(\bar{x},\bar{y})=\bar{x}_i\sum_{h\in M}\varphi_{1h}(\bar{x},\bar{y}).

∑i∈supp⁡(xˉ)(S1(xˉ))i=1\sum_{i\in\operatorname{supp}(\bar{x})}(S_1(\bar{x}))_i=1, for S1(xˉ)S_1(\bar{x}) vanishes outside supp⁡(xˉ)\operatorname{supp}(\bar{x}). Then we have

∑i∈supp⁡(xˉ)((R1(yˉ))i−(S1(xˉ))i)=−∑i∉supp⁡(xˉ)(R1(yˉ))i≤0.\sum_{i\in\operatorname{supp}(\bar{x})}\left((R_1(\bar{y}))_i-(S_1(\bar{x}))_i\right) =-\sum_{i\notin\operatorname{supp}(\bar{x})}(R_1(\bar{y}))_i\leq0.

Consequently, there exists i0∈supp⁡(xˉ)i_0\in\operatorname{supp}(\bar{x}) such that

(R1(yˉ))i0≤(S1(xˉ))i0,(R_1(\bar{y}))_{i_0}\leq(S_1(\bar{x}))_{i_0},

and therefore φ1i0(xˉ,yˉ)=0\varphi_{1i_0}(\bar{x},\bar{y})=0. Since xˉi0>0\bar{x}_{i_0}>0, the fixed-point equation yields

∑h∈Mφ1h(xˉ,yˉ)=0.\sum_{h\in M}\varphi_{1h}(\bar{x},\bar{y})=0.

It follows that, for every i∈Mi\in M,

(R1(yˉ))i≤(S1(xˉ))i.(R_1(\bar{y}))_i\leq(S_1(\bar{x}))_i.

We obtain

R1(yˉ)=S1(xˉ)R_1(\bar{y})=S_1(\bar{x})

for ∑i(R1(yˉ))i=∑i(S1(xˉ))i\sum_i(R_1(\bar{y}))_i=\sum_i(S_1(\bar{x}))_i. The same argument applied to the second equation in Equation (5) gives R2(xˉ)=S2(yˉ)R_2(\bar{x})=S_2(\bar{y}).

The last step is to extract quasi-strict Nash equilibria from the above fixed point (xˉ,yˉ)(\bar{x},\bar{y}). Choose the unique minimal simplices of Km\mathcal{K}_m and Kn\mathcal{K}_n containing xˉ\bar{x} and yˉ\bar{y}, respectively. Each point lies in the relative interior of its chosen simplex. These simplices correspond to the face chains

F0⊆⋯⊆Fr,G0⊆⋯⊆Gs.F_0 \subseteq\cdots\subseteq F_r,\qquad G_0 \subseteq\cdots\subseteq G_s.

We can write the points in barycentric coordinates

xˉ=∑t=0rλtpFt,yˉ=∑u=0sμuqGu.\bar{x}=\sum_{t=0}^{r}\lambda_t p_{F_t},\qquad\bar{y}=\sum_{u=0}^{s}\mu_u q_{G_u}.

where λt>0\lambda_t>0 for t=0,…,rt=0,\ldots,r and μu>0\mu_u>0 for u=0,…,su=0,\ldots,s, with ∑t=0rλt=1\sum_{t=0}^{r}\lambda_t=1 and ∑u=0sμu=1\sum_{u=0}^{s}\mu_u=1. Rewrite Equation (6) with Equation (2),

S1(xˉ)=∑t=0rλtℓm(supp⁡(pFt))=∑u=0sμuℓm(BR1(qGu))=R1(yˉ),(7)S_1(\bar{x})=\sum_{t=0}^{r}\lambda_t\ell_m(\operatorname{supp}(p_{F_t}))=\sum_{u=0}^{s}\mu_u\ell_m(BR_1(q_{G_u}))=R_1(\bar{y}), \tag*{(7)}
S2(yˉ)=∑u=0sμuℓn(supp⁡(qGu))=∑t=0rλtℓn(BR2(pFt))=R2(xˉ).(8)S_2(\bar{y})=\sum_{u=0}^{s}\mu_u\ell_n(\operatorname{supp}(q_{G_u}))=\sum_{t=0}^{r}\lambda_t\ell_n(BR_2(p_{F_t}))=R_2(\bar{x}). \tag*{(8)}

We claim that (pFr,qG0)(p_{F_r},q_{G_0}) is a quasi-strict Nash equilibrium. By Definition 1, verify the conditions

supp⁡(pFr)=BR1(qG0),supp⁡(qG0)=BR2(pFr).\operatorname{supp}(p_{F_r})=BR_1(q_{G_0}),\qquad\operatorname{supp}(q_{G_0})=BR_2(p_{F_r}).

The first condition holds by Equation (3) and Equation (4). supp⁡(pFr)\operatorname{supp}(p_{F_r}) and BR1(qG0)BR_1(q_{G_0}) 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 S2(yˉ)S_2(\bar{y}) and R2(xˉ)R_2(\bar{x}) have the same set of maximizing indices,

arg max⁡i(S2(yˉ))i=arg max⁡i(R2(xˉ))i.\underset{i}{\operatorname{arg\,max}}(S_2(\bar{y}))_i=\underset{i}{\operatorname{arg\,max}}(R_2(\bar{x}))_i.

These sets are precisely supp⁡(qG0)\operatorname{supp}(q_{G_0}) and BR2(pFr)BR_2(p_{F_r}), respectively, since they are the smallest sets in the corresponding chains, each ℓn(I)\ell_n(I) is uniform on II, and all weights are strictly positive. Hence

supp⁡(qG0)=BR2(pFr).\operatorname{supp}(q_{G_0})=BR_2(p_{F_r}).

Thus (pFr,qG0)(p_{F_r},q_{G_0}) 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 S1S_1, S2S_2, R1R_1, R2R_2 from Equation (2) and replace Nash modification by the EY modification in Lemma 1. Denote the EY modification by Πk\Pi_k. For (x,y)∈Δm×Δn(x,y)\in\Delta_m\times\Delta_n, set

h1(x,y)=x+R1(y)−S1(x),h2(x,y)=y+R2(x)−S2(y).(9)h_1(x,y)=x+R_1(y)-S_1(x),\qquad h_2(x,y)=y+R_2(x)-S_2(y). \tag*{(9)}

Define T′(x,y)=(x′,y′)T'(x,y)=(x',y') by

xi′=max⁡{(h1(x,y))i−tm(h1(x,y)),0},i∈M,x'_i=\max\{(h_1(x,y))_i-t_m(h_1(x,y)),0\},\qquad i\in M,
yj′=max⁡{(h2(x,y))j−tn(h2(x,y)),0},j∈N.y'_j=\max\{(h_2(x,y))_j-t_n(h_2(x,y)),0\},\qquad j\in N.

By Lemma 1, T′(x,y)=(Πm∘h1(x,y),Πn∘h2(x,y))T'(x,y)=(\Pi_m\circ h_1(x,y),\Pi_n\circ h_2(x,y)) is a continuous self-map of Δm×Δn\Delta_m\times\Delta_n.

Lemma 2. A fixed point (x,y)(x,y) of T′T' implies S1(x)=R1(y)S_1(x)=R_1(y) and S2(y)=R2(x)S_2(y)=R_2(x).

Proof. First observe that

supp⁡(S1(x))⊆supp⁡(x),supp⁡(S2(y))⊆supp⁡(y).\operatorname{supp}(S_1(x)) \subseteq\operatorname{supp}(x), \qquad\operatorname{supp}(S_2(y)) \subseteq\operatorname{supp}(y).

Indeed, if xi=0x_i=0, every vertex with a positive coefficient in a barycentric representation of xx has zero iith coordinate. By Equation (2), its image under S1S_1 also has zero iith coordinate. Affine interpolation therefore gives (S1(x))i=0(S_1(x))_i=0. The argument for S2S_2 is identical.

Suppose that (x,y)(x,y) is a fixed point of T′T'. Since R1(y),S1(x)∈ΔmR_1(y),S_1(x)\in\Delta_m, the coordinates of h1(x,y)h_1(x,y) sum to one. The candidate a=ma=m in the definition of tmt_m is therefore zero, so tm(h1(x,y))≥0t_m(h_1(x,y))\geq0.

For every i∈supp⁡(x)i\in\operatorname{supp}(x), the fixed-point equation gives

xi=(h1(x,y))i−tm(h1(x,y)).x_i=(h_1(x,y))_i-t_m(h_1(x,y)).

and hence

(R1(y))i−(S1(x))i=tm(h1(x,y)).(R_1(y))_i-(S_1(x))_i=t_m(h_1(x,y)).

For i∉supp⁡(x)i\notin\operatorname{supp}(x), the support property above gives (S1(x))i=0(S_1(x))_i=0. Consequently,

0=∑i∈[m]((R1(y))i−(S1(x))i)=∣supp⁡(x)∣⋅tm(h1(x,y))+∑i∉supp⁡(x)(R1(y))i.0=\sum_{i\in[m]}\left((R_1(y))_i-(S_1(x))_i\right)=|\operatorname{supp}(x)|\cdot t_m(h_1(x,y))+\sum_{i\notin\operatorname{supp}(x)}(R_1(y))_i.

Every term on the right is nonnegative. Since supp⁡(x)≠∅\operatorname{supp}(x)\neq\varnothing, it follows that tm(h1(x,y))=0t_m(h_1(x,y))=0 and (R1(y))i=0(R_1(y))_i=0 for all i∉Ii\notin I. Thus S1(x)=R1(y)S_1(x)=R_1(y). Applying the same argument to the second component gives S2(y)=R2(x)S_2(y)=R_2(x).

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 Rn\mathbb{R}^n defined by 2n2n 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 F∈CmF\in\mathcal{C}_m, let

IF={i∈M:xi>0 for some x∈F},JF={j∈N:F⊆Pj}.I_F=\{i\in M:x_i>0\text{ for some }x\in F\}, \qquad J_F=\{j\in N:F\subseteq P_j\}.

Given these index sets, a rational point pF∈relint⁡Fp_F\in\operatorname{relint}F can be computed in polynomial time. The same holds for G∈CnG\in\mathcal{C}_n.

Proof. Select j0j_0 as the smallest index in the set JFJ_F and solve

maximizeεsubject to∑i∈Mxi=1,xi=0∀i∈M∖IF,xi≥ε∀i∈IF,(BTx)j=(BTx)j0∀j∈JF,(BTx)j0−(BTx)j≥ε∀j∈N∖JF.\begin{aligned} \text{maximize}\quad&\varepsilon\\ \text{subject to}\quad&\sum_{i\in M}x_i=1,\\ &x_i=0 &&\forall i\in M\setminus I_F,\\ &x_i\geq\varepsilon&&\forall i\in I_F,\\ &(B^{\mathsf T}x)_j=(B^{\mathsf T}x)_{j_0} &&\forall j\in J_F,\\ &(B^{\mathsf T}x)_{j_0}-(B^{\mathsf T}x)_j\geq\varepsilon&&\forall j\in N\setminus J_F. \end{aligned}

Since FF is a face of Pj0P_{j_0}, the zero-coordinate and payoff-tie equalities recorded by IFI_F and JFJ_F cut out FF within Pj0P_{j_0}. The remaining inequalities are strict on relint⁡F\operatorname{relint}F, so the optimal value satisfies ε∗>0\varepsilon^*>0. Consequently, the xx-component of every optimal solution lies in relint⁡F\operatorname{relint}F. 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 G∈CnG\in\mathcal{C}_n is analogous, using AyA y in place of BTxB^{\mathsf T}x.

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 II, let ff and gg be composable continuous maps, with all dimensions polynomially bounded in ∣I∣|I|. If both maps satisfy the second condition of Definition 6, then their composition satisfies the second condition as well.

Proof. On a cell of ff, write f(x)=Ax+bf(x)=Ax+b. Substituting y=Ax+by=Ax+b into a dividing hyperplane aTy=ta^{\mathsf T}y=t for gg gives

(aTA)x=t−aTb.(a^{\mathsf T}A)x=t-a^{\mathsf T}b.

If aTA=0a^{\mathsf T}A=0, this equation introduces no new dividing hyperplane. Take all original dividing hyperplanes for ff, together with all nontrivial hyperplanes obtained by the above substitutions over all cells of ff. This finite collection divides the domain of ff into polyhedral regions on each of which a fixed affine formula for ff applies and its image lies in a region with a fixed affine formula for gg. If these formulas are Ax+bAx+b and By+cBy+c, respectively, then

(g∘f)(x)=BAx+Bb+c.(g\circ f)(x)=BAx+Bb+c.

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 ∣I∣|I|, so are the encoding lengths of all new coefficients. Finally, g∘fg\circ f is continuous because ff and gg 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)

T′(x,y)=(Πm∘h1(x,y),Πn∘h2(x,y)).T'(x,y)=(\Pi_m\circ h_1(x,y),\Pi_n\circ h_2(x,y)).

Let II denote the input game. Choose the points pFp_F and qGq_G for every F∈CmF\in\mathcal{C}_m and G∈CnG\in\mathcal{C}_n using Lemma 3. It admits that their rational coordinates have a polynomial encoding length of ∣I∣|I|. Select any (m−1)(m-1)-simplex σ=conv⁡{p0,…,pm−1}\sigma=\operatorname{conv}\{p_0,\ldots,p_{m-1}\} of Km\mathcal{K}_m, and set the matrix Pσ=[p0 ⋯ pm−1]P_\sigma=[p_0\ \cdots\ p_{m-1}]. This matrix is invertible, for these points are affinely independent and 1Tpi=1\mathbf{1}^{\mathsf T}p_i=1 for each valid ii. Let the matrices UσU_\sigma and VσV_\sigma contain the corresponding vertex images under S1S_1 and R2R_2, respectively. Formally,

Uσ=[ℓm(supp⁡(p0)) ⋯ ℓm(supp⁡(pm−1))],Vσ=[ℓn(BR2(p0)) ⋯ ℓn(BR2(pm−1))].U_\sigma=[\ell_m(\operatorname{supp}(p_0))\ \cdots\ \ell_m(\operatorname{supp}(p_{m-1}))],\qquad V_\sigma=[\ell_n(BR_2(p_0))\ \cdots\ \ell_n(BR_2(p_{m-1}))].

Then, the local formulas are

S1(x)=UσPσ−1x,R2(x)=VσPσ−1x.(10)S_1(x)=U_\sigma P_\sigma^{-1}x,\qquad R_2(x)=V_\sigma P_\sigma^{-1}x. \tag*{(10)}

The entries of UσU_\sigma and VσV_\sigma are either zero or reciprocals of positive integers at most max⁡{m,n}\max\{m,n\}. Since the entries of PσP_\sigma have polynomial encoding length, standard bounds for rational matrix inversion imply the same for Pσ−1P_\sigma^{-1}. The same argument applies to S2S_2 and R1R_1 on a (n−1)(n-1)-simplex η∈Kn\eta\in\mathcal{K}_n. Therefore, the coefficients of local formulas h1(x,y)h_1(x,y) and h2(x,y)h_2(x,y) have polynomial size.

Each (m−1)(m-1)-simplex σ\sigma and (n−1)(n-1)-simplex η\eta can be described by

σ={x∈Δm:Pσ−1x>0},η={y∈Δn:Qη−1y>0}.\sigma=\{x\in\Delta_m:P_\sigma^{-1}x>0\},\qquad\eta=\{y\in\Delta_n:Q_\eta^{-1}y>0\}.

The union of dividing hyperplanes in above two sets represents the dividing hyperplanes of the cell σ×η\sigma\times\eta in the space Δm×Δn\Delta_m\times\Delta_n. These coefficients of dividing hyperplanes have polynomial size as well. Thus, both maps h1h_1 and h2h_2 meet the second condition in Definition 6.

For Πm\Pi_m, we index the affine pieces by the coordinates retained after thresholding. For an input zz, let T={i∈[m]:zi>tm(z)}T = \{i \in[m] : z_i > t_m(z)\}. This set is nonempty, and the threshold equation gives

1=∑i∈T(zi−tm(z)),tm(z)=∑i∈Tzi−1∣T∣=:tT(z).1 = \sum_{i\in T}(z_i-t_m(z)), \qquad t_m(z) = \frac{\sum_{i\in T} z_i - 1}{|T|} =: t_T(z).

Thus fixing TT fixes an affine expression for the threshold.

For each nonempty T⊆[m]T \subseteq[m], consider the region

RT={z∈Rm:zi≥tT(z),i∈T,zi≤tT(z),i∉T}.R_T = \left\{z \in\mathbb{R}^m : \begin{array}{ll} z_i \ge t_T(z), & i \in T, \\ z_i \le t_T(z), & i \notin T \end{array}\right\}.

On this region, the vector

(Πm(z))i={zi−tT(z),i∈T,0,i∉T(\Pi_m(z))_i = \begin{cases} z_i-t_T(z), & i \in T, \\ 0, & i \notin T \end{cases}

is nonnegative and sums to one, so it is indeed the output of Πm\Pi_m by uniqueness of the threshold. Consequently, Πm\Pi_m is affine on RTR_T, including its boundary, and these regions cover Rm\mathbb{R}^m.

The required dividing hyperplanes are obtained from the nontrivial equations zi=tT(z)z_i = t_T(z) over all such TT. Their coefficients and those of the affine formulas have encoding length O(log⁡(m+1))O(\log(m+1)), hence polynomial in ∣I∣|I|. Thus Πm\Pi_m satisfies the second condition of Definition 6. The argument for Πn\Pi_n is identical.

Using Lemma 4, the composition maps Πm∘h1\Pi_m\circ h_1 and Πn∘h2\Pi_n\circ h_2 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 Km\mathcal{K}_m and Kn\mathcal{K}_n containing xx and yy 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 II, there exists a polynomial-time algorithm with access to a linear-comparison oracle for z∈Rm+nz \in\mathbb{R}^{m+n} that outputs No if z∉Δm×Δnz \notin\Delta_m \times\Delta_n. Otherwise, it returns the local formula T′(z)T'(z).

Proof. Write z=(x,y)z=(x,y) and consider the two parts separately by setting the coefficients corresponding to the other one to zero in each query. Test the constraints of Δm×Δn\Delta_m \times\Delta_n. If any test fails, reject. Recall the best-response regions are

Qi={y∈Δn:i∈BR1(y)}={y∈Δn:(Ay)i≥(Ay)h for all h∈M},Q_i = \{y \in\Delta_n : i \in BR_1(y)\} = \{y \in\Delta_n : (Ay)_i \ge(Ay)_h \text{ for all } h \in M\},
Pj={x∈Δm:j∈BR2(x)}={x∈Δm:(BTx)j≥(BTx)ℓ for all ℓ∈N}.P_j = \{x \in\Delta_m : j \in BR_2(x)\} = \{x \in\Delta_m : (B^\mathsf{T}x)_j \ge(B^\mathsf{T}x)_\ell\text{ for all } \ell\in N\}.

Use the oracle to locate a concrete pair of polytopes (P,Q)(P,Q) s.t. x∈Px \in P and y∈Qy \in Q. Since each PjP_j has an explicit rational inequality description of polynomial encoding length, a strong optimization oracle for PjP_j can be implemented in polynomial time by rational linear programming. Hence, for every nonempty PjP_j, 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 dim⁡P=m−1\dim P=m-1 and dim⁡Q=n−1\dim Q=n-1 since the full-dimensional regions PjP_j must cover Δm\Delta_m. Otherwise, the union of these closed sets would leave a full-dimensional open set in Δm\Delta_m covered only by finitely many lower-dimensional regions, which is impossible. The same holds for the regions QiQ_i in Δn\Delta_n.

For the selected region PP, first compute its label sets by linear programming:

IP={a∈M:max⁡v∈Pva>0},I_P = \left\{a \in M : \max_{v \in P} v_a > 0\right\},
JP={b∈N:max⁡v∈P((BTv)j−(BTv)b)=0}.J_P = \left\{b \in N : \max_{v \in P}\bigl((B^\mathsf{T}v)_j-(B^\mathsf{T}v)_b\bigr)=0\right\}.

These computations use only the explicit inequality description of PP. Given these labels, apply Lemma 3 to obtain the prescribed point p∈relint⁡Pp \in\operatorname{relint} P. The labels and interior point for QQ are computed analogously.

Then we need to compute the corresponding (m−1)(m-1)-simplex in PP and the corresponding (n−1)(n-1)-simplex in QQ, respectively. Equivalently, compute two sets of points {p0,…,pm−1}\{p_0,\ldots,p_{m-1}\} and {q0,…,qn−1}\{q_0,\ldots,q_{n-1}\} such that x∈conv⁡{p0,…,pm−1}x \in\operatorname{conv}\{p_0,\ldots,p_{m-1}\} and y∈conv⁡{q0,…,qn−1}y \in\operatorname{conv}\{q_0,\ldots,q_{n-1}\}. We next show how to compute pm−1,…,p0p_{m-1},\ldots,p_0 recursively. Set Fm−1=PF_{m-1}=P, pm−1=pp_{m-1}=p, and xm−1=xx_{m-1}=x. The initial label sets are Im−1=IPI_{m-1}=I_P and Jm−1=JPJ_{m-1}=J_P.

At stage ii, we maintain a polytope FiF_i, its label sets Ii=IFiI_i=I_{F_i} and Ji=JFiJ_i=J_{F_i}, its prescribed relative-interior point pip_i, and a matrix CiC_i defining target point xi∈Fix_i \in F_i. In each stage, first test whether xi=pix_i=p_i. 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 xx for other stages.

If xi≠pix_i \ne p_i, consider the ray

ri(t)=pi+t(xi−pi),t≥0.r_i(t)=p_i+t(x_i-p_i), \qquad t\geq0.

Let xi−1x_{i-1} be its first intersection with a facet of FiF_i, and choose that facet as Fi−1F_{i-1}, breaking ties by a fixed ordering.

To find this intersection, we first determine the facets of FiF_i from its label sets IiI_i and JiJ_i. Fix j0=min⁡Jij_0=\min J_i, and consider the inequalities

za≥0∀a∈Ii,(BTz)j0−(BTz)b≥0∀b∈N∖Ji.z_a\geq0 \quad\forall a\in I_i,\qquad(B^{\mathsf T}z)_{j_0}-(B^{\mathsf T}z)_b\geq0 \quad\forall b\in N\setminus J_i.

These are the inequalities in the label-based description of FiF_i that are not identically tight on FiF_i. For each such inequality h(z)≥0h(z)\geq0, form

Gh=Fi∩{z:h(z)=0},G_h=F_i\cap\{z:h(z)=0\},

and retain hh if GhG_h is nonempty and dim⁡Gh=dim⁡Fi−1\dim G_h=\dim F_i-1. These tests can be performed in polynomial time by rational linear programming. Let Hi\mathcal{H}_i be the resulting set of functions. Every facet of FiF_i is represented by at least one function in Hi\mathcal{H}_i. Each h∈Hih\in\mathcal{H}_i is homogeneous linear, is nonnegative on FiF_i, and satisfies h(pi)>0h(p_i)>0, since pi∈relint⁡Fip_i\in\operatorname{relint} F_i.

For h∈Hih\in\mathcal{H}_i, if the corresponding facet intersects with the ray, substituting the ray into h(ri(t))=0h(r_i(t))=0 gives

h(ri(t))=h(pi)+t(h(xi)−h(pi))=0.h(r_i(t))=h(p_i)+t(h(x_i)-h(p_i))=0.

We have

th=11−h(xi)/h(pi).t_h=\frac{1}{1-h(x_i)/h(p_i)}.

Choosing another g∈Hig\in\mathcal{H}_i, if it also intersects with the ray, we can compare

th≤tg⟺h(xi)h(pi)≤g(xi)g(pi)<1.t_h\leq t_g \quad\Longleftrightarrow\quad\frac{h(x_i)}{h(p_i)}\leq\frac{g(x_i)}{g(p_i)}<1.

Otherwise, if the ray also misses the supporting hyperplane {z:g(z)=0}\{z:g(z)=0\}, then g(xi)≥g(pi)g(x_i)\geq g(p_i). It is also possible that the ray meets this hyperplane outside FiF_i, possibly outside Δm\Delta_m, while g(xi)/g(pi)<1g(x_i)/g(p_i)<1. In this case, before reaching that intersection at tgt_g, the ray must meet some facet with defining function f∈Hif\in\mathcal{H}_i at a parameter tf<tgt_f<t_g. By the same comparison,

f(xi)f(pi)<g(xi)g(pi)<1.\frac{f(x_i)}{f(p_i)}<\frac{g(x_i)}{g(p_i)}<1.

Hence such an intersection outside FiF_i cannot yield the minimum ratio. Thus the first facet encountered is obtained by choosing h∗∈Hih_\ast\in\mathcal{H}_i that minimizes h(xi)/h(pi)h(x_i)/h(p_i), breaking ties by the fixed ordering.

To implement these comparisons using only linear queries in the original input xx, store the target points as

ui=Cix,wi=1⊤uiandxi=uiwi.u_i=C_i x,\quad w_i=\mathbf{1}^{\top}u_i\quad\text{and}\quad x_i=\frac{u_i}{w_i}.

where CiC_i is a rational matrix with polynomial size and 1⊤ui>0\mathbf{1}^{\top}u_i>0. The vectors uiu_i and points xix_i are used only as symbolic quantities. The algorithm explicitly stores the rational matrix CiC_i, rather than the numerical values of uiu_i, wiw_i, or xix_i. Initially, Cm−1=IdmC_{m-1}=I_{d_m}. The facet comparison becomes

h(xi)h(pi)≤g(xi)g(pi)⟺g(pi)h(uiwi)≤h(pi)g(uiwi)⟺g(pi)h(Cix)≤h(pi)g(Cix),\frac{h(x_i)}{h(p_i)}\leq\frac{g(x_i)}{g(p_i)} \quad\Longleftrightarrow\quad g(p_i)h\left(\frac{u_i}{w_i}\right)\leq h(p_i)g\left(\frac{u_i}{w_i}\right) \quad\Longleftrightarrow\quad g(p_i)h(C_i x)\leq h(p_i)g(C_i x),

which is a linear comparison in the original xx. After selecting h∗h_*, the intersection is exactly

xi−1=pi+11−h∗(xi)/h∗(pi)(xi−pi)=pi+wiwi−h∗(ui)/h∗(pi)(uiwi−pi)=ui−pi(h∗(ui)/h∗(pi))wi−(h∗(ui)/h∗(pi)).\begin{aligned} x_{i-1}&=p_i+\frac{1}{1-h_*(x_i)/h_*(p_i)}(x_i-p_i)\\ &=p_i+\frac{w_i}{w_i-h_*(u_i)/h_*(p_i)}\left(\frac{u_i}{w_i}-p_i\right)\\ &=\frac{u_i-p_i(h_*(u_i)/h_*(p_i))}{w_i-(h_*(u_i)/h_*(p_i))}. \end{aligned}

We therefore preserve the representation by setting

ui−1=ui−pi(h∗(ui)/h∗(pi)),wi−1=wi−(h∗(ui)/h∗(pi)),Fi−1=Fi∩{z:h∗(z)=0}.u_{i-1}=u_i-p_i(h_*(u_i)/h_*(p_i)),\quad w_{i-1}=w_i-(h_*(u_i)/h_*(p_i)),\quad F_{i-1}=F_i\cap\{z:h_*(z)=0\}.

Moreover, h∗(ui)/h∗(pi)=wih∗(xi)/h∗(pi)<wih_*(u_i)/h_*(p_i)=w_i h_*(x_i)/h_*(p_i)<w_i based on above analysis. Writing h∗(z)=a⊤zh_*(z)=a^{\top}z, update the matrix by

ui−1=ui−pi(h∗(ui)/h∗(pi))=Cix−pih∗(Cix)h∗(pi)=Cix−pia⊤Cixa⊤pi=(Idm−pia⊤a⊤pi)Cix.\begin{aligned} u_{i-1}&=u_i-p_i(h_*(u_i)/h_*(p_i))\\ &=C_i x-p_i\frac{h_*(C_i x)}{h_*(p_i)}\\ &=C_i x-p_i\frac{a^{\top}C_i x}{a^{\top}p_i} =\left(I_{d_m}-\frac{p_i a^{\top}}{a^{\top}p_i}\right)C_i x. \end{aligned}

Thus, Ci−1=(Idm−pia⊤a⊤pi)CiC_{i-1}=\left(I_{d_m}-\frac{p_i a^{\top}}{a^{\top}p_i}\right)C_i, which is a rational matrix. Not hard to verify that Idm−pia⊤a⊤piI_{d_m}-\frac{p_i a^{\top}}{a^{\top}p_i} has polynomial size for each ii and thus CiC_i has polynomial size for each ii. Additionally, 1⊤pi=1\mathbf{1}^{\top}p_i=1 since pip_i is a point in Δm\Delta_m. We obtain 1⊤ui−1=1⊤ui−1⊤pi(h∗(ui)/h∗(pi))=wi−h∗(ui)/h∗(pi)=wi−1>0\mathbf{1}^{\top}u_{i-1}=\mathbf{1}^{\top}u_i-\mathbf{1}^{\top}p_i(h_*(u_i)/h_*(p_i))=w_i-h_*(u_i)/h_*(p_i)=w_{i-1}>0.

To update the labels of the selected facet, delete coordinates identical to zero in Fi−1F_{i-1} and add new best-response actions in Fi−1F_{i-1} by linear programming,

Ii−1={a∈Ii:max⁡v∈Fi−1va>0},I_{i-1}=\left\{a\in I_i:\max_{v\in F_{i-1}}v_a>0\right\},
Ji−1=Ji∪{b∈N∖Ji:max⁡v∈Fi−1((B⊤v)j0−(B⊤v)b)=0}.J_{i-1}=J_i\cup\left\{b\in N\setminus J_i:\max_{v\in F_{i-1}}\left((B^{\top}v)_{j_0}-(B^{\top}v)_b\right)=0\right\}.

Using the updated labels, apply Lemma 3 to compute the prescribed point pi−1∈relint⁡Fi−1p_{i-1}\in\operatorname{relint}F_{i-1}.

If xi=pix_i=p_i, 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 pi=xip_i=x_i using a linear-comparison oracle for the original input xx is equivalent to determining whether Cix−wipi=0C_i x-w_i p_i=0, which just uses linear comparisons.

The resulting complete face chain F0⊂⋯⊂Fm−1F_0 \subset\cdots\subset F_{m-1} determines an (m−1)(m-1)-simplex

σ=conv⁡{p0,…,pm−1}\sigma= \operatorname{conv}\{p_0,\ldots,p_{m-1}\}

containing xx. The correctness can be proved by induction since for each valid ii xi=(h∗(xi)/h∗(pi))pi+(1−(h∗(xi)/h∗(pi)))xi−1x_i = (h_*(x_i)/h_*(p_i))p_i + (1-(h_*(x_i)/h_*(p_i)))x_{i-1}. The same argument applies to yy.

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

H(x,y)=(h1(x,y),h2(x,y))=C(xy)+c.H(x,y) = (h_1(x,y),h_2(x,y)) = C\begin{pmatrix}x\\y\end{pmatrix}+c.

Each comparison a⊤H(x,y)≤ba^\top H(x,y) \le b becomes

(a⊤C)(xy)≤b−a⊤c,(a^\top C)\begin{pmatrix}x\\y\end{pmatrix} \le b-a^\top c,

which is also a linear comparison in the original input. The resulting local formula for T′T' 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 (xˉ,yˉ)(\bar{x},\bar{y}) of T′T', which is rational and can be computed in PPAD. Execute the algorithm in Lemma 5 on input (xˉ,yˉ)(\bar{x},\bar{y}). 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 xˉ∈σ\bar{x} \in\sigma and yˉ∈η\bar{y} \in\eta, together with Pσ−1P_\sigma^{-1} and Qη−1Q_\eta^{-1} defined in (10). Compute the barycentric coordinates as follows

λ=Pσ−1xˉ,μ=Qη−1yˉ.\lambda=P_\sigma^{-1}\bar{x},\qquad\mu=Q_\eta^{-1}\bar{y}.

Select

r=max⁡{i:λi>0},s=min⁡{j:μj>0}.r=\max\{i:\lambda_i>0\},\qquad s=\min\{j:\mu_j>0\}.

As the proof of Theorem 5 shows, (pr,qs)(p_r,q_s) is a quasi-strict Nash equilibrium.

Complexity of deciding whether quasi-strict Nash equilibria exist

Theorem 2. For every fixed n≥3n \ge3, deciding whether an nn-player game in strategic form with rational payoffs admits a quasi-strict Nash equilibrium is ∃R\exists\mathbb{R}-complete, even for zero-sum games.

Proof. Containment in ∃R\exists\mathbb{R} for general-sum games is straightforward. Namely, let Pi,aP_{i,a} denote the expected payoff if player ii chooses action aa from action set AiA_i. Introduce a real variable viv_i to denote the best-response payoff of player ii and a vector of real variables νi\nu_i to denote the strategy. We can construct an existential formula

∃((νi(a))i,a,(vi)i):⋀i(∑a∈Aiνi(a)=1 ∧ ⋀a∈Ai[(νi(a)>0 ∧ Pi,a(ν−i)=vi) ∨ (νi(a)=0 ∧ Pi,a(ν−i)<vi)]).\exists\bigl((\nu_i(a))_{i,a},(v_i)_i\bigr): \bigwedge_i\left(\sum_{a\in A_i}\nu_i(a)=1\ \land\ \bigwedge_{a\in A_i}\left[\left(\nu_i(a)>0\ \land\ P_{i,a}(\nu_{-i})=v_i\right)\ \lor\ \left(\nu_i(a)=0\ \land\ P_{i,a}(\nu_{-i})<v_i\right)\right]\right).

It uses only polynomial equalities and inequalities.

For hardness, take an instance GG of Theorem 4. Construct a three-player game G^\widehat{G} with action sets

A^1=A∪{⊥1},A^2=X∪{⊥2},A^3=Y∪{⊥3}.\widehat{A}_1=A\cup\{\bot_1\},\qquad\widehat{A}_2=X\cup\{\bot_2\},\qquad\widehat{A}_3=Y\cup\{\bot_3\}.

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 a∈Aa\in A, with r=r(a,b,c)r=r(a,b,c) in its X×YX\times Y block and all other displayed payoff vectors are constant on their blocks. Every payoff vector sums to zero.

Y⊥3X(r,−r,0)(0,0,0)⊥2(0,0,0)(−1,0,1)a∈A\begin{array}{c|cc} & Y & \bot_3\\ \hline X & (r,-r,0) & (0,0,0)\\ \bot_2 & (0,0,0) & (-1,0,1) \end{array} \qquad a\in A
Y⊥3X(0,0,0)(0,0,0)⊥2(1,−1,0)(0,−1,1)a∈{⊥1}.\begin{array}{c|cc} & Y & \bot_3\\ \hline X & (0,0,0) & (0,0,0)\\ \bot_2 & (1,-1,0) & (0,-1,1) \end{array} \qquad a\in\{\bot_1\}.

The construction adds one action per player and uses only the original payoff entries, their negatives, and 0,±10,\pm1, so its size and encoding length are polynomial in the input size.

Suppose first that V(G)=0V(G)=0. Choose the full-support strategies x,yx,y supplied by the promise. Let ν1\nu_1 be uniform on A^1\widehat{A}_1, and set

ν2=(x1,…,x∣X∣,0),ν3=(12y1,…,12y∣Y∣,12).\nu_2=(x_1,\ldots,x_{|X|},0),\qquad \nu_3=\left(\frac{1}{2}y_1,\ldots,\frac{1}{2}y_{|Y|},\frac{1}{2}\right).

where the last coordinate corresponds to the additional action. It’s easy to check that all three strategies are valid. Moreover,

BR1(ν−1)=A^1,BR2(ν−2)=X,BR3(ν−3)=A^3.BR_1(\nu_{-1})=\widehat{A}_1,\qquad BR_2(\nu_{-2})=X,\qquad BR_3(\nu_{-3})=\widehat{A}_3.

The first equation follows from r(a,x,y)=0r(a,x,y)=0 for each a∈Aa\in A. For the second equation, ν1\nu_1 assigns equal probabilities to each pair ak+,ak−a_k^+,a_k^-, so every original action of player 2 has expected payoff zero. The action ⊥2\bot_2 yields payoff −ν1(⊥1)<0-\nu_1(\bot_1)<0. The last equation holds because ν2(⊥2)=0\nu_2(\bot_2)=0, so every action of player 3 has payoff zero. Thus (ν1,ν2,ν3)(\nu_1,\nu_2,\nu_3) is a quasi-strict Nash equilibrium of G^\widehat{G}, for

BR1(ν−1)=supp⁡(ν1),BR2(ν−2)=supp⁡(ν2),BR3(ν−3)=supp⁡(ν3).BR_1(\nu_{-1})=\operatorname{supp}(\nu_1),\qquad BR_2(\nu_{-2})=\operatorname{supp}(\nu_2),\qquad BR_3(\nu_{-3})=\operatorname{supp}(\nu_3).

Conversely, let (ν1,ν2,ν3)(\nu_1,\nu_2,\nu_3) be a quasi-strict Nash equilibrium of G^\widehat{G}. We first show that ν2(⊥2)=0\nu_2(\bot_2)=0. If ν2(⊥2)>0\nu_2(\bot_2)>0, player 3’s action ⊥3\bot_3 has positive payoff, while every original action has payoff zero. Hence player 3 plays ⊥3\bot_3 with probability one. Player 1’s action ⊥1\bot_1 then yields zero, while every original action yields −ν2(⊥2)<0-\nu_2(\bot_2)<0, so player 1 plays ⊥1\bot_1 with probability one. But player 2’s action ⊥2\bot_2 now yields −1-1, while every original action yields zero, contradicting ν2(⊥2)>0\nu_2(\bot_2)>0.

Since ν2(⊥2)=0\nu_2(\bot_2)=0, every action of player 3 has payoff zero. QSNE requires full support on A^3\widehat{A}_3. Suppose, for a contradiction, that ν1(⊥1)=0\nu_1(\bot_1)=0. Player 1’s action ⊥1\bot_1 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 ν1(⊥1)=0\nu_1(\bot_1)=0, player 2 can obtain zero by switching to ⊥2\bot_2, which is a valuable deviation. This contradicts the Nash equilibrium condition, so ν1(⊥1)>0\nu_1(\bot_1)>0.

Define two normalized vectors

x=(ν2(c))c∈X,y=(ν3(c)∑d∈Yν3(d))c∈Y.x=\left(\nu_2(c)\right)_{c\in X},\qquad y=\left(\frac{\nu_3(c)}{\sum_{d\in Y}\nu_3(d)}\right)_{c\in Y}.

Since ⊥1\bot_1 is played with positive probability and yields payoff zero, for each pair a+,a−∈Aa^+,a^-\in A, we have

r(a+,x,y)≤0,r(a−,x,y)≤0.(11)r(a^+,x,y)\leq0,\qquad r(a^-,x,y)\leq0. \tag*{(11)}

The condition r(a+,x,y)=−r(a−,x,y)r(a^{+},x,y)=-r(a^{-},x,y) in Theorem 4 implies r(a,x,y)=0r(a,x,y)=0 for every a∈Aa \in A and then V(G)=0V(G)=0. We have therefore proved, on the promised instances,

V(G)=0⟺G^ admits a quasi-strict Nash equilibrium.V(G)=0 \quad\Longleftrightarrow\quad\widehat{G}\text{ admits a quasi-strict Nash equilibrium.}

This establishes ∃R\exists\mathbb{R}-hardness for three-player zero-sum games.

Given any fixed n>3n>3, add n−3n-3 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. [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. [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
  3. [4]L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71:97–115, 1911. 1
  4. [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
  5. [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
  6. [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
  7. [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
  8. [11]M. Grötschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics. Springer Berlin Heidelberg, 2012. 16
  9. [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
  10. [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
  11. [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
  12. [16]Shizuo Kakutani. A generalization of Brouwer’s fixed point theorem. Duke Mathematical Journal, 8(3):457–459, 1941. 1DOI
  13. [17]N​arendra 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
  14. [18]Leonid G. Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathematics and Mathematical Physics, 20(1):53–72, 1980. 14DOI
  15. [19]Paul Milgrom and Joshua Mollner. Equilibrium selection in auctions and high stakes games. Econometrica, 86(1):219–261, 2018. 4DOI
  16. [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
  17. [21]Andrew McLennan and Rabee Tourky. Simple complexity from imitation games. Games and Economic Behavior, 68(2):683–688, 2010. 3DOI
  18. [22]J.R. Munkres. Topology. Featured Titles for Topology. Prentice Hall, Incorporated, 2000. 4, 8
  19. [23]J.R. Munkres. Elements Of Algebraic Topology. Textbooks in Mathematics. CRC Press, 2018. 4, 5
  20. [24]R. B. Myerson. Refinements of the Nash equilibrium concept. International Journal of Game Theory, 15:133–154, 1978. 3DOI
  21. [25]John Nash. Non-cooperative games. Annals of Mathematics, 54(2):286–295, 1951. 1, 2, 9, 12
  22. [26]Henk Norde. Bimatrix games have quasi-strict equilibria. Mathematical Programming, 85(1):35, 1999. 1, 4, 10DOI
  23. [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
  24. [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
  25. [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
  26. [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
  27. [31]David Squires. Impossibility theorems for normal form games. Theory and Decision, 44(1):67–81, 1998. 1DOI
  28. [32]Eric van Damme. Stability and Perfection of Nash Equilibria. Springer-Verlag, Berlin, Heidelberg, 2nd edition, 1991. 1

Paper details

vlnc:W_nwzkhnh9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents