we-solve (beta)

Econ-4 · economics · computer science · Computational economics

Computational complexity of optimin in finite games

LLM status Open unverified

Statement

Addendum ID: OPT-COMP-1. Formulation: editorial family of precise computational problems motivated by Ismail (2025), not a conjecture attributed verbatim to that article.

Definitions and assumptions

Let $G=(N,(A_i)_{i\in N},(v_i)_{i\in N})$ be a finite normal-form game, with $N=\{1,\ldots,n\}$, $n\ge2$, $m_i=|A_i|\ge2$, $A=\prod_i A_i$, and rational payoffs $v_i:A\to[-1,1]\cap\mathbb Q$. Set $\Delta_i=\Delta(A_i)$ and $\Delta=\prod_i\Delta_i$. Write $u_i(p)$ for the multilinear expected-payoff extension of $v_i$ at $p\in\Delta$. The default encoding is the explicit table of the $n|A|$ payoff entries in binary, of total bit length $L$. All complexity assertions refer to $L$ (and to the bit length of any additional rational inputs), not merely to the number of pure actions.

For each player $j$ and mixed profile $p$, define the correspondence of permitted strictly profitable unilateral deviations from the baseline $p$, including non-deviation, by \[ B_j(p)=\{p_j\}\ \cup\ \left\{q_j\in\Delta_j: u_j(q_j,p_{-j})>u_j(p)\right\}, \qquad B_{-i}(p)=\prod_{j\in N\setminus\{i\}}B_j(p). \] The optimin performance of player $i$ and the mixed-strategy optimin correspondence are, respectively, \[ \pi_i^G(p)=\inf_{q_{-i}\in B_{-i}(p)}u_i(p_i,q_{-i}), \] \[ \begin{aligned} \mathcal O^{\mathrm{mix}}(G)=\bigl\{p\in\Delta:\;&\nexists q\in\Delta\text{ such that } \pi_i^G(q)\ge\pi_i^G(p)\ \forall i\in N,\\ &\hspace{21mm}\text{and } \pi_j^G(q)>\pi_j^G(p)\text{ for some }j\in N\bigr\}. \end{aligned} \] Each $q_j\in B_j(p)$ is assessed against the original profile $p_{-j}$, even when several opponents deviate in the product $B_{-i}(p)$. Thus the definition permits combinations of independently profitable unilateral deviations; it does not require the combination to be jointly profitable. In particular, a Nash equilibrium $p$ has $B_j(p)=\{p_j\}$ for all $j$. The strict inequality in $B_j(p)$ must not silently be replaced by a weak inequality.

The pure-restricted variant is defined separately: replace $\Delta_j$ by $A_j$ in every deviation set and in the set of candidate profiles, denote the resulting performance by $\pi_i^{G,\mathrm{pure}}(a)$, and let $\mathcal O^{\mathrm{pure}}(G)\subseteq A$ consist of the profiles Pareto undominated under $\pi^{G,\mathrm{pure}}$. Membership in $\mathcal O^{\mathrm{pure}}(G)$ does not imply membership in $\mathcal O^{\mathrm{mix}}(G)$.

For exact mixed-strategy search, specify a finite algebraic-number representation of each output probability, or an explicitly equivalent exact real-algebraic representation. For approximate search, output rational probabilities. The required error notion and its binary-encoded rational tolerance $\varepsilon>0$ are always stated explicitly.

Formal research question

