IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v46y2021i2p452-470.html
   My bibliography  Save this article

Simulation of a Random Variable and its Application to Game Theory

Author

Listed:
  • Mehrdad Valizadeh

    (Department of Electrical Engineering, Sharif University of Technology, 1458889694 Tehran, Iran)

  • Amin Gohari

    (Tehran Institute for Advanced Studies (TeIAS), 1991813741 Tehran, Iran)

Abstract

We provide a new tool for simulation of a random variable (target source) from a randomness source with side information. Considering the total variation distance as the measure of precision, this tool offers an upper bound for the precision of simulation, which is vanishing exponentially in the difference of Rényi entropies of the randomness and target sources. This tool finds application in games in which the players wish to generate their actions (target source) as a function of a randomness source such that they are almost independent of the observations of the opponent (side information). In particular, we study zero-sum repeated games in which the players are restricted to strategies that require only a limited amount of randomness. Let be the max-min value of the n stage game. Previous works have characterized lim n → ∞ v n , that is, the long-run max-min value, but they have not provided any result on the value of v n for a given finite n -stage game. Here, we utilize our new tool to study how v n converges to the long-run max-min value.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormoor:v:46:y:2021:i:2:p:452-470
    DOI: 10.1287/moor.2020.1067
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2020.1067
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2020.1067?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. Olivier Gossner & Tristan Tomala, 2007. "Secret Correlation in Repeated Games with Imperfect Monitoring," PSE-Ecole d'économie de Paris (Postprint) 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. Valizadeh, Mehrdad & Gohari, Amin, 2019. "Playing games with bounded entropy," Games and Economic Behavior, Elsevier, vol. 115(C), pages 363-380.
    Full references (including those not matched with items on IDEAS)

    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. Valizadeh, Mehrdad & Gohari, Amin, 2019. "Playing games with bounded entropy," Games and Economic Behavior, Elsevier, vol. 115(C), pages 363-380.
    2. Le Treust, Maël & Tomala, Tristan, 2019. "Persuasion with limited communication capacity," Journal of Economic Theory, Elsevier, vol. 184(C).
    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. Nora, Vladyslav & Uno, Hiroshi, 2014. "Saddle functions and robust sets of equilibria," Journal of Economic Theory, Elsevier, vol. 150(C), pages 866-877.
    8. 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.
    9. 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.
    10. Hernández, Penélope & Urbano, Amparo, 2008. "Codification schemes and finite automata," Mathematical Social Sciences, Elsevier, vol. 56(3), pages 395-409, November.
    11. 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.
    12. Bavly, Gilad & Neyman, Abraham, 2014. "Online concealed correlation and bounded rationality," Games and Economic Behavior, Elsevier, vol. 88(C), pages 71-89.
    13. 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.
    14. 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.
    15. Olivier Gossner & Rida Laraki & Tristan Tomala, 2004. "Maxmin computation and optimal correlation in repeated games with signals," Working Papers hal-00242940, HAL.
    16. repec:dau:papers:123456789/6885 is not listed on IDEAS
    17. 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.
    18. 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.
    19. 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.
    20. 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.
    21. Hu, Tai-Wei, 2014. "Unpredictability of complex (pure) strategies," Games and Economic Behavior, Elsevier, vol. 88(C), pages 1-15.

    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:inm:ormoor:v:46:y:2021:i:2:p:452-470. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.