On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 26-45 |
Journal / Publication | Theoretical Computer Science |
Volume | 732 |
Online published | 17 Apr 2018 |
Publication status | Published - 7 Jul 2018 |
Link(s)
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.
Research Area(s)
- Componentwise ordering, Fixed point, Increasing mapping, Integer labeling, Lattice, PPA, Simplicial method, Tarski's fixed point theorem, Triangulation
Citation Format(s)
On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering. / Dang, Chuangyin; Ye, Yinyu.
In: Theoretical Computer Science, Vol. 732, 07.07.2018, p. 26-45.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review