Unpredictability of complex (pure) strategies

• 成果类型: Article
• 署名作者: Hu, Tai-Wei
• 署名单位: Northwestern University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.08.002
• 发表日期: 2014
• 页码: 1-15
• 关键词: Kolmogorov complexity; Objective probability; Frequency theory of probability; mixed strategy; Zero-sum game; Algorithmic randomness

摘要

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. (C) 2014 Elsevier Inc. All rights reserved.