Title :
Computing fixed points of an increasing mapping from a finite lattice formed by integer points of a box into itself
Author_Institution :
Dept. of Manuf. Eng. & Eng. Manage., City Univ. of Hong Kong, Kowloon, China
Abstract :
For a finite lattice (DI, ≤) consisting of integer points in an n-dimensional box D of Rn and an increasing mapping ψ from DI into itself, the well-known Tarski´s fixed point theorem asserts that there exists a point x* ∈ DI such that ψ(x*) = x*, which is a fixed point of ψ in DI and has applications in supermodular games from economic analysis. To compute such a fixed point, an arbitrary starting simplicial algorithm is developed in this paper through an introduction of an integer labeling rule and an application of a triangulation of Rn. The algorithm consists of two phases, one of which forms a variable dimension pivoting procedure and the other a full-dimensional pivoting procedure. Starting from an arbitrary integer point in D, the algorithm interchanges from one phase to the other, if necessary, and follows a finite simplicial path that leads to a fixed point of ψ in DI. The interchanging step is essential to ensure that the algorithm converges to a fixed point. A significant advantage of the algorithm is its arbitrary starting feature, which can certainly benefit from any information on where a fixed point may be found.
Keywords :
fixed point arithmetic; lattice theory; Tarski fixed point theorem; computing fixed points; economic analysis; finite lattice; full-dimensional pivoting procedure; integer labeling rule; integer points; n-dimensional box; supermodular games; variable dimension pivoting procedure; Economics; Games; Labeling; Lattices; Mathematical programming; Presses; Finite Lattice; Fixed Point; Increasing Mapping; Integer Labeling; Pivoting Procedure; Simplicial Algorithm; Tarski´s Fixed Point Theorem; Triangulation;
Conference_Titel :
Industrial Engineering and Engineering Management (IEEM), 2010 IEEE International Conference on
Conference_Location :
Macao
Print_ISBN :
978-1-4244-8501-7
Electronic_ISBN :
2157-3611
DOI :
10.1109/IEEM.2010.5674387