Threshold Nash equilibrium in extensive form: resolved classification

Threshold Nash equilibrium in extensive form: resolved classification

Result and proof dependencies

This is a reconstruction of an already resolved classification, not a new open-problem claim. For explicitly listed finite perfect-recall games with rational data and an unrestricted input number of players, the payoff-threshold Nash decision problem is $\exists\mathbb R$-complete. This attempt proves a polynomial existential-real encoding using realization plans and linear-program duality, and proves the reduction from the source's scalar objective to the catalogue's vector thresholds. The source's scalar hardness theorem is used as an external result. The solved label denotes this submitted complete argument for the stated classification, rather than independent external verification.

The question is whether a behavioral Nash equilibrium $b$ exists such that $U_j(b)\geq t_j$ for each specified player $j\in J$. Chance is allowed, and thresholds and terminal utilities are binary-encoded rationals. Replacing exact thresholds by numerical tolerances changes the question.

Realization plans and their exact behavioral meaning

For player $i$, let $\Sigma_i$ contain the empty own-action sequence and all sequences ending in one of its actions. Actions at different information sets receive distinct labels, so a sequence records information-set/action pairs even when the displayed action names coincide. Perfect recall gives each information set $I$ a unique preceding own sequence $\sigma_i(I)$. Introduce one variable $x_{i,\sigma}$ for each such sequence, with \[ x_{i,\varnothing}=1,\qquad x_{i,\sigma}\geq0,\qquad \sum_{a\in A(I)}x_{i,\sigma_i(I)a}=x_{i,\sigma_i(I)} \quad(I\text{ belonging to }i). \tag{1} \] Write these equations as $E_ix_i=e_i$ and let $X_i$ be the resulting nonnegative polytope. Its size is polynomial in the listed tree. Multiple information sets can have the same preceding own sequence; each has its own flow equation in (1), rather than a shared capacity constraint.

Given a behavioral strategy, the product of its own action probabilities along each sequence satisfies (1). Conversely, for a feasible realization plan define \[ b_{I,a}=\frac{x_{i,\sigma_i(I)a}}{x_{i,\sigma_i(I)}} \quad\text{if }x_{i,\sigma_i(I)}>0, \tag{2} \] and choose any action distribution if the denominator is zero. In that case nonnegativity and (1) force every immediate extension to be zero. Induction on sequence length proves that products under (2) recover all coordinates of $x_i$, including zero-probability sequences. Consequently these two representations induce identical leaf probabilities against every opponents' profile. They also represent exactly the same available unilateral payoff improvements.

For a leaf $\ell$, let $\sigma_i(\ell)$ be player $i$'s complete own sequence along its path, and let $\pi_c(\ell)$ be the product of chance probabilities there. Expected utilities are \[ U_i(x)=\sum_{\ell}u_i(\ell)\pi_c(\ell) \prod_h x_{h,\sigma_h(\ell)}. \tag{3} \] This is multilinear in the players' realization plans. With opponents fixed, write it as $c_i(x_{-i})^Tx_i$, by collecting the terms with the same own sequence. All coefficients of $c_i$ are explicit polynomials in the other players' variables, with a polynomial number of leaf terms.

Eliminating the universal deviation quantifier

At fixed $x_{-i}$, player $i$'s best-response problem is the linear program \[ \max_y c_i(x_{-i})^Ty \quad\text{subject to }E_iy=e_i,\ y\geq0. \tag{4} \] Its dual has unrestricted real variables $\lambda_i$ and is \[ \min_{\lambda_i}e_i^T\lambda_i \quad\text{subject to }E_i^T\lambda_i\geq c_i(x_{-i}). \tag{5} \] The primal is feasible and bounded because realization plans are nonempty and all their coordinates lie in $[0,1]$. Finite-dimensional linear-program duality therefore supplies an attained dual optimum. This statement remains valid when the fixed opponents' coordinates are arbitrary real numbers; it does not require them to be rational.

