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 journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)26-45
Journal / PublicationTheoretical Computer Science
Volume732
Online published17 Apr 2018
Publication statusPublished - 7 Jul 2018

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