Computation of Fixed Points of a Discrete Increasing Mapping and Its Applications to Supermodular Games

As a powerful mechanism for studying strategic complementarities, supermodular games have been extensively applied in supply chain management, wireless communications and economic analysis. In these applications, the computation of Nash equilibria plays an important role and has attracted a lot of attention. A mapping is increasing on a partially ordered set if it preserves the orders. If a mapping maps a point to itself, such a point is a fixed point. It is well known that the computation of Nash equilibria of a supermodular game can be reduced to the computation of fixed points of an increasing mapping (usually discrete or discontinuous). The problem we consider in this project is to determine whether an increasing mapping from the semilattice of all n-dimensional nonnegative integer vectors into itself has a fixed point. A special case of the problem is Tasrki’s fixed point theorem on a finite lattice of n-dimensional integer vectors. Although an iterative method was proposed to solve the problem in the literature, it remains a challenging problem and appeals for more efficient alternatives.This project aims to investigate the complexity of the problem and develop a pathfollowing method for computing fixed points of a discrete increasing mapping. An NP-complete problem will be converted into an equivalent problem of determining whether a particular discrete increasing mapping has a fixed point to derive NP-hardness. An integer labeling rule will be defined to assign to each integer point of the space an integer label between 0 and n+1. A cone-like set with an extra dimension will be introduced to facilitate the development. A triangulation will be adapted for subdividing the cone-like set into simplices. Applying these results, we will develop a path-following method, which exactly follows a finite simplicial path that starts from an arbitrary integer point in the space and either leads to a fixed point of a discrete increasing mapping or proves that no such point exists. Numerical comparisons with the iterative method will be carried out. An extension to approximating fixed points of an increasing mapping from the semilattice of all n-dimensional nonnegative vectors into itself will be accomplished by introducing a discrete increasing mapping. The path-following method and its extension will be applied to compute Nash equilibria of supermodular games. The ultimately expected outcomes of the project will be an efficient path-following method for computing fixed points of a discrete increasing mapping and its applications to supermodular games.