Central problem. Determine the exact worst-case computational complexity of constructing one element of $\mathcal O^{\mathrm{mix}}(G)$ for a rational finite game $G$. Classify the following interrelated, but distinct, search, decision, verification, and approximation problems. Any proposed completeness claim must specify its many-one, Turing, or search-reduction notion and its output encoding.

  1. Two-player general-sum mixed optimin. For the input class $n=2$ with arbitrary rational bimatrix payoffs, determine the complexity of the total search task \[ \mathsf{MIXED\text{-}OPTIMIN}_2:\quad G\longmapsto p\in\mathcal O^{\mathrm{mix}}(G). \] Does an algorithm run in time polynomial in the bimatrix input length $L$ under a suitable exact output model? Otherwise, establish a sharp hardness or completeness classification, distinguishing arbitrary $m_1,m_2$ from bounded-action subfamilies. Investigate membership or hardness relative to appropriately defined total-search classes such as $\mathsf{PPAD}$ and exact real-algebraic search classes such as $\mathsf{FIXP}$; neither classification is assumed.

  2. Three-player and general $n$-player mixed optimin. For each fixed $n\ge3$, and separately when $n$ is part of the input, determine the search complexity of \[ \mathsf{MIXED\text{-}OPTIMIN}_n:\quad G\longmapsto p\in\mathcal O^{\mathrm{mix}}(G). \] Identify the least player count at which the complexity provably differs from the two-player problem, if such a separation exists. Distinguish general-sum games from $n$-player constant-sum games ($\sum_i v_i(a)=c$ for every $a\in A$), and distinguish a fixed number of actions per player from unrestricted action counts. In particular, determine whether the three-player problem admits a $\mathsf{FIXP}$-type characterization, a different real-algebraic search characterization, or a strictly simpler algorithmic description; no transfer from Nash-equilibrium complexity is presumed.

  3. Approximation by strategy distance versus performance efficiency. Let $d=\sum_i m_i$, and use the sup norm on the coordinates of $\Delta\subseteq\mathbb R^d$. Classify the total rational-output approximation problem \[ \mathsf{NEAR\text{-}OPTIMIN}_n:\quad (G,\varepsilon)\longmapsto\widehat p\in\Delta\cap\mathbb Q^d \quad\text{with}\quad \inf_{p^*\in\mathcal O^{\mathrm{mix}}(G)} \|\widehat p-p^*\|_\infty\le\varepsilon. \] Separately, investigate the performance-based requirement that there be no $q\in\Delta$ for which \[ \pi_i^G(q)\ge\pi_i^G(\widehat p)\quad\forall i, \qquad \max_i\left(\pi_i^G(q)-\pi_i^G(\widehat p)\right)>\varepsilon. \] Determine the conditions under which such a performance-based approximation admits a rational output and, when it does, its complexity. Compare polynomial dependence on $L$ and $\log(1/\varepsilon)$ with polynomial dependence on $L$ and $1/\varepsilon$; do not conflate closeness in strategies with closeness in performance.

  4. Performance thresholds and scalarized optimization. For $r\in([-1,1]\cap\mathbb Q)^n$, determine the decision complexity of \[ \mathsf{OPTIMIN\text{-}GUARANTEE}_n(G,r):\quad \exists p\in\Delta\ \forall i\in N:\ \pi_i^G(p)\ge r_i\,? \] For rational weights $\lambda_i>0$ satisfying $\sum_i\lambda_i=1$, define \[ V_\lambda(G)=\max_{p\in\Delta}\sum_{i=1}^n\lambda_i\pi_i^G(p). \] Classify deciding $V_\lambda(G)\ge t$ for a rational threshold $t$, computing $V_\lambda(G)$ exactly or within $\varepsilon$, and constructing a maximizing profile. Every exact maximizer for strictly positive weights is an optimin point, but varying $\lambda$ need not generate every Pareto-undominated performance vector. Determine sharp complexity bounds, including those based on quantified polynomial inequalities over the reals, for these precisely formulated tasks.

  5. Checking and certifying a proposed mixed optimin. Given $G$ and a rational profile $p\in\Delta$, classify the decision problem \[ \mathsf{IS\text{-}OPTIMIN}_n(G,p):\quad p\in\mathcal O^{\mathrm{mix}}(G)\,? \] Also classify the feasibility of polynomial-size, polynomial-time-verifiable certificates of optimin membership or nonmembership under declared exact and approximate encodings. Distinguish this global Pareto-nondominance test from evaluation of the individual numbers $\pi_i^G(p)$ and from checking ordinary Nash inequalities.

  6. Succinct input and the pure-strategy boundary. If the game is given as an explicit payoff table, computing some $a\in\mathcal O^{\mathrm{pure}}(G)$ is already polynomial-time solvable, even with variable $n$; this is a settled baseline, not an open complexity classification. Instead, let the game be encoded by a Boolean or arithmetic circuit $C$ returning the rational payoff $v_i(a)$ given a player index $i$ and a pure action profile $a$. Determine the complexity of finding $a\in\mathcal O^{\mathrm{pure}}(G_C)$ and of deciding \[ \exists a\in\mathcal O^{\mathrm{pure}}(G_C) \quad\forall i:\quad \pi_i^{G_C,\mathrm{pure}}(a)\ge r_i, \] particularly when every player has two actions and the number of players grows. Record the circuit and payoff bit lengths, distinguish succinct from tabular input, and examine bounded-degree graphical or other compact representations separately.

  7. Structural restrictions and parameterized complexity. For every stated game representation, characterize tractable and hard subfamilies among two-person zero-sum, $n$-person constant-sum ($n\ge3$), common-interest, potential, symmetric, polymatrix, anonymous, and bounded-interaction graphical games. Determine, where meaningful, whether exact or approximate mixed optimin admits fixed-parameter tractability with respect to $n$, $\max_i m_i$, graph width, payoff rank, or a specified structural parameter. The finite two-person zero-sum case, where mixed optimin coincides with Nash equilibrium and can be computed by linear programming, is a settled boundary case.

  8. Sensitivity to permitted deviations. Repeat the exact-search, approximation, threshold, and verification questions after replacing each $B_j(p)$, consistently throughout the performance function, by either \[ \widehat B_j^{\mathrm{weak}}(p) =\{q_j\in\Delta_j:u_j(q_j,p_{-j})\ge u_j(p)\}, \] \[ \widehat B_j^{\mathrm{best}}(p) =\{p_j\}\cup\argmax_{q_j\in\Delta_j}u_j(q_j,p_{-j}). \] Both induce modified performance functions and modified Pareto-undominated sets; they are not definitions of the benchmark strict-deviation optimin. Identify which complexity changes are caused by strict-profitability tests, boundary degeneracies, and simultaneous products of individually defined deviation sets.

Interpretation and scope

The questions concern finding one optimin point, not necessarily enumerating the entire Pareto frontier. Exact mixed-strategy search, a rational $\varepsilon$-approximation to an exact point, additive performance efficiency, weighted-value computation, and global membership testing are different computational tasks. Complexity for a succinctly encoded pure game cannot be inferred from polynomial time for the explicitly tabulated version. Two-player zero-sum games must not be used to infer tractability of arbitrary two-player general-sum games; likewise, the fact that every Nash equilibrium of an $n$-person constant-sum game is optimin does not by itself transfer any hardness theorem in the opposite direction. An algorithm for approximate mixed optimin without a worst-case running-time or approximation theorem does not resolve these classifications.

Source audit and status

