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

Playing games with bounded entropy

Author

Listed:
  • Valizadeh, Mehrdad
  • Gohari, Amin

Abstract

We study zero-sum repeated games in which the maximizer (player or team) is restricted to strategies with limited randomness. Particularly, we analyze the maxmin payoff of the maximizer in two models: the first model forces the maximizer to randomize her actions just by conditioning them to the outcomes of an observed random source. In the second model, the maximizer is a team of players who are free to privately randomize their corresponding actions but do not have access to any explicit source of shared randomness needed for coordination. While prior works adopted the method of types to address these problems, we use the idea of random hashing being the core of randomness extractors. In addition, we use a tool for simulation of a source from another source. Utilizing these tools, we simplify and generalize the earlier results. We also study the computational aspects of the solution for the first model.

Suggested Citation

  • Valizadeh, Mehrdad & Gohari, Amin, 2019. "Playing games with bounded entropy," Games and Economic Behavior, Elsevier, vol. 115(C), pages 363-380.
    • Handle: RePEc:eee:gamebe:v:115:y:2019:i:c:p:363-380
    DOI: 10.1016/j.geb.2019.03.013
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S089982561930048X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2019.03.013?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Olivier Gossner & Rida Laraki & Tristan Tomala, 2004. "Informationally optimal correlation," Working Papers hal-00587228, HAL.
    2. Olivier Gossner & Tristan Tomala, 2007. "Secret Correlation in Repeated Games with Imperfect Monitoring," Post-Print hal-00487954, HAL.
    3. Gossner, Olivier & Vieille, Nicolas, 2002. "How to play with a biased coin?," Games and Economic Behavior, Elsevier, vol. 41(2), pages 206-226, November.
    4. Neyman, Abraham & Okada, Daijiro, 2000. "Repeated Games with Bounded Entropy," Games and Economic Behavior, Elsevier, vol. 30(2), pages 228-247, February.
    5. Ilan Adler, 2013. "The equivalence of linear programs and zero-sum games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(1), pages 165-177, February.
    6. Olivier Gossner & Tristan Tomala, 2007. "Secret Correlation in Repeated Games with Imperfect Monitoring," Mathematics of Operations Research, INFORMS, vol. 32(2), pages 413-424, May.
    7. Olivier Gossner & Tristan Tomala, 2007. "Secret Correlation in Repeated Games with Imperfect Monitoring," PSE-Ecole d'économie de Paris (Postprint) hal-00487954, HAL.
    8. Olivier Gossner & Rida Laraki & Tristan Tomala, 2009. "Informationally optimal correlation," PSE-Ecole d'économie de Paris (Postprint) hal-00485282, HAL.
    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. Mehrdad Valizadeh & Amin Gohari, 2021. "Simulation of a Random Variable and its Application to Game Theory," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 452-470, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Le Treust, Maël & Tomala, Tristan, 2019. "Persuasion with limited communication capacity," Journal of Economic Theory, Elsevier, vol. 184(C).
    2. Mehrdad Valizadeh & Amin Gohari, 2021. "Simulation of a Random Variable and its Application to Game Theory," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 452-470, May.
    3. Ron Peretz, 2011. "Correlation through Bounded Recall Strategies," Discussion Paper Series dp579, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    4. Bavly, Gilad & Peretz, Ron, 2019. "Limits of correlation in repeated games with bounded memory," Games and Economic Behavior, Elsevier, vol. 115(C), pages 131-145.
    5. Ron Peretz, 2013. "Correlation through bounded recall strategies," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(4), pages 867-890, November.
    6. Olivier Gossner & Penélope Hernández & Ron Peretz, 2016. "The complexity of interacting automata," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 461-496, March.
    7. Gossner, Olivier & Hörner, Johannes, 2010. "When is the lowest equilibrium payoff in a repeated game equal to the minmax payoff?," Journal of Economic Theory, Elsevier, vol. 145(1), pages 63-84, January.
    8. Kutay Cingiz & János Flesch & P. Jean-Jacques Herings & Arkadi Predtetchinski, 2020. "Perfect information games where each player acts only once," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 69(4), pages 965-985, June.
    9. Jiaying Deng & Hossein Ghasemkhani & Yong Tan & Arvind K Tripathi, 2023. "Actions speak louder than words: Imputing users’ reputation from transaction history," Production and Operations Management, Production and Operations Management Society, vol. 32(4), pages 1096-1111, April.
    10. Heng Liu, 2017. "Correlation and unmediated cheap talk in repeated games with imperfect monitoring," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 1037-1069, November.
    11. Jérôme Renault & Tristan Tomala, 2011. "General Properties of Long-Run Supergames," Dynamic Games and Applications, Springer, vol. 1(2), pages 319-350, June.
    12. Bavly, Gilad & Neyman, Abraham, 2014. "Online concealed correlation and bounded rationality," Games and Economic Behavior, Elsevier, vol. 88(C), pages 71-89.
    13. Deb, Joyee & González-Díaz, Julio & Renault, Jérôme, 2016. "Uniform folk theorems in repeated anonymous random matching games," Games and Economic Behavior, Elsevier, vol. 100(C), pages 1-23.
    14. Nora, Vladyslav & Uno, Hiroshi, 2014. "Saddle functions and robust sets of equilibria," Journal of Economic Theory, Elsevier, vol. 150(C), pages 866-877.
    15. Neyman, Abraham & Okada, Daijiro, 2009. "Growth of strategy sets, entropy, and nonstationary bounded recall," Games and Economic Behavior, Elsevier, vol. 66(1), pages 404-425, May.
    16. Hernández, Penélope & Urbano, Amparo, 2008. "Codification schemes and finite automata," Mathematical Social Sciences, Elsevier, vol. 56(3), pages 395-409, November.
    17. Marco Battaglini & Stephen Coate, 2008. "A Dynamic Theory of Public Spending, Taxation, and Debt," American Economic Review, American Economic Association, vol. 98(1), pages 201-236, March.
    18. Hu, Tai-Wei, 2014. "Unpredictability of complex (pure) strategies," Games and Economic Behavior, Elsevier, vol. 88(C), pages 1-15.
    19. Olivier Gossner & Rida Laraki & Tristan Tomala, 2004. "Maxmin computation and optimal correlation in repeated games with signals," Working Papers hal-00242940, HAL.
    20. repec:dau:papers:123456789/6885 is not listed on IDEAS
    21. Olivier Gossner & Jöhannes Horner, 2006. "When is the individually rational payoff in a repeated game equal to the minmax payoff?," Discussion Papers 1440, Northwestern University, Center for Mathematical Studies in Economics and Management Science.

    More about this item

    Keywords

    Repeated games; Bounded entropy; Randomness extraction; Source simulation; Entropy minimization; Information theory;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D83 - Microeconomics - - Information, Knowledge, and Uncertainty - - - Search; Learning; Information and Knowledge; Communication; Belief; Unawareness

    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:115:y:2019:i:c:p:363-380. See general information about how to correct material in RePEc.

    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 bibliographic 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.

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

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

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.