# Shapley–Folkman lemma

The **Shapley–Folkman lemma** is a result in convex geometry with applications in mathematical economics that describes the Minkowski addition of sets in a vector space. *Minkowski addition* is defined as the addition of the sets' members: for example, adding the set consisting of the integers zero and one to itself yields the set consisting of zero, one, and two:

- {0, 1} + {0, 1} = {0 + 0, 0 + 1, 1 + 0, 1 + 1} = {0, 1, 2}.

The Shapley–Folkman lemma and related results provide an affirmative answer to the question, "Is the sum of many sets close to being convex?"^{[2]} A set is defined to be *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 Shapley–Folkman lemma suggests that if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum is approximately convex.^{[1]}

The Shapley–Folkman lemma was introduced as a step in the proof of the **Shapley–Folkman theorem**, which states an upper bound on the distance between the Minkowski sum and its convex hull. 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.
The theorem's bound on the distance depends on the dimension *D* and on the shapes of the summand-sets, but *not* on the number of summand-sets *N*, when *N* > *D*.
The shapes of a subcollection of only *D* summand-sets determine the bound on the distance between the Minkowski *average* of *N* sets

- Template:Frac (
*Q*_{1}+*Q*_{2}+ ... +*Q*_{N})

and its convex hull. As *N* increases to infinity, the bound decreases to zero (for summand-sets of uniformly bounded size).^{[3]} The Shapley–Folkman theorem's upper bound was decreased by **Starr's corollary** (alternatively, the **Shapley–Folkman–Starr theorem**).

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-equilbrium 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.^{[4]} The topic of non-convex sets in economics has been studied by many Nobel laureates, besides Lloyd Shapley who won the prize in 2012: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008), and Paul Samuelson (1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with Leonid Hurwicz, Leonid Kantorovich (1975), and Robert Solow (1987).

The Shapley–Folkman lemma has applications also in optimization and probability theory.^{[3]} In optimization theory, the Shapley–Folkman lemma has been used to explain the successful solution of minimization problems that are sums of many functions.^{[5]}^{[6]} The Shapley–Folkman lemma has also been used in proofs of the "law of averages" for random sets, a theorem that had been proved for only convex sets.^{[7]}

## Introductory example

For example, 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].^{[8]}

The distance between the convex interval [0, 2] and the non-convex set {0, 1, 2} equals one-half

- 1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

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.^{[8]}

## Preliminaries

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

### Real vector spaces

A real vector 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

- (
*x*_{1},*y*_{1}) + (*x*_{2},*y*_{2}) = (*x*_{1}+*x*_{2},*y*_{1}+*y*_{2});

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 *D* can be viewed as the set of all *D*-tuples of *D* real numbers { (*v*_{1}, *v*_{2}, . . . , *v*_{D}) } 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.^{[9]}

### Convex sets