Ismail (2025, Definitions 1--3, Theorem 1, Remark 1, Remark 5, and Proposition 2/Corollary 1) supplies the optimin definition, existence, the pure-restricted benchmark, and the two-person zero-sum identification. It expressly does not infer the complexity of mixed optimin from the hardness of computing Nash equilibria. The author's Optimin-Solver repository advertises algorithms for pure optimin and approximate mixed optimin in two-player games, but its existence does not establish any worst-case complexity classification. Chen--Deng--Teng (2009), Daskalakis--Goldberg--Papadimitriou (2009), and Etessami--Yannakakis (2010) classify distinct Nash computation tasks; their $\mathsf{PPAD}$ and $\mathsf{FIXP}$ results are comparative benchmarks, not theorems about optimin. Àlvarez--Gabarro--Serna (2011) motivates careful separation of explicit and succinct game representations; it does not classify optimin computation.

The eight subquestions above are newly specified research targets, not eight individually verified open conjectures from the cited papers. On the reviewed sources, a tight worst-case classification for the general mixed-strategy optimin search problem is not established. The explicit-table pure case and the two-person zero-sum case are excluded from the unresolved core. No proof, reduction, or algorithm is asserted in this entry.

References

  1. S1 Mehmet S. Ismail (2025). Super-Nash Performance. International Economic Review 66(4), 1487--1503. https://doi.org/10.1111/iere.12764. Locator: Section 2, Definitions 1--3 (pp. 1488--1489); Section 3, Theorem 1 and Remark 1 (pp. 1490--1491), Remark 5 and Proposition 2/Corollary 1 (pp. 1492--1493). Establishes: the benchmark solution concept and existence/zero-sum properties. Does not establish: polynomial-time, hardness, or completeness results for general mixed optimin computation.

  2. S2 Mehmet S. Ismail. Optimin-Solver (public software repository). https://github.com/drmehmetismail/Optimin-Solver. Locator: README; optimin_pure.py and optimin_mixed_approximate.py. Establishes: availability of implementation examples for pure and approximate mixed optimin in two-person games. Does not establish: a worst-case complexity classification.

  3. S3 Xi Chen, Xiaotie Deng and Shang-Hua Teng (2009). Settling the Complexity of Computing Two-Player Nash Equilibria. Journal of the ACM 56(3), Article 14. https://doi.org/10.1145/1516512.1516516. Locator: central $\mathsf{PPAD}$-completeness theorem. Establishes: complexity of two-player Nash equilibrium. Does not establish: the same complexity for two-player optimin.

  4. S4 Constantinos Daskalakis, Paul W. Goldberg and Christos H. Papadimitriou (2009). The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing 39(1), 195--259. https://doi.org/10.1137/070699652. Locator: abstract and principal $\mathsf{PPAD}$-completeness statements. Establishes: Nash-computation complexity. Does not establish: optimin-computation complexity.

  5. S5 Kousha Etessami and Mihalis Yannakakis (2010). On the Complexity of Nash Equilibria and Other Fixed Points. SIAM Journal on Computing 39(6), 2531--2597. https://doi.org/10.1137/080720826. Locator: abstract and the definition of $\mathsf{FIXP}$; exact versus near-equilibrium distinctions. Establishes: real-algebraic search benchmarks for Nash equilibria. Does not establish: $\mathsf{FIXP}$ membership or hardness for optimin.

  6. S6 Carme Àlvarez, Joaquim Gabarro and Maria Serna (2011). Equilibria Problems on Games: Complexity versus Succinctness. Journal of Computer and System Sciences 77(6), 1172--1197. https://doi.org/10.1016/j.jcss.2011.01.001. Locator: abstract; comparisons of explicit and succinct representations of games. Establishes: representation-sensitive equilibrium complexity in other solution concepts. Does not establish: the corresponding complexity of optimin.

Common conventions: Source mathematical conventions

Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.

Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.

Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.

Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.

Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-4-A1 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-4

Problem ID: C72-4 Model: GPT 6 Astra Pro Version: 1

Status: Unresolved for the complete catalogue problem; this manuscript records partial results and research attempts.

Computational complexity of optimin in finite games

Addendum ID: OPT-COMP-1. JEL: C72. Formulation: formal computational research questions, with an explicitly distinguished status audit. Status convention. 
\textsc{Published}
: established in the cited literature. 
\textsc{Derived}
: an internally checked deduction constructed for this addendum, not independently peer-reviewed. 
\textsc{Unresolved here}
: no classification follows from the reviewed sources and arguments; not a claim of exhaustive literature coverage.

Definitions and assumptions

Let \[ G=(N,(A_i)_{i\in N},(v_i)_{i\in N}),\quad N=\{1,\ldots,n\},\quad n\ge2,\quad A=\prod_i A_i, \] be a finite strategic-form game with $m_i=|A_i|\ge2$ and rational pure payoffs $v_i:A\to[-1,1]\cap{\mathbb{Q}}$. Its mixed extension has ${\Delta}_i={\Delta}(A_i)$, ${\Delta}=\prod_i{\Delta}_i$, and multilinear expected payoffs $u_i:{\Delta}\to{\mathbb{R}}$. Unless specified otherwise, the input is the entire explicit payoff table, whose binary bit length is $L$; write $M=\prod_i m_i$ and $d=\sum_i m_i$. "Polynomial time" always means polynomial in $L$ and any additional input bit lengths, not necessarily polynomial in $n$.

