View source for Shapley–Folkman lemma

{{Short description|Sums of sets of vectors are nearly convex}}
{{bots|deny=Citation bot}}
{{Use dmy dates|date=October 2020}}
[[File:Shapley–Folkman lemma.svg|thumb|upright=1.35|alt=The Shapley–Folkman lemma depicted by a diagram with two panes, one on the left and the other on the right. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. Comparing the left array and the right pane, one confirms that the right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.|The Shapley–Folkman lemma is illustrated by the [[Minkowski addition]] of four sets. The point (+) in the [[convex hull]] of the Minkowski sum of the four [[convex set|non-convex set]]s (''right'') is the sum of four points (+) from the (left-hand) sets—two points in two non-convex sets plus two points in the convex hulls of two sets.  The convex hulls are shaded pink. The original sets each have exactly two points (shown as red dots).<ref name="s69">{{harvtxt|Starr|1969}}</ref>]]
The '''Shapley–Folkman&nbsp;[[lemma (mathematics)|lemma]]''' is a result in [[convex geometry]] that describes the [[Minkowski&nbsp;addition]] of [[set (mathematics)|set]]s in a [[vector space]]. It is named after mathematicians [[Lloyd Shapley]] and [[Jon Folkman]], but was first published by the economist [[Ross Starr|Ross&nbsp;M. Starr]].

The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the [[dimension (linear algebra)|dimension]] of the vector space, then their Minkowski&nbsp;sum is approximately convex.<ref name="s69" /><ref name="Howe">{{harvtxt|Howe|1979|p=1}}</ref>

