[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/the/publsh/942.html
   My bibliography  Save this article

The order independence of iterated dominance in extensive games

Author

Listed:
  • ,

    (Institute for Advanced Study, Princeton and Department of Computer Science, Stony Brook University)

  • ,

    (Department of Electrical Engineering and Computer Science, MIT)

Abstract
Shimoji and Watson (1998) prove that a strategy of an extensive game is rationalizable in the sense of Pearce if and only if it survives the maximal elimination of conditionally dominated strategies. Briefly, this process iteratively eliminates conditionally dominated strategies according to a specific order, which is also the start of an order of elimination of weakly dominated strategies. Since the final set of possible payoff profiles, or terminal nodes, surviving iterated elimination of weakly dominated strategies may be order-dependent, one may suspect that the same holds for conditional dominance. We prove that, although the sets of strategy profiles surviving two arbitrary elimination orders of conditional dominance may be very different from each other, they are equivalent in the following sense: for each player $i$ and each pair of elimination orders, there exists a function $\phi_i$ mapping each strategy of $i$ surviving the first order to a strategy of $i$ surviving the second order, such that, for every strategy profile $s$ surviving the first order, the profile $(\phi_i(s_i))_i$ induces the same {\em terminal node} as $s$ does. To prove our results we put forward a new notion of dominance and an elementary characterization of extensive-form rationalizability (EFR) that may be of independent interest. We also establish connections between EFR and other existing iterated dominance procedures, using our notion of dominance and our characterization of EFR.

Suggested Citation

  • , & ,, 2013. "The order independence of iterated dominance in extensive games," Theoretical Economics, Econometric Society, vol. 8(1), January.
    • Handle: RePEc:the:publsh:942
    as

    Download full text from publisher

    File URL: http://econtheory.org/ojs/index.php/te/article/viewFile/20130125/8134/251
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. , & ,, 2012. "Forward induction reasoning revisited," Theoretical Economics, Econometric Society, vol. 7(1), January.
    2. Ehud Kalai & Eitan Zemel, 1988. "On The Order of Eliminating Dominated Strategies," Discussion Papers 789, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
    3. Martin Dufwenberg & Mark Stegeman, 2002. "Existence and Uniqueness of Maximal Reductions Under Iterated Strict Dominance," Econometrica, Econometric Society, vol. 70(5), pages 2007-2023, September.
    4. Martin J. Osborne & Ariel Rubinstein, 1994. "A Course in Game Theory," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262650401, April.
    5. Shimoji, Makoto & Watson, Joel, 1998. "Conditional Dominance, Rationalizability, and Game Forms," Journal of Economic Theory, Elsevier, vol. 83(2), pages 161-195, December.
    6. Reny, Philip J, 1992. "Backward Induction, Normal Form Perfection and Explicable Equilibria," Econometrica, Econometric Society, vol. 60(3), pages 627-649, May.
    7. Apt Krzysztof R., 2004. "Uniform Proofs of Order Independence for Various Strategy Elimination Procedures," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 4(1), pages 1-48, September.
    8. Shimoji, Makoto, 2004. "On the equivalence of weak dominance and sequential best response," Games and Economic Behavior, Elsevier, vol. 48(2), pages 385-402, August.
    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. Heifetz Aviad & Meier Martin & Schipper Burkhard C., 2021. "Prudent Rationalizability in Generalized Extensive-form Games with Unawareness," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 21(2), pages 525-556, June.
    2. Manili, Julien, 2024. "Order independence for rationalizability," Games and Economic Behavior, Elsevier, vol. 143(C), pages 152-160.
    3. Martin Meier & Burkhard C. Schipper, 2022. "Conditional dominance in games with unawareness," Working Papers 351, University of California, Davis, Department of Economics.
    4. Bonanno, Giacomo, 2014. "A doxastic behavioral characterization of generalized backward induction," Games and Economic Behavior, Elsevier, vol. 88(C), pages 221-241.
    5. Giacomo Bonanno, 2013. "An epistemic characterization of generalized backward induction," Working Papers 60, University of California, Davis, Department of Economics.
    6. Perea, Andrés, 2018. "Why forward induction leads to the backward induction outcome: A new proof for Battigalli's theorem," Games and Economic Behavior, Elsevier, vol. 110(C), pages 120-138.
    7. Arieli, Itai & Aumann, Robert J., 2015. "The logic of backward induction," Journal of Economic Theory, Elsevier, vol. 159(PA), pages 443-464.
    8. Catonini, Emiliano, 2020. "On non-monotonic strategic reasoning," Games and Economic Behavior, Elsevier, vol. 120(C), pages 209-224.
    9. Rich, Patricia, 2015. "Rethinking common belief, revision, and backward induction," Mathematical Social Sciences, Elsevier, vol. 75(C), pages 102-114.
    10. Xiao Luo & Xuewen Qian & Chen Qu, 2020. "Iterated elimination procedures," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 437-465, September.
    11. Evan Piermont & Peio Zuazo-Garin, 2021. "Heterogeneously Perceived Incentives in Dynamic Environments: Rationalization, Robustness and Unique Selections," Papers 2105.06772, arXiv.org.
    12. Battigalli, P. & Catonini, E. & Manili, J., 2023. "Belief change, rationality, and strategic reasoning in sequential games," Games and Economic Behavior, Elsevier, vol. 142(C), pages 527-551.
    13. Perea, Andrés, 2014. "Belief in the opponentsʼ future rationality," Games and Economic Behavior, Elsevier, vol. 83(C), pages 231-254.
    14. Jing Chen & Silvio Micali, 2016. "Leveraging Possibilistic Beliefs in Unrestricted Combinatorial Auctions," Games, MDPI, vol. 7(4), pages 1-19, October.
    15. Giacomo Bonanno, 2013. "An epistemic characterization of generalized backward induction," Working Papers 132, University of California, Davis, Department of Economics.
    16. Catonini, Emiliano, 2019. "Rationalizability and epistemic priority orderings," Games and Economic Behavior, Elsevier, vol. 114(C), pages 101-117.
    17. Müller, Christoph, 2016. "Robust virtual implementation under common strong belief in rationality," Journal of Economic Theory, Elsevier, vol. 162(C), pages 407-450.
    18. Aviad Heifetz & Andrés Perea, 2015. "On the outcome equivalence of backward induction and extensive form rationalizability," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(1), pages 37-59, February.
    19. Rubén Becerril-Borja & Andrés Perea, 2020. "Common belief in future and restricted past rationality," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(3), pages 711-747, September.

    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. Battigalli, P. & Catonini, E. & Manili, J., 2023. "Belief change, rationality, and strategic reasoning in sequential games," Games and Economic Behavior, Elsevier, vol. 142(C), pages 527-551.
    2. Manili, Julien, 2024. "Order independence for rationalizability," Games and Economic Behavior, Elsevier, vol. 143(C), pages 152-160.
    3. Dekel, Eddie & Siniscalchi, Marciano, 2015. "Epistemic Game Theory," Handbook of Game Theory with Economic Applications,, Elsevier.
    4. Battigalli, Pierpaolo & De Vito, Nicodemo, 2021. "Beliefs, plans, and perceived intentions in dynamic games," Journal of Economic Theory, Elsevier, vol. 195(C).
    5. Zuazo-Garin, Peio, 2017. "Uncertain information structures and backward induction," Journal of Mathematical Economics, Elsevier, vol. 71(C), pages 135-151.
    6. Xiao Luo & Xuewen Qian & Chen Qu, 2020. "Iterated elimination procedures," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 437-465, September.
    7. Burkhard C. Schipper & Hang Zhou, 2022. "Level-k Thinking in the Extensive Form," Working Papers 352, University of California, Davis, Department of Economics.
    8. Shimoji, Makoto, 2004. "On the equivalence of weak dominance and sequential best response," Games and Economic Behavior, Elsevier, vol. 48(2), pages 385-402, August.
    9. Heifetz, Aviad & Meier, Martin & Schipper, Burkhard C, 2011. "Prudent rationalizability in generalized extensive-form games," MPRA Paper 30220, University Library of Munich, Germany.
    10. Catonini, Emiliano, 2020. "On non-monotonic strategic reasoning," Games and Economic Behavior, Elsevier, vol. 120(C), pages 209-224.
    11. Luo, Xiao & Yang, Chih-Chun, 2009. "Bayesian coalitional rationalizability," Journal of Economic Theory, Elsevier, vol. 144(1), pages 248-263, January.
    12. Perea, Andrés, 2017. "Forward induction reasoning and correct beliefs," Journal of Economic Theory, Elsevier, vol. 169(C), pages 489-516.
    13. Michael Trost, 2012. "An Epistemic Rationale for Order-Independence," Jena Economics Research Papers 2012-010, Friedrich-Schiller-University Jena.
    14. Heifetz, Aviad & Meier, Martin & Schipper, Burkhard C., 2013. "Dynamic unawareness and rationalizable behavior," Games and Economic Behavior, Elsevier, vol. 81(C), pages 50-68.
    15. Hsieh, Yue-Da & Qian, Xuewen & Qu, Chen, 2023. "Iterated bounded dominance," Economics Letters, Elsevier, vol. 232(C).
    16. Catonini, Emiliano, 2019. "Rationalizability and epistemic priority orderings," Games and Economic Behavior, Elsevier, vol. 114(C), pages 101-117.
    17. Müller, Christoph, 2016. "Robust virtual implementation under common strong belief in rationality," Journal of Economic Theory, Elsevier, vol. 162(C), pages 407-450.
    18. Makoto Shimoji, 2016. "Rationalizable Persuasion," Discussion Papers 16/08, Department of Economics, University of York.
    19. Chen, Yi-Chun & Long, Ngo Van & Luo, Xiao, 2007. "Iterated strict dominance in general games," Games and Economic Behavior, Elsevier, vol. 61(2), pages 299-315, November.
    20. Carlos Pimienta & Jianfei Shen, 2014. "On the equivalence between (quasi-)perfect and sequential equilibria," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(2), pages 395-402, May.

    More about this item

    Keywords

    Extensive-form rationalizability; dominance; iterative elimination; equivalence;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games

    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:the:publsh:942. 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: Martin J. Osborne (email available below). General contact details of provider: http://econtheory.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.