Variational Inequality Problems with a Continuum of Solutions:Existence and Computation

Abstract

In this paper three sufficient conditions are provided under each of which an upper semi-continuous point-to-set mapping defined on an arbitrary polytope has a connected set of zero points that connect two distinct faces of the polytope. These results follow in a constructive way by designing a new simplicial algorithm. The algorithm operates on a triangulation of the polytope and generates a piecewise linear path of points connecting two distinct faces of the polytope. Each point on the path is an approximate zero point. As the mesh size of the triangulation goes to zero, the path converges to a connected set of zero points linking the two distinct faces.As a consequence, our results generalize the fundamental Browder's fixed point theorem (1960) and an earlier result by the uthors [Herings, Talman and Yang: Mathematics of Operations Research, vol.21, no.3,(1996) 675-696] on the $n$-dimensional unit cube as well. An application in economics is also discussed. Furthermore, we obtain an existence theorem of a connected set of solutions to a nonlinear variational inequality problem over arbitrary polytopes. [**This is a joint work with Herings and Talman].