{{#invoke:Multiple image|render}}

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 a subset of *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^{[10]} or vacuously, depending on the author.

More formally, a set *Q* is convex if, for all points *v*_{0} and *v*_{1} in *Q* and for every real number *λ* in the unit interval [0,1], the point

- (1 −
*λ*)*v*_{0}+*λv*_{1}

is a member of *Q*.

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 {*v*_{0}, *v*_{1}, . . . , *v*_{D}} of a vector space is any weighted average *λ*_{0}*v*_{0} + *λ*_{1}*v*_{1} + . . . + *λ*_{D}*v*_{D}, for some indexed set of non-negative real numbers {*λ*_{d}} satisfying the equation *λ*_{0} + *λ*_{1} + . . . + *λ*_{D} = 1.^{[11]}

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.^{[10]}

### 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 cover *Q*. The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in *Q*.^{[12]} 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.^{[8]} The convex hull of the unit circle is the closed unit disk, which contains the unit circle.

### Minkowski addition

In a real vector space, the *Minkowski sum* of two (non-empty) sets *Q*_{1} and *Q*_{2} is defined to be the set *Q*_{1} + *Q*_{2} formed by the addition of vectors element-wise from the summand sets

*Q*_{1}+*Q*_{2}= {*q*_{1}+*q*_{2}:*q*_{1}∈*Q*_{1}and*q*_{2}∈*Q*_{2}}.^{[13]}

For example

- {0, 1} + {0, 1} = {0+0, 0+1, 1+0, 1+1} = {0, 1, 2}.
^{[8]}

By the principle of mathematical induction, the *Minkowski sum* of a finite family of (non-empty) sets

- {
*Q*_{n}:*Q*_{n}≠ Ø and 1 ≤*n*≤*N*}

is the set formed by element-wise addition of vectors

- ∑
*Q*_{n}= {∑*q*_{n}:*q*_{n}∈*Q*_{n}}.^{[14]}

### Convex hulls of Minkowski sums

Minkowski addition behaves well with respect to "*convexification*"—the operation of taking convex hulls. Specifically, for all subsets *Q*_{1} and *Q*_{2} of a real vector space, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,

- Conv(
*Q*_{1}+*Q*_{2}) = Conv(*Q*_{1}) + Conv(*Q*_{2}).

This result holds more generally, as a consequence of the principle of mathematical induction. For each finite collection of sets,

- Conv( ∑
*Q*_{n}) = ∑ Conv(*Q*_{n}).^{[15]}^{[16]}

## Statements

The preceding identity
Conv( ∑ *Q*_{n} ) = ∑ Conv( *Q*_{n} )
implies that
if a point *x* lies in the convex hull of the Minkowski sum of *N* sets

*x*∈ Conv( ∑*Q*_{n})

then *x* lies in the sum of the convex hulls of the summand-sets

*x*∈ ∑ Conv(*Q*_{n}).

By the definition of Minkowski addition, this last expression means that *x* = ∑ *q*_{n} for some selection of points *q*_{n} in the convex hulls of the summand-sets, that is, where each *q*_{n} ∈ Conv(*Q*_{n}). In this representation, the selection of the summand-points *q*_{n} depends on the chosen sum-point *x*.

### Lemma of Shapley and Folkman

For this representation of the point *x*, the **Shapley–Folkman lemma** states that if the dimension *D* is less than the number of summands

*D*<*N*

then convexification is needed for only *D* summand-sets, whose choice depends on *x*: The point has a representation

where *q*_{d} belongs to the convex hull of *Q*_{d} for *D* (or fewer) summand-sets and *q*_{n} belongs to *Q*_{n} itself for the remaining sets. That is,

for some re-indexing of the summand sets; this re-indexing depends on the particular point *x* being represented.^{[17]}

The Shapley–Folkman lemma implies, for example, that every point in [0, 2] is the sum of an integer from {0, 1} and a real number from [0, 1].^{[8]}

#### Dimension of a real vector space

Conversely, the Shapley–Folkman lemma characterizes the dimension of finite-dimensional, real vector spaces. That is, if a vector space obeys the Shapley–Folkman lemma for a natural number *D*, and for no number less than *D*, then its dimension is exactly *D*;^{[18]} the Shapley–Folkman lemma holds for only *finite-dimensional* vector spaces.^{[19]}

### Shapley–Folkman theorem and Starr's corollary

Shapley and Folkman used their lemma to prove their theorem, which bounds the distance between a Minkowski sum and its convex hull, the "*convexified*" sum:

- The
*Shapley–Folkman theorem*states that the squared Euclidean distance from any point in the convexified sum Conv( ∑*Q*_{n}) to the original (unconvexified) sum ∑*Q*_{n}is bounded by the sum of the squares of the*D*largest circumradii of the sets*Q*_{n}(the radii of the smallest spheres enclosing these sets).^{[20]}This bound is independent of the number of summand-sets*N*(if*N*>*D*).^{[21]}

The Shapley–Folkman theorem states a bound on the distance between the Minkowski sum and its convex hull; this distance is zero if and only if the sum is convex. Their bound on the distance depends on the dimension *D* and on the shapes of the summand-sets, but *not* on the number of summand-sets *N*, when *N* > *D*.^{[3]}

The circumradius often exceeds (and cannot be less than) the *inner radius*:^{[22]}

- The
*inner radius*of a set*Q*_{n}is defined to be the smallest number*r*such that, for any point*q*in the convex hull of*Q*_{n}, there is a sphere of radius*r*that contains a subset of*Q*_{n}whose convex hull contains*q*.

Starr used the inner radius to reduce the upper bound stated in the Shapley–Folkman theorem:

*Starr's corollary to the Shapley–Folkman theorem*states that the squared Euclidean distance from any point*x*in the convexified sum Conv( ∑*Q*_{n}) to the original (unconvexified) sum ∑*Q*_{n}is bounded by the sum of the squares of the*D*largest inner-radii of the sets*Q*_{n}.^{[22]}^{[23]}

Starr's corollary states an upper bound on the Euclidean distance between the Minkowski sum of *N* sets and the convex hull of the Minkowski sum; this distance between the sum and its convex hull is a measurement of the non-convexity of the set. For simplicity, this distance is called the "*non-convexity*" of the set (with respect to Starr's measurement). Thus, Starr's bound on the non-convexity of the sum depends on only the *D* largest inner radii of the summand-sets; however, Starr's bound does not depend on the number of summand-sets *N*, when *N* > *D*.
For example, the distance between the convex interval [0, 2] and the non-convex set {0, 1, 2} equals one-half

- 1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

Thus, Starr's bound on the non-convexity of the *average*

- Template:Frac ∑
*Q*_{n}

decreases as the number of summands *N* increases.
For example, the distance between the *averaged* set

- 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].
The shapes of a subcollection of only *D* summand-sets determine the bound on the distance between the *average set* and its convex hull; thus, as the number of summands increases to infinity, the bound decreases to zero (for summand-sets of uniformly bounded size).^{[3]} In fact, Starr's bound on the non-convexity of this average set decreases to zero as the number of summands *N* increases to infinity (when the inner radii of all the summands are bounded by the same number).^{[3]}

