Sharp Accuracy Thresholds for Entropy-Regularized Binary Games

Entropy regularization yields smooth, unique best responses, yet equilibrium computation can remain hard. For binary games, we quantify this limitation through an explicit threshold for the largest unilateral improvement in regularized payoff. On every fixed bounded interval of interaction strength, tolerances above the threshold admit polynomial-time algorithms, whereas finding solutions below it is PPAD-complete, with inverse-polynomial margins. Both bounds follow from a scalar identity linking contraction algorithms and hardness reductions. Moreover, hardness persists with fixed regularization, bounded payoffs, and sparse interactions, showing that local smoothness alone does not ensure tractability.