Succinct-∃R-Completeness and Information Bounds for Partially Observable Stochastic Games

Abstract

We establish computational and information bounds for Nash equilibrium in finite, general-sum partially observable stochastic games with an arbitrary number of players and an input-dependent horizon. For rational game data and a unary-encoded horizon, deciding whether an equilibrium meets prescribed payoff thresholds is complete for the succinct existential theory of the reals. Hardness already holds with seven players, polynomially many physical states and observations, and binary nontrivial terminal actions.The reduction realizes exponentially many real variables through private behavioral histories and checks local quadratic identities using a polynomial-size transducer. For unknown categorical kernels, we derive exact analytic collapse of finite Dirichlet hierarchies with continuous Gamma concentration hyperpriors, preserving the posterior-predictive trajectory law. Absolute exploitability-transfer bounds depend on unilateral model-error oscillation and admit total-variation and relative-entropy controls. A sequential chain rule includes initial-law mismatch; posterior-averaged divergence separately equals conditional mutual information. A binary-action family encoding d latent bits yields a Fano converse with an explicitprimitive-sample bound determined by the exact reward-channel capacity. Finally, finite-budget transfer and finite-grid certificates quantify the contributions of strategic computation, policy discretization, and payoff evaluation. Together, these results connect the succinct real complexity of exact equilibrium thresholding with sufficient and necessary information for controlling equilibrium error under model uncertainty