
The Shapley–Folkman
lemma
Lemma may refer to:
Language and linguistics
* Lemma (morphology), the canonical, dictionary or citation form of a word
* Lemma (psycholinguistics), a mental abstraction of a word about to be uttered
Science and mathematics
* Lemma (botany), a ...
is a result in
convex geometry
In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of n ...
that describes the
Minkowski addition of
sets in a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
. It is named after mathematicians
Lloyd Shapley and
Jon Folkman, but was first published by the economist
Ross M. Starr.
The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
of the vector space, then their Minkowski sum is approximately convex.
Related results provide more refined statements about ''how close'' the approximation is. For example, the Shapley–Folkman
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of ...
provides an
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an elem ...
on the
distance
Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...
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
In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
).
The Shapley–Folkman lemma has applications in
economics
Economics () is the social science that studies the production, distribution, and consumption of goods and services.
Economics focuses on the behaviour and interactions of economic agents and how economies work. Microeconomics analy ...
,
optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
and
probability theory
Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
.
In economics, it can be used to extend results proved for
convex preferences In economics, convex preferences are an individual's ordering of various outcomes, typically with regard to the amounts of various goods consumed, with the property that, roughly speaking, "averages are better than the extremes". The concept roughly ...
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
In probability theory, the law of large numbers (LLN) is a theorem that describes the result of performing the same experiment a large number of times. According to the law, the average of the results obtained from a large number of trials sho ...
for
random sets.
Introductory example
A set is ''convex'' if every
line segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...
joining two of its points is a
subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...
in the set: For example, the solid
disk is a convex set but the
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
is not, because the line segment joining two distinct points
is not a subset of the circle.
The ''convex hull'' of a set ''Q'' is the smallest convex set that contains ''Q''. This distance is zero
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bi ...
the sum is convex.
''Minkowski addition'' is the addition of the set
member
Member may refer to:
* Military jury, referred to as "Members" in military jargon
* Element (mathematics), an object that belongs to a mathematical set
* In object-oriented programming, a member of a class
** Field (computer science), entries in ...
s. For example, adding the set consisting of the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s zero and one to itself yields the set consisting of zero, one, and two:
The subset of the integers is contained in the
interval of
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s
, 2 which is convex. The Shapley–Folkman lemma implies that every point in
, 2is the sum of an integer from and a real number from
, 1
The distance between the convex interval
, 2and the non-convex set equals one-half
: 1/2 = , 1 − 1/2, = , 0 − 1/2, = , 2 − 3/2, = , 1 − 3/2, .
However, the distance between the ''
average
In ordinary language, an average is a single number taken as representative of a list of numbers, usually the sum of the numbers divided by how many numbers are in the list (the arithmetic mean). For example, the average of the numbers 2, 3, 4, 7, ...
'' Minkowski sum
: 1/2 ( + ) =
and its convex hull
, 1is only 1/4, which is half the distance (1/2) between its summand and
, 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.
Preliminaries
The Shapley–Folkman lemma depends upon the following definitions and results from
convex geometry
In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of n ...
.
Real vector spaces
A
real vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
of two
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coor ...
s can be given a
Cartesian coordinate system
A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured ...
in which every point is identified by an
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In co ...
of real numbers, called "coordinates", which are conventionally denoted by ''x'' and ''y''. Two points in the Cartesian plane can be ''
added'' coordinate-wise
: (''x''
1, ''y''
1) + (''x''
2, ''y''
2) = (''x''
1+''x''
2, ''y''
1+''y''
2);
further, a point can be ''
multiplied'' by each real number ''λ'' coordinate-wise
: ''λ'' (''x'', ''y'') = (''λx'', ''λy'').
More generally, any real vector space of (finite) dimension
can be viewed as the
set of all
-tuples of
real numbers on which two
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
s 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'' is defined to be ''
convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
'' if, for each pair of its points, every point on the
line segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...
that joins them is still in ''Q''. For example, a solid
disk is convex but a
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is const ...
is not, because it does not contain a line segment joining its points
; the non-convex set of three integers is contained in the interval
, 2 which is convex. For example, a solid
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the on ...
is convex; however, anything that is hollow or dented, for example, a
crescent
A crescent shape (, ) is a symbol or emblem used to represent the lunar phase in the first quarter (the "sickle moon"), or by extension a symbol representing the Moon itself.
In Hinduism, Lord Shiva is often shown wearing a crescent moon on his ...
shape, is non-convex. The
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
is convex, either by definition
or
vacuously
In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be satisfied. For example, the statement "she ...
, depending on the author.
More formally, a set ''Q'' is convex if, for all points ''v''
0 and ''v''
1 in ''Q'' and for every real number ''λ'' in the
unit interval
In mathematics, the unit interval is the closed interval , that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1. It is often denoted ' (capital letter ). In addition to its role in real analys ...
,1 the point
: (1 − ''λ'') ''v''
0 + ''λv''
1
is a
member
Member may refer to:
* Military jury, referred to as "Members" in military jargon
* Element (mathematics), an object that belongs to a mathematical set
* In object-oriented programming, a member of a class
** Field (computer science), entries in ...
of ''Q''.
By
mathematical induction
Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...
, a set ''Q'' is convex if and only if every
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other ...
of members of ''Q'' also belongs to ''Q''. By definition, a ''convex combination'' of an indexed subset of a vector space is any weighted average for some indexed set of non-negative real numbers satisfying the equation = 1.
The definition of a convex set implies that the ''
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, thei ...
'' 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
In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. ...
is the empty set, which is convex.
Convex hull

For every subset ''Q'' of a real vector space, its is the
minimal convex set that contains ''Q''. Thus Conv(''Q'') is the intersection of all the convex sets that
cover ''Q''. The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in ''Q''. For example, the convex hull of the set of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s is the closed
interval of
real number
In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...
s
,1 which contains the integer end-points.
The convex hull of the
unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucli ...
is the closed
unit disk
In mathematics, the open unit disk (or disc) around ''P'' (where ''P'' is a given point in the plane), is the set of points whose distance from ''P'' is less than 1:
:D_1(P) = \.\,
The closed unit disk around ''P'' is the set of points whose ...
, which contains the unit circle.
Minkowski addition

In any vector space (or algebraic structure with addition),
, the
Minkowski sum of two non-empty sets
is defined to be the element-wise operation
(See also.)
For example
:
This operation is clearly commutative and associative on the collection of non-empty sets. All such operations extend in a well-defined manner to recursive forms
By the principle of induction it is easy to see that
:
Convex hulls of Minkowski sums
Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets
of a real vector space,
, the
convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,
:
And by induction it follows that
:
for any
and non-empty subsets
,
.
Statements of the three main results
Notation
are positive integers.
is the dimension of the ambient space
.
are nonempty, bounded subsets of
. They are also called "summands".
is the number of summands.
is the Minkowski sum of the summands.
is an arbitrary vector in
.
Shapley–Folkman lemma
Since
, for any
, there exist elements
such that
. The Shapley–Folkman lemma refines this statement.
For example, every point in
is the sum of an element in
and an element in