کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875476 | 1441957 | 2018 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 26-45
Journal: Theoretical Computer Science - Volume 732, 7 July 2018, Pages 26-45
نویسندگان
Chuangyin Dang, Yinyu Ye,