IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2005.09836.html

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. Fernando Bernstein & Awi Federgruen, 2005. "Decentralized Supply Chains with Competing Retailers Under Demand Uncertainty," Management Science, INFORMS, vol. 51(1), pages 18-29, January.
    2. Echenique, Federico, 2007. "Finding all equilibria in games of strategic complements," Journal of Economic Theory, Elsevier, vol. 135(1), pages 514-532, July.
    3. Vives, Xavier, 1990. "Nash equilibrium with strategic complementarities," Journal of Mathematical Economics, Elsevier, vol. 19(3), pages 305-321.
    4. 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.
    5. Milgrom, Paul & Roberts, John, 1990. "Rationalizability, Learning, and Equilibrium in Games with Strategic Complementarities," Econometrica, Econometric Society, vol. 58(6), pages 1255-1277, November.
    6. 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.
    7. Milgrom, Paul & Shannon, Chris, 1994. "Monotone Comparative Statics," Econometrica, Econometric Society, vol. 62(1), pages 157-180, January.
    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. Echenique, Federico & Goel, Sumit & Lee, SangMok, 2024. "Stable allocations in discrete exchange economies," Journal of Economic Theory, Elsevier, vol. 222(C).

    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. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Rabah Amir & Adriana Gama, 2025. "On Cournot's theory of oligopoly with perfect complements," Serie documentos de trabajo del Centro de Estudios Económicos 2025-04, El Colegio de México, Centro de Estudios Económicos.
    13. 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.
    14. repec:kan:wpaper:201412 is not listed on IDEAS
    15. Yang, Jian & Qi, Xiangtong, 2013. "The nonatomic supermodular game," Games and Economic Behavior, Elsevier, vol. 82(C), pages 609-620.
    16. 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.
    17. Rabah Amir & Filomena Garcia & Malgorzata Knauff, 2006. "Endogenous Heterogeneity in Strategic Models: Symmetry-breaking via Strategic Substitutes and Nonconcavities," Working Papers Department of Economics 2006/29, ISEG - Lisbon School of Economics and Management, Department of Economics, Universidade de Lisboa.
    18. Federico Echenique, 2002. "Comparative Statics by Adaptive Dynamics and the Correspondence Principle," Econometrica, Econometric Society, vol. 70(2), pages 833-844, March.
    19. Magnus Hoffmann & Grégoire Rota‐Graziosi, 2020. "Endogenous timing in the presence of non‐monotonicities," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 53(1), pages 359-402, February.
    20. Ceparano, Maria Carmela & Quartieri, Federico, 2017. "Nash equilibrium uniqueness in nice games with isotone best replies," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 154-165.
    21. Kukushkin, Nikolai S., 2013. "Approximate Nash equilibrium under the single crossing conditions," MPRA Paper 44320, University Library of Munich, Germany.

    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.