Related results provide more refined statements about ''how close'' the approximation is. For example, the '''Shapley–Folkman [[theorem]]''' provides an [[upper bound]] on the [[Euclidean distance|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]]''').<ref name="Starr08" />

The Shapley–Folkman lemma has applications in [[economics]], [[mathematical optimization|optimization]] and [[probability theory]].<ref name="Starr08">{{harvtxt|Starr|2008}}</ref> 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 [[function (mathematics)|function]]s.<ref name="Ekeland76" /><ref name="Bertsekas82" /> In probability, it can be used to prove a [[law of large numbers]] for [[stochastic geometry|random sets]].<ref name="ArtsteinVitale" />
{{TOC limit|3}}

==Introductory example==
A set is ''convex'' if every [[line segment]] joining two of its points is a [[subset]] in the set: For example, the solid [[unit disk|disk]]&nbsp;<big><math>\bullet</math></big> is a convex set but the [[unit circle|circle]]&nbsp;<big><math>\circ</math></big> is not, because the line segment joining two distinct points&nbsp;<math>\oslash</math> is not a subset of the circle.

The ''convex hull'' of a set&nbsp;''{{Mvar|Q}}'' is the smallest convex&nbsp;set that contains&nbsp;''{{Mvar|Q}}''. This distance is zero [[if and only if]] the sum is convex.

''Minkowski addition'' is the addition of the set [[element (mathematics)|member]]s. For example, adding the set consisting of the [[integer]]s zero and one to itself yields the set consisting of zero, one, and two:<math display="block">\{0, 1\} + \{0, 1\} = \{0 + 0, 0 + 1, 1 + 0, 1 + 1\} = \{0, 1, 2\}.</math>The subset of the integers&nbsp;{{Math|{{mset|0,1,2}}}} is contained in the [[interval (mathematics)|interval]] of [[real number]]s&nbsp;{{Math|[0,2]}}, which is convex. The Shapley–Folkman lemma implies that every point in&nbsp;{{Math|[0,2]}} is the sum of an integer from&nbsp;{{Math|{{mset|0,1}}}} and a real number from&nbsp;{{Math|[0,1]}}.<ref name="Carter94">{{harvtxt|Carter|2001|p=94|}}</ref>

The distance between the convex interval&nbsp;{{Math|[0,2]}} and the non-convex set&nbsp;{{Math|{{mset|0,1,2}}}} equals one-half:
: <math>\frac{1}{2} = \left| 1 - \frac{1}{2} \right| = \left| 0 - \frac{1}{2} \right| = \left| 2 - \frac{3}{2} \right| = \left| 1 - \frac{3}{2} \right|. </math>
However, the distance between the ''[[arithmetic mean|average]]'' Minkowski&nbsp;sum
: <math>\frac{1}{2} \left( \{0,1\} + \{0,1\} \right) = \left\{ 0, \frac{1}{2}, 1 \right\} </math>
and its convex hull&nbsp;{{Math|[0,1]}} is only&nbsp;{{Math|1/4}}, which is half the distance&nbsp;({{Math|1/2}}) between its summand&nbsp;{{Math|{{mset|0,1}}}} and&nbsp;{{Math|[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 [[addition#summand|summand]]s.<ref name="Carter94" />

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

===Real vector spaces===

A [[real number|real]] [[vector space]] of two&nbsp;[[dimension (vector space)|dimension]]s 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&nbsp;{{Mvar|x}} and&nbsp;{{Mvar|y}}. Two points in the Cartesian&nbsp;plane can be ''[[Euclidean vector#Addition and subtraction|added]]'' coordinate-wise:
: <math>(x_1,y_1) + (x_2,y_2) = (x_1 + x_2, y_1 + y_2); </math>
further, a point can be ''[[scalar multiplication|multiplied]]'' by each real&nbsp;number&nbsp;{{Mvar|&lambda;}} coordinate-wise:
: <math>\lambda (x, y) = (\lambda x, \lambda y). </math>

More generally, any real vector space of (finite) dimension&nbsp;{{Mvar|D}} can be viewed as the [[set (mathematics)|set]] of all [[tuple|{{Mvar|D}}-tuple]]s of&nbsp;{{Mvar|D}} real&nbsp;numbers {{Math|{{mset|(''v''<sub>1</sub>, ''v''<sub>2</sub>, &mldr;, ''v''<sub>''D''</sub>)}}}} on which two&nbsp;[[operation (mathematics)|operation]]s are defined: [[Euclidean vector#Addition and subtraction|vector&nbsp;addition]] and [[scalar multiplication|multiplication by a real&nbsp;number]]. For finite-dimensional vector spaces, the operations of vector&nbsp;addition and real-number&nbsp;multiplication can each be defined coordinate-wise, following the example of the Cartesian plane.<ref>{{harvtxt|Arrow|Hahn|1980|p=375}}</ref>

===Convex sets===
{{multiple image
| width             = 155
| footer            = [[Line segment]]s test whether a subset be [[convex set|convex]].
| image1            = Convex polygon illustration1.svg
| alt1              = Illustration of a convex set, which looks somewhat like a disk: A (green) convex set contains the (black) line-segment joining the points x and y. The entire line-segment is a subset of the convex set.
| caption1          = In a [[convex set]]&nbsp;''Q'', the [[line segment]] connecting any two of its points is a subset of&nbsp;''Q''.
| image2            = Convex polygon illustration2.svg
| alt2              = Illustration of a green non-convex set, which looks somewhat like a [[boomerang]] or [[cashew]] nut. The black line-segment joins the points ''x'' and ''y'' of the green non-convex set. Part of the line segment is not contained in the green non-convex set.
| caption2          = In a [[convex set|non-convex set]]&nbsp;''Q'', a point in some [[line segment|line-segment]] joining two of its points is not a member of&nbsp;''Q''.
}}

In a real vector space, a [[empty set|non-empty]] set&nbsp;''{{Mvar|Q}}'' is defined to be ''[[convex set|convex]]'' if, for each pair of its points, every point on the [[line segment]] that joins them is still in&nbsp;''{{Mvar|Q}}''. For example, a solid [[unit disk|disk]]&nbsp;<big><math>\bullet</math></big> is convex but a [[unit circle|circle]]&nbsp;<big><math>\circ</math></big> is not, because it does not contain a line segment joining its points&nbsp;<math>\oslash</math>; the non-convex set of three integers&nbsp;{{Math|{{mset|0,1,2}}}} is contained in the interval&nbsp;{{Math|[0,2]}}, which is convex. For example, a solid [[cube (geometry)|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<ref name="Rock10" /> or [[vacuous truth|vacuously]], depending on the author.

More formally, a set&nbsp;''{{Mvar|Q}}'' is convex if, for all points&nbsp;{{Math|''v''<sub>1</sub>}}and&nbsp;{{Math|''v''<sub>2</sub>}} in&nbsp;''{{Mvar|Q}}'' and for every real number&nbsp;{{Mvar|&lambda;}} in the [[unit interval]]&nbsp;{{Math|[0,1]}}, the point
: <math>(1 - \lambda) v_1 + \lambda v_2</math>
is a [[element (mathematics)|member]] of&nbsp;''{{Mvar|Q}}''.

By [[mathematical induction]], a set&nbsp;''{{Mvar|Q}}'' is convex if and only&nbsp;if every [[convex combination]] of members of&nbsp;''{{Mvar|Q}}'' also belongs to&nbsp;''{{Mvar|Q}}''. By definition, a ''convex combination'' of an indexed&nbsp;subset&nbsp;{{Math|{{mset|''v''<sub>1</sub>, ''v''<sub>2</sub>, &mldr;, ''v''<sub>''D''</sub>}}}} of a vector space is any weighted average&nbsp;{{Math|''&lambda;''<sub>1</sub>''v''<sub>1</sub> + ''&lambda;''<sub>2</sub>''v''<sub>2</sub> + &mldr; + ''&lambda;''<sub>''D''</sub>''v''<sub>''D''</sub>}} for some indexed&nbsp;set of non-negative real numbers&nbsp;{{Math|{{mset|''&lambda;''<sub>''d''</sub>}}}} satisfying the equation&nbsp;{{Math|1=''&lambda;''<sub>0</sub> + ''&lambda;''<sub>1</sub> + &mldr; + ''&lambda;''<sub>''D''</sub> = 1}}.<ref>{{harvtxt|Arrow|Hahn|1980|p=376}},  {{harvtxt|Rockafellar|1997|pp=10–11}}, and {{harvtxt|Green|Heller|1981|p=37}}</ref>

The definition of a convex&nbsp;set implies that the ''[[intersection (set theory)|intersection]]'' of two convex&nbsp;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.<ref name="Rock10">{{harvtxt|Rockafellar|1997|p=10}}</ref>

===Convex hull===
[[File:Extreme points.svg|thumb|right|alt=A picture of a smoothed triangle, like a triangular (Mexican) tortilla-chip or a triangular road-sign. Each of the three rounded corners is drawn with a red curve. The remaining interior points of the triangular shape are shaded with blue.|In the [[convex hull]] of the red&nbsp;set, each blue&nbsp;point is a [[convex combination]] of some red&nbsp;points.]]

For every subset&nbsp;''{{Mvar|Q}}'' of a real vector&nbsp;space, its {{nowrap|''[[convex hull]]''&nbsp;{{math|1=Conv(''Q'')}}}} is the [[minimal element|minimal]] convex set that contains&nbsp;''{{Mvar|Q}}''. Thus&nbsp;{{Math|Conv(''Q'')}} is the intersection of all the convex sets that [[cover (mathematics)|cover]]&nbsp;''{{Mvar|Q}}''. The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in&nbsp;''{{Mvar|Q}}''.<ref>{{harvtxt|Arrow|Hahn|1980|p=385}} and {{harvtxt|Rockafellar|1997|pp=11–12}}</ref> For example, the convex hull of the set of [[integer]]s&nbsp;{{Math|{{mset|0,1}}}} is the closed [[interval (mathematics)|interval]] of [[real number]]s&nbsp;{{Math|[0,1]}}, which contains the integer end-points.<ref name="Carter94" /> The convex hull of the [[unit circle]] is the closed [[unit disk]], which contains the unit circle.

===Minkowski addition===
[[File:Minkowski sum graph - vector version.svg|thumb|alt=Three squares are shown in the non-negative quadrant of the Cartesian plane. |[[Minkowski addition]] of sets. The sum of the squares <math>Q_{1}=[0,1]^{2}</math> and <math>Q_{2}=[1,2]^{2}</math> is the square <math>Q_{1}+Q_{2}=[1,3]^{2}</math>.]]

In any vector space (or algebraic structure with addition), {{Mvar|X}}, the [[Minkowski addition|'''Minkowski sum''']] of two non-empty sets {{Math|''A'',''B'' &SubsetEqual; ''X''}} is defined to be the element-wise operation {{Math|1=''A'' + ''B'' = {{mset|''x'' + ''y'' | ''x'' &in; ''A'', ''y'' &in; ''B''}}}} (See also <ref>{{harvtxt|Schneider|1993|p=xi}} and {{harvtxt|Rockafellar|1997|p=16}}</ref>.) For example,
:<math>\{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.</math>
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 <math>\sum_{n=1}^{N}Q_{n}=Q_{1}+Q_{2}+\ldots+Q_{N}.</math> By the principle of induction it is easy to see that<ref>{{harvtxt|Rockafellar|1997|p=17}} and {{harvtxt|Starr|1997|p=78}}</ref>
:<math>\sum_{n=1}^{N}Q_{n}=\{\sum_{n=1}^{N}q_{n}\mid q_{n}\in Q_{n},~1\leq n\leq N\}.</math>

===Convex hulls of Minkowski sums===
Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets {{Math|''A'',''B'' &SubsetEqual; ''X''}} of a real vector space, {{Mvar|X}}, the [[convex hull]] of their Minkowski sum is the Minkowski sum of their convex hulls. That is,
:<math>\mathrm{Conv}(A+B) = \mathrm{Conv}(A)+\mathrm{Conv}(B).</math>
And by induction it follows that
:<math>\mathrm{Conv}(\sum_{n=1}^{N}Q_{n}) = \sum_{n=1}^{N}\mathrm{Conv}(Q_{n})</math>
for any {{Math|N &in; &Nopf;}} and non-empty subsets {{Math|''Q<sub>n</sub>'' &SubsetEqual; ''X'', 1 &le; ''n'' &le; ''N''}}.<ref name="Schneider">{{harvtxt|Schneider|1993|pp=2–3}}</ref><ref>{{harvtxt|Arrow|Hahn|1980|p=387}}</ref>

==Statements of the three main results==

=== Notation ===
{{Mvar|D}} and {{Mvar|N}} represent positive integers.  {{Mvar|D}} is the dimension of the ambient space {{Math|&reals;<sup>''D''</sup>}}.

{{Math|''Q''<sub>1</sub>, &mldr;, ''Q''<sub>''N''</sub>}} are nonempty, bounded subsets of {{Math|&reals;<sup>''D''</sup>}}. They are also called "summands". {{Mvar|N}} is the number of summands.

<math>Q = \sum_{n=1}^N Q_n</math> is the Minkowski sum of the summands.

{{Mvar|x}} represents an arbitrary vector in {{Math|Conv(''Q'')}}.

=== Shapley–Folkman lemma ===
Since <math>\mathrm{Conv}(Q) = \sum_{n=1}^{N}\mathrm{Conv}(Q_{n})</math>, for any {{Math|''x'' &in; Conv(''Q'')}}, there exist elements {{Math|''q<sub>n</sub>'' &in; Conv(''Q<sub>n</sub>'')}} such that <math>\sum_{n=1}^{N}q_{n}=x</math>. The '''Shapley–Folkman lemma''' refines this statement.

{{Math theorem
| name = Shapley–Folkman lemma
| note = 
| math_statement = For any {{math|1=''x'' &in; Conv(''Q'')}}, there exist elements {{math|1=''q<sub>n</sub>''}} such that <math>\sum_{n=1}^{N}q_{n}=x</math>, and at most {{mvar|D}} of the summands {{math|1=''q<sub>n</sub>'' &in; Conv(''Q<sub>n</sub>'') \ ''Q<sub>n</sub>''}}, while the others {{math|1=''q<sub>n</sub>'' &in; ''Q<sub>n</sub>''}}.
}}

For example, every point in {{Math|1=[0,2] = [0,1] + [0,1] = Conv({{mset|0,1}}) + Conv({{mset|0,1}})}} is the sum of an element in {{Math|{{mset|0,1}}}} and an element in {{Math|[0,1]}}.<ref name="Carter94" />

Shuffling indices if necessary, this means that every point in {{Math|Conv(''Q'')}} can be decomposed as

:<math>x = \sum_{n=1}^{D}q_{n} + \sum_{n=D+1}^{N} q_n</math>

where {{Math|''q<sub>n</sub>'' &in; Conv(''Q<sub>n</sub>'')}} for {{Math|1 &le; ''n'' &le; ''D''}} and {{Math|''q<sub>n</sub>'' &in; ''Q<sub>n</sub>''}} for {{Math|''D'' + 1 &le; ''n'' &le; ''N''}}. Note that the reindexing depends on the point {{Mvar|x}}.<ref>{{harvtxt|Starr|1969|pp=35–36}}</ref>

The lemma may be stated succinctly as

:<math>\mathrm{Conv}\left(\sum_{n=1}^{N}Q_{n}\right)\subseteq\bigcup_{I\subseteq\{1,2,\ldots N\}:~|I|=D}
\left(
\sum_{n\in I}\mathrm{Conv}(Q_{n})+\sum_{n\notin I}Q_{n}\right).</math>

====The converse of Shapley–Folkman lemma====
{{Math theorem
| name = converse of Shapley–Folkman lemma<ref>{{harvtxt|Schneider|1993|p=140}} credits this result to {{harvtxt|Borwein|O'Brien|1978}}</ref>
| note = 
| math_statement = If a vector space obeys the Shapley–Folkman lemma for a natural number&nbsp;{{mvar|D}}, and for no number less than&nbsp;{{mvar|D}}, then its dimension is finite, and exactly&nbsp;{{mvar|D}}.
}}

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 {{Mvar|Q}} and {{Math|Conv(''Q'')}} using squared [[Euclidean distance]].

For any nonempty subset <math>S \subseteq \R^D</math> and any point <math>x \in \R^D,</math> define their '''squared Euclidean distance''' to be the [[infimum]]<math display="block">d^2(x, S) = \inf_{y\in S}\|x-y\|^2.</math>More generally, for any two nonempty subsets <math>S, S' \subseteq \R^D,</math> define<math display="block">d^2(S, S') = \inf_{x\in S, y\in S'}\|x-y\|^2.</math>Note that <math>d^2(x, S) = (\inf_{y\in S}\|x-y\|)^2,</math> so we can simply write <math>d^2(x, S) = d(x, S)^2,</math> where <math>d(x, S) = \inf_{y\in S}\|x-y\|.</math> Similarly, <math>d^2(S, S') = d(S, S')^2.</math>

For example, <math>d^2([0, 2], \{0,1,2\}) = 1/4 = d([0, 2], \{0,1,2\})^2.</math>

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 {{Mvar|Q}} is by upper-bounding <math>d^2( \mathrm{Conv}(Q), Q).</math>

For any bounded subset <math>S \subset \R^D,</math> define its '''circumradius''' <math>rad(S)</math> to be the infimum of the radius of all [[Smallest circle problem|balls containing it]] (as shown in the diagram). More formally,
<math display="block">rad(S) \equiv \inf_{x \in R^N} \sup_{y \in S}\|x-y\|</math>Now we can state

{{Math theorem
| name = Shapley–Folkman theorem<ref>{{harvtxt|Starr|1969|p=36}}</ref><ref>{{harvtxt|Schneider|1993|p=129}}</ref>
| note = 
| math_statement = <math>d^2( Q, \mathrm{Conv}(Q)) ~\leq~ \sum_{\max D} rad(Q_n)^2.</math>
}}

where we use the notation <math>\sum_{\max D}</math> to mean "the sum of the {{Mvar|D}} largest terms".

Note that 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 ===
Define the '''inner radius''' <math>r(S)</math> of a bounded subset  <math>S \subset \R^D</math> to be the infimum of <math>r</math> such that, for any <math>x\in \mathrm{Conv}(S)</math>, there exists a ball <math>B</math> of radius <math>r</math> such that <math>x\in \mathrm{Conv}(S \cap B)</math>.<ref name="Starr 1969 37">{{harvtxt|Starr|1969|p=37}}</ref>[[File:Inner radius.svg|thumb|alt=A blue disk contains red points. A smaller green disk sits in the largest concavity in among these red points.|The circumradius (blue) and inner&nbsp;radius (green) of a point set (dark red, with its convex hull shown as the lighter red dashed lines). The inner&nbsp;radius is smaller than the circumradius except for subsets of a single circle, for which they are equal.]]

For example, let <math>B' \subset B \subset \R^D</math> be two nested balls, then the circumradius of <math>B\setminus B'</math> is the radius of <math>B</math>, but its inner radius is the radius of <math>B'</math>.

Since <math>r(S) \leq rad(S)</math> for any bounded subset  <math>S \subset \R^D</math>, the following theorem is a refinement:

{{Math theorem
| name = Shapley–Folkman–Starr theorem<ref name="Starr 1969 37" /><ref>{{harvtxt|Schneider|1993|pp=129–130}}
</ref>
| note = 
| math_statement = <math>d^2(Q, \mathrm{Conv}(Q)) \leq \sum_{\max D} r(Q_n)^2</math>.
}}

In particular, if we have an infinite sequence <math>(Q_n)_{n=1, 2, ...} </math> of nonempty, bounded subsets of <math>\mathbb R^D</math>, and if there exists some <math>r_0 \geq 0</math> such that the inner radius of each <math>Q_n</math> is upper-bounded by <math>r_0</math>, then <math display="block">d^2\left( \mathrm{Conv}\left(\frac 1N \sum_{n=1}^N Q_n \right), \frac 1N \sum_{n=1}^N Q_n \right) 
\leq
\frac{D r_0^2}{N}. </math>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,<ref name="Starr 1969 37" /> to the later [[Kenneth Arrow|Arrow]] and [[Frank Hahn|Hahn]],<ref>{{harvtxt|Arrow|Hahn|1980|pp=392–395}}</ref> [[J. W. S. Cassels|Cassels]],<ref name=":0">{{harvtxt|Cassels|1975|pp=435–436}}</ref> Schneider,<ref>{{harvtxt|Schneider|1993|p=128}}</ref> etc. An abstract and elegant proof by [[Ivar Ekeland|Ekeland]]<ref>{{harvtxt|Ekeland|1999|pp=357–359}}</ref> has been extended by Artstein.<ref>{{harvtxt|Artstein|1980|p=180}}</ref> Different proofs have also appeared in unpublished papers.<ref name="Howe" /><ref>{{cite book|title=Economics&nbsp;201B: Nonconvex preferences and approximate equilibria|chapter=1 The Shapley–Folkman theorem|pages=1–5|date=14 March 2005|first=Robert M.|last=Anderson|author-link=<!-- NOT WP's Robert M. Anderson -->|location=Berkeley, Calif.|publisher=Economics Department, University of California, Berkeley|chapter-url=http://elsa.berkeley.edu/users/anderson/Econ201B/NonconvexHandout.pdf|access-date=1 January 2011}}</ref> An elementary proof of the Shapley–Folkman lemma can be found in the book by [[Dimitri Bertsekas|Bertsekas]],<ref>
{{cite book
  | last = Bertsekas
  | first = Dimitri P.
  | author-link = Dimitri P. Bertsekas
  | title = Convex Optimization Theory
  | publisher = Athena Scientific
  | year = 2009
  | location = Belmont, Mass.
  | isbn =  978-1-886529-31-1   
}} 
</ref> 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 theorem|existence]] of the representation, but do not provide an [[algorithm]] for computing the representation. In&nbsp;1981, Starr published an [[iterative method|iterative algorithm]] for a less sharp version of the Shapley–Folkman–Starr theorem.<ref>{{cite journal |last=Starr |first=Ross&nbsp;M. |author-link=Ross M. Starr |year=1981 |title=Approximation of points of convex hull of a sum of sets by points of the sum: An elementary approach |journal=Journal of Economic Theory |volume=25 |issue=2 |pages=314–317 |doi=10.1016/0022-0531(81)90010-7 |mr=640201}}</ref>

=== A proof of the results ===
The following proof of Shapley–Folkman lemma is from.<ref>{{Cite journal |last=Zhou |first=Lin |date=June 1993 |title=A simple proof of the Shapley-Folkman theorem |url=http://dx.doi.org/10.1007/bf01212924 |journal=Economic Theory |volume=3 |issue=2 |pages=371–372 |doi=10.1007/bf01212924 |issn=0938-2259}}</ref> The proof idea is to lift the representation of <math>x</math> from <math>\R^{D}</math>to <math>\R^{D+N}</math>, use [[Carathéodory's theorem (convex hull)|Carathéodory's theorem for conic hulls]], then drop back to <math>\R^D</math>.

{{Math proof|title=Proof of Shapley–Folkman lemma|proof=

For each <math>n</math>, represent <math>q_n \in \mathrm{Conv}(Q_n)</math> as <math>q_n = \sum_{k=1}^K w_{n, k} q_{n,k}</math>, where <math>K</math> is a large finite number, <math>w_{n, k} \geq 0</math>, and <math>\sum_k w_{n, k} = 1</math>.

Now "lift" the representation <math>x = \sum_n \sum_k w_{n,k}q_{n,k}</math> from <math>\R^D</math> to <math>\R^{D+N}</math>. Define
<math display="block">\bar x = (x, 1, ..., 1);\quad \bar q_{n,k} = (q_{n,k}, e_n)</math>
where <math>e_n</math> is the vector in <math>\R^N</math> that has 1 at coordinate <math>n</math>, and 0 at all other coordinates.

With this, we have a lifted representation

<math display="block">\bar x = \sum_{n}\sum_k w_{n,k} \bar q_{n,k}.</math>
That is, <math>\bar x</math> is in the conic hull of <math>\{\bar q_{n, k}\}_{n\in 1:N, k\in 1:K}</math>.

By Carathéodory's theorem for conic hulls, we have an alternative representation

<math display="block">\bar x = \sum_{n}\sum_k w'_{n,k}\bar q_{n,k}</math>
such that <math>w'_{n,k} \geq 0</math>, and at most <math>N+D</math> of them are nonzero. Since we defined

<math display="block">\bar x = (x, 1, ..., 1);\quad \bar q_{n,k} = (q_{n,k}, e_n)</math>
this alternative representation is also a representation for <math>x</math>.

We argue that for any <math>n_0 \in 1:N</math>, there must be at least one value of <math>k</math> for which <math>w'_{n_0, k}</math> is nonzero. Remember that we defined <math>(\bar x)_{D + n_0}</math>, the <math>(D + n_0)</math> entry of <math>\bar x</math>, to be <math>1</math>. At the same time, from the lifted representation of <math>\bar x</math>,
<math display="block">(\bar x)_{D + n_0} = \left(\sum_{n} \sum_{k}  w'_{n,k} \bar q_{n,k}\right)_{D+n_0}</math>
<math display="block">= \sum_{n} \sum_{k}  w'_{n,k} (\bar q_{n,k})_{D+n_0}.</math>
We drop all terms on the r.h.s. for which <math>n \neq n_0</math> since they are zero. The remaining terms take the form <math>w'_{n_0,k} (\bar q_{n_0,k})_{D+n_0} = w'_{n_0, k}</math>, so we find the equation
<math display="block">1 = \sum_k w'_{n_0, k}.</math>
It follows that there is at least one element of the sum on the r.h.s. that is non-zero.

Combining the fact that for each value of <math>n</math> there is a non-zero <math>w_{n,k}'</math>, together with the fact that there are at most <math>N+D</math> of <math>w_{n,k}'</math> that are nonzero, we conclude that there can only be at most <math>D</math> elements of <math>n\in 1:N</math> for which there are at least two of <math>w_{n,k}'</math> that are nonzero.

Thus we obtain a representation

<math display="block">\bar x = \sum_{n} \left(\sum_k w'_{n,k} \bar q_{n,k}\right)</math>
where for at most <math>D</math> of <math>n</math>, the term <math>\sum_k w'_{n,k} \bar q_{n,k}</math> is not in <math>Q_n</math>.
}}

The following "probabilistic" proof of Shapley–Folkman–Starr theorem is from.<ref name=":0" />

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

Then, it is natural to consider the "variance" of a set <math>S</math> as<math display="block">Var(S) := \sup_{x \in \mathrm{Conv}(S)} \inf_{\mathbb E[X] = x, X\text{ is finitely supported in }S} Var[X]</math>With that, <math>d(S, \mathrm{Conv}(S))^2 \leq Var(S) \leq r(S) \leq rad(S)</math>.{{Math proof|proof=

<math>d(S, \mathrm{Conv}(S))^2 \leq Var(S)</math>: Expand their definitions.

<math>Var(S) \leq rad(S)</math>: if <math>x\in \mathrm{Conv}(S)</math> then let <math>X</math> be finitely supported in <math>S</math> such that <math>E[X] = x</math>. Now since <math>S</math> is bounded in a ball of radius <math>rad(S)+\epsilon</math> centered at some <math>o</math>, we have <math>Var[X] = Var[X-o] \leq E[\|X-o\|^2] \leq rad(S) + \epsilon</math>.

<math>Var(S) \leq r(S)</math>: use the previous result.  
}}{{Math proof|proof=

It suffices to show <math>Var\left(Q\right) \leq \sum_{\max D} Var(Q_n)</math>.

<math>\forall x \in \mathrm{Conv}(Q)</math>, by Shapley–Folkman lemma, there exists a representation <math>x = \sum_{n\in I} x_n + \sum_{n \in J} q_n</math>, such that <math>I, J</math> partitions <math>\{1, 2, ..., N\}, |I| \leq D, x_n \in \mathrm{Conv}(Q_n), q_n\in Q_n</math>.

Now, for each <math>n\in I</math>, construct random vectors <math>X_n</math> such that <math>X_n</math> is finitely supported on <math>Q_n</math>, with <math>\mathbb E[X_n] = x_n</math> and <math>Var[X_n] < Var[Q_n] + \epsilon</math>, where <math>\epsilon> 0</math> is an arbitrary small number.

Let all such <math>X_n</math> be independent. Then let <math>X = \sum_{n\in I} X_n + \sum_{n\in J} q_n</math>. Since each <math>q_n</math> is a deterministic vector, we have

<math display="block">Var[X] =Var \left[\sum_{n\in I} X_n\right]= \sum_{n\in I} Var \left[ X_n\right] \leq \sum_{n\in I}\left(Var(Q_n) + \epsilon\right) \leq \sum_{\max D} Var(Q_n) + D\epsilon.</math>

Since this is true for arbitrary <math>\epsilon > 0</math>, we have <math>Var[X] \leq \sum_{\max D} Var(Q_n)</math>, and we are done.  
|title=Proof of Shapley–Folkman–Starr theorem}}

== History ==
[[File:Shapley, Lloyd (1923).jpeg|thumb|alt=Picture of Lloyd Shapley|A Winner of the 2012 Nobel Award in Economics, [[Lloyd Shapley]] proved the Shapley–Folkman lemma with [[Jon Folkman]].<ref name="s69" />]]The lemma of [[Lloyd Shapley]] and [[Jon Folkman]] was first published by the economist [[Ross Starr|Ross&nbsp;M. Starr]], who was investigating the existence of [[general equilibrium theory#Nonconvexities in large economies|economic equilibria]] while studying with [[Kenneth Arrow]].<ref name="s69" /> 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&nbsp;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]].<ref name="g89-p138">{{harvtxt|Guesnerie|1989|p=138}}</ref>

The topic of [[non-convexity (economics)|non-convex sets in economics]] has been studied by many [[Nobel Prize in Economics|Nobel laureates]]: Shapley himself (2012), Arrow (1972), [[Robert Aumann]] (2005), [[Gérard Debreu]] (1983), [[Tjalling Koopmans]] (1975), [[Paul Krugman]] (2008), and [[Paul Samuelson]] (1970); the complementary topic of [[convexity in economics|convex sets in economics]] has been emphasized by these laureates, along with [[Leonid Hurwicz]], [[Leonid Kantorovich]] (1975), and [[Robert Solow]] (1987).

==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===
[[File:Indifference curves showing budget line.svg|thumb|right|alt=The nonnegative quadrant of the Cartesian plane appears. A blue straight-line slopes downward as a secant joining two points, one on each of the axes. This blue line is tangent to a red curve that touches it at a marked point, whose coordinates are labeled ''Qx'' and ''Qy''.|The consumer [[preference (economics)|prefers]] every basket of goods on the [[indifference curve]]&nbsp;''I''<sub>3</sub> over each basket on &nbsp;''I''<sub>2</sub>.
The basket&nbsp;(''Q''<sub>x</sub>,&nbsp;''Q''<sub>y</sub>), where the budget line (''shown in blue'') [[supporting hyperplane|supports]]&nbsp;''I''<sub>2</sub>, is optimal and also feasible, unlike any basket lying on &nbsp;''I''<sub>3</sub> which is preferred but unfeasible.]]
{{See also|Convexity in economics}}
In [[microeconomics|economics]], a consumer's [[Preference (economics)|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 (set theory)|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.<ref>{{harvtxt|Mas-Colell|1985|pp=58–61}} and {{harvtxt|Arrow|Hahn|1980|pp=76–79}}</ref>

An optimal basket of goods occurs where the budget-line [[supporting hyperplane|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 (mathematics)|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.<ref>{{harvtxt|Arrow|Hahn|1980|pp=79–81}}</ref>

====Non-convex preferences====
[[File:NonConvex.gif|right|thumb|alt=Image of a non-convex preference set with a concavity un-supported by the budget line|When the consumer's preferences have concavities, the consumer may jump between two separate optimal baskets.]]
{{See also|Non-convexity (economics)}}
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.<ref>{{harvtxt|Starr|1969|p=26}}: "After all,
one may be indifferent between an automobile and a boat, but in most cases one&nbsp;can neither&nbsp;drive nor&nbsp;sail the combination of half&nbsp;boat, half&nbsp;car."</ref>

When the consumer's preference set is non-convex, then (for some prices) the consumer's demand is not [[connected space|connected]]; a disconnected demand implies some discontinuous behavior by the consumer, as discussed by [[Harold Hotelling]]:
<blockquote>
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.<ref>{{harvtxt|Hotelling|1935|p=74}}</ref>
</blockquote>
The difficulties of studying non-convex preferences were emphasized by [[Herman Wold]]<ref>{{harvtxt|Wold|1943b|pp=231 and&nbsp;239–240}} and {{harvtxt|Wold|Juréen|1953|p=146}}</ref> and again by [[Paul Samuelson]], who wrote that non-convexities are "shrouded in eternal darkness&nbsp;...",<ref>{{harvtxt|Samuelson|1950|pp=359–360}}:<blockquote>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.</blockquote></ref>{{efn|1="Eternal darkness" describes the Hell of [[John Milton]]'s ''[[Paradise Lost]]'', whose concavity is compared to the [[Serbonian Bog]] in [[wikisource:Paradise Lost (1674)/Book II|Book&nbsp;II, lines&nbsp;592–594]]:</p><blockquote>A gulf profound as that Serbonian Bog<br />Betwixt Damiata and <!-- correcting failed-capitalization in Arrow Hahn "m" (sic) -->Mount Casius old,<br />Where Armies whole have sunk.</blockquote>Milton's description of concavity serves as the [[epigraph (literature)|literary epigraph]] prefacing chapter seven of {{harvtxt|Arrow|Hahn|1980|p=169}}, "Markets with non-convex preferences and production", which presents the results of {{harvtxt|Starr|1969}}.}} according to&nbsp;Diewert.<ref name="Diewert" >{{harvtxt|Diewert|1982|pp=552–553}}</ref>

Nonetheless, non-convex preferences were illuminated from&nbsp;1959 to&nbsp;1961 by a sequence of papers in ''[[The Journal of Political Economy]]''&nbsp;(''JPE''). The main contributors were Farrell,<ref>
{{harvs|txt|last=Farrell|year1=1959|year2=1961a|year3=1961b}}</ref> Bator,<ref>{{harvs|txt|last=Bator|year1=1961a|year2=1961b}}</ref> [[Tjalling Koopmans|Koopmans]],<ref>
{{harvtxt|Koopmans|1961|p=478}} and others—for example, {{harvtxt|Farrell|1959|pp=390–391}} and {{harvtxt|Farrell|1961a|p=484}}, {{harvtxt|Bator|1961a|pp=482–483}}, {{harvtxt|Rothenberg|1960|p=438}}, and {{harvtxt|Starr|1969|p=26}}—commented on {{harvtxt|Koopmans|1957|pp=1–126, especially&nbsp;9–16 [1.3 Summation of opportunity sets],&nbsp;23–35 [1.6 Convex sets and the price implications of optimality], and&nbsp;35–37 [1.7 The role of convexity assumptions in the analysis]}}</ref> and Rothenberg.<ref name="Rothenberg" >{{harvs|txt|last=Rothenberg|year1=1960|loc1=p.&nbsp;447|year2=1961}}
</ref> In particular, Rothenberg's paper discussed the approximate convexity of sums of non-convex sets.<ref name="ArrowHahn182" >{{harvtxt|Arrow|Hahn|1980|p=182}}</ref> These <!-- ''Journal of Political Economy'' --> ''JPE''-papers stimulated a paper by [[Lloyd Shapley]] and [[Martin Shubik]], which considered convexified consumer-preferences and introduced the concept of an "approximate equilibrium".<ref>{{harvtxt|Shapley|Shubik|1966|p=806}}</ref> The <!-- ''Journal of Political Economy''  -->''JPE''-papers and the Shapley–Shubik paper influenced another notion of "quasi-equilibria", due to [[Robert Aumann]].<ref name="Aumann" >{{harvtxt|Aumann|1966|pp=1–2}} uses results from 
{{harvs|txt|last=Aumann|year1=1964|year2=1965}}<!-- NOT original research, this comment appears often, e.g. in "What is Bob Aumann trying to accomplish" in the CORE 20th anniversary volume, in which Guesnerie appears --></ref><ref>Taking the convex hull of non-convex preferences had been discussed earlier by {{harvtxt|Wold|1943b|p=243}} and by {{harvtxt|Wold|Juréen|1953|p=146}}, according to {{harvtxt|Diewert|1982|p=552}}.</ref>

==== Starr's 1969 paper and contemporary economics ====
[[File:Kenneth Arrow, Stanford University.jpg|thumb|upright|alt=Picture of Kenneth Arrow|[[Kenneth Arrow]] (1972 [[Nobel Prize in Economics|Nobel laureate]]) helped [[Ross&nbsp;M. Starr]] to study [[convex set|non-convex]] [[convex preferences|economies]].<ref name="StarrArrow"/>]]

Previous publications on [[non-convexity (economics)|non-convexity and economics]] were collected in an annotated bibliography by [[Kenneth Arrow]]. He gave the bibliography to [[Ross Starr|Starr]], who was then an undergraduate enrolled in Arrow's (graduate) advanced mathematical-economics course.<ref name="StarrArrow">{{harvtxt|Starr|Stinchcombe|1999|pp=217–218}}
</ref> 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 [[eponym]]ous lemma and theorem in "private correspondence", which was reported by Starr's published paper of 1969.<ref name="s69"/>

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&nbsp;''p''<sub>opt</sub> with the following properties:

* For each quasi-equilibrium's prices&nbsp;''p''<sub>opt</sub>, all consumers can choose optimal baskets (maximally preferred and meeting their budget constraints).
* At quasi-equilibrium prices&nbsp;''p''<sub>opt</sub> 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 [[Hausdorff distance|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.<ref>{{harvtxt|Arrow|Hahn|1980|pp=169–182}} and {{harvtxt|Starr|1969|pp=27–33}}</ref>

Starr established that
<blockquote>
"in the aggregate, the discrepancy between an allocation in the fictitious economy generated by [taking the convex hulls of all of the consumption&nbsp;and&nbsp;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&nbsp;agent experiences a deviation from intended actions that vanishes in significance as the number&nbsp;of&nbsp;agents goes to infinity".<ref>{{harvtxt|Green|Heller|1981|p=44}}</ref>
</blockquote>
Following Starr's&nbsp;1969 paper, the Shapley–Folkman–Starr results have been widely used in economic theory. [[Roger&nbsp;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&nbsp;side, preference&nbsp;nonconvexities do not destroy the standard results".<ref>{{harvtxt|Guesnerie|1989|pp=99}}</ref> "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Guesnerie.<ref name="g89-p138"/> The topic of [[non-convexity (economics)|non-convex sets in economics]] has been studied by many [[Nobel Prize in Economics|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 [[convexity in economics|convex sets in economics]] has been emphasized by these laureates, along with [[Leonid Hurwicz]], [[Leonid Kantorovich]] (1975), and [[Robert Solow]] (1987).<ref name="MasColell87">{{harvtxt|Mas-Colell|1987}}</ref> The Shapley–Folkman–Starr results have been featured in the economics literature: in [[microeconomics]],<ref>{{harvtxt|Varian|1992|pp=393–394}}<p>{{harvtxt|Mas-Colell|Whinston|Green|1995|pp=627–630}}</p></ref> in general-equilibrium theory,<ref>{{harvtxt|Arrow|Hahn|1980|pp=169–182}}</p><p>{{harvtxt|Mas-Colell|1985|pp=52–55, 145–146, 152–153, and 274–275}}</p><p>{{harvtxt|Hildenbrand|1974|pp=37, 115–116, 122, and 168}}</p><p>{{harvtxt|Starr|1997|p=169}}</p><p>{{harvtxt|Ellickson|1994|pp=xviii, 306–310, 312, 328–329, 347, and 352}}</p></ref> in [[public economics]]<ref>{{cite book |last=Laffont|first=Jean-Jacques|author-link=Jean-Jacques Laffont|year=1988 |chapter=3. Nonconvexities|title=Fundamentals of public economics|publisher=[[MIT]] Press|pp=63–65|isbn=0-262-12127-1 |url=https://books.google.com/books?q=editions:&id=O5MnAQAAIAAJ}}
</ref> (including [[market failure]]s),<ref>{{harvtxt|Salanié|2000|pp=112–113 and 107–115}}</ref> as well as in [[game theory]],<ref>{{harvtxt|Ichiishi|1983|pp=24–25}}</ref> in [[mathematical economics]],<ref>{{harvtxt|Cassels|1981|pp=127 and 33–34}}</ref> and in [[applied mathematics#Mathematics for economists|applied mathematics]] (for economists).<ref name="Aubin"/><ref name="Carter" >{{harvtxt|Carter|2001|pp=93–94,&nbsp;143,&nbsp;318–319,&nbsp;375–377, and&nbsp;416}}</ref> The Shapley–Folkman–Starr results have also influenced economics research using [[measure (mathematics)|measure]] and [[integral|integration theory]].<ref>{{harvtxt|Trockel|1984|p=30}}</ref>

===Mathematical optimization===
[[File:Epigraph convex.svg|right|thumb|upright=1.35|alt=A graph of a convex function, which is drawn in black. Its epigraph, the area above its graph, is solid green.|A [[function (mathematics)|function]] is [[convex function|convex]] if the region above its [[graph of a function|graph]] is a [[convex set]].]]
The Shapley–Folkman lemma has been used to explain why large [[nonlinear programming|minimization]] problems with [[convex function|non-convexities]] can be nearly solved (with [[iterative methods]] whose convergence proofs are stated for only [[convex optimization|convex problems]]). The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.<ref name="Bertsekas99"/>

====Preliminaries of optimization theory====
[[Nonlinear programming|Nonlinear optimization]] relies on the following definitions for [[function (mathematics)|function]]s:

*The [[graph of a function|''graph'']] of a function&nbsp;''f'' is the set of the pairs of [[domain of a function|argument]]s&nbsp;''x'' and function evaluations&nbsp;''f''(''x'')
: Graph(''f'') = <big><big>{</big></big> <big>(</big>''x'',&nbsp;''f''(''x'') <big>)</big> <big><big>}</big></big>

* The ''[[epigraph (mathematics)|epigraph]]'' of a [[real-valued function]]&nbsp;''f'' is the set of points ''above'' the graph
[[File:Sine.svg|right|thumb|alt=A graph of the sine function, which periodically oscillates up and down between −1 and +1, with the period 2π.|The [[sine|sine&nbsp;function]] is [[convex function|non-convex]].]]
: Epi(''f'') = <big>{</big>&nbsp;(''x'',&nbsp;''u'')&nbsp;:&nbsp;''f''(''x'')&nbsp;≤&nbsp;''u''&nbsp;<big>}</big>.

*A real-valued function is defined to be a ''[[convex function]]'' if its epigraph is a convex set.<ref name="Rock23" >{{harvtxt|Rockafellar|1997|p=23}}</ref>

For example, the [[quadratic&nbsp;function]]&nbsp;''f''(''x'')&nbsp;=&nbsp;''x''<sup>2</sup> is convex, as is the [[absolute&nbsp;value]] function&nbsp;''g''(''x'')&nbsp;=&nbsp;|''x''|. However, the [[sine|sine&nbsp;function]] (pictured) is non-convex on the [[interval (mathematics)#Definitions|interval]]&nbsp;(0,&nbsp;π).

====Additive optimization problems====
In many optimization problems, the [[optimization (mathematics)#objective function|objective function]]&nbsp;f is ''separable'': that is, ''f'' is the sum of ''many'' summand-functions, each of which has its own argument:

: ''f''(''x'') = ''f''<big>(</big>&nbsp;(''x''<sub>1</sub>, ..., ''x''<sub> <math>N</math></sub>)<big>&nbsp;)</big> = <big>Σ</big>&nbsp;''f''<sub>''n''</sub>(''x''<sub>''n''</sub>).

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

: ''x''<sub>min</sub>&nbsp;=&nbsp;(''x''<sub>1</sub>,&nbsp;...,&nbsp;''x''<sub> <math>N</math></sub>)<sub>min</sub>

with the minimum value&nbsp;{{nowrap|''f''(''x''<sub>min</sub>).}}  For this separable problem, we also consider an optimal solution  <big>(</big>''x''<sub>min</sub>,&nbsp;''f''(''x''<sub>min</sub>) <big>)</big>
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
: <big>(</big>''x''<sub>''j''</sub>,&nbsp;''f''(''x''<sub>j</sub>) <big>)</big><big>&nbsp;∈&nbsp;</big> <big>Σ</big> Conv <big>(</big>Graph( ''f''<sub>''n''</sub> ) <big>)</big>.<ref name="Ekeland76"/>{{efn|1=
The [[limit of a sequence]] is a member of the [[closure (topology)|closure of the original set]], which is the smallest [[closed set]] that contains the original set. The Minkowski sum of two [[closed set]]s need not be closed, so the following [[subset#inclusion|inclusion]] can be strict
: Clos(P)&nbsp;+&nbsp;Clos(Q) ⊆ Clos(&nbsp;Clos(P)&nbsp;+&nbsp;Clos(Q)&nbsp;);
the inclusion can be strict even for two ''convex'' closed summand-sets, according to {{harvtxt|Rockafellar|1997|pp=49 and&nbsp;75}}. Ensuring that the Minkowski&nbsp;sum of sets be closed requires the closure operation, which appends limits of convergent sequences.}}
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&nbsp;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 optimization|convex minimization]] [[iterative method|method]]s on problems that were known to be non-convex; for [[nonlinear programming|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.<ref>{{harvtxt|Lemaréchal|1973|p=38}}
Lemaréchal's experiments were discussed in later publications: <p>{{harvtxt|Aardal|1995|pp=2–3}}</p><p>{{harvtxt|Hiriart-Urruty|Lemaréchal|1993|pp=143–145, 151, 153, and&nbsp;156}}</p></ref><ref name="Ekeland76" >{{harvtxt|Ekeland|1999|pp=357–359}}: Published in the first English edition of 1976, Ekeland's appendix proves the Shapley–Folkman lemma, also acknowledging [[Claude Lemaréchal|Lemaréchal]]'s experiments on page&nbsp;373.</ref><ref name="Ekeland74" >{{cite journal|last=Ekeland|first=Ivar |title=Une estimation ''a&nbsp;priori'' en programmation non&nbsp;convexe|journal=Comptes&nbsp;Rendus Hebdomadaires des Séances de l'Académie des Sciences |series=Séries&nbsp;A et&nbsp;B|language=fr|issn=0151-0509<!-- Not archived on CRAS site, and CRAS's title has changed multiple times -->|volume=279|year=1974|pages=149–151|mr=395844}}<!-- Ekeland sole author; cites Lemaréchal by title whereas the 1976 appendix acknowledges but does not cite Lemaréchal (1973)--></ref> Ekeland's analysis explained the success of methods of convex&nbsp;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.<ref name="Ekeland76" /><ref name="Ekeland74" /><ref name="AubinEkeland" >{{harvtxt|Aubin|Ekeland|1976|pp=226,&nbsp;233,&nbsp;235,&nbsp;238, and&nbsp;241}}</ref>
{{efn|1={{harvtxt|Aubin|Ekeland|1976}} and {{harvtxt|Ekeland|1999|pp=362–364}} also considered the ''[[Convex conjugate#Biconjugate convex|convex]]''&nbsp;[[Convex conjugate#Biconjugate|closure]] of a problem of non-convex minimization—that is, the problem defined as the [[Kuratowski closure axioms|closed]] [[convex hull|convex]] [[closure operator|hull]] of the [[epigraph (mathematics)|epigraph]] of the original problem. Their study of duality gaps was extended by Di&nbsp;Guglielmo to the ''[[quasiconvex function|quasiconvex]]'' closure of a non-convex [[multiobjective optimization|minimization]] problem—that is, the problem defined as the [[Kuratowski closure axioms|closed]] [[convex hull|convex]] [[closure operator|hull]] of the [[semicontinuity#lower|lower]] [[level set|level&nbsp;set]]s.<ref>{{harvtxt|Di&nbsp;Guglielmo|1977|pp=287–288}}
</ref>}} The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.<ref name="Ekeland76" /><ref name="Bertsekas82" >{{harvtxt|Bertsekas|1996|pp=364–381}} acknowledging {{harvtxt|Ekeland|1999}} on page&nbsp;374 and {{harvtxt|Aubin|Ekeland|1976}} on page&nbsp;381:<p>
{{harvtxt|Bertsekas|1996|pp=364–381}} describes an application of [[dual problem|Lagrangian dual]] methods to the [[scheduling (production processes)|scheduling]] of [[electricity generation|electrical power plant]]s ("[[power system simulation#Unit commitment|unit&nbsp;commitment problem]]s"), where non-convexity appears because of [[integer programming|integer constraints]]:</p><p>{{harvtxt|Bertsekas|Lauer|Sandell|Posbergh|1983}}</p></ref><ref name="Aubin" >{{harvtxt|Aubin|2007|pp=458–476}}</ref><ref name="Bertsekas99" >{{harvtxt|Bertsekas|1999|p=496}}</ref>

===Probability and measure theory===
Convex sets are often studied with [[probability theory]]. Each point in the convex hull of a ([[empty set|non-empty]]) subset&nbsp;''Q'' of a finite-dimensional space is the [[expected value]] of a [[simple function|simple]] [[multivariate random variable|random&nbsp;vector]] that takes its values in&nbsp;''Q'', as a consequence of [[Carathéodory's theorem (convex hull)|Carathéodory's lemma]]. Thus, for a non-empty set&nbsp;''Q'', the collection of the expected&nbsp;values of the simple, ''Q''-valued random&nbsp;vectors equals&nbsp;''Q''{{'s}} convex hull; this equality implies that the Shapley–Folkman–Starr results are useful in probability theory.<ref>{{harvtxt|Schneider|Weil|2008|p=45}}</ref> In the other direction, probability theory provides tools to examine convex&nbsp;sets generally and the Shapley–Folkman–Starr results specifically.<ref>{{harvtxt|Cassels|1975|pp=433–434}}
</ref> The Shapley–Folkman–Starr results have been widely used in the [[stochastic geometry|probabilistic theory of random sets]],<ref>{{harvtxt|Molchanov|2005|pp=195–198,&nbsp;218,&nbsp;232,&nbsp;237–238 and&nbsp;407}}</ref> for example, to prove a [[law of large numbers|law of large&nbsp;numbers]],<ref name="ArtsteinVitale">{{harvtxt|Artstein|Vitale|1975|pp=881–882}}</ref><ref name="PurRal85">{{harvtxt|Puri|Ralescu|1985|pp=154–155}}
</ref> a [[central limit theorem]],<ref name="PurRal85" /><ref>{{harvtxt|Weil|1982|pp=203, and&nbsp;205–206}}</ref> and a [[large deviations theory|large-deviations]]&nbsp;[[rate function|principle]].<ref>{{harvtxt|Cerf|1999|pp=243–244}} uses applications of the Shapley–Folkman lemma from {{harvtxt|Puri|Ralescu|1985|pp=154–155}}.</ref> These proofs of [[convergence of random variables|probabilistic limit&nbsp;theorems]] used the Shapley–Folkman–Starr results to avoid the assumption that all the random&nbsp;sets be convex.

A [[probability measure]] is a finite [[measure (mathematics)|measure]], and the Shapley–Folkman lemma has applications in non-probabilistic measure&nbsp;theory, such as the theories of [[volume]] and of [[vector measure]]s. The Shapley–Folkman lemma enables a refinement of the [[Brunn–Minkowski theorem|Brunn–Minkowski inequality]], which bounds the volume of sums in terms of the volumes of their summand-sets.<ref>{{harvtxt|Ruzsa|1997|p=345}}</ref> 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 [[Vector measure#Lyapunov's theorem|Lyapunov's theorem]], which states that the [[image (mathematics)|range]] of a [[vector measure]] is convex.<ref name="Tardella" >{{harvtxt|Tardella|1990|pp=478–479}}</ref> 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&nbsp;''p''<sub>1</sub> and&nbsp;''p''<sub>2</sub> are [[probability measure]]s defined on the same [[measure (mathematics)#Measurable space|measurable&nbsp;space]], 
then the [[product function]]&nbsp;{{nowrap|''p''<sub>1</sub>&nbsp;''p''<sub>2</sub>}} is a vector&nbsp;measure, 
where&nbsp;{{nowrap|''p''<sub>1</sub>&nbsp;''p''<sub>2</sub>}} 
is defined for every [[event (probability theory)|event]]&nbsp;''ω'' 
by
:<big>(</big>''p''<sub>1</sub>&nbsp;''p''<sub>2</sub><big>)</big>(''ω'')=<big>(</big>''p''<sub>1</sub>(''ω''),&nbsp;''p''<sub>2</sub>(''ω'')<big>)</big>.  
Lyapunov's theorem has been used in [[mathematical economics|economics]],<ref name="Aumann"/><ref>{{harvtxt|Vind|1964|pp=168 and&nbsp;175}} was noted by the winner of the 1983 [[Nobel Prize in Economics]], [[Gérard Debreu]]. {{harvtxt|Debreu|1991|p=4}} wrote:
<blockquote>
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&nbsp;1964. It appeared in a new light with the introduction of integration&nbsp;theory in the study of economic competition: If one associates with every agent of an economy an arbitrary set in the commodity&nbsp;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.&nbsp;A.&nbsp;Lyapunov, see {{harvtxt|Vind|1964}}."] But explanations of the ... functions of prices ... can be made to rest&nbsp;on the ''convexity of sets derived by that averaging&nbsp;process''. ''Convexity'' in the commodity&nbsp;space ''obtained by aggregation'' over a collection of insignificant agents is an insight that economic theory owes ... to integration theory. [''Italics added'']
</blockquote>
</ref> in ([[bang–bang control|"bang-bang"]]) [[control theory]], and in [[statistical theory]].<ref name="Artstein">{{harvtxt|Artstein|1980|pp=172–183}}</ref> Lyapunov's theorem has been called a [[discretization|continuous]] counterpart of the Shapley–Folkman lemma,<ref name="Starr08" /> which has itself been called a [[discrete mathematics#Discrete analogues of continuous mathematics|discrete analogue]] of Lyapunov's theorem.<ref name="MCBlock78" >{{harvtxt|Mas-Colell|1978|p=210}}</ref>
{{clear}}

==Notes==
{{notelist|30em}}
{{Reflist|30em}}

==References==
{{refbegin|30em}}
* {{cite journal|last=Aardal|first=Karen|author-link=Karen Aardal|title=''Optima'' interview - Claude Lemaréchal|journal=Optima: Mathematical Programming Society Newsletter|pages=2–4|date=March 1995|volume=45 |url=http://www.mathprog.org/Old-Optima-Issues/optima45.pdf|access-date=2 February 2011}}
* {{cite book|last1=Arrow|first1=Kenneth&nbsp;J.|author-link1=Kenneth Arrow|last2=Hahn|first2=Frank&nbsp;H. |author-link2=Frank Hahn|year=1980|title=General competitive analysis|publisher=North-Holland<!-- |pages=375–401 -->|series=Advanced Textbooks in Economics|volume=12|edition=reprint of San Francisco, CA: Holden-Day,&nbsp;Inc. Mathematical Economics Texts&nbsp;'''6'''|orig-year=1971|location=Amsterdam|isbn=0-444-85497-5|mr=439057}}
* {{cite journal|last=Artstein|first=Zvi|title=Discrete and continuous bang-bang and facial&nbsp;spaces, or: Look for the extreme points|journal=SIAM Review|volume=22|year=1980|issue=2|pages=172–185 |doi=10.1137/1022026 |mr=564562|jstor=2029960}} Republished in a [[festschrift]] for [[Robert Aumann|Robert&nbsp;J. Aumann]], winner of the 2008 [[Nobel Prize in Economics]]:
** {{cite book|ref=none|last=Artstein|first=Zvi|chapter=22 Discrete and continuous bang–bang and facial spaces or: Look for the extreme points|pages=449–462|title=Game and economic theory: Selected contributions in honor of Robert J. Aumann|chapter-url=http://www.press.umich.edu/titleDetailDesc.do?id=14414 |editor1-first=Sergiu|editor1-last=Hart|editor2-first=Abraham|editor2-last=Neyman |publisher=University of Michigan Press|location=Ann Arbor, Mich. |year=1995|isbn=0-472-10673-2|url-status=dead|archive-date=24 May 2011 |archive-url=https://web.archive.org/web/20110524002010/http://press.umich.edu/titleDetailDesc.do?id=14414}}
* {{cite journal|last1=Artstein|first1=Zvi|last2=Vitale|first2=Richard&nbsp;A.|year=1975|title=A strong law of large numbers for random compact sets|journal=The Annals of Probability|volume=3|issue=5|pages=879–882 |doi=10.1214/aop/1176996275|mr=385966|jstor=2959130|zbl=0313.60012|id={{Project Euclid|euclid.ss/1176996275}}|doi-access=free}}
* {{cite book|last=Aubin|first=Jean-Pierre|chapter=14.2 Duality in the case of non-convex integral criterion and constraints (especially&nbsp;14.2.3 The Shapley–Folkman theorem, pages&nbsp;463–465)|title=Mathematical methods of game and economic theory|edition=Reprint with new preface of&nbsp;1982 North-Holland revised English|publisher=Dover Publications|location=Mineola, NY|year=2007|isbn=978-0-486-46265-3|mr=2449499}}
* {{cite journal|last1=Aubin|first1=J.&nbsp;P.|last2=Ekeland|first2=I.|journal=[[Mathematics of Operations Research]]|title=Estimates of the duality gap in nonconvex optimization|volume=1|issue=3|pages=225–245 |year=1976 |doi=10.1287/moor.1.3.225|mr=449695|jstor=3689565}}
* {{cite journal|last=Aumann|first=Robert&nbsp;J.|author-link=Robert Aumann|title=Markets with a continuum of traders|journal=Econometrica|volume=32|issue=1–2|date=January–April 1964|pages=39–50|jstor=1913732 |mr=172689 |doi=10.2307/1913732}}
* {{cite journal|last=Aumann|first=Robert&nbsp;J.|author-link=Robert Aumann|title=Integrals of set-valued functions|journal=Journal of Mathematical Analysis and Applications|volume=12|issue=1|date=August 1965 |pages=1–12 |doi=10.1016/0022-247X(65)90049-1|mr=185073|doi-access=free}}
* {{cite journal|last=Aumann|first=Robert&nbsp;J.|author-link=Robert Aumann|title=Existence of competitive equilibrium in markets with a continuum of traders|journal=Econometrica|volume=34|issue=1|date=January 1966|pages=1–17 |jstor=1909854|mr=191623|doi=10.2307/1909854}}
* {{cite journal|last=Bator|first=Francis M. |title=On convexity, efficiency, and markets|journal=The Journal of Political Economy|volume=69|issue=5|date=October 1961a|pages=480–483|jstor=1828537 |doi=10.1086/258540}}
* {{cite journal|last=Bator|first=Francis M.|title=On convexity, efficiency, and markets: Rejoinder|journal=Journal of Political Economy|volume=69|issue=5|date=October 1961b|pages=489 |jstor=1828539 |doi=10.1086/258542}}
* {{cite book|last=Bertsekas|first=Dimitri&nbsp;P.|author-link=Dimitri P. Bertsekas|title=Nonlinear Programming|edition=Second|chapter=5.1.6 Separable problems and their geometry|pages=494–498|publisher=Athena Scientific|year=1999 |location=Cambridge, Mass.|isbn =1-886529-00-0}}
* {{cite book|last=Bertsekas|first=Dimitri&nbsp;P.|author-link=Dimitri P. Bertsekas|chapter=5.6 Large scale separable integer programming problems and the exponential method of multipliers|title=Constrained optimization and Lagrange multiplier methods|year=1996|location=Belmont, Mass. |isbn=1-886529-04-3|publisher=Athena Scientific|mr=690767}} Reprint of (1982) Academic Press.
* {{cite journal|last1=Bertsekas|first1=Dimitri P.|author-link1=Dimitri Bertsekas|last2=Lauer |first2=Gregory S.|last3=Sandell|first3=Nils R. Jr. |last4=Posbergh|first4=Thomas A.|journal=IEEE Transactions on Automatic Control |volume=28|date=January 1983|title=Optimal short-term scheduling of large-scale power systems|pages=1–11|doi=10.1109/tac.1983.1103136|issue=1 |url=http://web.mit.edu/dimitrib/www/Unit_Comm.pdf|access-date=2 February 2011}} Proceedings of 1981 IEEE Conference on Decision and Control, San Diego, CA, December 1981, pp.&nbsp;432–443.
* {{cite journal|last1=Borwein|first1=J. M.|author-link=Jonathan Borwein|last2=O'Brien|first2=R. C. |title=Cancellation characterizes convexity|journal=Nanta Mathematica (Nanyang University) |issn=0077-2739 |volume=11|year=1978 |pages=100–102|mr=510842}}
* {{cite book|last=Carter|first=Michael|title=Foundations of mathematical economics|publisher=MIT Press |location=Cambridge, Mass.|year=2001|isbn=0-262-53192-5|id=([http://michaelcarteronline.com/FOME/ Author's website] with [http://michaelcarteronline.com/FOME/answers.html answers to exercises]) |mr=1865841 |url=http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8630|url-status=dead|archive-url=https://web.archive.org/web/20060915230536/http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8630|archive-date=15 September 2006}}
* {{cite journal|last=Cassels|first=J. W. S.|author-link=J. W. S. Cassels|title=Measures of the non-convexity of sets and the Shapley–Folkman–Starr theorem|journal=[[Mathematical Proceedings of the Cambridge Philosophical Society]] |volume=78|year=1975|issue=3|pages=433–436|doi=10.1017/S0305004100051884|mr=385711}}
* {{cite book|last=Cassels|first=J.&nbsp;W.&nbsp;S.|author-link=J. W. S. Cassels|chapter=Appendix&nbsp;A Convex sets|title=Economics for mathematicians |series=London Mathematical Society lecture note series |volume=62 |publisher=Cambridge University Press|location=Cambridge, UK|year=1981|isbn=0-521-28614-X |mr=657578}}
* {{cite journal|last=Cerf|first=Raphaël|title=Large deviations for sums of i.i.d. random compact sets |journal=[[Proceedings of the American Mathematical Society]]|volume=127|year=1999|issue=8|pages=2431–2436|doi=10.1090/S0002-9939-99-04788-7|mr=1487361|doi-access=free}}
* {{cite journal|last=Debreu|first=Gérard|author-link=Gérard Debreu|title=The Mathematization of economic theory|issue=Presidential address delivered at the&nbsp;103rd meeting of the American Economic Association, 29 December 1990, Washington, DC|journal=The American Economic Review|volume=81|date=March 1991|pages=1–7|jstor=2006785}}
* {{cite journal|last=Di&nbsp;Guglielmo|first=F.|title=Nonconvex duality in multiobjective optimization |doi=10.1287/moor.2.3.285|volume=2|year=1977|issue=3|pages=285–291|journal=[[Mathematics of Operations Research]] |mr=484418 |jstor=3689518}}
* {{cite book|first=W.&nbsp;E.|last=Diewert|chapter=12 Duality approaches to microeconomic theory
|pages=535–599
|chapter-url=http://www.sciencedirect.com/science/article/B7P5Y-4FDF0FN-R/2/dcc0f8c9352eb054c96b3ff481976ce7
|doi=10.1016/S1573-4382(82)02007-4
|title=Handbook of mathematical economics|editor1-link=Kenneth Arrow |editor1-first=Kenneth Joseph|editor1-last=Arrow|editor2-first=Michael D.|editor2-last=Intriligator|series=Handbooks in Economics|volume=2 |publisher=North-Holland Publishing|location=Amsterdam|year=1982|isbn=978-0-444-86127-6|mr=648778}}
* {{cite book|last=Ekeland|first=Ivar|author-link=Ivar Ekeland|chapter=Appendix&nbsp;I: An ''a&nbsp;priori'' estimate in convex programming|editor1-last=Ekeland|editor1-first=Ivar|editor2-last=Temam|editor2-first=Roger|editor2-link=Roger Temam|title=Convex analysis and variational problems |edition=Corrected reprinting of the North-Holland|orig-year=1976|series=Classics in Applied Mathematics |volume=28|publisher=Society for Industrial and Applied Mathematics&nbsp;(SIAM)|location=Philadelphia |year=1999|pages=357–373|isbn=0-89871-450-8|mr=1727362}}
* {{cite book|last=Ellickson|first=Bryan |title=Competitive equilibrium: Theory and applications |publisher=Cambridge University Press|isbn=978-0-521-31988-1|year=1994|doi = 10.1017/CBO9780511609411}}
* {{cite journal|last=Farrell|first=M.&nbsp;J.|date=August 1959|title=The Convexity assumption in the theory of competitive markets|journal=[[The Journal of Political Economy]]|volume=67|issue=4|pages=371–391|jstor=1825163 |doi=10.1086/258197}}
* {{cite journal|last=Farrell|first=M.&nbsp;J.|date=October 1961a|title=On Convexity, efficiency, and markets: A Reply|journal=Journal of Political Economy|volume=69|issue=5|pages=484–489|jstor=1828538 |doi=10.1086/258541}}
* {{cite journal|last=Farrell|first=M.&nbsp;J.|date=October 1961b|title=The Convexity assumption in the theory of competitive markets: Rejoinder|journal=Journal of Political Economy|volume=69|issue=5 |pages=493|jstor=1828541 |doi=10.1086/258544}}
* {{cite book|first1=Jerry|last1=Green|first2=Walter P.|last2=Heller|chapter=1 Mathematical analysis and convexity with applications to economics|pages=15–52|doi=10.1016/S1573-4382(81)01005-9|title=Handbook of mathematical economics|editor1-link=Kenneth Arrow |editor1-first=Kenneth Joseph|editor1-last=Arrow|editor2-first=Michael D. |editor2-last=Intriligator|series=Handbooks in Economics|volume=1 |publisher=North-Holland Publishing |location=Amsterdam|year=1981|isbn=0-444-86126-2|mr=634800}}
* {{cite book|last=Guesnerie|first=Roger|author-link=Roger Guesnerie|year=1989|chapter=First-best allocation of resources with nonconvexities in production|pages=99–143|editor-first=Bernard|editor-last=Cornet|editor2-first=Henry|editor2-last=Tulkens|title=Contributions to Operations&nbsp;Research and Economics: The twentieth anniversary of CORE (Papers from the symposium held in Louvain-la-Neuve, January&nbsp;1987)|publisher=MIT Press |location=Cambridge, Mass.|isbn=0-262-03149-3|mr=1104662}}
* {{cite book|last=Hildenbrand|first=Werner|author-link=Werner Hildenbrand|title=Core and equilibria of a large economy|series=Princeton studies in mathematical economics|volume=5|publisher=Princeton University Press |location=Princeton, NJ|year=1974|isbn=978-0-691-04189-6|mr=389160}}
* {{cite book|last1=Hiriart-Urruty|first1=Jean-Baptiste|last2=Lemaréchal|first2=Claude|author-link2=Claude Lemaréchal|year=1993|chapter=XII Abstract duality for practitioners|title=Convex analysis and minimization algorithms, Volume&nbsp;'''II''': Advanced theory and bundle methods|series=Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]|volume=306|publisher=Springer-Verlag |location=Berlin |pages=136–193 (and bibliographical comments on pp.&nbsp;334–335)|isbn=3-540-56852-2 |mr=1295240}}
* {{cite journal|first=Harold|last=Hotelling|author-link=Harold Hotelling |title=Demand functions with limited budgets|journal=Econometrica|volume=3|issue=1|date=January 1935|pages=66–78|jstor=1907346 |doi=10.2307/1907346}}
* {{cite report|last=Howe|first=Roger|author-link=Roger Evans Howe|date=November 1979|title=On the tendency toward convexity of the vector sum of sets |publisher=[[Cowles Foundation|Cowles Foundation for Research in Economics]], Yale University|series=Cowles Foundation discussion papers|location=New Haven, Conn.|volume=538 |url=http://cowles.econ.yale.edu/P/cd/d05a/d0538.pdf |access-date=15 January 2011}}
* {{cite book|last=Ichiishi|first=Tatsuro |title=Game theory for economic analysis|series=Economic theory, econometrics, and mathematical economics|publisher=Academic Press [Harcourt Brace Jovanovich, Publishers] |location=New York |year=1983|isbn=0-12-370180-5|mr=700688}}
* {{cite book|last=Koopmans|first=Tjalling&nbsp;C.|author-link=Tjalling Koopmans|year=1957 |chapter=Allocation of resources and the price system|editor-last=Koopmans|editor-first=Tjalling&nbsp;C |editor-link=Tjalling Koopmans |title=Three essays on the state of economic science|publisher=McGraw–Hill Book Company|location=New York|pages=1–126|isbn=0-07-035337-9}}
* {{cite journal|last=Koopmans |first=Tjalling&nbsp;C. |author-link=Tjalling Koopmans |date=October 1961 |title=Convexity assumptions, allocative efficiency, and competitive equilibrium |journal=The Journal of Political Economy |volume=69 |issue=5 |pages=478–479 |jstor=1828536 |doi=10.1086/258539}}
* {{cite report|last=Lemaréchal|first=Claude|author-link=Claude Lemaréchal|title=Utilisation de la dualité dans les problémes non&nbsp;convexes [Use of duality for non–convex problems]|language=fr| date=April 1973 |issue=16|location=Domaine de Voluceau, [[Rocquencourt, Yvelines|Rocquencourt]], [[Le Chesnay|Le&nbsp;Chesnay]], France|publisher=[[National Institute for Research in Computer Science and Control|IRIA (now&nbsp;INRIA)]], Laboratoire de recherche en informatique et automatique}} <!-- Ekeland cites this report in the ''[[Comptes Rendus|CRAS]]'' announcement of the results of his Appendix&nbsp;I -->
* {{cite journal|last=Mas-Colell|first=Andreu|author-link=Andreu Mas-Colell|year=1978|title=A note on the core&nbsp;equivalence theorem: How many blocking coalitions are there?|journal=Journal of Mathematical Economics |volume=5 |issue=3|pages=207–215|doi=10.1016/0304-4068(78)90010-1|mr=514468}}
* {{cite book|last=Mas-Colell|first=Andreu|author-link=Andreu Mas-Colell|year=1985|chapter=1.L Averages of sets|title=The Theory of general economic equilibrium: A ''differentiable'' approach|series=Econometric Society monographs |volume=9|publisher=Cambridge University Press|isbn=0-521-26514-2|mr=1113262}}
* {{cite book|last=Mas-Colell|first=A.|author-link=Andreu Mas-Colell|chapter=Non-convexity|title=The new Palgrave: A dictionary of economics|editor1-first=John|editor1-last=Eatwell|editor1-link=John Eatwell, Baron Eatwell|editor2-first=Murray|editor2-last=Milgate|editor2-link=Murray Milgate|editor3-first=Peter|editor3-last=Newman|editor3-link=Peter Kenneth Newman|publisher=Palgrave Macmillan|year=1987|edition=first|doi=10.1057/9780230226203.3173<!-- SNAFU at NP? 30 Jan 2011-->|pages=653–661|chapter-url=http://www.dictionaryofeconomics.com/article?id=pde1987_X001573|id=([http://www.econ.upf.edu/~mcolell/research/art_083b.pdf PDF file at Mas-Colell's homepage])|title-link=The New Palgrave Dictionary of Economics|isbn=9780333786765}}
* {{cite book|last1=Mas-Colell|first1=Andreu|author-link=Andreu Mas-Colell|last2=Whinston|first2=Michael&nbsp;D. |first3=Jerry&nbsp;R.|last3=Green|chapter=17.1 Large&nbsp;economies and nonconvexities |title=Microeconomic theory |publisher=Oxford&nbsp;University Press|year=1995|isbn=978-0-19-507340-9}}
* {{cite book|last=Molchanov|first=Ilya|chapter=3 Minkowski addition|title=Theory of random sets |series=Probability and its applications |publisher=Springer-Verlag London|location=London|year=2005 |isbn=978-1-84996-949-9 |pages=[https://archive.org/details/theoryrandomsets00molc_724/page/n209 194]–240 |doi=10.1007/1-84628-150-4|mr=2132405 |url=https://archive.org/details/theoryrandomsets00molc_724|url-access=limited}}
* {{cite journal|last1=Puri|first1=Madan&nbsp;L.|last2=Ralescu|first2=Dan&nbsp;A.|title=Limit theorems for random compact sets in Banach space|journal=Mathematical Proceedings of the Cambridge Philosophical Society |year=1985 |volume=97|issue=1|pages=151–158|doi=10.1017/S0305004100062691|mr=764504 |bibcode=1985MPCPS..97..151P}}
* {{cite book|last=Rockafellar|first=R.&nbsp;Tyrrell|author-link=R. Tyrrell Rockafellar|title=Convex analysis|series=Princeton Landmarks in Mathematics|publisher=Princeton University Press|location=Princeton, NJ |year=1997 |isbn=0-691-01586-4|mr=1451876}}. Reprint of the 1970 ({{MR|274683}}) Princeton Mathematical Series&nbsp;'''28'''
* {{cite journal |last=Rothenberg |first=Jerome |date=October 1960 |title=Non-convexity, aggregation, and Pareto optimality |journal=The Journal of Political Economy |volume=68 |issue=5 |pages=435–468 |jstor=1830308 |doi=10.1086/258363}}
* {{cite journal |last=Rothenberg |first=Jerome |date=October 1961 |title=Comments on non-convexity |journal=Journal of Political Economy |volume=69 |issue=5 |pages=490–492 |jstor=1828540|doi=10.1086/258543}}
* {{cite journal|last=Ruzsa|first=Imre&nbsp;Z.|author-link=Imre Z. Ruzsa|title=The Brunn–Minkowski inequality and nonconvex sets|journal=[[Geometriae Dedicata]]|volume=67|doi=10.1023/A:1004958110076 |doi-access=free |year=1997|issue=3|pages=337–348 |mr=1475877}}
* {{cite book|last=Salanié|first=Bernard|chapter=7 Nonconvexities |title=Microeconomics of market failures |year=2000|publisher=MIT&nbsp;Press|location=Cambridge, Mass.|pages=107–125|isbn=0-262-19443-0}} English translation of the (1998) French ''Microéconomie: Les défaillances du&nbsp;marché'' (Economica, Paris)
* {{cite journal|last=Samuelson|first=Paul&nbsp;A.|author-link=Paul Samuelson|title=The problem of integrability in utility theory|journal=Economica|series=New Series|volume=17 |issue=68|date=November 1950|pages=355–385 |mr=43436 |jstor=2549499|doi=10.2307/2549499}}
* {{cite book|last=Schneider|first=Rolf|title=Convex&nbsp;bodies: The Brunn–Minkowski theory |series=Encyclopedia of Mathematics and its Applications|volume=44|publisher=Cambridge University Press |location=Cambridge, UK|year=1993 |isbn=0-521-35220-7|mr=1216521 |url=https://archive.org/details/convexbodiesbrun0000schn}}
* {{cite book|last1=Schneider|first1=Rolf|last2=Weil|first2=Wolfgang|title=Stochastic and integral geometry |series=Probability and its applications|doi=10.1007/978-3-540-78859-1|year=2008|publisher=Springer |isbn=978-3-540-78858-4 |mr=2455326}}
* {{cite journal|last1=Shapley|first1=L.&nbsp;S.|author-link1=Lloyd Shapley|last2=Shubik|first2=M.|author-link2=Martin Shubik|title=Quasi-cores in a monetary economy with nonconvex preferences|journal=Econometrica |volume=34 |issue=4|date=October 1966|pages=805–827|jstor=1910101|zbl=0154.45303|doi=10.2307/1910101 |url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0623552|archive-url=https://web.archive.org/web/20170924084740/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0623552|url-status=dead|archive-date=24 September 2017}}
* {{cite journal|last=Starr|first=Ross&nbsp;M.|author-link=Ross Starr|issue=1|journal=Econometrica|pages=25–38|title=Quasi-equilibria in markets with non-convex preferences (Appendix&nbsp;2: The Shapley–Folkman theorem, pp.&nbsp;35–37)|volume=37|year=1969|jstor=1909201|doi=10.2307/1909201}}
* {{cite book|last=Starr|first=Ross M.|chapter=Shapley–Folkman theorem|title=The new Palgrave dictionary of economics|editor-first=Steven&nbsp;N.|editor-last=Durlauf|editor2-first=Lawrence E.|editor2-last=Blume|editor1-link=Steven N. Durlauf|editor2-link=Lawrence E. Blume|publisher=Palgrave Macmillan|year=2008|edition=Second|pages=317–318 (1st ed.)|chapter-url=http://www.dictionaryofeconomics.com/article?id=pde2008_S000107 |doi=10.1057/9780230226203.1518 |title-link=The New Palgrave Dictionary of Economics|isbn=978-0-333-78676-5}}
* {{cite book|last=Starr |first=Ross&nbsp;M.|chapter=8 Convex sets, separation theorems, and non-convex sets in&nbsp;'''R'''<sup> <math>N</math></sup> (new chapters&nbsp;22 and&nbsp;25–26 in (2011) second ed.)|title=General equilibrium theory: An introduction |edition=1st|publisher=Cambridge University Press|location=Cambridge, UK |year=1997|isbn=0-521-56473-5|mr=1462618}}
* {{cite book|last1=Starr|first1=R.&nbsp;M.|author-link1=Ross Starr|last2=Stinchcombe|first2=M.&nbsp;B. |chapter=Exchange in a network of trading posts|title=Markets, information and uncertainty: Essays in economic theory in honor of Kenneth&nbsp;J. Arrow|editor-first=Graciela|editor-last=Chichilnisky|editor-link=Graciela Chichilnisky|pages=217–234|publisher=Cambridge University Press|location=Cambridge, UK |year=1999|isbn=978-0-521-08288-4|doi = 10.1017/CBO9780511896583}}
* {{cite journal|last=Tardella|first=Fabio|title=A new proof of the Lyapunov convexity theorem|journal=SIAM Journal on Control and Optimization|volume=28|year=1990|issue=2|pages=478–481 |doi=10.1137/0328026 |mr=1040471}}
* {{cite book|last=Trockel|first=Walter|title=Market demand: An analysis of large economies with nonconvex preferences|series=Lecture Notes in Economics and Mathematical Systems|volume=223|publisher=Springer-Verlag |location=Berlin |year=1984|isbn=3-540-12881-6|mr=737006}}
* {{cite book|last=Varian|first=Hal&nbsp;R.|author-link=Hal Varian|chapter=21.2 Convexity and size |title=Microeconomic Analysis|publisher=W. W. Norton & Company|edition=3rd|year=1992|isbn=978-0-393-95735-8 |mr=1036734 |url-access=registration|url=https://archive.org/details/microeconomicana00vari_0}}
* {{cite journal|last=Vind|first=Karl|date=May 1964|title=Edgeworth-allocations in an exchange economy with many traders|journal=International Economic Review|volume=5|pages=165–177|issue=2|jstor=2525560 |doi=10.2307/2525560}}
* {{cite journal|last=Weil|first=Wolfgang|title=An application of the central limit theorem for Banach-space–valued random variables to the theory of random sets|journal=Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete |trans-journal=Probability Theory and Related Fields|volume=60|year=1982 |issue=2|pages=203–208|doi=10.1007/BF00531823|mr=663901|doi-access=free}}
* {{cite journal|last=Wold|first=Herman|author-link=Herman Wold|year=1943b|title=A synthesis of pure demand analysis&nbsp;'''II'''|journal=Skandinavisk Aktuarietidskrift |trans-journal=Scandinavian Actuarial Journal|volume=26 |pages=220–263<!-- Diewert gives wrong pages, according to Math Rev and my inspection of the article and of Wold's book with Jureen -->|mr=11939|doi=10.1080/03461238.1943.10404737}}
* {{cite book|last1=Wold|first1=Herman|author-link1=Herman Wold|last2=Juréen|first2=Lars (in association with Wold) |chapter=8 Some further applications of preference fields (pp.&nbsp;129–148)|title=Demand analysis: A study in econometrics|location=New York|publisher=John Wiley and Sons|series=Wiley publications in statistics |year=1953 |mr=64385}}
{{refend}}

==External links==

* {{cite book|title=Economics&nbsp;201B: Nonconvex preferences and approximate equilibria|chapter=1 The Shapley–Folkman theorem|pages=1–5| date=March 2005 |first=Robert M.|last=Anderson|author-link=<!-- NOT WP's Robert M. Anderson -->|location=Berkeley, Calif.|publisher=Economics Department, University of California, Berkeley|chapter-url=http://elsa.berkeley.edu/users/anderson/Econ201B/NonconvexHandout.pdf|access-date=15 January 2011}}
* {{cite book|last=Starr|first=Ross&nbsp;M.|author-link=Ross Starr|chapter=8 Convex sets, separation theorems, and non-convex sets in&nbsp;'''R'''<sup> <math>N</math></sup> (Section&nbsp;8.2.3 Measuring non-convexity, the Shapley–Folkman theorem)|title=General&nbsp;equilibrium theory: An introduction|date=September 2009|pages=3–6|chapter-url=http://www.econ.ucsd.edu/~rstarr/113Winter2010/Webpage/PDFonlyCUPsubmission/Chap8-2009/2009CHAP-08092109.pdf|mr=1462618|id=(Draft of second edition, from Starr's course at the Economics Department of the University of California, San Diego)|doi=10.1017/CBO9781139174749|isbn=9781139174749|access-date=15 January 2011|archive-date=1 July 2010|archive-url=https://web.archive.org/web/20100701131416/http://www.econ.ucsd.edu/~rstarr/113Winter2010/Webpage/PDFonlyCUPsubmission/Chap8-2009/2009CHAP-08092109.pdf|url-status=dead}}
* {{cite web|last=Starr|first=Ross&nbsp;M.|author-link=Ross Starr|title=Shapley–Folkman theorem| date=May 2007 |pages=1–3|url=http://www.econ.ucsd.edu/~rstarr/SFarticle.pdf|access-date=15 January 2011|id=(Draft of article for the second edition of ''New&nbsp;Palgrave Dictionary of Economics'')}}

{{Geometry-footer|state=collapsed}}
{{Microeconomics|state=collapsed}}
{{Convex analysis and variational analysis}}

{{good article}}

{{DEFAULTSORT:Shapley-Folkman Lemma}}

[[Category:Additive combinatorics]]
[[Category:Convex hulls]]
[[Category:Convex geometry]]
[[Category:Convex optimization]]
[[Category:Geometric transversal theory]]
[[Category:General equilibrium theory]]
[[Category:Lloyd Shapley]]
[[Category:Sumsets]]
[[Category:Theorems in geometry]]