Unpredictability of complex (pure) strategies

Tai Wei Hu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-15
Number of pages15
JournalGames and Economic Behavior
Volume88
DOIs
StatePublished - Jan 1 2014

Keywords

  • Algorithmic randomness
  • Frequency theory of probability
  • Kolmogorov complexity
  • Mixed strategy
  • Objective probability
  • Zero-sum game

ASJC Scopus subject areas

  • Finance
  • Economics and Econometrics

Fingerprint Dive into the research topics of 'Unpredictability of complex (pure) strategies'. Together they form a unique fingerprint.

Cite this