The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. 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. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr. 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). The Shapley–Folkman lemma has applications in economics, optimization and probability theory. In economics, it can be used to extend results proved for convex preferences to non-convex preferences. In optimization theory, it can be used to explain the successful solution of minimization problems that are sums of many functions. In probability, it can be used to prove a law of large numbers for random sets.
Introductory example A set is said to be convex if every line segment joining two of its points is a subset in the set. The solid disk ∙ {\displaystyle \bullet } is a convex set, but the circle ∘ {\displaystyle \circ } is not, because the line segment joining two distinct points ⊘ {\displaystyle \oslash } is not a subset of the circle. The convex hull of a set Q {\displaystyle Q} is the smallest convex set that contains Q {\displaystyle Q} . Minkowski addition is an operation on sets that forms the set of sums of members of the sets, with one member from each set. 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 } . {\displaystyle \{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.} This subset of the integers { 0 , 1 , 2 } {\displaystyle \{0,1,2\}} is contained in the interval of real numbers [ 0 , 2 ] {\displaystyle [0,2]} , which is its convex hull. The Shapley–Folkman lemma implies that every point in [ 0 , 2 ] {\displaystyle [0,2]} is the sum of an integer from { 0 , 1 } {\displaystyle \{0,1\}} and a real number from [ 0 , 1 ] {\displaystyle [0,1]} : to get the convex hull of the Minkowski sum of { 0 , 1 } {\displaystyle \{0,1\}} with itself, only one of the summands needs to be replaced by its convex hull. The non-convex set { 0 , 1 } {\displaystyle \{0,1\}} and its convex hull [ 0 , 1 ] {\displaystyle [0,1]} are at Hausdorff distance 1 2 {\displaystyle {\tfrac {1}{2}}} from each other, and this distance remains the same for the non-convex set { 0 , 1 , 2 } {\displaystyle \{0,1,2\}} and its convex hull [ 0 , 2 ] {\displaystyle [0,2]} . In both cases the convex hull contains points such as 1 2 {\displaystyle {\tfrac {1}{2}}} that are at distance 1 2 {\displaystyle {\tfrac {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 by averaging, 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
1 2 ( { 0 , 1 } + { 0 , 1 } ) = { 0 , 1 2 , 1 } {\displaystyle {\frac {1}{2}}\left(\{0,1\}+\{0,1\}\right)=\left\{0,{\tfrac {1}{2}},1\right\}}
and its convex hull [ 0 , 1 ] {\displaystyle [0,1]} is only 1 4 {\displaystyle {\tfrac {1}{4}}} , which is half the distance 1 2 {\displaystyle {\tfrac {1}{2}}} between its summand { 0 , 1 } {\displaystyle \{0,1\}} and its convex hull [ 0 , 1 ] {\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 the Shapley–Folkman theorem and Shapley–Folkman–Starr theorem, as consequences of the Shapley–Folkman lemma.
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 {\displaystyle x} and y {\displaystyle 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 ) ; {\displaystyle (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 λ {\displaystyle \lambda } coordinate-wise:
λ ( x , y ) = ( λ x , λ y ) . {\displaystyle \lambda (x,y)=(\lambda x,\lambda y).}
More generally, any real vector space of (finite) dimension D {\displaystyle D} can be viewed as the set of all D {\displaystyle D} -tuples of D {\displaystyle D} real numbers ( x 1 , x 2 , … , x D ) {\displaystyle (x_{1},x_{2},\ldots ,x_{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.
Convex sets
In a real vector space, a non-empty set Q {\displaystyle 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 {\displaystyle Q} . For example, a solid disk ∙ {\displaystyle \bullet } is convex but a circle ∘ {\displaystyle \circ } is not, because it does not contain a line segment joining opposite points. 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 or vacuously. More formally, a set Q {\displaystyle Q} is convex if, for all points q 1 {\displaystyle q_{1}} and q 2 {\displaystyle q_{2}} in Q {\displaystyle Q} and for every real number λ {\displaystyle \lambda } in the unit interval [ 0 , 1 ] {\displaystyle [0,1]} , the point
( 1 − λ ) q 1 + λ q 2 {\displaystyle (1-\lambda )q_{1}+\lambda q_{2}}
is a member of Q {\displaystyle Q} . By mathematical induction, a set Q {\displaystyle Q} is convex if and only if every convex combination of members of Q {\displaystyle Q} also belongs to Q {\displaystyle Q} . By definition, a convex combination of indexed points v 1 , v 2 , … v D {\displaystyle v_{1},v_{2},\ldots v_{D}} of a vector space is any weighted average λ 1 v 1 + λ 2 v 2 + ⋯ + λ D v D {\displaystyle \lambda _{1}v_{1}+\lambda _{2}v_{2}+\cdots +\lambda _{D}v_{D}} for indexed real numbers λ 1 , λ 2 , … λ D {\displaystyle \lambda _{1},\lambda _{2},\ldots \lambda _{D}} satisfying the equation λ 1 + λ 2 + ⋯ + λ D = 1 {\displaystyle \lambda _{1}+\lambda _{2}+\cdots +\lambda _{D}=1} . 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.
Convex hull
For every subset Q {\displaystyle Q} of a real vector space, its convex hull conv Q {\displaystyle \operatorname {conv} Q} is the minimal convex set that contains Q {\displaystyle Q} . Thus conv Q {\displaystyle \operatorname {conv} Q} is the intersection of all the convex sets that cover Q {\displaystyle Q} . The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in Q {\displaystyle Q} . For example, the convex hull of the set of integers { 0 , 1 } {\displaystyle \{0,1\}} is the closed interval of real numbers [ 0 , 1 ] {\displaystyle [0,1]} , which has the maximum and minimum of the given set as its endpoints. The convex hull of the unit circle is the closed unit disk, which contains the unit circle and its interior.
Minkowski addition
In any vector space (or algebraic structure with addition), X {\displaystyle X} , the Minkowski sum of two non-empty sets A , B ⊆ X {\displaystyle A,B\subseteq X} is defined to be the element-wise operation A + B = { x + y ∣ x ∈ A , y ∈ B } . {\displaystyle A+B=\{x+y\mid x\in A,y\in B\}.} For example,
{ 0 , 1 } + { 0 , 1 } = { 0 + 0 , 0 + 1 , 1 + 0 , 1 + 1 } = { 0 , 1 , 2 } . {\displaystyle {\begin{aligned}\{0,1\}+\{0,1\}&=\{0+0,0+1,1+0,1+1\}\\&=\{0,1,2\}.\end{aligned}}}
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 ∑ n = 1 N Q n = Q 1 + Q 2 + … + Q N . {\textstyle \sum _{n=1}^{N}Q_{n}=Q_{1}+Q_{2}+\ldots +Q_{N}.} By the principle of induction,
∑ n = 1 N Q n = { ∑ n = 1 N q n | q n ∈ Q n , 1 ≤ n ≤ N } . {\displaystyle \sum _{n=1}^{N}Q_{n}=\left\{\sum _{n=1}^{N}q_{n}\mathrel {\Bigg |} q_{n}\in Q_{n},~1\leq n\leq N\right\}.}
Convex hulls of Minkowski sums Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets A , B ⊆ X {\displaystyle A,B\subseteq X} of a real vector space, X {\displaystyle X} , the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,
conv ( A + B ) = ( conv A ) + ( conv B ) . {\displaystyle \operatorname {conv} (A+B)=(\operatorname {conv} A)+(\operatorname {conv} B).}
And by induction it follows that
conv ∑ n = 1 N Q n = ∑ n = 1 N conv Q n {\displaystyle \operatorname {conv} \sum _{n=1}^{N}Q_{n}=\sum _{n=1}^{N}\operatorname {conv} Q_{n}}
for any N ∈ N {\displaystyle N\in \mathbb {N} } and non-empty subsets Q n ∈ X , 1 ≤ n ≤ N {\displaystyle Q_{n}\in X,\ 1\leq n\leq N} .
Statements of the three main results
Notation In the following statements, D {\displaystyle D} and N {\displaystyle N} represent positive integers. D {\displaystyle D} is the dimension of the ambient space R D {\displaystyle \mathbb {R} ^{D}} .
Q 1 , … , Q N {\displaystyle Q_{1},\dots ,Q_{N}} represent nonempty, bounded subsets of R D {\displaystyle \mathbb {R} ^{D}} . They are also called "summands". N {\displaystyle N} is the number of summands.
Q = ∑ n = 1 N Q n {\displaystyle Q=\sum _{n=1}^{N}Q_{n}} denotes the Minkowski sum of the summands. The variable x {\displaystyle x} is used to represent an arbitrary vector in conv Q {\displaystyle \operatorname {conv} Q} .
Shapley–Folkman lemma Because the convex hull and Minkowski sum operations can always be interchanged, as conv Q = ∑ n = 1 N conv ( Q n ) {\displaystyle \operatorname {conv} Q=\sum _{n=1}^{N}\operatorname {conv} (Q_{n})} , it follows that for every x ∈ conv Q {\displaystyle x\in \operatorname {conv} Q} , there exist elements q n ∈ conv Q n {\displaystyle q_{n}\in \operatorname {conv} Q_{n}} such that ∑ n = 1 N q n = x {\displaystyle \sum _{n=1}^{N}q_{n}=x} . The Shapley–Folkman lemma refines this statement.
For example, every point in [ 0 , 2 ] = [ 0 , 1 ] + [ 0 , 1 ] = conv { 0 , 1 } + conv { 0 , 1 } {\displaystyle [0,2]=[0,1]+[0,1]=\operatorname {conv} \{0,1\}+\operatorname {conv} \{0,1\}} is the sum of an element in { 0 , 1 } {\displaystyle \{0,1\}} and an element in [ 0 , 1 ] {\displaystyle [0,1]} . Shuffling indices if necessary, this means that every point in conv Q {\displaystyle \operatorname {conv} Q} can be decomposed as
x = ∑ n = 1 D q n + ∑ n = D + 1 N q n {\displaystyle x=\sum _{n=1}^{D}q_{n}+\sum _{n=D+1}^{N}q_{n}}
where q n ∈ conv Q n {\displaystyle q_{n}\in \operatorname {conv} Q_{n}} for 1 ≤ n ≤ D {\displaystyle 1\leq n\leq D} and q n ∈ Q n {\displaystyle q_{n}\in \operatorname {Q} _{n}} for D + 1 ≤ n ≤ N {\displaystyle D+1\leq n\leq N} . Note that the reindexing depends on the point x {\displaystyle x} . The lemma may be stated succinctly as
conv ( ∑ n = 1 N Q n ) ⊆ ⋃ I ⊆ { 1 , 2 , … N } : | I | = D ( ∑ n ∈ I conv Q n + ∑ n ∉ I Q n ) . {\displaystyle \operatorname {conv} \left(\sum _{n=1}^{N}Q_{n}\right)\subseteq \bigcup _{I\subseteq \{1,2,\ldots N\}:~|I|=D}\left(\sum _{n\in I}\operatorname {conv} Q_{n}+\sum _{n\notin I}Q_{n}\right).}
The converse of Shapley–Folkman lemma
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 Q {\displaystyle Q} and conv Q {\displaystyle \operatorname {conv} Q} using Hausdorff distance. Hausdorff distances measure how close two sets are. For two sets X {\displaystyle X} and Y {\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 x {\displaystyle x} to a set Y {\displaystyle Y} is defined as the infimum of pairwise distances,
d ( x , Y ) = inf y ∈ Y ‖ x − y ‖ , {\displaystyle d(x,Y)=\inf _{y\in Y}\|x-y\|,}
then let X ε {\displaystyle X_{\varepsilon }} denote the set of all points within distance ε {\displaystyle \varepsilon } of X {\displaystyle X} ; equivalently this is closure of the Minkowski sum of X {\displaystyle X} with a ball of radius ε {\displaystyle \varepsilon } . Then for X ⊂ Y {\displaystyle X\subset Y} , the Hausdorff distance is
d H ( X , Y ) = inf { ε ∣ X ε ⊃ Y } . {\displaystyle d_{\mathrm {H} }(X,Y)=\inf\{\varepsilon \mid X_{\varepsilon }\supset Y\}.}
The Shapley–Folkman theorem quantifies how close to convexity Q {\displaystyle Q} is by upper-bounding its Hausdorff distance to conv Q {\displaystyle \operatorname {conv} Q} , using the circumradii of its constituent sets. For any bounded set S ⊂ R D , {\displaystyle S\subset \mathbb {R} ^{D},} define its circumradius rad S {\displaystyle \operatorname {rad} S} to be the smallest radius of a ball containing it. More formally, letting x {\displaystyle x} denote the center of the smallest enclosing ball, it can be defined as
rad S = inf { ε ∣ ∃ x ∈ R N : { x } ε ⊃ S } . {\displaystyle \operatorname {rad} S=\inf\{\varepsilon \mid \exists x\in \mathbb {R} ^{N}:\{x\}_{\varepsilon }\supset S\}.} With this notation in place, the Shapley–Folkman theorem can be stated as:
Here the notation ∑ max D {\textstyle \sum _{\max D}} means "the sum of the D {\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.
Shapley–Folkman–Starr theorem
The Shapley–Folkman theorem can be strengthened by replacing the circumradius of the terms in a Minkowski by a smaller value, the inner radius, which intuitively measures the radius of the holes in a set rather than the radius of a set. Define the inner radius r ( S ) {\displaystyle r(S)} of a bounded subset S ⊂ R D {\displaystyle S\subset \mathbb {R} ^{D}} to be the infimum of r {\displaystyle r} such that, for any x ∈ conv S {\displaystyle x\in \operatorname {conv} S} , there exists a ball B {\displaystyle B} of radius r {\displaystyle r} such that x ∈ conv ( S ∩ B ) {\displaystyle x\in \operatorname {conv} (S\cap B)} .
Proofs There have been many proofs of these results, from the original, to the later Arrow and Hahn, Cassels, Schneider, etc. An abstract and elegant proof by Ekeland has been extended by Artstein. Different proofs have also appeared in unpublished papers. An elementary proof of the Shapley–Folkman lemma can be found in the book by Bertsekas, 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.
Via Carathéodory's theorem The following proof of Shapley–Folkman lemma is from Zhou (1993). The proof idea is to lift the representation of x {\displaystyle x} from R D {\displaystyle \mathbb {R} ^{D}} to R D + N {\displaystyle \mathbb {R} ^{D+N}} , use Carathéodory's theorem for conic hulls, then drop back to R D {\displaystyle \mathbb {R} ^{D}} .
Probabilistic The following "probabilistic" proof of Shapley–Folkman–Starr theorem is from Cassels (1975). We can interpret conv S {\displaystyle \operatorname {conv} S} in probabilistic terms: ∀ x ∈ conv S {\displaystyle \forall x\in \operatorname {conv} S} , since x = ∑ w n q n {\displaystyle x=\sum w_{n}q_{n}} for some q n ∈ S {\displaystyle q_{n}\in S} , we can define a random vector X {\displaystyle X} , finitely supported in S {\displaystyle S} , such that P r ( X = q n ) = w n {\displaystyle Pr(X=q_{n})=w_{n}} , and x = E [ X ] {\displaystyle x=\mathbb {E} [X]} .
Then, it is natural to consider the "variance" of a set S {\displaystyle S} as Var ( S ) := sup x ∈ conv S inf E [ X ] = x , X is finitely supported in S Var [ X ] {\displaystyle \operatorname {Var} (S):=\sup _{x\in \operatorname {conv} S}\inf _{\mathbb {E} [X]=x,X{\text{ is finitely supported in }}S}\operatorname {Var} [X]} With that, d ( S , conv ( S ) ) 2 ≤ Var ( S ) ≤ r ( S ) ≤ r a d ( S ) {\displaystyle d(S,\operatorname {conv} (S))^{2}\leq \operatorname {Var} (S)\leq r(S)\leq rad(S)} .
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. 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.
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
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. 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.
Non-convex preferences
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