Complexity and Mixed Strategy Equilibria
Tai‐Wei Hu · 2012
Unpredictable behavior is central for optimal play in many strategic situations because a predictable pattern leaves a player vulnerable to exploitation. A theory of unpredictable behavior is presented in the context of repeated two-person zero-sum games in which the stage games have no pure strategy equilibrium. Computational complexity considerations are introduced to restrict players ’ strategy sets. The use of Kolmogorov complexity allows us to obtain a sufficient condition for equilibrium existence. The resulting theory has implications for the empirical literature that tests the equilibrium hypothesis in a similar context. In particular, the failure of some tests for randomness does not justify rejection of equilibrium play.