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

Chuangyin Dang; Qi Qi; Yinyu Ye

doi:10.1007/978-981-97-7752-5_13

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

Chuangyin Dang, Qi Qi^*, Yinyu Ye

^*Corresponding author for this work

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings
Editors	Bo Li, Minming Li, Xiaoming Sun
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	159-174
Number of pages	16
ISBN (Print)	9789819777518
DOIs	https://doi.org/10.1007/978-981-97-7752-5_13
Publication status	Published - 2025
Externally published	Yes
Event	18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024 - Hong Kong, China Duration: 29 Jul 2024 → 31 Jul 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14752 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024
Country/Territory	China
City	Hong Kong
Period	29/07/24 → 31/07/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

Keywords

Co-NP Hardness
Equilibrium Computation
Fixed Point Theorem
Order Preserving Mapping
Supermodular Game

Access to Document

10.1007/978-981-97-7752-5_13

Cite this

Dang, C., Qi, Q., & Ye, Y. (2025). Computations and Complexities of Tarski’s Fixed Points and Supermodular Games. In B. Li, M. Li, & X. Sun (Eds.), Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings (pp. 159-174). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14752 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-97-7752-5_13

Dang, Chuangyin ; Qi, Qi ; Ye, Yinyu. / Computations and Complexities of Tarski’s Fixed Points and Supermodular Games. Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. editor / Bo Li ; Minming Li ; Xiaoming Sun. Springer Science and Business Media Deutschland GmbH, 2025. pp. 159-174 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0577f9d424c340ec974b978fa31944ae,

title = "Computations and Complexities of Tarski{\textquoteright}s Fixed Points and Supermodular Games",

abstract = "We consider two models of computation for Tarski{\textquoteright}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{\textquoteright}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{\textquoteright}s fixed point theorem. Exploring the difference between supermodular games and Tarski{\textquoteright}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.",

keywords = "Co-NP Hardness, Equilibrium Computation, Fixed Point Theorem, Order Preserving Mapping, Supermodular Game",

author = "Chuangyin Dang and Qi Qi and Yinyu Ye",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.; 18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024 ; Conference date: 29-07-2024 Through 31-07-2024",

year = "2025",

doi = "10.1007/978-981-97-7752-5\_13",

language = "English",

isbn = "9789819777518",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "159--174",

editor = "Bo Li and Minming Li and Xiaoming Sun",

booktitle = "Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings",

}

Dang, C, Qi, Q & Ye, Y 2025, Computations and Complexities of Tarski’s Fixed Points and Supermodular Games. in B Li, M Li & X Sun (eds), Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14752 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 159-174, 18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024, Hong Kong, China, 29/07/24. https://doi.org/10.1007/978-981-97-7752-5_13

Computations and Complexities of Tarski’s Fixed Points and Supermodular Games. / Dang, Chuangyin; Qi, Qi; Ye, Yinyu.
Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. ed. / Bo Li; Minming Li; Xiaoming Sun. Springer Science and Business Media Deutschland GmbH, 2025. p. 159-174 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14752 LNCS).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Computations and Complexities of Tarski’s Fixed Points and Supermodular Games

AU - Dang, Chuangyin

AU - Qi, Qi

AU - Ye, Yinyu

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

KW - Co-NP Hardness

KW - Equilibrium Computation

KW - Fixed Point Theorem

KW - Order Preserving Mapping

KW - Supermodular Game

UR - https://www.scopus.com/pages/publications/85215292236

U2 - 10.1007/978-981-97-7752-5_13

DO - 10.1007/978-981-97-7752-5_13

M3 - Conference Paper published in a book

AN - SCOPUS:85215292236

SN - 9789819777518

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 159

EP - 174

BT - Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings

A2 - Li, Bo

A2 - Li, Minming

A2 - Sun, Xiaoming

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024

Y2 - 29 July 2024 through 31 July 2024

ER -

Dang C, Qi Q, Ye Y. Computations and Complexities of Tarski’s Fixed Points and Supermodular Games. In Li B, Li M, Sun X, editors, Frontiers of Algorithmics - 18th International Joint Conference, IJTCS-FAW 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2025. p. 159-174. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-97-7752-5_13