The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the
dimension of the vector space, then their Minkowski sum is approximately convex.[1][2]
Related results provide more refined statements about how close the approximation is. For example, the Shapley–Folkman
theorem provides an
upper bound on the
distance between any point in the Minkowski sum and its
convex hull. This upper bound is sharpened by the Shapley–Folkman–Starr theorem (alternatively, Starr's
corollary).[3]
A set is convex if every
line segment joining two of its points is a
subset in the set: For example, the solid
disk is a convex set but the
circle is not, because the line segment joining two distinct points is not a subset of the circle.
The convex hull of a set Q is the smallest convex set that contains Q. This distance is zero
if and only if the sum is convex.
Minkowski addition is the addition of the set
members. For example, adding the set consisting of the
integers zero and one to itself yields the set consisting of zero, one, and two:
The subset of the integers {0, 1, 2} is contained in the
interval of
real numbers [0, 2], which is convex. The Shapley–Folkman lemma implies that every point in [0, 2] is the sum of an integer from {0, 1} and a real number from [0, 1].[7]
The distance between the convex interval [0, 2] and the non-convex set {0, 1, 2} equals one-half
However, the distance between the average Minkowski sum
1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}
and its convex hull [0, 1] is only 1/4, which is half the distance (1/2) between its summand {0, 1} and [0, 1]. As more sets are added together, the average of their sum "fills out" its convex hull: The maximum distance between the average and its convex hull approaches zero as the average includes more
summands.[7]
Preliminaries
The Shapley–Folkman lemma depends upon the following definitions and results from
convex geometry.
Real vector spaces
A
realvector space of two
dimensions can be given a
Cartesian coordinate system in which every point is identified by an
ordered pair of real numbers, called "coordinates", which are conventionally denoted by x and y. Two points in the Cartesian plane can be added coordinate-wise
(x1, y1) + (x2, y2) = (x1+x2, y1+y2);
further, a point can be multiplied by each real number λ coordinate-wise
λ (x, y) = (λx, λy).
More generally, any real vector space of (finite) dimension can be viewed as the
set of all
-tuples of real numbers { (v1, v2, . . . , vD) } on which two
operations are defined:
vector addition and
multiplication by a real number. For finite-dimensional vector spaces, the operations of vector addition and real-number multiplication can each be defined coordinate-wise, following the example of the Cartesian plane.[8]
In a real vector space, a
non-empty set Q is defined to be convex if, for each pair of its points, every point on the
line segment that joins them is still in Q. For example, a solid
disk is convex but a
circle is not, because it does not contain a line segment joining its points ; the non-convex set of three integers {0, 1, 2} is contained in the interval [0, 2], which is convex. For example, a solid
cube is convex; however, anything that is hollow or dented, for example, a
crescent shape, is non-convex. The
empty set is convex, either by definition[9] or
vacuously, depending on the author.
More formally, a set Q is convex if, for all points v0 and v1 in Q and for every real number λ in the
unit interval [0,1], the point
By
mathematical induction, a set Q is convex if and only if every
convex combination of members of Q also belongs to Q. By definition, a convex combination of an indexed subset {v0, v1, . . . , vD} of a vector space is any weighted average λ0v0 + λ1v1 + . . . + λDvD, for some indexed set of non-negative real numbers {λd} satisfying the equation λ0 + λ1 + . . . + λD = 1.[10]
The definition of a convex set implies that the intersection of two convex sets is a convex set. More generally, the intersection of a family of convex sets is a convex set. In particular, the intersection of two
disjoint sets is the empty set, which is convex.[9]
Convex hull
For every subset Q of a real vector space, its convex hull Conv(Q) is the
minimal convex set that contains Q. Thus Conv(Q) is the intersection of all the convex sets that
coverQ. The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in Q.[11] For example, the convex hull of the set of
integers {0,1} is the closed
interval of
real numbers [0,1], which contains the integer end-points.[7] The convex hull of the
unit circle is the closed
unit disk, which contains the unit circle.
Minkowski addition
In any vector space (or algebraic structure with addition), , the
Minkowski sum of two non-empty sets is defined to be the element-wise operation (See also.[12])
For example
This operation is clearly commutative and associative on the collection of non-empty sets. All such operations extend in a well-defined manner to recursive forms By the principle of induction it is easy to see that[13]
Convex hulls of Minkowski sums
Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets of a real vector space, , the
convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,
are nonempty, bounded subsets of . They are also called "summands". is the number of summands.
is the Minkowski sum of the summands.
is an arbitrary vector in .
Shapley–Folkman lemma
Since , for any , there exist elements such that . The Shapley–Folkman lemma refines this statement.
Shapley–Folkman lemma — For any , there exist elements such that , and at most of the summands , while the others .
For example, every point in is the sum of an element in and an element in .[7]
Shuffling indices if necessary, this means that every point in can be decomposed as
where for
and for . Note that the reindexing depends on the point .[16]
The lemma may be stated succinctly as
The converse of Shapley–Folkman lemma
converse of Shapley–Folkman lemma[17] — If a vector space obeys the Shapley–Folkman lemma for a natural number , and for no number less than , then its dimension is finite, and exactly .
In particular, the Shapley–Folkman lemma requires the vector space to be finite-dimensional.
Shapley–Folkman theorem
Shapley and Folkman used their lemma to prove the following theorem, which quantifies the difference between and using squared
Euclidean distance.
For any nonempty subset and any point define their squared Euclidean distance to be the
infimum
And more generally, for any two nonempty subsets define
Note that so we can simply write where Similarly,
For example,
The squared Euclidean distance is a measure of how "close" two sets are. In particular, if two sets are compact, then their squared Euclidean distance is zero if and only if they are equal. Thus, we may quantify how close to convexity is by upper-bounding
For any bounded subset define its circumradius to be the infimum of the radius of all
balls containing it (as shown in the diagram). More formally,
In particular, if we have an infinite sequence of nonempty, bounded subsets of , and if there exists some such that the inner radius of each is upper-bounded by , then
This can be interpreted as stating that, as long as we have an upper bound on the inner radii, performing "Minkowski-averaging" would get us closer and closer to a convex set.
Other proofs of the results
There have been many proofs of these results, from the original,[20] to the later
Arrow and
Hahn,[22]Cassels,[23] Schneider,[24] etc. An abstract and elegant proof by
Ekeland[25] has been extended by Artstein.[26] Different proofs have also appeared in unpublished papers.[2][27] An elementary proof of the Shapley–Folkman lemma can be found in the book by
Bertsekas,[28] together with applications in estimating the duality gap in separable optimization problems and zero-sum games.
Usual proofs of these results are nonconstructive: they establish only the
existence of the representation, but do not provide an
algorithm for computing the representation. In 1981, Starr published an
iterative algorithm for a less sharp version of the Shapley–Folkman–Starr theorem.[29]
A proof of the results
The following proof of Shapley–Folkman lemma is from.[30] The proof idea is to lift the representation of from to , use
Carathéodory's theorem for conic hulls, then drop back to .
Proof of Shapley–Folkman lemma
Since , there exists a minimal set of indices , such that , but for any proper subset .
Since we can always drop to such a set , we WLOG assume that is itself a minimal set of indices, that is, cannot be represented as where is a proper subset of .
For each , represent as , where is a large finite number, , and .
Now "lift" the representation from to . Define
where is the vector in that has 1 at coordinate , and 0 at all other coordinates.
With this, we have a lifted representation
That is, is in the conic hull of .
By Carathéodory's theorem for conic hulls, we have an alternative representation
such that , and at most of them are nonzero. Since we defined
this alternative representation is also a representation for .
Since we assumed that cannot be represented as where is a proper subset of , we find that for every , at least one of is nonzero.
Since at most of are nonzero, we find that for at most of , at least two of are nonzero.
Thus we obtain a representation
where for at most of , the term is not in .
The following "probabilistic" proof of Shapley–Folkman–Starr theorem is from.[23]
We can interpret in probabilistic terms: , since for some , we can define a random vector , finitely supported in , such that , and .
Then, it is natural to consider the "variance" of a set as
With that, .
Proof
: Expand their definitions.
: if then let be finitely supported in such that . Now since is bounded in a ball of radius centered at some , we have .
: use the previous result.
Proof of Shapley–Folkman–Starr theorem
It suffices to show .
, by Shapley–Folkman lemma, there exists a representation , such that partitions .
Now, for each , construct random vectors such that is finitely supported on , with and , where is an arbitrary small number.
Let all such be independent. Then let . Since each is a deterministic vector, we have
Since this is true for arbitrary , we have , and we are done.
History
The lemma of
Lloyd Shapley and
Jon Folkman was first published by the economist
Ross M. Starr, who was investigating the existence of
economic equilibria while studying with
Kenneth Arrow.[1] In his paper, Starr studied a convexified economy, in which non-convex sets were replaced by their convex hulls; Starr proved that the convexified economy has equilibria that are closely approximated by "quasi-equilibria" of the original economy; moreover, he proved that every quasi-equilibrium has many of the optimal properties of true equilibria, which are proved to exist for convex economies.
Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used to show that central results of (convex) economic theory are good approximations to large economies with non-convexities; for example, quasi-equilibria closely approximate equilibria of a convexified economy. "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote
Roger Guesnerie.[31]
The Shapley–Folkman lemma enables researchers to extend results for Minkowski sums of convex sets to sums of general sets, which need not be convex. Such sums of sets arise in
economics, in
mathematical optimization, and in
probability theory; in each of these three mathematical sciences, non-convexity is an important feature of applications.
In
economics, a consumer's
preferences are defined over all "baskets" of goods. Each basket is represented as a non-negative vector, whose coordinates represent the quantities of the goods. On this set of baskets, an indifference curve is defined for each consumer; a consumer's indifference curve contains all the baskets of commodities that the consumer regards as equivalent: That is, for every pair of baskets on the same indifference curve, the consumer does not prefer one basket over another. Through each basket of commodities passes one indifference curve. A consumer's preference set (relative to an indifference curve) is the
union of the indifference curve and all the commodity baskets that the consumer prefers over the indifference curve. A consumer's preferences are convex if all such preference sets are convex.[32]
An optimal basket of goods occurs where the budget-line
supports a consumer's preference set, as shown in the diagram. This means that an optimal basket is on the highest possible indifference curve given the budget-line, which is defined in terms of a price vector and the consumer's income (endowment vector). Thus, the set of optimal baskets is a
function of the prices, and this function is called the consumer's demand. If the preference set is convex, then at every price the consumer's demand is a convex set, for example, a unique optimal basket or a line-segment of baskets.[33]
However, if a preference set is non-convex, then some prices determine a budget-line that supports two separate optimal-baskets. For example, we can imagine that, for zoos, a lion costs as much as an eagle, and further that a zoo's budget suffices for one eagle or one lion. We can suppose also that a zoo-keeper views either animal as equally valuable. In this case, the zoo would purchase either one lion or one eagle. Of course, a contemporary zoo-keeper does not want to purchase half of an eagle and half of a lion (or a
griffin)! Thus, the zoo-keeper's preferences are non-convex: The zoo-keeper prefers having either animal to having any strictly convex combination of both.[34]
When the consumer's preference set is non-convex, then (for some prices) the consumer's demand is not
connected; a disconnected demand implies some discontinuous behavior by the consumer, as discussed by
Harold Hotelling:
If indifference curves for purchases be thought of as possessing a wavy character, convex to the origin in some regions and concave in others, we are forced to the conclusion that it is only the portions convex to the origin that can be regarded as possessing any importance, since the others are essentially unobservable. They can be detected only by the discontinuities that may occur in demand with variation in price-ratios, leading to an abrupt jumping of a point of tangency across a chasm when the straight line is rotated. But, while such discontinuities may reveal the existence of chasms, they can never measure their depth. The concave portions of the indifference curves and their many-dimensional generalizations, if they exist, must forever remain in unmeasurable obscurity.[35]
The difficulties of studying non-convex preferences were emphasized by
Herman Wold[36] and again by
Paul Samuelson, who wrote that non-convexities are "shrouded in eternal darkness ...",[37][a] according to Diewert.[38]
Nonetheless, non-convex preferences were illuminated from 1959 to 1961 by a sequence of papers in The Journal of Political Economy (JPE). The main contributors were Farrell,[39] Bator,[40]Koopmans,[41] and Rothenberg.[42] In particular, Rothenberg's paper discussed the approximate convexity of sums of non-convex sets.[43] These JPE-papers stimulated a paper by
Lloyd Shapley and
Martin Shubik, which considered convexified consumer-preferences and introduced the concept of an "approximate equilibrium".[44] The JPE-papers and the Shapley–Shubik paper influenced another notion of "quasi-equilibria", due to
Robert Aumann.[45][46]
Starr's 1969 paper and contemporary economics
Previous publications on
non-convexity and economics were collected in an annotated bibliography by
Kenneth Arrow. He gave the bibliography to
Starr, who was then an undergraduate enrolled in Arrow's (graduate) advanced mathematical-economics course.[47] In his term-paper, Starr studied the general equilibria of an artificial economy in which non-convex preferences were replaced by their convex hulls. In the convexified economy, at each price, the
aggregate demand was the sum of convex hulls of the consumers' demands. Starr's ideas interested the mathematicians
Lloyd Shapley and
Jon Folkman, who proved their
eponymous lemma and theorem in "private correspondence", which was reported by Starr's published paper of 1969.[1]
In his 1969 publication, Starr applied the Shapley–Folkman–Starr theorem. Starr proved that the "convexified" economy has general equilibria that can be closely approximated by "quasi-equilibria" of the original economy, when the number of agents exceeds the dimension of the goods: Concretely, Starr proved that there exists at least one quasi-equilibrium of prices popt with the following properties:
For each quasi-equilibrium's prices popt, all consumers can choose optimal baskets (maximally preferred and meeting their budget constraints).
At quasi-equilibrium prices popt in the convexified economy, every good's market is in equilibrium: Its supply equals its demand.
For each quasi-equilibrium, the prices "nearly clear" the markets for the original economy: an
upper bound on the
distance between the set of equilibria of the "convexified" economy and the set of quasi-equilibria of the original economy followed from Starr's corollary to the Shapley–Folkman theorem.[48]
Starr established that
"in the aggregate, the discrepancy between an allocation in the fictitious economy generated by [taking the convex hulls of all of the consumption and production sets] and some allocation in the real economy is bounded in a way that is independent of the number of economic agents. Therefore, the average agent experiences a deviation from intended actions that vanishes in significance as the number of agents goes to infinity".[49]
The Shapley–Folkman lemma has been used to explain why large
minimization problems with
non-convexities can be nearly solved (with
iterative methods whose convergence proofs are stated for only
convex problems). The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.[61]
In many optimization problems, the
objective function f is separable: that is, f is the sum of many summand-functions, each of which has its own argument:
f(x) = f( (x1, ..., x) ) = Σ fn(xn).
For example, problems of
linear optimization are separable. Given a separable problem with an optimal solution, we fix an optimal solution
xmin = (x1, ..., x)min
with the minimum value f(xmin). For this separable problem, we also consider an optimal solution (xmin, f(xmin) )
to the "convexified problem", where convex hulls are taken of the graphs of the summand functions. Such an optimal solution is the
limit of a sequence of points in the convexified problem
Of course, the given optimal-point is a sum of points in the graphs of the original summands and of a small number of convexified summands, by the Shapley–Folkman lemma.
This analysis was published by
Ivar Ekeland in 1974 to explain the apparent convexity of separable problems with many summands, despite the non-convexity of the summand problems. In 1973, the young mathematician
Claude Lemaréchal was surprised by his success with
convex minimizationmethods on problems that were known to be non-convex; for
minimizing nonlinear problems, a solution of the
dual problem need not provide useful information for solving the primal problem, unless the primal problem be convex and satisfy a
constraint qualification. Lemaréchal's problem was additively separable, and each summand function was non-convex; nonetheless, a solution to the dual problem provided a close approximation to the primal problem's optimal value.[63][4][64] Ekeland's analysis explained the success of methods of convex minimization on large and separable problems, despite the non-convexities of the summand functions. Ekeland and later authors argued that additive separability produced an approximately convex aggregate problem, even though the summand functions were non-convex. The crucial step in these publications is the use of the Shapley–Folkman lemma.[4][64][65][c] The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.[4][5][58][61]
Probability and measure theory
Convex sets are often studied with
probability theory. Each point in the convex hull of a (
non-empty) subset Q of a finite-dimensional space is the
expected value of a
simplerandom vector that takes its values in Q, as a consequence of
Carathéodory's lemma. Thus, for a non-empty set Q, the collection of the expected values of the simple, Q-valued random vectors equals Q's convex hull; this equality implies that the Shapley–Folkman–Starr results are useful in probability theory.[67] In the other direction, probability theory provides tools to examine convex sets generally and the Shapley–Folkman–Starr results specifically.[68] The Shapley–Folkman–Starr results have been widely used in the
probabilistic theory of random sets,[69] for example, to prove a
law of large numbers,[6][70] a
central limit theorem,[70][71] and a
large-deviationsprinciple.[72] These proofs of
probabilistic limit theorems used the Shapley–Folkman–Starr results to avoid the assumption that all the random sets be convex.
A
probability measure is a finite
measure, and the Shapley–Folkman lemma has applications in non-probabilistic measure theory, such as the theories of
volume and of
vector measures. The Shapley–Folkman lemma enables a refinement of the
Brunn–Minkowski inequality, which bounds the volume of sums in terms of the volumes of their summand-sets.[73] The volume of a set is defined in terms of the
Lebesgue measure, which is defined on subsets of
Euclidean space. In advanced measure-theory, the Shapley–Folkman lemma has been used to prove
Lyapunov's theorem, which states that the
range of a
vector measure is convex.[74] Here, the traditional term "range" (alternatively, "image") is the set of values produced by the function.
A vector measure is a vector-valued generalization of a measure;
for example,
if p1 and p2 are
probability measures defined on the same
measurable space,
then the
product functionp1p2 is a vector measure,
where p1p2
is defined for every
eventω
by
A gulf profound as that Serbonian Bog Betwixt Damiata and Mount Casius old, Where Armies whole have sunk.
Milton's description of concavity serves as the
literary epigraph prefacing chapter seven of
Arrow & Hahn (1980, p. 169), "Markets with non-convex preferences and production", which presents the results of
Starr (1969).
the inclusion can be strict even for two convex closed summand-sets, according to
Rockafellar (1997, pp. 49 and 75). Ensuring that the Minkowski sum of sets be closed requires the closure operation, which appends limits of convergent sequences.
^
abcdeEkeland (1999, pp. 357–359): Published in the first English edition of 1976, Ekeland's appendix proves the Shapley–Folkman lemma, also acknowledging
Lemaréchal's experiments on page 373.
^Anderson, Robert M. (14 March 2005).
"1 The Shapley–Folkman theorem"(PDF). Economics 201B: Nonconvex preferences and approximate equilibria. Berkeley, Calif.: Economics Department, University of California, Berkeley. pp. 1–5. Retrieved 1 January 2011.
^Starr (1969, p. 26): "After all,
one may be indifferent between an automobile and a boat, but in most cases one can neither drive nor sail the combination of half boat, half car."
It will be noted that any point where the indifference curves are convex rather than concave cannot be observed in a competitive market. Such points are shrouded in eternal darkness—unless we make our consumer a monopsonist and let him choose between goods lying on a very convex "budget curve" (along which he is affecting the price of what he buys). In this monopsony case, we could still deduce the slope of the man's indifference curve from the slope of the observed constraint at the equilibrium point.
^Koopmans (1961, p. 478) and others—for example,
Farrell (1959, pp. 390–391) and
Farrell (1961a, p. 484),
Bator (1961a, pp. 482–483),
Rothenberg (1960, p. 438), and
Starr (1969, p. 26)—commented on
Koopmans (1957, pp. 1–126, especially 9–16 [1.3 Summation of opportunity sets], 23–35 [1.6 Convex sets and the price implications of optimality], and 35–37 [1.7 The role of convexity assumptions in the analysis])
^
abEkeland, Ivar (1974). "Une estimation a priori en programmation non convexe". Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Séries A et B (in French). 279: 149–151.
ISSN0151-0509.
MR0395844.
The concept of a convex set (i.e., a set containing the segment connecting any two of its points) had repeatedly been placed at the center of economic theory before 1964. It appeared in a new light with the introduction of integration theory in the study of economic competition: If one associates with every agent of an economy an arbitrary set in the commodity space and if one averages those individual sets over a collection of insignificant agents, then the resulting set is necessarily convex. [Debreu appends this footnote: "On this direct consequence of a theorem of A. A. Lyapunov, see
Vind (1964)."] But explanations of the ... functions of prices ... can be made to rest on the convexity of sets derived by that averaging process. Convexity in the commodity space obtained by aggregation over a collection of insignificant agents is an insight that economic theory owes ... to integration theory. [Italics added]
Arrow, Kenneth J.;
Hahn, Frank H. (1980) [1971]. General competitive analysis. Advanced Textbooks in Economics. Vol. 12 (reprint of San Francisco, CA: Holden-Day, Inc. Mathematical Economics Texts 6 ed.). Amsterdam: North-Holland.
ISBN0-444-85497-5.
MR0439057.
Aubin, Jean-Pierre (2007). "14.2 Duality in the case of non-convex integral criterion and constraints (especially 14.2.3 The Shapley–Folkman theorem, pages 463–465)". Mathematical methods of game and economic theory (Reprint with new preface of 1982 North-Holland revised English ed.). Mineola, NY: Dover Publications.
ISBN978-0-486-46265-3.
MR2449499.
Bator, Francis M. (October 1961a). "On convexity, efficiency, and markets". The Journal of Political Economy. 69 (5): 480–483.
doi:
10.1086/258540.
JSTOR1828537.
Bator, Francis M. (October 1961b). "On convexity, efficiency, and markets: Rejoinder". Journal of Political Economy. 69 (5): 489.
doi:
10.1086/258542.
JSTOR1828539.
Bertsekas, Dimitri P. (1999). "5.1.6 Separable problems and their geometry". Nonlinear Programming (Second ed.). Cambridge, Mass.: Athena Scientific. pp. 494–498.
ISBN1-886529-00-0.
Bertsekas, Dimitri P. (1996). "5.6 Large scale separable integer programming problems and the exponential method of multipliers". Constrained optimization and Lagrange multiplier methods. Belmont, Mass.: Athena Scientific.
ISBN1-886529-04-3.
MR0690767. Reprint of (1982) Academic Press.
Borwein, J. M.; O'Brien, R. C. (1978). "Cancellation characterizes convexity". Nanta Mathematica (Nanyang University). 11: 100–102.
ISSN0077-2739.
MR0510842.
Cassels, J. W. S. (1975). "Measures of the non-convexity of sets and the Shapley–Folkman–Starr theorem". Mathematical Proceedings of the Cambridge Philosophical Society. 78 (3): 433–436.
doi:
10.1017/S0305004100051884.
MR0385711.
Cassels, J. W. S. (1981). "Appendix A Convex sets". Economics for mathematicians. London Mathematical Society lecture note series. Vol. 62. Cambridge, UK: Cambridge University Press.
ISBN0-521-28614-X.
MR0657578.
Debreu, Gérard (March 1991). "The Mathematization of economic theory". The American Economic Review. 81 (Presidential address delivered at the 103rd meeting of the American Economic Association, 29 December 1990, Washington, DC): 1–7.
JSTOR2006785.
Ekeland, Ivar (1999) [1976]. "Appendix I: An a priori estimate in convex programming". In Ekeland, Ivar;
Temam, Roger (eds.). Convex analysis and variational problems. Classics in Applied Mathematics. Vol. 28 (Corrected reprinting of the North-Holland ed.). Philadelphia: Society for Industrial and Applied Mathematics (SIAM). pp. 357–373.
ISBN0-89871-450-8.
MR1727362.
Farrell, M. J. (October 1961a). "On Convexity, efficiency, and markets: A Reply". Journal of Political Economy. 69 (5): 484–489.
doi:
10.1086/258541.
JSTOR1828538.
Farrell, M. J. (October 1961b). "The Convexity assumption in the theory of competitive markets: Rejoinder". Journal of Political Economy. 69 (5): 493.
doi:
10.1086/258544.
JSTOR1828541.
Green, Jerry; Heller, Walter P. (1981). "1 Mathematical analysis and convexity with applications to economics". In
Arrow, Kenneth Joseph; Intriligator, Michael D. (eds.). Handbook of mathematical economics. Handbooks in Economics. Vol. 1. Amsterdam: North-Holland Publishing. pp. 15–52.
doi:
10.1016/S1573-4382(81)01005-9.
ISBN0-444-86126-2.
MR0634800.
Guesnerie, Roger (1989). "First-best allocation of resources with nonconvexities in production". In Cornet, Bernard; Tulkens, Henry (eds.). Contributions to Operations Research and Economics: The twentieth anniversary of CORE (Papers from the symposium held in Louvain-la-Neuve, January 1987). Cambridge, Mass.: MIT Press. pp. 99–143.
ISBN0-262-03149-3.
MR1104662.
Hildenbrand, Werner (1974). Core and equilibria of a large economy. Princeton studies in mathematical economics. Vol. 5. Princeton, NJ: Princeton University Press.
ISBN978-0-691-04189-6.
MR0389160.
Hiriart-Urruty, Jean-Baptiste;
Lemaréchal, Claude (1993). "XII Abstract duality for practitioners". Convex analysis and minimization algorithms, Volume II: Advanced theory and bundle methods. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 306. Berlin: Springer-Verlag. pp. 136–193 (and bibliographical comments on pp. 334–335).
ISBN3-540-56852-2.
MR1295240.
Ichiishi, Tatsuro (1983). Game theory for economic analysis. Economic theory, econometrics, and mathematical economics. New York: Academic Press [Harcourt Brace Jovanovich, Publishers].
ISBN0-12-370180-5.
MR0700688.
Koopmans, Tjalling C. (October 1961). "Convexity assumptions, allocative efficiency, and competitive equilibrium". The Journal of Political Economy. 69 (5): 478–479.
doi:
10.1086/258539.
JSTOR1828536.
Lemaréchal, Claude (April 1973). Utilisation de la dualité dans les problémes non convexes [Use of duality for non–convex problems] (Report) (in French). Domaine de Voluceau,
Rocquencourt,
Le Chesnay, France:
IRIA (now INRIA), Laboratoire de recherche en informatique et automatique.
Mas-Colell, Andreu (1985). "1.L Averages of sets". The Theory of general economic equilibrium: A differentiable approach. Econometric Society monographs. Vol. 9. Cambridge University Press.
ISBN0-521-26514-2.
MR1113262.
Mas-Colell, Andreu; Whinston, Michael D.; Green, Jerry R. (1995). "17.1 Large economies and nonconvexities". Microeconomic theory. Oxford University Press.
ISBN978-0-19-507340-9.
Puri, Madan L.; Ralescu, Dan A. (1985). "Limit theorems for random compact sets in Banach space". Mathematical Proceedings of the Cambridge Philosophical Society. 97 (1): 151–158.
Bibcode:
1985MPCPS..97..151P.
doi:
10.1017/S0305004100062691.
MR0764504.
Rothenberg, Jerome (October 1960). "Non-convexity, aggregation, and Pareto optimality". The Journal of Political Economy. 68 (5): 435–468.
doi:
10.1086/258363.
JSTOR1830308.
Rothenberg, Jerome (October 1961). "Comments on non-convexity". Journal of Political Economy. 69 (5): 490–492.
doi:
10.1086/258543.
JSTOR1828540.
Salanié, Bernard (2000). "7 Nonconvexities". Microeconomics of market failures. Cambridge, Mass.: MIT Press. pp. 107–125.
ISBN0-262-19443-0. English translation of the (1998) French Microéconomie: Les défaillances du marché (Economica, Paris)
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.
doi:
10.2307/1909201.
JSTOR1909201.
Starr, Ross M. (1997). "8 Convex sets, separation theorems, and non-convex sets in R (new chapters 22 and 25–26 in (2011) second ed.)". General equilibrium theory: An introduction (1st ed.). Cambridge, UK: Cambridge University Press.
ISBN0-521-56473-5.
MR1462618.
Tardella, Fabio (1990). "A new proof of the Lyapunov convexity theorem". SIAM Journal on Control and Optimization. 28 (2): 478–481.
doi:
10.1137/0328026.
MR1040471.
Trockel, Walter (1984). Market demand: An analysis of large economies with nonconvex preferences. Lecture Notes in Economics and Mathematical Systems. Vol. 223. Berlin: Springer-Verlag.
ISBN3-540-12881-6.
MR0737006.
Vind, Karl (May 1964). "Edgeworth-allocations in an exchange economy with many traders". International Economic Review. 5 (2): 165–177.
doi:
10.2307/2525560.
JSTOR2525560.
Wold, Herman; Juréen, Lars (in association with Wold) (1953). "8 Some further applications of preference fields (pp. 129–148)". Demand analysis: A study in econometrics. Wiley publications in statistics. New York: John Wiley and Sons.
MR0064385.
External links
Anderson, Robert M. (March 2005).
"1 The Shapley–Folkman theorem"(PDF). Economics 201B: Nonconvex preferences and approximate equilibria. Berkeley, Calif.: Economics Department, University of California, Berkeley. pp. 1–5. Retrieved 15 January 2011.
Starr, Ross M. (May 2007).
"Shapley–Folkman theorem"(PDF). pp. 1–3. (Draft of article for the second edition of New Palgrave Dictionary of Economics). Retrieved 15 January 2011.