For $p\in{\Delta}$, let the strictly profitable unilateral responses of player $j$, including non-deviation, be \[ B_j(p)=\{p_j\}\cup \left\{q_j\in{\Delta}_j:u_j(q_j,p_{-j})>u_j(p)\right\}, \qquad B_{-i}(p)=\prod_{j\ne i}B_j(p). \tag{OPT.1}\label{wsref-0-6f-70-74-69-6d-69-6e-3a-65-71-3a-42} \] Each individual profitability comparison is against the original baseline profile $p$. The product permits combinations of independently profitable unilateral deviations; such a combination need not itself be profitable for all deviators. The baseline is always available. The benchmark optimin performance and mixed optimin set of Ismail (2025, Definitions 1--3) are \[ \pi_i(p)=\inf_{q_{-i}\in B_{-i}(p)}u_i(p_i,q_{-i}),\qquad {\mathcal O}^{\rm mix}(G)=\left\{p\in{\Delta}:\ \nexists q\in{\Delta}: \pi(q)\ge\pi(p),\ \pi(q)\ne\pi(p)\right\}. \tag{OPT.2}\label{wsref-0-6f-70-74-69-6d-69-6e-3a-65-71-3a-70-69} \] Vector inequalities are componentwise. Pareto nondominance in (2) concerns the performance vector, not necessarily actual payoffs. In finite mixed games, ${\mathcal O}^{\rm mix}(G)$ is nonempty [S1]; it may contain irrational probability vectors (see Section optimin:sec:checks).

For the pure-restricted concept, replace the candidate set ${\Delta}$ by $A$ and each ${\Delta}_j$ in (1) by $A_j$. Denote these objects by $\pi^{\rm pure}$ and ${\mathcal O}^{\rm pure}(G)$. In general ${\mathcal O}^{\rm pure}(G)\not\subseteq{\mathcal O}^{\rm mix}(G)$; a pure-restricted optimin is not necessarily mixed-optimin.

For exact mixed computation, specify how algebraic probabilities are encoded (e.g. isolating intervals and defining polynomials, or an equivalent real-algebraic representation). Rational candidate profiles and rational approximation outputs have binary-encoded fractions. For rational $\varepsilon\in(0,1)$ the strategy metric is $\|p-q\|_\infty$ on ${\mathbb{R}}^d$. The type of reduction (many-one, Turing, or solution-preserving search reduction) must be identified before using a complexity-completeness label.

Formal research question: principal open complexity problems

The overarching open target is a sharp worst-case classification of the total search problem \[ \mathsf{MIXED\text{-}OPTIMIN}:\quad G\longmapsto p\in{\mathcal O}^{\rm mix}(G). \tag{OPT.3}\label{wsref-0-6f-70-74-69-6d-69-6e-3a-65-71-3a-73-65-61-72-63-68} \] An arbitrary acceptable optimin is sufficient: neither maximizing welfare nor meeting a specified threshold is required. The decision/selection hardness results recorded later do not classify this task. The following precise variants organize the remaining work. Where a component is already resolved, it is marked accordingly and the further question is stated explicitly.
  1. Two-player general-sum exact search (central unresolved case). For rational bimatrix inputs with arbitrary action counts $m_1,m_2$, determine the exact complexity of (3) for $n=2$. Is there a polynomial-time algorithm under a specified exact algebraic-output model? If not, establish a correct search reduction and tight hardness/completeness bound (for example relative to ${\mathsf{PPAD}}$, ${\mathsf{FIXP}}$ or another justified total-search class). Separately classify bounded-support, bounded-action, or special-rank subfamilies. Do not infer PPAD-hardness merely from NP-hardness of choosing a performance-threshold-satisfying optimin.

  2. Three-player and general $n$-player exact search. For each fixed $n\ge3$ and separately for variable $n$, determine the sharp search complexity of (3), distinguishing (i) general-sum, (ii) constant-sum, and (iii) zero-sum classes and fixed versus unbounded action counts. Determine whether a suitably formulated ${\mathsf{FIXP}}$-complete or other real search characterization applies, and whether a lower player count supports genuinely easier arbitrary-point search. A Nash oracle suffices to find an optimin in constant-sum games; the reverse reduction is not established by that observation.

  3. Exact-to-near approximation and a repair of performance efficiency. Classify the rational-output total search problem \[ \mathsf{NEAR\text{-}OPTIMIN}(G,\varepsilon):\quad \widehat p\in{\Delta}\cap{\mathbb{Q}}^d,\qquad \inf_{p^*\in{\mathcal O}^{\rm mix}(G)}\|\widehat p-p^*\|_\infty\le\varepsilon. \tag{OPT.4} \] Can the real-algebraic upper bounds be improved to polynomial time or to a sharp standard approximation/search class, with explicit dependence on $L$, $\log(1/\varepsilon)$, and $1/\varepsilon$? The different condition \[ \nexists q\in{\Delta}:\quad\pi(q)\ge\pi(\widehat p),\qquad \max_i\left(\pi_i(q)-\pi_i(\widehat p)\right)>\varepsilon \tag{OPT.5} \] is not always satisfiable by rational $\widehat p$, even for positive $\varepsilon$ (Section optimin:sec:checks). Accordingly, classify this second task only on a declared promise class guaranteeing a rational witness, or with algebraic outputs, or after specifying a different robust performance metric. Do not conflate (4) and (5).

  4. Sharper threshold/value complexity where still open. For rational $r=(r_1,\ldots,r_n)$, positive rational weights $\lambda_i$ summing to one, and rational $t$, define \[ \mathsf{GUARANTEE}(G,r):\ \exists p\in{\Delta}\ \forall i:\pi_i(p)\ge r_i\,?,\qquad V_\lambda(G)=\max_{p\in{\Delta}}\sum_i\lambda_i\pi_i(p). \tag{OPT.6} \] The associated threshold $V_\lambda(G)\ge t$ and (6)'s guarantee problem are already NP-hard for bimatrix games and ${\exists\mathbb{R}}$-complete for three-player zero-sum games by reductions detailed below (
    \textsc{Derived}
    ). The remaining sharper targets include: does unrestricted bimatrix feasibility belong to ${\mathsf{NP}}$, or is it ${\exists\mathbb{R}}$-complete? Determine the exact output complexity of $V_\lambda$ and a maximizing profile; classify rational additive-value approximation versus rational approximate maximizers, and pursue finer hardness/approximation bounds. For a specified threshold, distinguish merely some feasible profile from an arbitrary optimin.

  5. Sharper certification and verification boundaries. For a rational proposed mixed profile $p$, define \[ \mathsf{IS\text{-}OPTIMIN}(G,p):\quad p\in{\mathcal O}^{\rm mix}(G)\,? \tag{OPT.7} \] The general problem is in ${\mathrm{co}\text{-}\exists\mathbb{R}}$, and a four-player hardness construction gives ${\mathrm{co}\text{-}\exists\mathbb{R}}$-completeness (
    \textsc{Derived}
    ). Classify its exact complexity with two and three players, under restrictions such as symmetric, potential or polymatrix games, and for algebraically encoded candidate profiles. Investigate certification under explicitly declared promise gaps. Do not confuse checking (7), which compares $p$ with all profiles, with polynomial-time computation of the numbers $\pi_i(p)$.

  6. Succinct pure games: resolve the remaining search/representation gap. On an explicit table, finding one or all pure-restricted optimins is polynomial-time (a settled fact). For a succinct Boolean/rational-payoff circuit $C$, require payoff computation to take polynomial bit time and produce polynomial-bit rationals. Threshold feasibility of a pure optimin is $\Sigma_2^P$-complete even when every player has two actions (
    \textsc{Derived}
    ). Determine tight total-search classifications under (i) all-binary-player representations, (ii) general polynomial-bit encodings of action strings, and (iii) restricted graphical or anonymous representations. Establish applicable search-reduction notions and identify precisely which structural restrictions restore polynomial time.

  7. Structural and parameterized mixed-strategy search. Determine sharp search and selection complexity beyond the already-solved full-table common-interest and two-person zero-sum cases, including (i) potential games, (ii) $n$-person constant-sum games for $n\ge3$, (iii) symmetric games, (iv) polymatrix/graphical games, (v) anonymous and low-rank games, and (vi) bounded-interaction graphs. Investigate parameterization by $n$, $d=\sum_i m_i$, support size, local width, payoff rank, and approximation tolerance. Fixed $d$ yields polynomial-time algebraic computation for each fixed dimension, but this alone is not a uniform fixed-parameter-tractability (FPT) theorem; give parameter-explicit $f(d)L^{O(1)}$ bounds before asserting FPT. Pure-restricted and two-person zero-sum tractability are baseline cases, not unresolved problems.

  8. Alternate permissible-deviation rules and totality. Replace (1), separately, by \[ \widehat B_j^{\rm weak}(p)=\{q_j:u_j(q_j,p_{-j})\ge u_j(p)\},\qquad \widehat B_j^{\rm best}(p)=\{p_j\}\cup{\operatorname*{arg\,max}}_{q_j\in{\Delta}_j}u_j(q_j,p_{-j}). \tag{OPT.8} \] A $2\times2$ counterexample shows that their corresponding mixed Pareto-optimin sets may be empty (
    \textsc{Derived}
    ). Therefore first classify assumptions guaranteeing existence, or formally require an output of "empty". On classes with totality, determine search/threshold/approximation complexity; specify whether the scalar value is a maximum or only a supremum. The pure-restricted modifications remain total by finiteness and are polynomial for explicit tables.

