Document Open Access Logo

Reducing Tarski to Unique Tarski (In the Black-Box Model)

Authors Xi Chen, Yuhao Li, Mihalis Yannakakis

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2023.21.pdf
  • Filesize: 1.68 MB
  • 23 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Exact and approximate computation of equilibria
Keywords
  • Tarski fixed point
  • Query complexity
  • TFNP

Metrics

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

Abstract

We study the problem of finding a Tarski fixed point over the k-dimensional grid [n]^k. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique Tarski problem have exactly the same query complexity. Our reduction is based on a novel notion of partial-information functions which we use to fool algorithms for the unique Tarski problem as if they were working on a monotone function with a unique fixed point.

Cite As Get BibTex

Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tarski to Unique Tarski (In the Black-Box Model). In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CCC.2023.21

Author Details

Xi Chen
  • Columbia University, New York, NY, USA
Yuhao Li
  • Columbia University, New York, NY, USA
Mihalis Yannakakis
  • Columbia University, New York, NY, USA

Funding

  • Chen, Xi: Supported by NSF grants IIS-1838154, CCF-2106429 and CCF-2107187.
  • Li, Yuhao: Supported by NSF grants CCF-1563155, CCF-1703925, IIS-1838154, CCF-2106429 and CCF-2107187.
  • Yannakakis, Mihalis: Supported by NSF grants CCF-2107187 and CCF-2212233.

Acknowledgements

We would like to thank anonymous CCC reviewers for their helpful comments to improve the presentation of the paper.

References

  1. Xi Chen and Yuhao Li. Improved upper bounds for finding tarski fixed points. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 1108-1118, 2022. Google Scholar
  2. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, 1992. Google Scholar
  3. Chuangyin Dang, Qi Qi, and Yinyu Ye. Computational models and complexities of tarski’s fixed points. Technical report, Stanford University, 2011. Google Scholar
  4. Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s theorem, supermodular games, and the complexity of equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  5. John Fearnley, Paul W. Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: CLS = PPAD ∩ PLS. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 46-59. ACM, 2021. Google Scholar
  6. John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique end of potential line. J. Comput. Syst. Sci., 114:1-35, 2020. Google Scholar
  7. John Fearnley, Dömötör Pálvölgyi, and Rahul Savani. A faster algorithm for finding tarski fixed points. ACM Transactions on Algorithms (TALG), 18(3):1-23, 2022. Google Scholar
  8. Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further collapses in TFNP. In 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 of LIPIcs, pages 33:1-33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  9. Massimo Marinacci and Luigi Montrucchio. Unique tarski fixed points. Math. Oper. Res., 44(4):1174-1191, 2019. URL: https://doi.org/10.1287/moor.2018.0959.
  10. Paul Milgrom and John Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica: Journal of the Econometric Society, pages 1255-1277, 1990. Google Scholar
  11. L. Shapley. Stochastic games. Proc. Nat. Acad. Sci., 39(10):1095-1100, 1953. Google Scholar
  12. Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific journal of Mathematics, 5(2):285-309, 1955. Google Scholar
  13. Donald M Topkis. Equilibrium points in nonzero-sum n-person submodular games. Siam Journal on control and optimization, 17(6):773-787, 1979. Google Scholar
  14. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact