Exact Stationary Equilibria in Discounted Perfect-Information Games: A three-player arithmetic construction and FIXP-completeness

We prove that, for every fixed number of players at least three, computing an exact stationary equilibrium of a rational discounted perfect-information stochastic game is FIXP-complete under separable-linear reductions. Hardness holds already for games with discount 1/2 and at most two actions per state. Membership in FIXP is known for general discounted stochastic games; whether the problem is FIXP-hard for three or more players was left open by Hansen and Nie. We reduce from exact Nash equilibrium in three-player strategic-form games. In the constructed game, each real number is carried by one player's value at a state: two-state modules compute signed affine maps and clipping, and a cycle of three states computes a reciprocal while passing the value to another player. Uniform reward bounds and interval registers enforce these identities at every equilibrium, including in the presence of feedback. Each coordinate of the Nash equilibrium is one minus the continuation probability at a single state. For completeness, we also give a direct membership proof for the perfect-information model in which every division of the fixed-point circuit is defined on the whole domain.