IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v166y2016icp517-535.html
   My bibliography  Save this article

Random extensive form games

Author

Listed:
  • Arieli, Itai
  • Babichenko, Yakov

Abstract

We consider two-player random extensive form games where the payoffs at the leaves are independently drawn at random from a given feasible set C. We study the asymptotic distribution of the subgame perfect equilibrium outcome for binary-trees with increasing depth in various random (or deterministic) assignments of players to nodes. We characterize the assignments under which the asymptotic distribution concentrates around a point. Our analysis provides a novel way with a solid strategic justification to implement a Pareto efficient outcome for two-player implementation problems.

Suggested Citation

  • Arieli, Itai & Babichenko, Yakov, 2016. "Random extensive form games," Journal of Economic Theory, Elsevier, vol. 166(C), pages 517-535.
    • Handle: RePEc:eee:jetheo:v:166:y:2016:i:c:p:517-535
    DOI: 10.1016/j.jet.2016.09.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022053116300849
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2016.09.010?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. Rinott, Yosef & Scarsini, Marco, 2000. "On the Number of Pure Strategy Nash Equilibria in Random Games," Games and Economic Behavior, Elsevier, vol. 33(2), pages 274-293, November.
    2. Ken Binmore & Ariel Rubinstein & Asher Wolinsky, 1986. "The Nash Bargaining Solution in Economic Modelling," RAND Journal of Economics, The RAND Corporation, vol. 17(2), pages 176-188, Summer.
    3. McLennan, Andrew, 1997. "The Maximal Generic Number of Pure Nash Equilibria," Journal of Economic Theory, Elsevier, vol. 72(2), pages 408-410, February.
    4. Miyagawa, Eiichi, 2002. "Subgame-perfect implementation of bargaining solutions," Games and Economic Behavior, Elsevier, vol. 41(2), pages 292-308, November.
    5. Moulin, H., 1984. "Implementing the Kalai-Smorodinsky bargaining solution," Journal of Economic Theory, Elsevier, vol. 33(1), pages 32-45, June.
    6. Abreu, Dilip & Sen, Arunava, 1990. "Subgame perfect implementation: A necessary and almost sufficient condition," Journal of Economic Theory, Elsevier, vol. 50(2), pages 285-299, April.
    7. Powers, Imelda Yeung, 1990. "Limiting Distributions of the Number of Pure Strategy Nash Equilibria in N-Person Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(3), pages 277-286.
    8. Nejat Anbarci, 1993. "Noncooperative Foundations of the Area Monotonic Solution," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 108(1), pages 245-258.
    9. Pradeep Dubey, 1986. "Inefficiency of Nash Equilibria," Mathematics of Operations Research, INFORMS, vol. 11(1), pages 1-8, February.
    10. Vartiainen, Hannu, 2007. "Subgame perfect implementation: A full characterization," Journal of Economic Theory, Elsevier, vol. 133(1), pages 111-126, March.
    11. Moore, John & Repullo, Rafael, 1988. "Subgame Perfect Implementation," Econometrica, Econometric Society, vol. 56(5), pages 1191-1220, September.
    12. Howard, J. V., 1992. "A social choice rule and its implementation in perfect equilibrium," Journal of Economic Theory, Elsevier, vol. 56(1), pages 142-159, February.
    13. McLennan, Andrew & Berg, Johannes, 2005. "Asymptotic expected number of Nash equilibria of two-player normal form games," Games and Economic Behavior, Elsevier, vol. 51(2), pages 264-295, May.
    14. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, January.
    15. Takahashi, Satoru, 2008. "The number of pure Nash equilibria in a random game with nondecreasing best responses," Games and Economic Behavior, Elsevier, vol. 63(1), pages 328-340, 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. Torsten Heinrich & Yoojin Jang & Luca Mungo & Marco Pangallo & Alex Scott & Bassel Tarbush & Samuel Wiese, 2023. "Best-response dynamics, playing sequences, and convergence to equilibrium in random games," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 703-735, September.
    2. Anton M Unakafov & Thomas Schultze & Alexander Gail & Sebastian Moeller & Igor Kagan & Stephan Eule & Fred Wolf, 2020. "Emergence and suppression of cooperation by action visibility in transparent games," PLOS Computational Biology, Public Library of Science, vol. 16(1), pages 1-32, January.
    3. 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.

    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. Michele Lombardi & Naoki Yoshihara, 2020. "Partially-honest Nash implementation: a full characterization," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 871-904, October.
    2. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Nov 2023.
    3. Yakov Babichenko & Leonard J. Schulman, 2015. "Pareto Efficient Nash Implementation Via Approval Voting," Papers 1502.05238, arXiv.org, revised Mar 2017.
    4. Torsten Heinrich & Yoojin Jang & Luca Mungo & Marco Pangallo & Alex Scott & Bassel Tarbush & Samuel Wiese, 2021. "Best-response dynamics, playing sequences, and convergence to equilibrium in random games," Papers 2101.04222, arXiv.org, revised Nov 2022.
    5. 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.
    6. John Conley & Simon Wilkie, 1994. "Implementing the nash extension bargaining solution for non-convex problems," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 205-216, December.
    7. Torsten Heinrich & Yoojin Jang & Luca Mungo & Marco Pangallo & Alex Scott & Bassel Tarbush & Samuel Wiese, 2023. "Best-response dynamics, playing sequences, and convergence to equilibrium in random games," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 703-735, September.
    8. Pei, Ting & Takahashi, Satoru, 2019. "Rationalizable strategies in random games," Games and Economic Behavior, Elsevier, vol. 118(C), pages 110-125.
    9. Johannes Spinnewijn & Frans Spinnewyn, 2015. "Revising claims and resisting ultimatums in bargaining problems," Review of Economic Design, Springer;Society for Economic Design, vol. 19(2), pages 91-116, June.
    10. Jackson, Matthew & Moulin, Hervé, 1992. "Implementing a public project and distributing its cost," Journal of Economic Theory, Elsevier, vol. 57(1), pages 125-140.
    11. Bergin, James & Duggan, John, 1999. "An Implementation-Theoretic Approach to Non-cooperative Foundations," Journal of Economic Theory, Elsevier, vol. 86(1), pages 50-76, May.
    12. Takahashi, Satoru, 2008. "The number of pure Nash equilibria in a random game with nondecreasing best responses," Games and Economic Behavior, Elsevier, vol. 63(1), pages 328-340, May.
    13. Roberto Serrano, 2005. "Fifty years of the Nash program, 1953-2003," Investigaciones Economicas, Fundación SEPI, vol. 29(2), pages 219-258, May.
    14. Roberto Serrano, 2004. "Fifty Years of the Nash Program, 1953-2003," Working Papers 2004-20, Brown University, Department of Economics.
    15. Müller, Christoph, 2020. "Robust implementation in weakly perfect Bayesian strategies," Journal of Economic Theory, Elsevier, vol. 189(C).
    16. Maskin, Eric & Sjostrom, Tomas, 2002. "Implementation theory," Handbook of Social Choice and Welfare,in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 5, pages 237-288 Elsevier.
    17. l'Haridon, Olivier & Malherbet, Franck & Pérez-Duarte, Sébastien, 2013. "Does bargaining matter in the small firms matching model?," Labour Economics, Elsevier, vol. 21(C), pages 42-58.
    18. 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.
    19. Trockel, Walter, 2017. "Can and should the Nash Program be looked at as a part of mechanism theory," Center for Mathematical Economics Working Papers 322, Center for Mathematical Economics, Bielefeld University.
    20. Yusuke Samejima, 2005. "A Note on Implementation of Bargaining Solutions," Theory and Decision, Springer, vol. 59(3), pages 175-191, November.

    More about this item

    Keywords

    Random games; Extensive form games; Subgame-perfect equilibrium; Pareto efficiency; Implementation;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory

    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:jetheo:v:166:y:2016:i:c:p:517-535. 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/622869 .

    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.