Source audit and current complexity status

Precisely specified taskStatus and provenance
TaskStatus and provenance
Strict-deviation $\pi(p)$, rational $p$, explicit table${\mathsf{FP}}$ for all player counts (
\textsc{Derived}
vertex enumeration).
Pure-restricted optimin: find one, enumerate all, verify, or decide performance thresholds; explicit table${\mathsf{P}}$, all $n$ (elementary enumeration; 
\textsc{Published}
pure existence in Ismail).
Pure Nash existence/search conditional on existence; explicit normal form${\mathsf{P}}$, all $n$ (
\textsc{Published} [S2]
); correction of an earlier erroneous claim.
Exact arbitrary mixed optimin, general-sum bimatrixUnresolved here. Algebraic computation possible; no NP-/PPAD-/FIXP-hardness of arbitrary search established.
Exact arbitrary mixed optimin, general $n$Exact real-algebraic algorithm (
\textsc{Derived}
); no sharp general search classification.
Distance-$\varepsilon$ rational output to an exact mixed optimin${\mathsf{FP}}^{\Sigma_2\mathbb R}\subseteq\mathsf{FPSPACE}$ (
\textsc{Derived}
; real-hierarchy upper bound [S9]).
Rational performance-efficient output according to (5)Not always total; four-player counterexample for each $0<\varepsilon<1$ (
\textsc{Derived}
).
Two-player general-sum guarantee/value thresholds${\mathsf{NP}}$-hard and in ${\exists\mathbb{R}}$; cap-saturating subproblems ${\mathsf{NP}}$-complete (
\textsc{Derived}
from [S4]).
Three-player zero-sum guarantee thresholds $\pi\ge0$${\exists\mathbb{R}}$-complete (
\textsc{Derived}
from published bilinear hardness [S5]).
Three-player zero-sum single-player performance threshold${\exists\mathbb{R}}$-complete (
\textsc{Derived}
from [S5]).
Three-player zero-sum positive-weight value threshold${\exists\mathbb{R}}$-complete, with fixed weights $(1/5,2/5,2/5)$ (
\textsc{Derived}
).
Numerical approximation of scalar optimum $V_\lambda$${\mathsf{FP}}^{{\exists\mathbb{R}}}$ upper bound for additive value approximation; does not imply a rational near-maximizing profile (
\textsc{Derived}
).
Check a rational mixed profile for global optimin status${\mathrm{co}\text{-}\exists\mathbb{R}}$-complete for four players; in ${\mathrm{co}\text{-}\exists\mathbb{R}}$ for any $n$ (
\textsc{Derived}
).
Check performance efficiency at fixed $\varepsilon=1/2$${\mathrm{co}\text{-}\exists\mathbb{R}}$-complete for four players (
\textsc{Derived}
).
Succinct pure-restricted guarantee thresholds, variable binary-action players$\Sigma_2^P$-complete (
\textsc{Derived}
).
Succinct pure-restricted arbitrary search, general action encodings${\mathsf{FP}}^{\Sigma_2^P}$ upper bound; Turing hardness under general succinct action encodings (
\textsc{Derived}
); binary-player search tighter bound unresolved.
Two-player zero-sum and constant-sum mixed optimin search${\mathsf{P}}$ via minimax linear programming (
\textsc{Published}
equivalence [S1]).
Explicit tabular common-interest mixed optimin search${\mathsf{P}}$ via a global pure payoff maximum (
\textsc{Derived}
).
Weak-deviation/best-response modified mixed optiminMay be empty even in a rational $2\times2$ game (
\textsc{Derived}
).

