IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2104.10528.html
   My bibliography  Save this paper

Random perfect information games

Author

Listed:
  • J'anos Flesch
  • Arkadi Predtetchinski
  • Ville Suomala

Abstract

The paper proposes a natural measure space of zero-sum perfect information games with upper semicontinuous payoffs. Each game is specified by the game tree, and by the assignment of the active player and of the capacity to each node of the tree. The payoff in a game is defined as the infimum of the capacity over the nodes that have been visited during the play. The active player, the number of children, and the capacity are drawn from a given joint distribution independently across the nodes. We characterize the cumulative distribution function of the value $v$ using the fixed points of the so-called value generating function. The characterization leads to a necessary and sufficient condition for the event $v \geq k$ to occur with positive probability. We also study probabilistic properties of the set of Player I's $k$-optimal strategies and the corresponding plays.

Suggested Citation

  • J'anos Flesch & Arkadi Predtetchinski & Ville Suomala, 2021. "Random perfect information games," Papers 2104.10528, arXiv.org.
    • Handle: RePEc:arx:papers:2104.10528
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2104.10528
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. R. Laraki & A. Maitra & W. Sudderth, 2013. "Two-Person Zero-Sum Stochastic Games with Semicontinuous Payoff," Dynamic Games and Applications, Springer, vol. 3(2), pages 162-171, June.
    2. Roger A. Purves & William D. Sudderth, 2011. "Perfect Information Games with Upper Semicontinuous Payoffs," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 468-473, August.
    3. Pei, Ting & Takahashi, Satoru, 2019. "Rationalizable strategies in random games," Games and Economic Behavior, Elsevier, vol. 118(C), pages 110-125.
    4. Ben Amiet & Andrea Collevecchio & Marco Scarsini & Ziwen Zhong, 2021. "Pure Nash Equilibria and Best-Response Dynamics in Random Games," Mathematics of Operations Research, INFORMS, vol. 46(4), pages 1552-1572, November.
    5. János Flesch & Jeroen Kuipers & Ayala Mashiah-Yaakovi & Gijs Schoenmakers & Eilon Solan & Koos Vrieze, 2010. "Perfect-Information Games with Lower-Semicontinuous Payoffs," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 742-755, November.
    6. Harris, Christopher J, 1985. "Existence and Characterization of Perfect Equilibrium in Games of Perfect Information," Econometrica, Econometric Society, vol. 53(3), pages 613-628, May.
    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. János Flesch & Arkadi Predtetchinski, 2016. "Subgame-Perfect ϵ-Equilibria in Perfect Information Games with Common Preferences at the Limit," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1208-1221, November.
    2. Carlos Alós-Ferrer & Klaus Ritzberger, 2017. "Characterizing existence of equilibrium for large extensive form games: a necessity result," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 63(2), pages 407-430, February.
    3. Alós-Ferrer, Carlos & Ritzberger, Klaus, 2016. "Equilibrium existence for large perfect information games," Journal of Mathematical Economics, Elsevier, vol. 62(C), pages 5-18.
    4. J. Kuipers & J. Flesch & G. Schoenmakers & K. Vrieze, 2016. "Subgame-perfection in recursive perfect information games, where each player controls one state," International Journal of Game Theory, Springer;Game Theory Society, vol. 45(1), pages 205-237, March.
    5. János Flesch & Arkadi Predtetchinski, 2020. "Parameterized games of perfect information," Annals of Operations Research, Springer, vol. 287(2), pages 683-699, April.
    6. Flesch, Janos & Herings, P. Jean-Jacques & Maes, Jasmine & Predtetchinski, Arkadi, 2019. "Individual upper semicontinuity and subgame perfect ϵ-equilibria in games with almost perfect information," Research Memorandum 002, Maastricht University, Graduate School of Business and Economics (GSBE).
    7. Pangallo, Marco & Heinrich, Torsten & Jang, Yoojin & Scott, Alex & Tarbush, Bassel & Wiese, Samuel & Mungo, Luca, 2021. "Best-Response Dynamics, Playing Sequences, And Convergence To Equilibrium In Random Games," INET Oxford Working Papers 2021-23, Institute for New Economic Thinking at the Oxford Martin School, University of Oxford.
    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. Duvocelle, Benoit & Flesch, János & Staudigl, Mathias & Vermeulen, Dries, 2022. "A competitive search game with a moving target," European Journal of Operational Research, Elsevier, vol. 303(2), pages 945-957.
    10. János Flesch & P. Jean-Jacques Herings & Jasmine Maes & Arkadi Predtetchinski, 2022. "Individual upper semicontinuity and subgame perfect $$\epsilon $$ ϵ -equilibria in games with almost perfect information," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 73(2), pages 695-719, April.
    11. János Flesch & Arkadi Predtetchinski, 2017. "A Characterization of Subgame-Perfect Equilibrium Plays in Borel Games of Perfect Information," Mathematics of Operations Research, INFORMS, vol. 42(4), pages 1162-1179, November.
    12. János Flesch & Arkadi Predtetchinski, 2016. "Subgame-perfect $$\epsilon $$ ϵ -equilibria in perfect information games with sigma-discrete discontinuities," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 61(3), pages 479-495, March.
    13. He, Wei & Sun, Yeneng, 2020. "Dynamic games with (almost) perfect information," Theoretical Economics, Econometric Society, vol. 15(2), May.
    14. János Flesch & Jeroen Kuipers & Ayala Mashiah-Yaakovi & Gijs Schoenmakers & Eran Shmaya & Eilon Solan & Koos Vrieze, 2014. "Non-existence of subgame-perfect $$\varepsilon $$ ε -equilibrium in perfect information games with infinite horizon," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 945-951, November.
    15. Cingiz, Kutay & Flesch, János & Herings, P. Jean-Jacques & Predtetchinski, Arkadi, 2016. "Doing it now, later, or never," Games and Economic Behavior, Elsevier, vol. 97(C), pages 174-185.
    16. Jeroen Kuipers & János Flesch & Gijs Schoenmakers & Koos Vrieze, 2021. "Subgame perfection in recursive perfect information games," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(2), pages 603-662, March.
    17. Elliot Lipnowski & Laurent Mathevet & Dong Wei, 2020. "Attention Management," American Economic Review: Insights, American Economic Association, vol. 2(1), pages 17-32, March.
    18. Germano, Fabrizio, 2003. "Bertrand-edgeworth equilibria in finite exchange economies," Journal of Mathematical Economics, Elsevier, vol. 39(5-6), pages 677-692, July.
    19. repec:cep:stitep:/2012/563 is not listed on IDEAS
    20. Streufert, Peter, 2018. "The Category of Node-and-Choice Forms, with Subcategories for Choice-Sequence Forms and Choice-Set Forms," MPRA Paper 90490, University Library of Munich, Germany.
    21. János Flesch & P. Jean-Jacques Herings & Jasmine Maes & Arkadi Predtetchinski, 2021. "Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels," Dynamic Games and Applications, Springer, vol. 11(4), pages 704-737, December.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:arx:papers:2104.10528. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.