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)
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