Reading the table. ${\exists\mathbb{R}}$-completeness is a decision statement, with ${\mathsf{NP}}\subseteq{\exists\mathbb{R}}\subseteq{\mathsf{PSPACE}}$. ${\mathrm{co}\text{-}\exists\mathbb{R}}$ is the complement decision class. An ${\exists\mathbb{R}}$-hard performance threshold is not a valid reduction to the total problem (3): an arbitrary optimin may fail the threshold even when another optimin satisfies it. Search problems requiring exact irrational outputs need a real/algebraic model rather than informal ordinary NP-completeness terminology. The results marked 

\textsc{Derived}
are internal research findings with the caveats described at the start; the Nash-computation complexity classes in [S6, S7] are comparison results, not classifications of optimin.

Important correction: pure Nash equilibrium is also polynomial on a full table

An earlier discussion asserted that pure Nash search was generally non-polynomial on explicitly represented games. That was incorrect. If the input lists all $nM$ entries, test the $m_i$ unilateral alternatives for each player at every one of $M$ pure profiles. This is polynomial in the explicit input length and either finds a pure Nash equilibrium or determines that none exists. The same elementary distinction is stated in [S2]. Hardness theorems for succinctly represented pure Nash games, or Nash equilibria with specified properties, do not contradict it [S3, S2, S4].

What remains different between pure Nash and pure optimin

Pure Nash equilibrium may fail to exist, whereas a pure-restricted optimin always exists because a finite set of performance vectors has a Pareto-maximal element [S1]. Enumeration returns all pure optima with at most $O(nM^2)$ payoff evaluations/comparisons up to bit costs; the same order gives an explicit-table algorithm for pure Nash existence (though not the same test). This does not prove efficient pure optimin computation in the number of players: $M$ is exponential in $n$ when there are two actions per player.

Mathematical verification notes

These are brief verification arguments, placed after the open statements. The arguments below record the reductions and constructions used in this attack; these results are not attributed to the paper introducing optimin.

Exact performance evaluation and its symbolic hypograph

For rational $p$, set $g_{ja}=u_j(e_a,p_{-j})-u_j(p)$, so $\sum_a p_{ja}g_{ja}=0$. Then \[ \overline{B_j(p)}= \begin{cases} \{p_j\},&\max_a g_{ja}=0,\\ \{q_j\in{\Delta}_j:\sum_a q_{ja}g_{ja}\ge0\},&\max_a g_{ja}>0. \end{cases} \tag{OPT.9} \] In the second branch this is a simplex cut by a halfspace. Besides permitted pure vertices, its vertices occur where an edge from $g_{ja}>0$ to $g_{jb}<0$ meets the hyperplane; the positive and negative coordinates are \[ q_{ja}=\frac{-g_{jb}}{g_{ja}-g_{jb}},\quad q_{jb}=\frac{g_{ja}}{g_{ja}-g_{jb}}. \tag{OPT.10} \] At most $m_j^2$ candidates per opponent suffice. Multi-affinity implies that minimizing $u_i(p_i,q_{-i})$ over the independent product is attained at a product of vertices, with at most $\prod_{j\ne i}m_j^2\le M^2$ combinations. Thus rational-profile evaluation is polynomial in the full table. Crucially, if no strict improvement exists, replacing $\{p_j\}$ by the entire weak-response polytope would be wrong.

Conditioning on which gains are positive, zero or negative gives a polynomial-size semialgebraic description of $z_i\le\pi_i(p)$: for every valid candidate deviation tuple $q_{-i}$ require $z_i\le u_i(p_i,q_{-i})$. Multiplying only denominators known positive under their guards produces polynomial inequalities. Algebraic gate variables prevent exponential symbolic expansion. This yields ${\exists\mathbb{R}}$ upper bounds for threshold existence and ${\mathrm{co}\text{-}\exists\mathbb{R}}$ for rational-profile nondominance.

The two-player single-component linear-programming identity

