David Eppstein (talk | contribs) m →References: two columns |
Malleus Fatuorum (talk | contribs) m →References: fix |
||
(2 intermediate revisions by the same user not shown) | |||
Line 69: | Line 69: | ||
Following Starr's paper, the Shapley–Folkman–Starr results were "much exploited in the theoretical literature", according to Guesnerie (page 112), who wrote the following: |
Following Starr's paper, the Shapley–Folkman–Starr results were "much exploited in the theoretical literature", according to Guesnerie (page 112), who wrote the following: |
||
<blockquote> |
<blockquote> |
||
some key results obtained under the convexity assumption remain (approximately) relevant in circumstances where convexity fails. For example, in economies with a large consumption side, nonconvexities in preferences do not destroy the standard results of, say Debreu's theory of value. In the same way, if indivisibilities in the production sector are small with respect to the size of the economy |
some key results obtained under the convexity assumption remain (approximately) relevant in circumstances where convexity fails. For example, in economies with a large consumption side, nonconvexities in preferences do not destroy the standard results of, say Debreu's theory of value. In the same way, if indivisibilities in the production sector are small with respect to the size of the economy ... then standard results are affected in only a minor way. (page 99) |
||
</blockquote> |
</blockquote> |
||
To this text, Guesnerie appended the following footnote: |
To this text, Guesnerie appended the following footnote: |
||
Line 163: | Line 163: | ||
==References== |
==References== |
||
{{Reflist| |
{{Reflist|colwidth=30em}} |
||
{{DEFAULTSORT:Shapley–Folkman Lemma}} |
{{DEFAULTSORT:Shapley–Folkman Lemma}} |
Revision as of 15:00, 28 October 2010
![](https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Shapley%E2%80%93Folkman_lemma.svg/300px-Shapley%E2%80%93Folkman_lemma.svg.png)
![](https://upload.wikimedia.org/wikipedia/commons/9/9d/Kenneth_Arrow%2C_Stanford_University.jpg)
In convex geometry and mathematical economics, the Shapley–Folkman lemma and the closely related Shapley–Folkman–Starr theorem state that the Minkowski sum of many non-convex subsets of a finite-dimensional vector space is nearly convex. The Shapley–Folkman results are named after Lloyd Shapley and Jon Folkman, who proved both the Shapley–Folkman lemma and a weaker version of the Shapley–Folkman–Starr theorem in an unpublished report, "Starr's problem" (1966), which was cited by Starr (1969).[1]
As Starr showed, these results may be used to show the existence of approximate equilibria for nonconvex economies. His research on this problem began while he was an undergraduate at Stanford University, where Starr had enrolled in the (graduate) advanced mathematical economics course of Kenneth J. Arrow.[3]
The Shapley–Folkman–Starr results have applications in optimization theory and probability, besides their applications in economics and geometry.
Minkowski sums and convex hulls
The Minkowski sum of a finite family of sets Si in a vector space is the set
of points that can be formed by adding together one vector chosen from each set.
The operations of Minkowski summation and of forming convex hulls commute: The convex hull of the Minkowski sum is the Minkowski sum of the convex hulls.[4][5]
Statement of the lemma
![](https://upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Shapley%2C_Lloyd_%281980%29.jpg/220px-Shapley%2C_Lloyd_%281980%29.jpg)
If the sets Si are compact but not necessarily convex, then their Minkowski sum M might also be nonconvex. The Shapley–Folkman lemma states that, when M is the Minkowski sum of n subsets of a d-dimensional vector space and n > d, then any point x in the convex hull of M can be decomposed as a sum with a similar form to the sum in the definition of M:
where xi belongs to the convex hull of Si for at most d of the terms in the sum, and xi belongs Si itself for all remaining terms.[1]
Conversely, the Shapley–Folkman lemma characterizes the dimension of real, finite-dimensional vector-spaces, by Theorem 3.1.7 of Schneider (page 131).[5]
The (combinatorial) Shapley–Folkman lemma is often referred to as the "Shapley–Folkman theorem", also, e.g. by Schneider (pages 130 and 140).[5]
Shapley–Folkman theorem and Starr's corollary
Shapley and Folkman used their lemma, which is purely combinatorial, to prove a metric result, the Shapley–Folkman theorem: the squared Euclidean distance from any point x in the convex hull of M to M itself is at most the sum of the squares of the d largest circumradii of the sets Si; see page 129 of Schneider.[5]
In his corollary refining the Shapley–Folkman theorem, Starr (1969, p. 37)[1] showed that circumradius could be replaced in its statement by inner radius. The inner radius of a nonconvex set Si is a measure of its nonconvexity, defined to be smallest number r such that, for any point x in the convex hull of Si, there is a sphere of radius r that contains a subset of Si whose convex hull contains x. Starr's corollary is often referred to as the "Shapley–Folkman–Starr theorem"; see Schneider's Shapley–Folkman–Starr Theorem 1.3.6 on page 130.[5]
Applications
The Shapley–Folkman lemma has applications in economics, probability, and optimization theory.
Mathematical economics
Starr (1969) applied the Shapley–Folkman theorem to mathematical economics. Starr proved that even without convex preferences there exists an approximate general economic equilibrium. Both the Shapley–Folkman theorem and Starr's corollary bound the distance from an "approximate" economic equilibrium to an equilibrium of a "convexified" economy, when the number of agents exceeds the dimension of the goods.[1]
Following Starr's paper, the Shapley–Folkman–Starr results were "much exploited in the theoretical literature", according to Guesnerie (page 112), who wrote the following:
some key results obtained under the convexity assumption remain (approximately) relevant in circumstances where convexity fails. For example, in economies with a large consumption side, nonconvexities in preferences do not destroy the standard results of, say Debreu's theory of value. In the same way, if indivisibilities in the production sector are small with respect to the size of the economy ... then standard results are affected in only a minor way. (page 99)
To this text, Guesnerie appended the following footnote:
The derivation of these results in general form has been one of the major achievements of postwar economic theory.[2][6]
In particular, the Shapley–Folkman–Starr results were incorporated in the theory of general economic equilibria[7] and in the theory of market failures[8] and of public economics.[9] The Shapley–Folkman–Starr results are introduced in graduate-level textbooks in microeconomics[10], general equilibrium theory[11], game theory[12], and mathematical economics[13].
Probability and measure theory
In mathematics, convex sets and simple random vectors are closely related, so it is not surprising that the Shapley–Folkman–Starr results find use in probability theory and measure theory; in the other direction, probability theory provides tools to examine convex sets generally and the Shapley–Folkman–Starr results specifically.[14]
In convex geometry and integral geometry, the Shapley–Folkman–Starr results have been used to refine the Brunn–Minkowski inequality.[15] In the theory of vector measures, the Shapley–Folkman lemma has been used to prove Lyapunov's theorem on the convexity of the range of a (nonatomic) vector measure[16], a result that has many applications in ("bang–bang") control theory and in statistical decision theory.[17]
Artstein & Vitale (1975) used the Shapley–Folkman theorem to prove a law of large numbers for random sets.[18] Following Artstein & Vitale's paper, the Shapley–Folkman–Starr results have been widely used in the stochastic geometry of random sets.[19] In particular, Weil used the Shapley-Folkman lemma and Starr's corollary to prove a central limit theorem for random variables that take their values in a Banach space.[20]
Mathematical optimization
Aubin & Ekeland (1976) applied the Shapley–Folkman lemma to explain the success of Lagrangian dual methods on nonlinear programming problems with nonconvexities.[21] The problem had been raised by numerical experiments by Lemaréchal.[22] Similar applications of the Shapley–Folkman lemma are described in optimizaton monographs[22][23] and textbooks.[24][25]
References
- ^ a b c d e Starr, Ross M. (1969), "Quasi-equilibria in markets with non-convex preferences (Appendix 2: The Shapley–Folkman theorem, pp. 35–37)", Econometrica, 37 (1): 25–38, JSTOR 1909201
{{citation}}
: Cite has empty unknown parameter:|1=
(help). - ^ a b Page 138 in Guesnerie: Guesnerie, Roger (1989). "First-best allocation of resources with nonconvexities in production". In Bernard Cornet and Henry Tulkens (ed.). Contributions to Operations Research and Economics: The twentieth anniversary of CORE (Papers from the symposium held in Louvain-la-Neuve, January 1987). Cambridge, MA: MIT Press. pp. 99–143. ISBN 0-262-03149-3. MR1104662.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - ^ a b Pages 217–218 in Starr and Stinchcombe:
Starr, R.M.; Stinchcombe, M.B. (1999). "Exchange in a network of trading posts". In Graciela Chichilnisky (ed.). Markets, Information and Uncertainty: Essays in Economic Theory in Honor of Kenneth J. Arrow. Cambridge: Cambridge University Press. pp. 217–234. doi:10.2277/0521553555. ISBN 9780521082884.
{{cite book}}
: Cite has empty unknown parameters:|1=
,|2=
, and|3=
(help) - ^ See Theorem 3 (pages 562–563) in Krein and Šmulian: Template:Cite article
- ^ a b c d e For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196): Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of Mathematics and its Applications. Vol. 44. Cambridge: Cambridge University Press. pp. xiv+490. ISBN 0-521-35220-7. MR1216521.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - ^ Compare Green, Jerry; Heller, Walter P. (1981). "1 Mathematical analysis and convexity with applications to economics". In Kenneth Joseph Arrow and Michael D. Intriligator (ed.). Handbook of mathematical economics, Volume I. Handbooks in Economics. Vol. 1. Amsterdam-New York: North-Holland Publishing Co. pp. pp. 15--52. ISBN 0-444-86126-2. MR634800.
{{cite book}}
:|pages=
has extra text (help); Cite has empty unknown parameter:|1=
(help) - ^
- See pages 392–399 for the Shapley–Folkman–Starr results and see page 188 for applications in Arrow & Hahn: Arrow, Kenneth J.; Hahn, Frank H. (1971). "Appendix B: Convex and related sets". General Competitive Analysis. Mathematical economics texts [Advanced textbooks in economics]. San Francisco, CA: Holden–Day, Inc. [North-Holland]. pp. 375–401. ISBN 0 444 85497 5. MR439057.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - Pages 52–55 with applications on pages 145–146, 152–153, and 274–275 in Mas-Colell: Mas-Colell, Andreu (1985). "1.L Averages of sets". The Theory of General Economic Equilibrium: A Differentiable Approach. Econometric Society Monographs. Cambridge UP. ISBN 0-521-26514-2. MR1113262.
{{cite book}}
: Cite has empty unknown parameters:|1=
and|2=
(help) - Theorem C(6) on page 37 and applications on pages 115-116, 122, and 168: Hildenbrand, Werner (1974). Core and Equilibria of a Large Economy. Princeton Studies in Mathematical Economics. Princeton, N.J.: Princeton University Press. pp. viii+251. ISBN 978-0691041896. MR389160.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help)
- See pages 392–399 for the Shapley–Folkman–Starr results and see page 188 for applications in Arrow & Hahn: Arrow, Kenneth J.; Hahn, Frank H. (1971). "Appendix B: Convex and related sets". General Competitive Analysis. Mathematical economics texts [Advanced textbooks in economics]. San Francisco, CA: Holden–Day, Inc. [North-Holland]. pp. 375–401. ISBN 0 444 85497 5. MR439057.
- ^ See section 7.2 Convexification by numbers in Salanié: Salanié, Bernard (2000). "7 Nonconvexities". Microeconomics of market failures (English translation of the (1998) French Microéconomie: Les défaillances du marché (Economica, Paris) ed.). Cambridge, MA: MIT Press. pp. 107–125.
- ^ An "informal" presentation appears in pages 63–65 of Laffont: Laffont, Jean-Jacques (1988). "3 Nonconvexities". Fundamentals of Public Economics. MIT.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - ^
- Varian, Hal R. (1992). "21.2 convexity and size". Microeconomic Analysis (3rd ed.). W. W. Norton & Company. pp. 393–394. ISBN 978-0393957358. MR1036734.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - Page 626: Mas-Colell, Andreu; Whinston, Michael D.; Green, Jerry R. (1995). "17.1 Large economies and nonconvexities". Microeconomic theory. Oxford University Press. pp. 627–630. ISBN 978-0195073409.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help)
- Varian, Hal R. (1992). "21.2 convexity and size". Microeconomic Analysis (3rd ed.). W. W. Norton & Company. pp. 393–394. ISBN 978-0393957358. MR1036734.
- ^ Page 169 in the first edition of Starr: Starr, Ross M. (2011). "8 Convex sets, separation theorems, and non-convex sets in RN". General equilibrium theory: An introduction (Second ed.). Cambridge: Cambridge University Press. pp. xxiv+250 (first 1993 edition). ISBN 9780521533867 paperback, 9780521826457 hardback (first edition 0-521-56414-X, 0-521-56473-5). MR1462618.
{{cite book}}
: Check|isbn=
value: invalid character (help); Cite has empty unknown parameter:|1=
(help); External link in
(help); Unknown parameter|publisher=
|month=
ignored (help)- See Ellickson (page xviii), especially Chapter 7 "Walras meets Nash" (especially section 7.4 "Nonconvexity" pages 306–310 and 312, and also 328–329) and Chapter 8 "What is Competition?" (pages 347 and 352): Ellickson, Bryan (1994). Competitive equilibrium: Theory and applications. Cambridge University Press. p. 420. doi:10.2277/0521319889. ISBN 9780521319881.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - Blad, Michael C.; Keiding, Hans (1990). Microeconomics: Institutions, equilibrium and optimality. Advanced Textbooks in Economics Series. Vol. 30. Elsevier. p. 424. ISBN 9780444886446, 0444886443.
{{cite book}}
: Check|isbn=
value: invalid character (help); Cite has empty unknown parameter:|1=
(help)
- See Ellickson (page xviii), especially Chapter 7 "Walras meets Nash" (especially section 7.4 "Nonconvexity" pages 306–310 and 312, and also 328–329) and Chapter 8 "What is Competition?" (pages 347 and 352): Ellickson, Bryan (1994). Competitive equilibrium: Theory and applications. Cambridge University Press. p. 420. doi:10.2277/0521319889. ISBN 9780521319881.
- ^ Theorem 1.6.5 on pages 24-25 of Ichiishi: Ichiishi, Tatsuro (1983). Game theory for economic analysis. Economic theory, econometrics, and mathematical economics. New York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. x+164. ISBN 0-12-370180-5. MR700688.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - ^
- Pages 127 and 33–34 in Cassels: Cassels, J.W.S. (1981). "Appendix A "Convex sets"". Economics for mathematicians. London Mathematical Society Lecture Note Series. Vol. 62. Cambridge-New York: Cambridge University Press. pp. xi+145. ISBN 0-521-28614-X. MR657578.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - Carter, Michael (2001). Foundations of mathematical economics. Cambridge, MA: MIT Press. pp. xx+649. ISBN 0-262-53192-5. MR1865841.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - Moore, James C. (1999). Mathematical methods for economic theory: Volume I. Studies in economic theory. Vol. 9. Berlin: Springer-Verlag. pp. xii+414. MR1727000.
{{cite book}}
: Cite has empty unknown parameter:|2=
(help); Text "isbn3-540-66235-9" ignored (help)
- Pages 127 and 33–34 in Cassels: Cassels, J.W.S. (1981). "Appendix A "Convex sets"". Economics for mathematicians. London Mathematical Society Lecture Note Series. Vol. 62. Cambridge-New York: Cambridge University Press. pp. xi+145. ISBN 0-521-28614-X. MR657578.
- ^ Template:Cite article
- ^ Template:Cite article
- ^ Template:Cite article
- ^ Template:Cite article Artstein's article has been republished in a festschrift by students of Robert J. Aumann: Artstein, Zvi; Hart, Sergiu (ed.); Neyman, Abraham (ed.) (1995). "22 "Discrete and continuous bang-bang and facial spaces or: Look for the extreme points"". Game and economic theory: Selected contributions in honor of Robert J. Aumann. Ann Arbor, MI: University of Michigan Press. pp. 449–462. ISBN 0-472-10673-2.
{{cite book}}
:|first2=
has generic name (help); Cite has empty unknown parameter:|1=
(help). - ^ Artstein, Zvi; Vitale, Richard A. (1975), "A strong law of large numbers for random compact sets", The Annals of Probability, 3 (5): 879–882, doi:10.1214/aop/1176996275, MR385966.JSTOR 2959130
{{citation}}
: Cite has empty unknown parameter:|1=
(help). - ^ Pages 195–198, 218, 232, 237–238 and 407: Molchanov, Ilya (2005). "3 Minkowski addition". Theory of random sets. Probability and its Applications. Springer-Verlag London Ltd. pp. 194–240. ISBN 978-185223-892-3, 1-85233-892-X. MR2132405.
{{cite book}}
: Check|isbn=
value: invalid character (help); Cite has empty unknown parameter:|1=
(help); Unknown parameter|address=
ignored (|location=
suggested) (help) - ^ Template:Cite article
- ^ Aubin, J.P.; Ekeland, I. (1976), "Estimates of the duality gap in nonconvex optimization", Mathematics of Operations Research, 1 (3): 225–245, doi:10.1287/moor.1.3.225, MR449695.JSTOR 3689565
{{citation}}
: Cite has empty unknown parameter:|1=
(help); External link in
(help).|journal=
- ^ a b Ekeland, Ivar (1976). "Appendix I: An a priori estimate in convex programming". In Ekeland, Ivar and Temam, Roger (ed.). Convex Analysis and Variational Problems. Studies in Mathematics and its Applications. Vol. 1 (Translated from the (1973) French, with new appendices ed.). Amsterdam: North-Holland Publishing Co. pp. 357–373. MR463994.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help)CS1 maint: multiple names: editors list (link) (Republished in SIAM's series, Classics in Applied Mathematics) This reference contains a proof of the Shapley–Folkman lemma. - ^ Besides presenting Ekeland-style analysis of duality gaps (acknowledgment on page 381), Bertsekas (1982) applies Lagrangian dual methods to the
scheduling of electrical power plants ("unit commitment problems"), where nonconvexity appears because of integer constraints: Bertsekas, Dimitri P. (1982). "5.6 Large scale separable integer programming problems and the exponential method of multipliers". Constrained optimization and Lagrange multiplier methods. Computer Science and Applied Mathematics (first [Reprinted 1996 Athena Scientific, Belmont MA., 1-886529-04-3] ed.). New York: Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]. pp. 364–381. ISBN 0-12-093480-9. MR690767.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help) - ^ See Figure 5.1.9 (page 496) in Bertsekas: Bertsekas, Dimitri P. (1999). "5.1.6 Separable problems and their geometry". Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. pp. 494–498. ISBN 1-886529-00-0.
- ^ Pages 267–279: Hiriart-Urruty, Jean-Baptiste (1998). "6 Ensembles et fonctions convexes. Projection sur un convexe fermé". Optimisation et analyse convexe. Mathématiques. Paris: Presses Universitaires de France. pp. 247–306. ISBN 2-13-048983-4. MR1613914.
{{cite book}}
: Cite has empty unknown parameter:|1=
(help)