Combine (1), (6), and $U_j(x)\geq t_j$ for $j\in J$. This is a purely existential system of polynomial equalities and non-strict inequalities. There is one pair of realization/dual vectors per player, and the listed tree bounds the total number of sequences, constraints, and payoff terms. Chance products have polynomial bit length because their denominator and numerator bit lengths add along paths. If desired, every long product in (3) can be replaced by auxiliary multiplication variables and quadratic equalities/equalities, using one gate variable per product step. This also makes clear that no exponentially expanded strategic-form payoff table is hidden in the encoding. We have proved membership in $\exists\mathbb R$.

From a scalar objective to player thresholds

The source proves $\exists\mathbb R$-hardness for deciding whether some Nash equilibrium achieves a rational linear objective \[ \omega(U)=\sum_i w_iU_i\geq\lambda. \tag{7} \] Construct an additional passive player $0$ whose utility at each terminal leaf is \[ u_0(\ell)=\sum_iw_iu_i(\ell). \] It has no decisions. If the formal encoding requires every player to have an information set, add a root node with its sole available action. Retain the original tree, chance probabilities, and every original player's utility. Set $J=\{0\}$ and $t_0=\lambda$.

Original-player deviations and payoffs are unchanged, while player $0$ has no alternative action. Thus projecting any new-game Nash equilibrium onto the original players gives an old-game equilibrium, and every old-game equilibrium extends to one in the new game. Linearity of expectation gives $U_0=\sum_iw_iU_i$, so the threshold for player $0$ holds exactly when (7) does. The construction has polynomial size and rational bit complexity even if the objective weights have either sign. It proves hardness for the vector-threshold language and completes the classification together with the preceding membership proof.

Checks against misleading simplifications

A two-player coordination example distinguishes equilibrium existence from successful threshold selection. Give both players payoff $2$ at $(A,A)$, $1$ at $(B,B)$, and $0$ off the diagonal, representing the game as two hidden sequential actions. Its pure equilibria yield $2$ and $1$; its interior equilibrium mixes $A$ with probability $1/3$ for each player and yields $2/3$. A threshold $3/2$ for either player accepts only the high-payoff equilibrium. A generic exact equilibrium procedure could return either other equilibrium and would not thereby decide the threshold question correctly.

The real variables in (6) need not admit polynomial-bit rational values. Therefore the existential encoding is not an NP certificate argument. Nor does the fixed-point search classification immediately decide whether a payoff-favorable fixed point exists. These are different quantifier and output requirements. The passive-player construction also changes the number of players, so it does not prove hardness for every previously fixed player count. Nothing here establishes chance-free hardness if the imported scalar hardness proof uses chance.

Completion Estimate

100%

This is a post hoc, heuristic estimate for the full catalogue target. The attempt gives a polynomial existential-real encoding of behavioral Nash through realization plans and attained best-response dual certificates. Its passive-player reduction transfers the cited scalar-objective hardness to the full vector-threshold language, completing the canonical classification with explicit perfect-recall, rational-data and player-count assumptions.

Reference and attribution

The external scalar hardness result is Theorem 2 and Section 6.1 of Vincent Cheval, Florian Horn, Soumyajit Paul, and Mahsa Shirmohammadi, On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games, arXiv:2507.11509v2 (2026). https://arxiv.org/pdf/2507.11509v2. The realization-plan dual certificate and passive-player equivalence are proved explicitly here. The paper's historical discussion of an older unresolved classification should not be read as its final result.

Threshold Nash equilibrium in extensive form: resolved classification

Problem ID: C72-656 Model: GPT 6 Astra Pro Version: 2

Result and proof dependencies

This is a reconstruction of an already resolved classification, not a new open-problem claim. For explicitly listed finite perfect-recall games with rational data and an unrestricted input number of players, the payoff-threshold Nash decision problem is $\exists\mathbb R$-complete. This attempt proves a polynomial existential-real encoding using realization plans and linear-program duality, and proves the reduction from the source's scalar objective to the catalogue's vector thresholds. The source's scalar hardness theorem is used as an external result. The solved label denotes this submitted complete argument for the stated classification, rather than independent external verification.

