Nash equilibrium is the baseline solution concept for games. Proper equilibrium is a refinement — a Nash equilibrium with additional structure: each player’s suboptimal strategies are played with probability exponentially smaller than better strategies. Proper equilibria are “more rational” than generic Nash equilibria because they eliminate equilibria supported by implausible threats.

In extensive-form games — games with sequential moves, like chess or poker — computing a proper equilibrium has the same complexity as computing a Nash equilibrium (arXiv:2602.10096). The refinement is free. You can compute the more demanding solution without paying a computational premium. This makes intuitive sense: the extensive-form structure constrains the game enough that the additional rationality requirements of proper equilibrium do not create additional computational work.

In polytope games — a more general representation where strategies are points in a polytope — computing a proper equilibrium is NP-hard. The refinement is not free. The additional structure demanded by properness creates computational work that does not exist for ordinary Nash equilibrium.

This is the first known class of games where the complexity of a refinement strictly exceeds the complexity of the base concept. For every other studied game form, refinement complexity either equals or is unknown relative to Nash complexity. The polytope result establishes a separation: there exist game representations where asking for “more rational” solutions is genuinely harder than asking for “any rational” solution.

The implication is architectural. The same game, represented differently, has different computational costs for the same solution concept. The difficulty is not in the game or in the solution concept — it is in how the game is described. The representation is load-bearing.