Unpredictability of complex (pure) strategies

- The paper provides a new framework for unpredictable behavior.
- I show that complexity (modeled by oracle machines) can be a substitute of randomness.
- A Nash equilibrium exists in pure strategies if the endowed oracles are mutually complex.
- I show that relative frequencies are central to unpredictability in repeated games.

Unpredictable behavior is central to optimal play in many strategic situations because predictable patterns leave players vulnerable to exploitation. A theory of unpredictable behavior based on differential complexity constraints is presented in the context of repeated two-person zero-sum games. Each player's complexity constraint is represented by an endowed oracle and a strategy is feasible if it can be implemented with an oracle machine using that oracle. When one player's oracle is sufficiently more complex than the other player's, an equilibrium exists with one player fully exploiting the other. If each player has an incompressible sequence (relative to the opponent's oracle) according to Kolmogorov complexity, an equilibrium exists in which equilibrium payoffs are equal to those of the stage game and all equilibrium strategies are unpredictable. A full characterization of history-independent equilibrium strategies is also obtained.