A set intersection theorem and applications

Using Scarf's algorithm for “computing” a fixed point of a continuous mapping, the following is proved: LetM ₁ ? M _n be closed sets inR ⁿ which cover the standard simplexS, so thatM _i coversS _i , the face ofS opposite vertexi. We say a point inS iscompletely labeled if it belongs to everyM _i andk-almost-completely labeled if it belongs to all butM _k . Then there exists a closed setT ofk-almost-completely labeled points which connects vertexk with some completely labeled point. This result is used to prove Browder's theorem (a parametric fixed-point theorem) inR ⁿ . It is also used to generate “algorithms” for the nonlinear complementarity problem which are analogous to the Lemke—Howson algorithm and the Cottle—Dantzig algorithm, respectively, for the linear complementarity problem.