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

Computations and Complexities of Tarski's Fixed Points and Supermodular Games

Author

Listed:
  • Chuangyin Dang
  • Qi Qi
  • Yinyu Ye

Abstract

We consider two models of computation for Tarski's order preserving function f related to fixed points in a complete lattice: the oracle function model and the polynomial function model. In both models, we find the first polynomial time algorithm for finding a Tarski's fixed point. In addition, we provide a matching oracle bound for determining the uniqueness in the oracle function model and prove it is Co-NP hard in the polynomial function model. The existence of the pure Nash equilibrium in supermodular games is proved by Tarski's fixed point theorem. Exploring the difference between supermodular games and Tarski's fixed point, we also develop the computational results for finding one pure Nash equilibrium and determining the uniqueness of the equilibrium in supermodular games.

Suggested Citation

  • Chuangyin Dang & Qi Qi & Yinyu Ye, 2020. "Computations and Complexities of Tarski's Fixed Points and Supermodular Games," Papers 2005.09836, arXiv.org.
    • Handle: RePEc:arx:papers:2005.09836
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Milgrom, Paul & Shannon, Chris, 1994. "Monotone Comparative Statics," Econometrica, Econometric Society, vol. 62(1), pages 157-180, January.
    2. Fernando Bernstein & Awi Federgruen, 2005. "Decentralized Supply Chains with Competing Retailers Under Demand Uncertainty," Management Science, INFORMS, vol. 51(1), pages 18-29, January.
    3. Echenique, Federico, 2007. "Finding all equilibria in games of strategic complements," Journal of Economic Theory, Elsevier, vol. 135(1), pages 514-532, July.
    4. Vives, Xavier, 1990. "Nash equilibrium with strategic complementarities," Journal of Mathematical Economics, Elsevier, vol. 19(3), pages 305-321.
    5. Fernando Bernstein & Awi Federgruen, 2004. "A General Equilibrium Model for Industries with Price and Service Competition," Operations Research, INFORMS, vol. 52(6), pages 868-886, December.
    6. Milgrom, Paul & Roberts, John, 1990. "Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities," Econometrica, Econometric Society, vol. 58(6), pages 1255-1277, November.
    7. Gérard P. Cachon, 2001. "Stock Wars: Inventory Competition in a Two-Echelon Supply Chain with Multiple Retailers," Operations Research, INFORMS, vol. 49(5), pages 658-674, October.
    8. Gérard P. Cachon & Martin A. Lariviere, 1999. "Capacity Choice and Allocation: Strategic Behavior and Supply Chain Performance," Management Science, INFORMS, vol. 45(8), pages 1091-1108, August.
    9. Steven A. Lippman & Kevin F. McCardle, 1997. "The Competitive Newsboy," Operations Research, INFORMS, vol. 45(1), pages 54-65, February.
    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. Federico Echenique & Sumit Goel & SangMok Lee, 2022. "Stable allocations in discrete exchange economies," Papers 2202.04706, arXiv.org, revised Feb 2024.

    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. Echenique, Federico, 2007. "Finding all equilibria in games of strategic complements," Journal of Economic Theory, Elsevier, vol. 135(1), pages 514-532, July.
    2. Sobel, Joel, 2019. "Iterated weak dominance and interval-dominance supermodular games," Theoretical Economics, Econometric Society, vol. 14(1), January.
    3. Güler, Kemal & Körpeoğlu, Evren & Şen, Alper, 2018. "Newsvendor competition under asymmetric cost information," European Journal of Operational Research, Elsevier, vol. 271(2), pages 561-576.
    4. Gérard P. Cachon, 2001. "Stock Wars: Inventory Competition in a Two-Echelon Supply Chain with Multiple Retailers," Operations Research, INFORMS, vol. 49(5), pages 658-674, October.
    5. Mahajan, Aseem & Pongou, Roland & Tondji, Jean-Baptiste, 2023. "Supermajority politics: Equilibrium range, policy diversity, utilitarian welfare, and political compromise," European Journal of Operational Research, Elsevier, vol. 307(2), pages 963-974.
    6. Echenique, Federico, 2004. "A characterization of strategic complementarities," Games and Economic Behavior, Elsevier, vol. 46(2), pages 325-347, February.
    7. Camacho, Carmen & Kamihigashi, Takashi & Sağlam, Çağrı, 2018. "Robust comparative statics for non-monotone shocks in large aggregative games," Journal of Economic Theory, Elsevier, vol. 174(C), pages 288-299.
    8. Amir, Rabah & Bloch, Francis, 2009. "Comparative statics in a simple class of strategic market games," Games and Economic Behavior, Elsevier, vol. 65(1), pages 7-24, January.
    9. Rabah Amir & Giuseppe Feo, 2014. "Endogenous timing in a mixed duopoly," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(3), pages 629-658, August.
    10. Uttiya Paul & Tarun Sabarwal, 2023. "Directional monotone comparative statics in function spaces," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 11(1), pages 153-169, April.
    11. Cumbul, Eray & Virág, Gábor, 2018. "Multilateral limit pricing in price-setting games," Games and Economic Behavior, Elsevier, vol. 111(C), pages 250-273.
    12. Allouch, Nizar & Jalloul, Maya & Duncan, Alfred, 2023. "Strategic default in financial networks," Games and Economic Behavior, Elsevier, vol. 142(C), pages 941-954.
    13. Nikolai Kukushkin, 2015. "The single crossing conditions for incomplete preferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(1), pages 225-251, February.
    14. Emin Karagözoğlu & Kerim Keskin & Çağrı Sağlam, 2024. "Submodularity and supermodularity in contest games," International Journal of Economic Theory, The International Society for Economic Theory, vol. 20(2), pages 182-198, June.
    15. Prokopovych, Pavlo & Yannelis, Nicholas C., 2017. "On strategic complementarities in discontinuous games with totally ordered strategies," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 147-153.
    16. Dubey, Pradeep & Haimanko, Ori & Zapechelnyuk, Andriy, 2006. "Strategic complements and substitutes, and potential games," Games and Economic Behavior, Elsevier, vol. 54(1), pages 77-94, January.
    17. Roy, Sunanda & Sabarwal, Tarun, 2012. "Characterizing stability properties in games with strategic substitutes," Games and Economic Behavior, Elsevier, vol. 75(1), pages 337-353.
    18. repec:kan:wpaper:201412 is not listed on IDEAS
    19. Yang, Jian & Qi, Xiangtong, 2013. "The nonatomic supermodular game," Games and Economic Behavior, Elsevier, vol. 82(C), pages 609-620.
    20. Philip J. Reny, 2011. "On the Existence of Monotone Pure‐Strategy Equilibria in Bayesian Games," Econometrica, Econometric Society, vol. 79(2), pages 499-553, March.
    21. Belhaj, Mohamed & Bramoullé, Yann & Deroïan, Frédéric, 2014. "Network games under strategic complementarities," Games and Economic Behavior, Elsevier, vol. 88(C), pages 310-319.

    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:2005.09836. 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.