TheShapley–Folkman lemma is a result inconvex geometry that describes theMinkowski addition ofsets in avector space. The lemma may be intuitively understood as saying that, if the number of summed sets exceeds thedimension of the vector space, then their Minkowski sum is approximately convex.^[1][2] It is named after mathematiciansLloyd Shapley andJon Folkman, but was first published by the economistRoss M. Starr.

Related results provide more refined statements about how close the approximation is. For example, theShapley–Folkman theorem provides anupper bound on thedistance between any point in the Minkowski sum and itsconvex hull. This upper bound is sharpened by theShapley–Folkman–Starr theorem (alternatively,Starr's corollary).^[3]

The Shapley–Folkman lemma has applications ineconomics,optimization andprobability theory.^[3] In economics, it can be used to extend results proved forconvex preferences to non-convex preferences. In optimization theory, it can be used to explain the successful solution of minimization problems that are sums of manyfunctions.^[4][5] In probability, it can be used to prove alaw of large numbers forrandom sets.^[6]

Aset is said to beconvex if everyline segment joining two of its points is asubset in the set. The soliddisk${\displaystyle \bullet }$ is a convex set, but thecircle${\displaystyle \circ }$ is not, because the line segment joining two distinct points${\displaystyle \oslash }$ is not a subset of the circle.^[7] Theconvex hull of a set${\displaystyle Q}$ is the smallest convex set that contains${\displaystyle Q}$.^[8]

Minkowski addition is an operation on sets that forms the set of sums ofmembers of the sets, with one member from each set.^[9] For example, adding the set consisting of theintegers zero and one to itself yields the set consisting of zero, one, and two:$${\displaystyle \{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.}$$ This subset of the integers${\displaystyle \{0,1,2\}}$ is contained in theinterval ofreal numbers${\displaystyle [0,2]}$, which is its convex hull. The Shapley–Folkman lemma implies that every point in${\displaystyle [0,2]}$ is the sum of an integer from${\displaystyle \{0,1\}}$ and a real number from${\displaystyle [0,1]}$: to get the convex hull of the Minkowski sum of${\displaystyle \{0,1\}}$ with itself, only one of the summands needs to be replaced by its convex hull.^[10]

The non-convex set${\displaystyle \{0,1\}}$ and its convex hull${\displaystyle [0,1]}$ are atHausdorff distance${\displaystyle \frac{1}{2}}$ from each other,and this distance remains the same for the non-convex set${\displaystyle \{0,1,2\}}$ and its convex hull${\displaystyle [0,2]}$. In both cases the convex hull contains points such as${\displaystyle \frac{1}{2}}$ that are at distance${\displaystyle \frac{1}{2}}$ from the members of the non-convex set. In this example, the Minkowski sum operation does not decrease the distance between the sum and its convex hull. But when summing is replaced byaveraging, by scaling the sum by the number of terms in the sum, the distance between the scaled Minkowski sum and its convex hull does go down. The distance between the average Minkowski sum$${\displaystyle \frac{1}{2}\left(\{0,1\}+\{0,1\}\right)=\left\{0,\frac{1}{2},1\right\}}$$and its convex hull${\displaystyle [0,1]}$ is only${\displaystyle \frac{1}{4}}$, which is half the distance${\displaystyle \frac{1}{2}}$ between itssummand${\displaystyle \{0,1\}}$ and its convex hull${\displaystyle [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. This reduction in distance can be stated more formally as theShapley–Folkman theorem andShapley–Folkman–Starr theorem, as consequences of the Shapley–Folkman lemma.^[10]

The Shapley–Folkman lemma depends upon the following definitions and results fromconvex geometry.

Arealvector space of two dimensions can be given aCartesian coordinate system in which every point is identified by anordered pair of real numbers, called "coordinates", which are conventionally denoted by${\displaystyle x}$ and${\displaystyle y}$. Two points in the Cartesian plane can beadded coordinate-wise:$${\displaystyle (x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2);}$$further, a point can bemultiplied by each real number${\displaystyle \lambda }$ coordinate-wise:$${\displaystyle \lambda (x,y)=(\lambda x,\lambda y).}$$

More generally, any real vector space of (finite) dimension${\displaystyle D}$ can be viewed as theset of all${\displaystyle D}$-tuples of${\displaystyle D}$ real numbers${\displaystyle (x_1,x_2,\dots ,x_D)}$ on which two operations are defined:vector addition andmultiplication 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.^[11]

In aconvex set Q, theline segment connecting any two of its points is a subset of Q.

In anon-convex set Q, a point in someline-segment joining two of its points is not a member of Q.

Line segments test whether a subset isconvex.

In a real vector space, anon-empty set${\displaystyle Q}$ is defined to beconvex if, for each pair of its points, every point on theline segment that joins them is still in${\displaystyle Q}$. For example, a soliddisk ${\displaystyle \bullet }$ is convex but acircle ${\displaystyle \circ }$ is not, because it does not contain a line segment joining opposite points.^[7] A solidcube is convex; however, anything that is hollow or dented, for example, acrescent shape, is non-convex. Theempty set is convex, either by definition^[12] orvacuously.^[13]

More formally, a set${\displaystyle Q}$ is convex if, for all points${\displaystyle q_1}$ and${\displaystyle q_2}$ in${\displaystyle Q}$ and for every real number${\displaystyle \lambda }$ in theunit interval${\displaystyle [0,1]}$, the point$${\displaystyle (1-\lambda )q_1+\lambda q_2}$$is amember of${\displaystyle Q}$. Bymathematical induction, a set${\displaystyle Q}$ is convex if and only if everyconvex combination of members of${\displaystyle Q}$ also belongs to${\displaystyle Q}$. By definition, aconvex combination of indexed points${\displaystyle v_1,v_2,\dots v_D}$ of a vector space is any weighted average${\displaystyle {\lambda }_1{v}_1+{\lambda }_2{v}_2+\cdots +{\lambda }_D{v}_D}$ for indexed real numbers${\displaystyle {\lambda }_1,{\lambda }_2,\dots {\lambda }_D}$ satisfying the equation${\displaystyle {\lambda }_1+{\lambda }_2+\cdots +{\lambda }_D=1}$.^[14]

The definition of a convex set implies that theintersection 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 twodisjoint sets is the empty set, which is convex.^[12]

For every subset${\displaystyle Q}$ of a real vector space, itsconvex hull${\displaystyle \mathrm{conv}Q}$ is theminimal convex set that contains${\displaystyle Q}$. Thus${\displaystyle \mathrm{conv}Q}$ is the intersection of all the convex sets thatcover${\displaystyle Q}$.^[8] The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in${\displaystyle Q}$.^[15] For example, the convex hull of the set ofintegers${\displaystyle \{0,1\}}$ is the closedinterval ofreal numbers${\displaystyle [0,1]}$, which has the maximum and minimum of the given set as its endpoints.^[10] The convex hull of theunit circle is the closedunit disk, which contains the unit circle and its interior.^[16]

In any vector space (or algebraic structure with addition),${\displaystyle X}$, theMinkowski sum of two non-empty sets${\displaystyle A,B\subseteq X}$ is defined to be the element-wise operation^[17]$${\displaystyle A+B=\{x+y\mid x\in A,y\in B\}.}$$ 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$\sum _{n=1}^N{Q}_n=Q_1+Q_2+\dots +Q_N.$ By the principle of induction,^[18]$${\displaystyle \sum _{n=1}^N{Q}_n=\left\{\sum _{n=1}^N{q}_n|q_n\in Q_n,1\le n\le N\right\}.}$$

Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets${\displaystyle A,B\subseteq X}$ of a real vector space,${\displaystyle X}$, theconvex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,$${\displaystyle \mathrm{conv}(A+B)=(\mathrm{conv}A)+(\mathrm{conv}B).}$$And by induction it follows that$${\displaystyle \mathrm{conv}\sum _{n=1}^N{Q}_n=\sum _{n=1}^N\mathrm{conv}{Q}_n}$$for any${\displaystyle N\in \mathbb{N}}$ and non-empty subsets${\displaystyle Q_n\in X,1\le n\le N}$.^[19][20]

In the following statements,${\displaystyle D}$ and${\displaystyle D}$ represent positive integers.${\displaystyle D}$ is the dimension of the ambient space${\displaystyle {\mathbb{R}}^D}$.

${\displaystyle Q_1,\dots ,Q_N}$ represent nonempty, bounded subsets of${\displaystyle {\mathbb{R}}^D}$. They are also called "summands".${\displaystyle N}$ is the number of summands.

${\displaystyle Q=\sum _{n=1}^N{Q}_n}$ denotes the Minkowski sum of the summands.

The variable${\displaystyle x}$ is used to represent an arbitrary vector in${\displaystyle \mathrm{conv}Q}$.

Because the convex hull and Minkowski sum operations can always be interchanged, as${\displaystyle \mathrm{conv}Q=\sum _{n=1}^N\mathrm{conv}(Q_n)}$, it follows that for every${\displaystyle x\in \mathrm{conv}Q}$, there exist elements${\displaystyle q_n\in \mathrm{conv}{Q}_n}$ such that${\displaystyle \sum _{n=1}^N{q}_n=x}$. TheShapley–Folkman lemma refines this statement.^[21]

For example, every point in${\displaystyle [0,2]=[0,1]+[0,1]=\mathrm{conv}\{0,1\}+\mathrm{conv}\{0,1\}}$ is the sum of an element in${\displaystyle \{0,1\}}$ and an element in${\displaystyle [0,1]}$.^[10]

Shuffling indices if necessary, this means that every point in${\displaystyle \mathrm{conv}Q}$ can be decomposed as

$${\displaystyle x=\sum _{n=1}^D{q}_n+\sum _{n=D+1}^N{q}_n}$$

where${\displaystyle q_n\in \mathrm{conv}{Q}_n}$ for${\displaystyle 1\le n\le D}$ and${\displaystyle q_n\in {\mathrm{Q}}_n}$ for${\displaystyle D+1\le n\le N}$. Note that the reindexing depends on the point${\displaystyle x}$.^[22]

The lemma may be stated succinctly as

$${\displaystyle \mathrm{conv}\left(\sum _{n=1}^N{Q}_n\right)\subseteq \bigcup _{I\subseteq \{1,2,\dots N\}:|I|=D}\left(\sum _{n\in I}\mathrm{conv}{Q}_n+\sum _{n\notin I}{Q}_n\right).}$$

In particular, the Shapley–Folkman lemma requires the vector space to be finite-dimensional.^[23]

Shapley and Folkman used their lemma to prove the following theorem, which quantifies the difference between${\displaystyle Q}$ and${\displaystyle \mathrm{conv}Q}$ usingHausdorff distance. Hausdorff distances measure how close two sets are. For two sets${\displaystyle X}$ and${\displaystyle Y}$, the Hausdorff distance is, intuitively, the smallest amount by which each must be expanded to cover the other. More formally,if the distance from a point${\displaystyle x}$ to a set${\displaystyle Y}$ is defined as theinfimum of pairwise distances,$${\displaystyle d(x,Y)=\underset{y\in Y}{inf}\Vert x-y\Vert ,}$$then let${\displaystyle X_{\epsilon }}$ denote the set of all points withindistance${\displaystyle \epsilon }$ of${\displaystyle X}$; equivalently this is closure of the Minkowski sum of${\displaystyle X}$ with a ball of radius${\displaystyle \epsilon }$. Then for${\displaystyle X\subset Y}$, the Hausdorff distance is^[24]$${\displaystyle d_{\mathrm{H}}(X,Y)=inf\{\epsilon \mid X_{\epsilon }\supset Y\}.}$$

The Shapley–Folkman theorem quantifies how close to convexity${\displaystyle Q}$ is by upper-bounding its Hausdorff distance to${\displaystyle \mathrm{conv}Q}$, using the circumradii of its constituent sets. For anybounded set${\displaystyle S\subset {\mathbb{R}}^D,}$ define its circumradius${\displaystyle \mathrm{rad}S}$ to be thesmallest radius of a ball containing it. More formally, letting${\displaystyle x}$ denote the center of the smallest enclosing ball, it can be defined as^[25]$${\displaystyle \mathrm{rad}S=inf\{\epsilon \mid \mathrm{\exists }x\in {\mathbb{R}}^N:\{x{\}}_{\epsilon }\supset S\}.}$$ With this notation in place, the Shapley–Folkman theorem can be stated as:

Here the notation$\sum _{maxD}$ means "the sum of the${\displaystyle D}$ largest terms". This upper bound depends on the dimension of ambient space and the shapes of the summands, but not on the number of summands.^[28]

The Shapley–Folkman theorem can be strengthened by replacing the circumradius of the terms in a Minkowski by a smaller value, theinner radius, which intuitively measures the radius of the holes in a set rather than the radius of a set.Define the inner radius${\displaystyle r(S)}$ of a bounded subset${\displaystyle S\subset {\mathbb{R}}^D}$ to be the infimum of${\displaystyle r}$ such that, for any${\displaystyle x\in \mathrm{conv}S}$, there exists a ball${\displaystyle B}$ of radius${\displaystyle r}$ such that${\displaystyle x\in \mathrm{conv}(S\cap B)}$.^[29]

There have been many proofs of these results, from the original,^[29] to the laterArrow andHahn,^[31]Cassels,^[32] Schneider,^[33] etc. An abstract and elegant proof byEkeland^[34] has been extended by Artstein.^[35] Different proofs have also appeared in unpublished papers.^[2][36] An elementary proof of the Shapley–Folkman lemma can be found in the book byBertsekas, together with applications in estimating the duality gap in separable optimization problems and zero-sum games.^[37]

Usual proofs of these results are nonconstructive: they establish only theexistence of the representation, but do not provide analgorithm for computing the representation. In 1981, Starr published aniterative algorithm for a less sharp version of the Shapley–Folkman–Starr theorem.^[28]

The following proof of Shapley–Folkman lemma is fromZhou (1993). The proof idea is to lift the representation of${\displaystyle x}$ from${\displaystyle {\mathbb{R}}^D}$to${\displaystyle {\mathbb{R}}^{D+N}}$, useCarathéodory's theorem for conic hulls, then drop back to${\displaystyle {\mathbb{R}}^D}$.^[38]

The following "probabilistic" proof of Shapley–Folkman–Starr theorem is fromCassels (1975).^[32]

We can interpret${\displaystyle \mathrm{conv}S}$ in probabilistic terms:${\displaystyle \mathrm{\forall }x\in \mathrm{conv}S}$, since${\displaystyle x=\sum w_n{q}_n}$ for some${\displaystyle q_n\in S}$, we can define a random vector${\displaystyle X}$, finitely supported in${\displaystyle S}$, such that${\displaystyle Pr(X=q_n)=w_n}$, and${\displaystyle x=\mathbb{E}[X]}$.

Then, it is natural to consider the "variance" of a set${\displaystyle S}$ as$${\displaystyle Var(S):=\underset{x\in \mathrm{conv}S}{sup}\underset{\mathbb{E}[X]=x,X\text{ is finitely supported in }S}{inf}Var[X]}$$With that,${\displaystyle d(S,\mathrm{conv}(S){)}^2\le Var(S)\le r(S)\le rad(S)}$.

The lemma ofLloyd Shapley andJon Folkman was first^[38] published by the economistRoss M. Starr, who was investigating the existence ofeconomic equilibria while studying withKenneth Arrow. In his paper, Starr studied aconvexified 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.^[1]

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 largeeconomies 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", wroteRoger Guesnerie.^[39]

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 ineconomics, inmathematical optimization, and inprobability theory; in each of these three mathematical sciences, non-convexity is an important feature of applications.

Ineconomics, a consumer'spreferences 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, anindifference 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'spreference set (relative to an indifference curve) is theunion of the indifference curve and all the commodity baskets that the consumer prefers over the indifference curve. A consumer'spreferences areconvex if all such preference sets are convex.^[40]

An optimal basket of goods occurs where the budget-linesupports 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 afunction of the prices, and this function is called the consumer'sdemand. 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.^[41]

However, if a preference set isnon-convex, then some prices determine a budget-line that supports twoseparate 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 agriffin)! Thus, the zoo-keeper's preferences are non-convex: The zoo-keeper prefers having either animal to having any strictly convex combination of both.^[42]

When the consumer's preference set is non-convex, then (for some prices) the consumer's demand is notconnected; a disconnected demand implies some discontinuous behavior by the consumer, as discussed byHarold 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.^[43]

The difficulties of studying non-convex preferences were emphasized byHerman Wold^[44] and again byPaul Samuelson, who wrote that non-convexities are "shrouded in eternal darkness",^[45][a] according to Diewert.^[46]

Nonetheless, non-convex preferences were illuminated from 1959 to 1961 by a sequence of papers inThe Journal of Political Economy (JPE). The main contributors were Farrell,^[47] Bator,^[48]Koopmans,^[49] and Rothenberg.^[50] In particular, Rothenberg's paper discussed the approximate convexity of sums of non-convex sets.^[51] TheseJPE-papers stimulated a paper byLloyd Shapley andMartin Shubik, which considered convexified consumer-preferences and introduced the concept of an "approximate equilibrium".^[52] TheJPE-papers and the Shapley–Shubik paper influenced another notion of "quasi-equilibria", due toRobert Aumann.^[53][54]

Previous publications onnon-convexity and economics were collected in an annotated bibliography byKenneth Arrow. He gave the bibliography toStarr, who was then an undergraduate enrolled in Arrow's (graduate) advanced mathematical-economics course.^[55] 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, theaggregate demand was the sum of convex hulls of the consumers' demands. Starr's ideas interested the mathematiciansLloyd Shapley andJon Folkman, who proved theireponymous 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${\displaystyle p_{\mathrm{o}\mathrm{p}\mathrm{t}}}$ with the following properties:

• For each quasi-equilibrium's prices${\displaystyle p_{\mathrm{o}\mathrm{p}\mathrm{t}}}$, all consumers can choose optimal baskets (maximally preferred and meeting their budget constraints).
• At quasi-equilibrium prices${\displaystyle p_{\mathrm{o}\mathrm{p}\mathrm{t}}}$ 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: anupper bound on thedistance 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.^[56]

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".^[57]

Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used in economic theory.Roger Guesnerie summarized their economic implications: "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, preference nonconvexities do not destroy the standard results".^[58] "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Guesnerie.^[39] The topic ofnon-convex sets in economics has been studied by manyNobel laureates: Arrow (1972),Robert Aumann (2005),Gérard Debreu (1983),Tjalling Koopmans (1975),Paul Krugman (2008), andPaul Samuelson (1970); the complementary topic ofconvex sets in economics has been emphasized by these laureates, along withLeonid Hurwicz,Leonid Kantorovich (1975), andRobert Solow (1987).^[59] The Shapley–Folkman–Starr results have been featured in the economics literature: inmicroeconomics,^[60] in general-equilibrium theory,^[61] inpublic economics^[62] (includingmarket failures),^[63] as well as ingame theory,^[64] inmathematical economics,^[65] and inapplied mathematics (for economists).^[66][67] The Shapley–Folkman–Starr results have also influenced economics research usingmeasure andintegration theory.^[68]

The Shapley–Folkman lemma has been used to explain why largeminimization problems withnon-convexities can be nearly solved (withiterative methods whose convergence proofs are stated for onlyconvex problems). The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.^[69]

Nonlinear optimization relies on the following definitions forfunctions:

• Thegraph of a function f is the set of the pairs ofarguments x and function evaluations f(x)

Graph(f) ={(x, f(x))}

• Theepigraph of areal-valued function f is the set of pointsabove the graph

Epi(f) ={ (x, u) : f(x) ≤ u }.

• A real-valued function is defined to be aconvex function if its epigraph is a convex set.^[70]

For example, thequadratic function f(x) = x² is convex, as is theabsolute value function g(x) = |x|. However, thesine function (pictured) is non-convex on theinterval (0, π).

In many optimization problems, theobjective function f isseparable: that is,f is the sum ofmany summand-functions, each of which has its own argument:$${\displaystyle f(x)=f((x_1,\dots ,x_N))=\sum f_n(x_n).}$$

For example, problems oflinear optimization are separable. Given a separable problem with an optimal solution, fix an optimal solution$${\displaystyle x_{min}=(x_1,\dots ,x_N{)}_{min}}$$with the minimum value${\displaystyle f(x_{min})}$. For this separable problem, consider an optimal solution${\displaystyle (x_{min},f(x_{min}))}$ to theconvexified problem, where convex hulls are taken of the graphs of the summand functions. Such an optimal solution is thelimit of a sequence^[b] of points in the convexified problem$${\displaystyle (x_j,f(x_j))\in \sum \mathrm{conv}\mathrm{Graph}(f_n).}$$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.^[4]

This analysis was published byIvar 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 mathematicianClaude Lemaréchal was surprised by his success withconvex minimizationmethods on problems that were known to be non-convex; forminimizing nonlinear problems, a solution of thedual problem need not provide useful information for solving the primal problem, unless the primal problem be convex and satisfy aconstraint 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.^[72][4][73] Ekeland's analysis explained the success of methods of convex minimization onlarge andseparable 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][73][74][c]} The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.^{[4][5][66][69]}

Convex sets are often studied withprobability theory. Each point in the convex hull of a (non-empty) subset Q of a finite-dimensional space is theexpected value of asimplerandom vector that takes its values in Q, as a consequence ofCarathé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.^[77] In the other direction, probability theory provides tools to examine convex sets generally and the Shapley–Folkman–Starr results specifically.^[78] The Shapley–Folkman–Starr results have been widely used in theprobabilistic theory of random sets,^[79] for example, to prove alaw of large numbers,^[6][80] acentral limit theorem,^[80][81] and alarge-deviations principle.^[82] These proofs ofprobabilistic limit theorems used the Shapley–Folkman–Starr results to avoid the assumption that all the random sets be convex.

Aprobability measure is a finitemeasure, and the Shapley–Folkman lemma has applications in non-probabilistic measure theory, such as the theories ofvolume and ofvector measures. The Shapley–Folkman lemma enables a refinement of theBrunn–Minkowski inequality, which bounds the volume of sums in terms of the volumes of their summand-sets.^[83] The volume of a set is defined in terms of theLebesgue measure, which is defined on subsets ofEuclidean space. In advanced measure-theory, the Shapley–Folkman lemma has been used to proveLyapunov's theorem, which states that therange of avector measure is convex.^[84] Here, the traditional term "range" (alternatively, "image") is the set of values produced by the function. Avector measure is a vector-valued generalization of a measure; for example, if p₁ and p₂ areprobability measures defined on the samemeasurable space, then theproduct function p₁ p₂ is a vector measure, where p₁ p₂ is defined for everyevent ω by

(p₁ p₂)(ω)=(p₁(ω), p₂(ω)).

Lyapunov's theorem has been used ineconomics,^[53][85] in ("bang-bang")control theory, and instatistical theory.^[86] Lyapunov's theorem has been called acontinuous counterpart of the Shapley–Folkman lemma,^[3] which has itself been called adiscrete analogue of Lyapunov's theorem.^[87]

• Starr, Ross M. (September 2009)."8 Convex sets, separation theorems, and non-convex sets in R^N (Section 8.2.3 Measuring non-convexity, the Shapley–Folkman theorem)"(PDF).General Equilibrium Theory: An Introduction. pp. 3–6.doi:10.1017/CBO9781139174749.ISBN 9781139174749.MR 1462618. (Draft of second edition, from Starr's course at the Economics Department of the University of California, San Diego). Archived fromthe original(PDF) on 1 July 2010. Retrieved15 January 2011.
• Starr, Ross M. (May 2007)."Shapley–Folkman theorem"(PDF). pp. 1–3. (Draft of article for the second edition ofNew Palgrave Dictionary of Economics). Retrieved15 January 2011.

• Additive combinatorics
• Convex hulls
• Convex geometry
• Convex optimization
• Geometric transversal theory
• General equilibrium theory
• Lloyd Shapley
• Sumsets
• Theorems in geometry

• Articles with short description
• Short description is different from Wikidata
• Use dmy dates from October 2020
• CS1 French-language sources (fr)
• CS1 maint: ignored ISBN errors
• Good articles