Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875476 | Theoretical Computer Science | 2018 | 20 Pages |
Abstract
Let Î be a finite lattice of integer points in a box of Rn and f an increasing mapping in terms of the componentwise ordering from Î to itself. The well-known Tarski's fixed point theorem asserts that f has a fixed point in Î . A simple expansion of f from Î to a larger lattice C of integer points in a box of Rn yields that the smallest point in C is always a fixed point of f (an expanded Tarski's fixed point problem). By introducing an integer labeling rule and applying a cubic triangulation of the Euclidean space, we prove in this paper that the expanded Tarski's fixed point problem is in the class PPA when f is given as an oracle. It is shown in this paper that Nash equilibria of a bimatrix game can be reformulated as fixed points different from the smallest point in C of an increasing mapping from C to itself. This implies that the expanded Tarski's fixed point problem has at least the same complexity as that of the Nash equilibrium problem. As a byproduct, we also present a homotopy-like simplicial method to compute a Tarski fixed point of f. The method starts from an arbitrary lattice point and follows a finite simplicial path to a fixed point of f.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chuangyin Dang, Yinyu Ye,