For bimatrix payoff matrices $(A,B)$, with row mixture $x$ and column mixture $y$, \[ \max_{x,y}\pi_1(x,y)= \max_b\ \max_{\substack{x\in{\Delta}(A_1)\\x^\mathsf T B e_b\ge x^\mathsf T B e_c\ (\forall c)}} x^\mathsf T A e_b. \tag{OPT.11} \] To bound an arbitrary profile, observe that an opponent pure best reply is either already on the opponent's equilibrium support or is a strictly profitable deviation. Conversely, choosing the opponent's pure best reply $e_b$ makes that opponent unable to deviate profitably, attaining the displayed objective. There are polynomially many linear programs. This optimizes just one $\pi_i$; selecting a globally undominated vector remains a separate task.

Cap saturation and three-player hardness

If $\sum_i u_i(p)\le C$ at every profile, and $\sum_i r_i=C$, then \[ \pi(p)\ge r\quad\Longleftrightarrow\quad p\text{ is a Nash equilibrium with }u(p)=r. \tag{OPT.12} \] Indeed $\pi\le u$ forces equality in the total-payoff cap; any strictly profitable deviation for one player would lower some other player's payoff below its threshold. Conversely a Nash equilibrium has no strict profitable deviations. For bimatrix NP-hardness, use the specific cap-saturating SAT construction in Conitzer--Sandholm [S4], not an arbitrary Nash hardness statement.

For three-player hardness start with the ${\exists\mathbb{R}}$-complete bilinear system $\sum_{a,b}c^{(k)}_{ab}x_ay_b=0$ for all $k$, with $x,y$ in simplexes [S5, Proposition 2 in the arXiv version]. A signed-equation selector $S$ chooses $(s,k)$ with $s\in\{\pm1\}$; set \[ (u_S,u_X,u_Y)=(2s q_k,-s q_k,-s q_k). \tag{OPT.13} \] This defines rational pure-table payoffs by evaluating $q_k$ on pure actions, then using their multilinear extensions. It is constant-sum zero (rescale if necessary). By (12), performance thresholds $(0,0,0)$ are met exactly by a zero-payoff Nash equilibrium, which the selector's best-response condition makes equivalent to the bilinear equations being zero. For the fixed unequal weights $(1/5,2/5,2/5)$, the weighted value is $0$ exactly in the feasible case, and is negative otherwise. This is an optimin-specific reduction derived from [S5], not a published optimin-complexity theorem in that paper.

Four-player verification hardness and irrational rational-output obstruction

Introduce a fourth binary gate player to the previous game: if the gate is open ($e=1$), the first three players receive their original payoffs; if it is closed ($e=0$), they receive zero; the gate obtains $u_4=e$. A rational baseline with a closed gate and signs balanced has $\pi=(0,0,0,0)$. It has a performance dominator exactly if the original bilinear system is feasible, with a gain of one for the gate in yes-instances. Thus verification is ${\mathrm{co}\text{-}\exists\mathbb{R}}$-complete already with four players. This must not be rephrased as proving that finding any optimin is hard.

For the distinct issue of rational approximate performance, put \[ q_1(x,y)=x-y,\qquad q_2(x,y)=xy+x+y-1, \quad\text{with }x,y\in[0,1]. \tag{OPT.14} \] In the signed-selector game with payoffs $(s q_k/2,-s q_k/4,-s q_k/4)$, all players' performances are nonpositive, and the only possible nondominated vector has $x=y=\sqrt2-1$. Add an extra selector action $D$ with original-player payoffs zero and a binary player $T$ with payoff $1$ on $D$, $0$ otherwise. The exact profile $D$ and $x=y=\sqrt2-1$ has performance $(0,0,0,1)$. At every rational profile, some $q_k\ne0$; the selector can profitably move to a signed action whenever $D$ has positive mass, reducing $T$'s performance to zero. Thus every rational profile is dominated by an improvement of one in $T$'s performance. This gives the non-totality of the specified rational-output performance approximation for every $0<\varepsilon<1$, without affecting existence of rational strategy-distance approximations.

Succinct binary-player pure thresholds and modified-rule nonexistence

In a succinct game where all pure actions are binary, reduce a quantified Boolean instance $\exists x\,\forall y\,\varphi(x,y)$ by encoding each universal bit using a directed triple of guard players with payoffs $u_h=b_h(1-2b_{h+1})$, indices modulo three. Requiring nonnegative performance forces the guards' baseline triple to $000$, yet allows each first guard bit to independently switch to $1$ profitably. An extra monitor player receives $\varphi$ and must guarantee payoff one, forcing $\forall y\,\varphi(x,y)$. This explains the $\Sigma_2^P$-hardness; membership follows from the existential baseline and universal deviation tuple. The reduction is for a circuit input, not a full payoff table.

For the two modified rules (8), the rational payoff table \[ \begin{array}{c|cc} &L&R\\\hline T&(1,0)&(0,0)\\ B&(0,1)&(0,0) \end{array} \tag{OPT.15} \] with $x=\Pr(B)$, $y=\Pr(L)$, gives for both modifications \[ \widetilde\pi_1(x,y)=\begin{cases}(1-x)y,&x>0,\\0,&x=0,\end{cases} \qquad\widetilde\pi_2(x,y)=0. \tag{OPT.16} \] Every attained first component is strictly below one, and can be improved with $y'=1$ and sufficiently small $x'>0$, leaving the second component at zero. Therefore neither modified mixed optima set has any element. The strict benchmark does have $(T,L)$ as an optimin.