Version 2 status and provenance. The supplied audit confirms that the issue is attribution and scope, rather than a newly identified error in the submitted theorem. This revision keeps the full argument and identifies the general scalar classification as a published result and the vector formulation as its elementary passive-player consequence. The submitted solved status concerns that precise classification; it does not credit this reconstruction as a new research resolution. The audit's coalition and matching computations do not verify this manuscript, and this revision claims no fresh external source check.

The question is whether a behavioral Nash equilibrium $b$ exists such that $U_j(b)\geq t_j$ for each specified player $j\in J$. Chance is allowed, and thresholds and terminal utilities are binary-encoded rationals. Replacing exact thresholds by numerical tolerances changes the question.

Realization plans and their exact behavioral meaning

For player $i$, let $\Sigma_i$ contain the empty own-action sequence and all sequences ending in one of its actions. Actions at different information sets receive distinct labels, so a sequence records information-set/action pairs even when the displayed action names coincide. Perfect recall gives each information set $I$ a unique preceding own sequence $\sigma_i(I)$. Introduce one variable $x_{i,\sigma}$ for each such sequence, with \[ x_{i,\varnothing}=1,\qquad x_{i,\sigma}\geq0,\qquad \sum_{a\in A(I)}x_{i,\sigma_i(I)a}=x_{i,\sigma_i(I)} \quad(I\text{ belonging to }i). \tag{1} \] Write these equations as $E_ix_i=e_i$ and let $X_i$ be the resulting nonnegative polytope. Its size is polynomial in the listed tree. Multiple information sets can have the same preceding own sequence; each has its own flow equation in (1), rather than a shared capacity constraint.

Given a behavioral strategy, the product of its own action probabilities along each sequence satisfies (1). Conversely, for a feasible realization plan define \[ b_{I,a}=\frac{x_{i,\sigma_i(I)a}}{x_{i,\sigma_i(I)}} \quad\text{if }x_{i,\sigma_i(I)}>0, \tag{2} \] and choose any action distribution if the denominator is zero. In that case nonnegativity and (1) force every immediate extension to be zero. Induction on sequence length proves that products under (2) recover all coordinates of $x_i$, including zero-probability sequences. Consequently these two representations induce identical leaf probabilities against every opponents' profile. They also represent exactly the same available unilateral payoff improvements.

For a leaf $\ell$, let $\sigma_i(\ell)$ be player $i$'s complete own sequence along its path, and let $\pi_c(\ell)$ be the product of chance probabilities there. Expected utilities are \[ U_i(x)=\sum_{\ell}u_i(\ell)\pi_c(\ell) \prod_h x_{h,\sigma_h(\ell)}. \tag{3} \] This is multilinear in the players' realization plans. With opponents fixed, write it as $c_i(x_{-i})^Tx_i$, by collecting the terms with the same own sequence. All coefficients of $c_i$ are explicit polynomials in the other players' variables, with a polynomial number of leaf terms.

Eliminating the universal deviation quantifier

At fixed $x_{-i}$, player $i$'s best-response problem is the linear program \[ \max_y c_i(x_{-i})^Ty \quad\text{subject to }E_iy=e_i,\ y\geq0. \tag{4} \] Its dual has unrestricted real variables $\lambda_i$ and is \[ \min_{\lambda_i}e_i^T\lambda_i \quad\text{subject to }E_i^T\lambda_i\geq c_i(x_{-i}). \tag{5} \] The primal is feasible and bounded because realization plans are nonempty and all their coordinates lie in $[0,1]$. Finite-dimensional linear-program duality therefore supplies an attained dual optimum. This statement remains valid when the fixed opponents' coordinates are arbitrary real numbers; it does not require them to be rational.