### Proofs and computations

The original proof of the Shapley–Folkman lemma established only the existence of the representation, but did not provide an algorithm for computing the representation: Similar proofs have been given by Arrow and Hahn,^{[24]} Cassels,^{[25]} and Schneider,^{[26]} among others. An abstract and elegant proof by Ekeland has been extended by Artstein.^{[27]}^{[28]} Different proofs have appeared in unpublished papers, also.^{[2]}^{[29]} In 1981, Starr published an iterative method for computing a representation of a given sum-point; however, his computational proof provides a weaker bound than does the original result.^{[30]}

## Applications

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.

### Economics

{{#invoke:see also|seealso}}
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.^{[31]}

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.^{[32]}

#### Non-convex preferences

{{#invoke:see also|seealso}}
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.^{[33]}

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.

^{[34]}

The difficulties of studying non-convex preferences were emphasized by Herman Wold^{[35]} and again by Paul Samuelson, who wrote that non-convexities are "shrouded in eternal darkness ...",^{[36]} according to Diewert.^{[37]}

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,^{[38]} Bator,^{[39]} Koopmans,^{[40]} and Rothenberg.^{[41]} In particular, Rothenberg's paper discussed the approximate convexity of sums of non-convex sets.^{[42]} 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".^{[43]} The *JPE*-papers and the Shapley–Shubik paper influenced another notion of "quasi-equilibria", due to Robert Aumann.^{[44]}^{[45]}

#### 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.^{[46]} 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-equilbria*" 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 *p*_{opt} with the following properties:

- For each quasi-equilibrium's prices
*p*_{opt}, all consumers can choose optimal baskets (maximally preferred and meeting their budget constraints).

- At quasi-equilibrium prices
*p*_{opt}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.
^{[47]}

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".

^{[48]}

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".^{[49]} "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Guesnerie.^{[4]} The topic of non-convex sets in economics has been studied by many Nobel laureates: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008), and Paul Samuelson (1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with Leonid Hurwicz, Leonid Kantorovich (1975), and Robert Solow (1987).^{[50]} The Shapley–Folkman–Starr results have been featured in the economics literature: in microeconomics,^{[51]} in general-equilibrium theory,^{[52]}^{[53]} in public economics^{[54]} (including market failures),^{[55]} as well as in game theory,^{[56]} in mathematical economics,^{[57]} and in applied mathematics (for economists).^{[58]}^{[59]} The Shapley–Folkman–Starr results have also influenced economics research using measure and integration theory.^{[60]}

### Mathematical optimization

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]}

#### Preliminaries of optimization theory

Nonlinear optimization relies on the following definitions for functions:

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

- The
*epigraph*of a real-valued function*f*is the set of points*above*the graph

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

- A real-valued function is defined to be a
*convex function*if its epigraph is a convex set.^{[62]}

For example, the quadratic function *f*(*x*) = *x*^{2} is convex, as is the absolute value function *g*(*x*) = |*x*|. However, the sine function (pictured) is non-convex on the interval (0, π).

#### Additive optimization problems

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*( (*x*_{1}, ...,*x*_{N}) ) = ∑*f*_{n}(*x*_{n}).

For example, problems of linear optimization are separable. Given a separable problem with an optimal solution, we fix an optimal solution

*x*_{min}= (*x*_{1}, ...,*x*_{N})_{min}

with the minimum value *f*(*x*_{min}). For this separable problem, we also consider an optimal solution (*x*_{min}, *f*(*x*_{min}) )
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

- (
*x*_{j},*f*(*x*_{j}) ) ∈ ∑ Conv (Graph(*f*_{n}) ).^{[5]}^{[63]}

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 minimization methods on problems that were known to be non-convex; for minimizing nonlinear problems, a solution of the dual problem 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.^{[64]}^{[5]}^{[65]} 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.^{[5]}^{[65]}^{[66]} The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.^{[5]}^{[6]}^{[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 simple random 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*Template:'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,^{[7]}^{[70]} a central limit theorem,^{[70]}^{[71]} and a large-deviations principle.^{[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 *p*_{1} and *p*_{2} are probability measures defined on the same measurable space,
then the product function *p*_{1} *p*_{2} is a vector measure,
where *p*_{1} *p*_{2}
is defined for every event *ω*
by

- (
*p*_{1}*p*_{2})(*ω*)=(*p*_{1}(*ω*),*p*_{2}(*ω*)).

Lyapunov's theorem has been used in economics,^{[44]}^{[75]} in ("bang-bang") control theory, and in statistical theory.^{[76]} Lyapunov's theorem has been called a continuous counterpart of the Shapley–Folkman lemma,^{[3]} which has itself been called a discrete analogue of Lyapunov's theorem.^{[77]}

## Notes

- ↑
^{1.0}^{1.1}^{1.2}^{1.3}^{1.4}Template:Harvtxt - ↑
^{2.0}^{2.1}Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=citation }} - ↑
^{3.0}^{3.1}^{3.2}^{3.3}^{3.4}^{3.5}Template:Harvtxt - ↑
^{4.0}^{4.1}Template:Harvtxt - ↑
^{5.0}^{5.1}^{5.2}^{5.3}^{5.4}Template:Harv: 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. - ↑
^{6.0}^{6.1}Template:Harvtxt acknowledging Template:Harvtxt on page 374 and Template:Harvtxt on page 381:{{#invoke:citation/CS1|citation |CitationClass=book }}

Template:Harvtxt describes an application of Lagrangian dual methods to the scheduling of electrical power plants ("unit commitment problems"), where non-convexity appears because of integer constraints:

{{#invoke:Citation/CS1|citation

|CitationClass=journal

}} - ↑
^{7.0}^{7.1}Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=citation }} - ↑
^{8.0}^{8.1}^{8.2}^{8.3}^{8.4}Template:Harvtxt - ↑ Template:Harvtxt
- ↑
^{10.0}^{10.1}Template:Harvtxt - ↑ Template:Harvtxt, Template:Harvtxt, and Template:Harvtxt
- ↑ Template:Harvtxt and Template:Harvtxt
- ↑ Template:Harvtxt and Template:Harvtxt
- ↑ Template:Harvtxt and Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt credits this result to Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑
^{22.0}^{22.1}Template:Harvtxt - ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt and Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt: "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."
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation
|CitationClass=journal
}}
Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}