Interpretation and scope

  1. Publisher-backed versus research-derived. Ismail (2025) supplies the benchmark, upper semicontinuity/existence, the pure-restricted existence observation, and the two-person zero-sum equivalence. It does not establish the NP-hardness, ${\exists\mathbb{R}}$-completeness, ${\mathrm{co}\text{-}\exists\mathbb{R}}$-completeness, or $\Sigma_2^P$-completeness claims developed here. The exact bilinear source is Berthelsen--Hansen (2022); Conitzer--Sandholm (2008) supplies the SAT game with a social-welfare cap. These references have been checked against their text and bibliographic records.
  2. Open versus solved. The central arbitrary mixed search classifications remain unanswered by the deductions above. Thresholds, scalarized value, and global verification can be hard for a selected optimin without proving that obtaining any one is hard. In particular no general-sum bimatrix ${\mathsf{PPAD}}$-completeness or ${\mathsf{FIXP}}$-completeness theorem is claimed here.
  3. Exact, rational and approximate. Exact strategies may be irrational; numerical approximation of the value $V_\lambda$ is easier to define than a rational approximate maximizing profile. The former has a real-feasibility-oracle bound; the latter may be impossible at a fixed positive tolerance under the specified performance-efficiency notion.
  4. Unattained scalar suprema for modified rules. Upper semicontinuity of Ismail's strict performance function is used for the maximum and existence statements. It does not automatically transfer to rules (8). For those variants, "maximum" must not be asserted absent attainment.
  5. No unqualified FPT claim. The fixed-dimensional real-algebraic algorithms imply polynomial running time when total dimension $d$ is a fixed constant. One must exhibit an explicit uniform bound $f(d)L^{O(1)}$ to claim fixed-parameter tractability; no such tight parameter result is established as a separate theorem in this entry.
  6. Status of originality. These are mathematical reductions and examples prepared for this project, not peer-reviewed research results. Their validity was rechecked against definitions, elementary algebra, and source lemmas; exhaustive priority or novelty relative to the full 2026 literature has not been certified.

References

  1. S1 Mehmet S. Ismail (2025), Super-Nash Performance, International Economic Review 66(4), 1487--1503. https://doi.org/10.1111/iere.12764. Definitions 1--3; Theorem 1, Remarks 1 and 5; Proposition 2/Corollary 1; Appendix Lemma A.1. Source for optimin, not for our complexity classifications.
  2. S2 Carme Àlvarez, Joaquim Gabarro, Maria Serna (2011), Equilibria Problems on Games: Complexity versus Succinctness, Journal of Computer and System Sciences 77(6), 1172--1197. https://doi.org/10.1016/j.jcss.2011.01.001. Abstract and representation analysis: pure Nash existence in explicit strategic games is polynomial-time; NP- and $\Sigma_2^P$-hardness in more succinct encodings.
  3. S3 Georg Gottlob, Gianluigi Greco, Francesco Scarcello (2005), Pure Nash Equilibria: Hard and Easy Games, Journal of Artificial Intelligence Research 24, 357--406. https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/gottlob05a.pdf. Relevant graphical/compact input restrictions; not a hardness claim for explicit full tables.
  4. S4 Vincent Conitzer, Tuomas Sandholm (2008), New Complexity Results about Nash Equilibria, Games and Economic Behavior 63(2), 621--641. https://doi.org/10.1016/j.geb.2008.02.015; author PDF https://www.cs.cmu.edu/~conitzer/nashGEB08.pdf. Section 3, Definition 4 and Theorem 1: symmetric SAT game, cap $2(n-1)$, Nash payoffs $n-1$ iff satisfiable. The optimin cap reduction is a distinct deduction here.
  5. S5 Marie Louisa Tølbøll Berthelsen, Kristoffer Arnsfelt Hansen (2022), On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria, Theory of Computing Systems 66(3), 519--545. https://doi.org/10.1007/s00224-022-10080-1; preprint https://arxiv.org/abs/2001.05196. Proposition 2 and Definition 1 of arXiv v1: ${\exists\mathbb{R}}$-complete homogeneous bilinear feasibility and the three-player signed-equation zero-sum game. The associated optimin results here are deductions, not their theorems.
  6. S6 Xi Chen, Xiaotie Deng, Shang-Hua Teng (2009), Settling the Complexity of Computing Two-Player Nash Equilibria, Journal of the ACM 56(3), Article 14. https://doi.org/10.1145/1516512.1516516. Bimatrix Nash search is PPAD-complete, not automatically mixed-optimin search.
  7. S7 Kousha Etessami, Mihalis Yannakakis (2010), On the Complexity of Nash Equilibria and Other Fixed Points, SIAM Journal on Computing 39(6), 2531--2597. https://doi.org/10.1137/080720826. FIXP and exact-versus-near real algebraic search for Nash.
  8. S8 James Renegar (1992), On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Parts I--III, Journal of Symbolic Computation 13(3), 255--352. https://doi.org/10.1016/S0747-7171(10)80003-3 (Part I); https://doi.org/10.1016/S0747-7171(10)80005-7 (Part III). Quantifier elimination, fixed-dimensional polynomiality and algebraic sampling.
  9. S9 Thekla Hamm, Lucas Meijer, Tillmann Miltzow, Subhasree Patro (2025), Oracle Separations for $\mathbb R\mathrm{PH}$. https://arxiv.org/abs/2502.09279. Theorem 14, real polynomial-hierarchy PSPACE bound; used only for the stated polynomial-space upper bound.
  10. S10 Larry J. Stockmeyer (1976), The Polynomial-Time Hierarchy, Theoretical Computer Science 3(1), 1--22. https://doi.org/10.1016/0304-3975(76)90061-X. Standard second-level quantified-Boolean source problem; the pure-optimin guards are constructed here.

Completion Estimate

40%

Go to contribution →