Combine (1), (6), and $U_j(x)\geq t_j$ for $j\in J$. This is a purely existential system of polynomial equalities and non-strict inequalities. There is one pair of realization/dual vectors per player, and the listed tree bounds the total number of sequences, constraints, and payoff terms. Chance products have polynomial bit length because their denominator and numerator bit lengths add along paths. If desired, every long product in (3) can be replaced by auxiliary multiplication variables and quadratic equalities/equalities, using one gate variable per product step. This also makes clear that no exponentially expanded strategic-form payoff table is hidden in the encoding. We have proved membership in $\exists\mathbb R$.

From a scalar objective to player thresholds

The source proves $\exists\mathbb R$-hardness for deciding whether some Nash equilibrium achieves a rational linear objective \[ \omega(U)=\sum_i w_iU_i\geq\lambda. \tag{7} \] Construct an additional passive player $0$ whose utility at each terminal leaf is \[ u_0(\ell)=\sum_iw_iu_i(\ell). \] It has no decisions. If the formal encoding requires every player to have an information set, add a root node with its sole available action. Retain the original tree, chance probabilities, and every original player's utility. Set $J=\{0\}$ and $t_0=\lambda$.

Original-player deviations and payoffs are unchanged, while player $0$ has no alternative action. Thus projecting any new-game Nash equilibrium onto the original players gives an old-game equilibrium, and every old-game equilibrium extends to one in the new game. Linearity of expectation gives $U_0=\sum_iw_iU_i$, so the threshold for player $0$ holds exactly when (7) does. The construction has polynomial size and rational bit complexity even if the objective weights have either sign. It proves hardness for the vector-threshold language and completes the classification together with the preceding membership proof.

Checks against misleading simplifications

A two-player coordination example distinguishes equilibrium existence from successful threshold selection. Give both players payoff $2$ at $(A,A)$, $1$ at $(B,B)$, and $0$ off the diagonal, representing the game as two hidden sequential actions. Its pure equilibria yield $2$ and $1$; its interior equilibrium mixes $A$ with probability $1/3$ for each player and yields $2/3$. A threshold $3/2$ for either player accepts only the high-payoff equilibrium. A generic exact equilibrium procedure could return either other equilibrium and would not thereby decide the threshold question correctly.

The real variables in (6) need not admit polynomial-bit rational values. Therefore the existential encoding is not an NP certificate argument. Nor does the fixed-point search classification immediately decide whether a payoff-favorable fixed point exists. These are different quantifier and output requirements. The passive-player construction also changes the number of players, so it does not prove hardness for every previously fixed player count. Nothing here establishes chance-free hardness if the imported scalar hardness proof uses chance.

Verification and final scope. The proof checks both directions of realization-plan equivalence, attained best-response duality, and the passive-player payoff identity. Its lower bound depends on Cheval, Horn, Paul, and Shirmohammadi's cited Theorem 2 and Section 6.1. The scalar classification was already published; this reconstruction makes its vector-threshold implication explicit. Neither the supplied finite-check programs nor this revision establishes a new external computational validation. Fixed-player, chance-free, strict-threshold, and approximate variants remain outside the proved statement.

Completion Estimate

100%

This is a post hoc, heuristic estimate for the full catalogue target. The canonical target is the general perfect-recall vector-threshold classification. The retained realization-plan dual encoding and passive-player reduction account for that target, using the published scalar hardness theorem. The estimate denotes coverage of this known classification and its stated formulation variant, not novelty, external verification, or completion of fixed-player and chance-free variants.

Reference and attribution

The external scalar hardness result is Theorem 2 and Section 6.1 of Vincent Cheval, Florian Horn, Soumyajit Paul, and Mahsa Shirmohammadi, On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games, arXiv:2507.11509v2 (2026). https://arxiv.org/pdf/2507.11509v2. The realization-plan dual certificate and passive-player equivalence are proved explicitly here. The paper's historical discussion of an older unresolved classification should not be read as its final result.