- ↑ Template:Harvtxt:

{{#invoke:Citation/CS1|citationIt 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.

|CitationClass=journal

}}"Eternal darkness" describes the Hell of John Milton's

*Paradise Lost*, whose concavity is compared to the Serbonian Bog in Book II, lines 592–594:

Milton's description of concavity serves as the literary epigraph prefacing chapter seven of Template:Harvtxt, "Markets with non-convex preferences and production", which presents the results of Template:Harvtxt.A gulf profound as that Serbonian Bog

Betwixt Damiata and Mount Casius old,

Where Armies whole have sunk. - ↑ Template:Harvtxt
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }} {{#invoke:Citation/CS1|citation |CitationClass=journal }} {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:Citation/CS1|citation |CitationClass=journal }} {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ {{#invoke:Citation/CS1|citation
|CitationClass=journal
}}
Template:Harvtxt and others—for example, Template:Harvtxt and Template:Harvtxt, Template:Harvtxt, Template:Harvtxt, and Template:Harvtxt—commented on Template:Harvtxt:

{{#invoke:citation/CS1|citation |CitationClass=book }}

- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }} ({{#invoke:Citation/CS1|citation |CitationClass=journal }})
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑
^{44.0}^{44.1}Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }} Template:Harvtxt uses results from Template:Harvs:{{#invoke:Citation/CS1|citation |CitationClass=journal }}

{{#invoke:Citation/CS1|citation |CitationClass=journal }}

- ↑ Taking the convex hull of non-convex preferences had been discussed earlier by Template:Harvtxt and by Template:Harvtxt, according to Template:Harvtxt.
- ↑
^{46.0}^{46.1}Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }} - ↑ Template:Harvtxt. Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt
- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation
|CitationClass=book
}}
Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}

