The complexity of Tarski's fixed point theorem

DOI10.1016/j.tcs.2008.05.005zbMath1146.06003OpenAlexW1968084917MaRDI QIDQ935168

Ching-Lueh Chang, Yuh-Dauh Lyuu, Yen-Wu Ti

Publication date: 31 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.05.005

zbMATH Keywords

fixed pointcomplete latticerandomized algorithmTarski's fixed point theoremoraclequery complexityorder-preserving mappingKnaster-Tarski theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complete lattices, completions (06B23) Randomized algorithms (68W20)

Related Items

On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering ⋮ Optimal bounds on finding fixed points of contraction mappings

Cites Work

• Unnamed Item
• Nash equilibrium with strategic complementarities
• Constructive versions of Tarski's fixed point theorems
• The equilibrium set of two-player games with complementarities is a sublattice
• Fixed point theorems for correspondences with values in a partially ordered set and extended supermodular games
• On a characterization of stable matchings
• A short and constructive proof of Tarski's fixed-point theorem
• A lattice-theoretical fixpoint theorem and its applications
• A characterization of complete lattices
• Monotone stopping games
• Equilibrium Points in Nonzero-Sum n-Person Submodular Games
• Equilibrium in a Production Economy with an Income Tax
• On a discrete-time non-zero-sum Dynkin problem with monotonicity
• Abstract interpretation and application to logic programs
• Minimizing a Submodular Function on a Lattice
• The Tarski–Kantorovitch prinicple and the theory of iterated function systems