IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v88y2014icp1-15.html
   My bibliography  Save this article

Unpredictability of complex (pure) strategies

Author

Listed:
  • Hu, Tai-Wei

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.

Suggested Citation

  • Hu, Tai-Wei, 2014. "Unpredictability of complex (pure) strategies," Games and Economic Behavior, Elsevier, vol. 88(C), pages 1-15.
  • Handle: RePEc:eee:gamebe:v:88:y:2014:i:c:p:1-15
    DOI: 10.1016/j.geb.2014.08.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825614001213
    Download Restriction: Full text for ScienceDirect subscribers only

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Tai-Wei Hu, 2013. "Expected utility theory from the frequentist perspective," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 53(1), pages 9-25, May.
    2. Prasad, Kislaya, 2009. "The rationality/computability trade-off in finite games," Journal of Economic Behavior & Organization, Elsevier, vol. 69(1), pages 17-26, January.
    3. Anderlini, Luca & Sabourian, Hamid, 1995. "Cooperation and Effective Computability," Econometrica, Econometric Society, vol. 63(6), pages 1337-1369, November.
    4. Gossner, Olivier & Vieille, Nicolas, 2002. "How to play with a biased coin?," Games and Economic Behavior, Elsevier, vol. 41(2), pages 206-226, November.
    5. Mark Walker & John Wooders, 2001. "Minimax Play at Wimbledon," American Economic Review, American Economic Association, vol. 91(5), pages 1521-1538, December.
    6. Neyman, Abraham & Okada, Daijiro, 1999. "Strategic Entropy and Complexity in Repeated Games," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 191-223, October.
    7. Neyman, Abraham & Okada, Daijiro, 2000. "Repeated Games with Bounded Entropy," Games and Economic Behavior, Elsevier, vol. 30(2), pages 228-247, February.
    8. Ben-Porath Elchanan, 1993. "Repeated Games with Finite Automata," Journal of Economic Theory, Elsevier, vol. 59(1), pages 17-32, February.
    9. Ignacio Palacios-Huerta, 2003. "Professionals Play Minimax," Review of Economic Studies, Oxford University Press, vol. 70(2), pages 395-415.
    10. Lehrer, Ehud, 1988. "Repeated games with stationary bounded recall strategies," Journal of Economic Theory, Elsevier, vol. 46(1), pages 130-144, October.
    11. Aumann, Robert J., 1997. "Rationality and Bounded Rationality," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 2-14, October.
    12. Hu, Tai Wei & Shmaya, Eran, 2013. "Expressible inspections," Theoretical Economics, Econometric Society, vol. 8(2), May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bavly, Gilad & Peretz, Ron, 2015. "How to gamble against all odds," Games and Economic Behavior, Elsevier, vol. 94(C), pages 157-168.

    More about this item

    Keywords

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

    JEL classification:

    • D01 - Microeconomics - - General - - - Microeconomic Behavior: Underlying Principles
    • D80 - Microeconomics - - Information, Knowledge, and Uncertainty - - - General

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:gamebe:v:88:y:2014:i:c:p:1-15. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Dana Niculescu). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.