- ↑ Template:Harvtxt
Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}

Template:Harvtxt: {{#invoke:citation/CS1|citation

|CitationClass=book

}} - ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation
|CitationClass=book
}}
Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}

- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑
^{58.0}^{58.1}Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }} - ↑ Template:Harvtxt
- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑
^{61.0}^{61.1}Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }} - ↑ Template:Harvtxt
- ↑
The limit of a sequence is a member of the closure of the original set, which is the smallest closed set that contains the original set. The Minkowski sum of two closed sets need not be closed, so the following inclusion can be strict
- Clos(P) + Clos(Q) ⊆ Clos( Clos(P) + Clos(Q) );

*convex*closed summand-sets, according to Template:Harvtxt. Ensuring that the Minkowski sum of sets be closed requires the closure operation, which appends limits of convergent sequences. - ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation
|CitationClass=citation
}}.
Lemaréchal's experiments were discussed in later publications:
Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}

Template:Harvtxt: {{#invoke:citation/CS1|citation

|CitationClass=book

}} - ↑
^{65.0}^{65.1}{{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation
|CitationClass=journal
}}
Template:Harvtxt and Template:Harvtxt also considered the

*convex*closure of a problem of non-convex minimization—that is, the problem defined as the closed convex hull of the epigraph of the original problem. Their study of duality gaps was extended by Di Guglielmo to the*quasiconvex*closure of a non-convex minimization problem—that is, the problem defined as the closed convex hull of the lower level sets:Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}

- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑
^{70.0}^{70.1}Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }} - ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }} Cerf uses applications of the Shapley–Folkman lemma from Template:Harvtxt.
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation
|CitationClass=journal
}} Vind's article was noted by the winner of the 1983 Nobel Prize in Economics, Gérard Debreu. Template:Harvtxt wrote:
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 Template:Harvtxt."] 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*]{{#invoke:Citation/CS1|citation |CitationClass=journal }}

- ↑ Template:Harvtxt Template:Harvtxt was republished in a festschrift for Robert J. Aumann, winner of the 2008 Nobel Prize in Economics: {{#invoke:citation/CS1|citation |CitationClass=book }}
- ↑ Template:Harvtxt: {{#invoke:Citation/CS1|citation |CitationClass=journal }}

## References

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=book }}

## External links

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

Template:Geometry-footer {{#invoke: Navbox | navbox }} {{ safesubst:#invoke:Unsubst||$N=Use dmy dates |date=__DATE__ |$B= }}

- Use dmy dates from May 2011
- Articles with invalid date parameter in template
- Convex hulls
- Convex geometry
- Geometric transversal theory
- Additive combinatorics
- Sumsets
- Mathematical and quantitative methods (economics)
- Mathematical economics
- General equilibrium and disequilibrium
- Convexity in economics
- Theorems in geometry