Intersection theorems on polytopes

Citation
G. Van Der Laan et al., Intersection theorems on polytopes, MATH PROGR, 84(1), 1999, pp. 25-38
Citations number
22
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
84
Issue
1
Year of publication
1999
Pages
25 - 38
Database
ISI
SICI code
0025-5610(199901)84:1<25:ITOP>2.0.ZU;2-0
Abstract
Intersection theorems are used to prove the existence of solutions to mathe matical programming and game theoretic problems. The known intersection the orems on the unit simplex are the theorems of Knaster-Kuratowski-Mazurkiewi cz (KKM), Scarf, Shapley, Freund, and Ichiishi. Recently the intersection r esult of KKM has been generalized by Ichiishi and Idzik to closed coverings of a compact convex polyhedron, called a polytope. In this paper we formul ate a general intersection theorem on the polytope. To do so, we need to ge neralize the concept of balancedness as is used by Shapley and by Ichiishi. The theorem implies most of the results stated above as special cases. Fir st, we show that the theorems of KKM, Scarf. Shapley, Freund, and Ichiishi on the unit simplex and also some theorems of Ichiishi and Idzik on a polyt ope all satisfy the conditions of our theorem on the polytope. Secondly, th e general theorem allows us to formulate the analogs of these theorems on t he polytope.