Document Open Access Logo

A Faster Algorithm for Finding Tarski Fixed Points

Authors John Fearnley, Rahul Savani

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.29.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

John Fearnley
  • Department of Computer Science, University of Liverpool, UK
Rahul Savani
  • Department of Computer Science, University of Liverpool, UK

Acknowledgements

We would like to thank Kousha Etessami, Thomas Webster, and an anonymous reviewer for pointing out that the proof of Lemma 12 could be drastically simplified from its original version.

Cite As Get BibTex

John Fearnley and Rahul Savani. A Faster Algorithm for Finding Tarski Fixed Points. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.STACS.2021.29

Abstract

Dang et al. have given an algorithm that can find a Tarski fixed point in a k-dimensional lattice of width n using O(log^k n) queries [Chuangyin Dang et al., 2020]. Multiple authors have conjectured that this algorithm is optimal [Chuangyin Dang et al., 2020; Kousha Etessami et al., 2020], and indeed this has been proven for two-dimensional instances [Kousha Etessami et al., 2020]. We show that these conjectures are false in dimension three or higher by giving an O(log² n) query algorithm for the three-dimensional Tarski problem, which generalises to give an O(log^{k-1} n) query algorithm for the k-dimensional problem when k ≥ 3.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • query complexity
  • Tarski fixed points
  • total function problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ching-Lueh Chang, Yuh-Dauh Lyuu, and Yen-Wu Ti. The complexity of Tarski’s fixed point theorem. Theor. Comput. Sci., 401(1-3):228-235, 2008. Google Scholar
  2. Chuangyin Dang, Qi Qi, and Yinyu Ye. Computations and complexities of Tarski’s fixed points and supermodular games. CoRR, abs/2005.09836, 2020. Stanford tech report version appeared in 2012. URL: http://arxiv.org/abs/2005.09836.
  3. Chuangyin Dang and Yinyu Ye. On the complexity of a class of discrete fixed point problems under the lexicographic ordering. Technical report, City University of Hong Kong, 2018. CY2018-3, 17 pages. Google Scholar
  4. Chuangyin Dang and Yinyu Ye. On the complexity of an expanded tarski’s fixed point problem under the componentwise ordering. Theor. Comput. Sci., 732:26-45, 2018. Google Scholar
  5. Chuangyin Dang and Yinyu Ye. Erratum/correction to "on the complexity of an expanded tarski’s fixed point problem under the componentwise ordering" [Theor. Comput. Sci. 732 (2018) 26-45]. Theor. Comput. Sci., 817:80, 2020. Google Scholar
  6. Federico Echenique. Finding all equilibria in games of strategic complements. J. Econ. Theory, 135(1):514-532, 2007. Google Scholar
  7. Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s theorem, supermodular games, and the complexity of equilibria. In Proc. of ITCS, volume 151, pages 18:1-18:19, 2020. Google Scholar
  8. John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. CoRR, abs/2011.01929, 2020. URL: http://arxiv.org/abs/2011.01929.
  9. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. J. Comput. Syst. Sci., 114:1-35, 2020. Google Scholar
  10. Paul Milgrom and John Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica, 58(6):1255-1277, 1990. Google Scholar
  11. Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285-309, 1955. Google Scholar
  12. Donald M. Topkis. Equilibrium points in nonzero-sum n-person submodular games. SIAM J. Control Optim, 17:773-787, 1979. Google Scholar
  13. Donald M. Topkis. Supermodularity and Complementarity. Princeton University Press, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact