Shapley–Folkman lemma
   HOME

TheInfoList



OR:

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), ...
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 ...
that describes the Minkowski addition of
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
s 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 can ...
. It is named after mathematicians
Lloyd Shapley Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
and
Jon Folkman Jon Hal Folkman (December 8, 1938 – January 23, 1969) was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation. Schooling Folkman was a Putnam Fellow in 1960. He received his Ph.D. in 1964 from P ...
, 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 coord ...
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 t ...
provides an upper bound 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 In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
. 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 anal ...
, optimization 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 ...
. 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 shou ...
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 i ...
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 of ...
in the set: For example, the solid disk \bullet 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 cons ...
 \circ is not, because the line segment joining two distinct points \oslash 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 bic ...
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 languag ...
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 measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
, 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 ...
.


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 can ...
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 coord ...
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 ...
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 con ...
of real numbers, called "coordinates", which are conventionally denoted by ''x'' and ''y''. Two points in the Cartesian plane can be '' added'' coordinate-wise : (''x''1, ''y''1) + (''x''2, ''y''2) = (''x''1+''x''2, ''y''1+''y''2); further, a point can be '' multiplied'' by each real number ''λ'' coordinate-wise : ''λ'' (''x'', ''y'') = (''λx'', ''λy''). More generally, any real vector space of (finite) dimension  D can be viewed as the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of all D-tuples of  D 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'' 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 i ...
that joins them is still in ''Q''. For example, a solid disk \bullet 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 cons ...
 \circ is not, because it does not contain a line segment joining its points \oslash; 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 only ...
is convex; however, anything that is hollow or dented, for example, a crescent shape, is non-convex. The empty set is convex, either by definition or vacuously, 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 analysis ...
  ,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 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. A ...
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 Cover or covers may refer to: Packaging * Another name for a lid * Cover (philately), generic term for envelope or package * Album cover, the front of the packaging * Book cover or magazine cover ** Book design ** Back cover copy, part of copy ...
 ''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 languag ...
s  is the closed interval of
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
,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 d ...
, which contains the unit circle.


Minkowski addition

In any vector space (or algebraic structure with addition), X, the Minkowski sum of two non-empty sets A, B\subseteq X is defined to be the element-wise operation A+B := \. (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 \sum_^Q_=Q_+Q_+\ldots+Q_. By the principle of induction it is easy to see that :\sum_^Q_=\.


Convex hulls of Minkowski sums

Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets A,B\subseteq X of a real vector space, X, the
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of their Minkowski sum is the Minkowski sum of their convex hulls. That is, :\mathrm(A+B) = \mathrm(A)+\mathrm(B). And by induction it follows that :\mathrm(\sum_^Q_) = \sum_^\mathrm(Q_) for any N\in\mathbb and non-empty subsets Q_\subseteq X, 1\leq n\leq N.


Statements of the three main results


Notation

D, N\in \ are positive integers. D is the dimension of the ambient space \mathbb R^D. Q_1, ..., Q_N are nonempty, bounded subsets of \mathbb R^D. They are also called "summands". N is the number of summands. Q = \sum_^N Q_n is the Minkowski sum of the summands. x is an arbitrary vector in \mathrm(Q).


Shapley–Folkman lemma

Since \mathrm(Q) = \sum_^\mathrm(Q_), for any x \in \mathrm(Q), there exist elements q_\in\mathrm(Q_) such that \sum_^q_=x. The Shapley–Folkman lemma refines this statement. For example, every point in ,2 ,1 ,1\mathrm(\)+\mathrm(\) is the sum of an element in \ and an element in ,1/math>. Shuffling indices if necessary, this means that every point in \mathrm(Q) can be decomposed as :x = \sum_^q_ + \sum_^ q_n where q_\in\mathrm(Q_) for 1\leq n\leq D and q_\in Q_ for D+1\leq n\leq N. Note that the reindexing depends on the point x. The lemma may be stated succinctly as :\mathrm\left(\sum_^Q_\right)\subseteq\bigcup_ \left( \sum_\mathrm(Q_)+\sum_Q_\right).


The converse of Shapley–Folkman lemma

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


Shapley–Folkman theorem

Shapley and Folkman used their lemma to prove the following theorem, which quantifies the difference between Q and \mathrm(Q) using squared
Euclidean distance In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefore ...
. For any nonempty subset S \subset \R^D and any point x\in \R^D, define their squared Euclidean distance to bed^2(x, S) = \inf_\, x-y\, ^2.And more generally, for any two nonempty subsets S, S' \subset \R^D, define d^2(S, S') = \inf_\, x-y\, ^2.Note that d^2(x, S) = (\inf_\, x-y\, )^2, so we can simply write d^2(x, S) = d(x, S)^2, where d(x, S) = \inf_\, x-y\, . Similarly, d^2(S, S') = d(S, S')^2. For example, d^2(
, 2 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
\) = 1/4 = d(
, 2 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
\)^2. 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 iff they are equal. Thus, we may quantify how close to convexity Q is by upper-bounding d^2( \mathrm(Q), Q). For any bounded subset S \subset \R^D, define its circumradius rad(S)to be the infimum of the radius of all balls containing it (as shown in the diagram). More formally,rad(S) \equiv \inf _ \sup _\, x-y\, Now we can state where we use the notation \sum_ to mean "the sum of the 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 r(S) of a bounded subset S \subset \R^D to be the infimum of r such that, for any x\in \mathrm(S), there exists a ball B of radius r such that x\in \mathrm(S \cap B). For example, let B' \subset B \subset \R^D be two nested balls, then the circumradius of B\setminus B' is the radius of B, but its inner radius is the radius of B'. Since r(S) \leq rad(S) for any bounded subset S \subset \R^D, the following theorem is a refinement: In particular, if we have an infinite sequence (Q_n)_ of nonempty, bounded subsets of \mathbb R^D, and if there exists some r_0 \geq 0 such that the inner radius of each Q_n is upper-bounded by r_0, then d^2\left( \mathrm\left(\frac 1N \sum_^N Q_n \right), \frac 1N \sum_^N Q_n \right) \leq \frac. 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.


Proofs of the results

There have been many proofs of these results, from the original , to the later
Arrow An arrow is a fin-stabilized projectile launched by a bow. A typical arrow usually consists of a long, stiff, straight shaft with a weighty (and usually sharp and pointed) arrowhead attached to the front end, multiple fin-like stabilizers ...
and Hahn,
Cassels Cassels is a surname, and may refer to: * Andrew Cassels (1969-), Canadian former ice hockey player * Elsie Cassels (1864–1938), Scottish born naturalist and Canadian ornithologist * John Franklin Cassels (1852-1930), member of the Mississippi Ho ...
, Schneider, etc. An abstract and elegant proof by Ekeland has been extended by Artstein. Different proofs have also appeared in unpublished papers. An elementary proof of the Shapley–Folkman lemma can be found in the book by Bertsekas, together with applications in estimating the duality gap in separable optimization problems and zero-sum games. Usual proofs of these results are nonconstructive: they establish only the
existence Existence is the ability of an entity to interact with reality. In philosophy, it refers to the ontological property of being. Etymology The term ''existence'' comes from Old French ''existence'', from Medieval Latin ''existentia/exsistentia' ...
of the representation, but do not provide an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for computing the representation. In 1981, Starr published an iterative algorithm for a less sharp version of the Shapley–Folkman–Starr theorem.


History

The lemma of
Lloyd Shapley Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
and
Jon Folkman Jon Hal Folkman (December 8, 1938 – January 23, 1969) was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation. Schooling Folkman was a Putnam Fellow in 1960. He received his Ph.D. in 1964 from P ...
was first published by the economist Ross M. Starr, who was investigating the existence of economic equilibria while studying with
Kenneth Arrow Kenneth Joseph Arrow (23 August 1921 – 21 February 2017) was an American economist, mathematician, writer, and political theorist. He was the joint winner of the Nobel Memorial Prize in Economic Sciences with John Hicks in 1972. In economi ...
. In his paper, Starr studied a ''convexified'' economy, in which non-convex sets were replaced by their convex hulls; Starr proved that the convexified economy has equilibria that are closely approximated by "quasi-equilibria" of the original economy; moreover, he proved that every quasi-equilibrium has many of the optimal properties of true equilibria, which are proved to exist for convex economies. Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used to show that central results of (convex) economic theory are good approximations to large economies with non-convexities; for example, quasi-equilibria closely approximate equilibria of a convexified economy. "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Roger Guesnerie. The topic of non-convex sets in economics has been studied by many
Nobel laureates The Nobel Prizes ( sv, Nobelpriset, no, Nobelprisen) are awarded annually by the Royal Swedish Academy of Sciences, the Swedish Academy, the Karolinska Institutet, and the Norwegian Nobel Committee to individuals and organizations who make ou ...
: Shapley himself (2012), Arrow (1972), Robert Aumann (2005),
Gérard Debreu Gérard Debreu (; 4 July 1921 – 31 December 2004) was a French-born economist and mathematician. Best known as a professor of economics at the University of California, Berkeley, where he began work in 1962, he won the 1983 Nobel Memorial Prize ...
(1983),
Tjalling Koopmans Tjalling Charles Koopmans (August 28, 1910 – February 26, 1985) was a Dutch-American mathematician and economist. He was the joint winner with Leonid Kantorovich of the 1975 Nobel Memorial Prize in Economic Sciences for his work on the theory ...
(1975),
Paul Krugman Paul Robin Krugman ( ; born February 28, 1953) is an American economist, who is Distinguished Professor of Economics at the Graduate Center of the City University of New York, and a columnist for ''The New York Times''. In 2008, Krugman was t ...
(2008), and
Paul Samuelson Paul Anthony Samuelson (May 15, 1915 – December 13, 2009) was an American economist who was the first American to win the Nobel Memorial Prize in Economic Sciences. When awarding the prize in 1970, the Swedish Royal Academies stated that he " ...
(1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with
Leonid Hurwicz Leonid Hurwicz (; August 21, 1917 – June 24, 2008) was a Polish-American economist and mathematician, known for his work in game theory and mechanism design. He originated the concept of incentive compatibility, and showed how desired outcome ...
,
Leonid Kantorovich Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
(1975), and
Robert Solow Robert Merton Solow, GCIH (; born August 23, 1924) is an American economist whose work on the theory of economic growth culminated in the exogenous growth model named after him. He is currently Emeritus Institute Professor of Economics at th ...
(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 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 anal ...
, in
mathematical 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 in
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 ...
; in each of these three mathematical sciences, non-convexity is an important feature of applications.


Economics

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 anal ...
, a consumer's
preferences In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between alternatives. For example, someone prefers A over B if they would rather choose A than B. Preferences are central to decision t ...
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 In economics, an indifference curve connects points on a graph representing different quantities of two goods, points between which a consumer is ''indifferent''. That is, any combinations of two products indicated by the curve will provide the c ...
'' is defined for each consumer; a consumer's indifference curve contains all the baskets of commodities that the consumer regards as equivalent: That is, for every pair of baskets on the same indifference curve, the consumer does not prefer one basket over another. Through each basket of commodities passes one indifference curve. A consumer's ''preference set'' (relative to an indifference curve) is the union of the indifference curve and all the commodity baskets that the consumer prefers over the indifference curve. A consumer's ''preferences'' are ''convex'' if all such preference sets are convex. An optimal basket of goods occurs where the budget-line supports a consumer's preference set, as shown in the diagram. This means that an optimal basket is on the highest possible indifference curve given the budget-line, which is defined in terms of a price vector and the consumer's income (endowment vector). Thus, the set of optimal baskets is a function of the prices, and this function is called the consumer's '' demand''. If the preference set is convex, then at every price the consumer's demand is a convex set, for example, a unique optimal basket or a line-segment of baskets.


Non-convex preferences

However, if a preference set is ''non-convex'', then some prices determine a budget-line that supports two ''separate'' optimal-baskets. For example, we can imagine that, for zoos, a lion costs as much as an eagle, and further that a zoo's budget suffices for one eagle or one lion. We can suppose also that a zoo-keeper views either animal as equally valuable. In this case, the zoo would purchase either one lion or one eagle. Of course, a contemporary zoo-keeper does not want to purchase half of an eagle and half of a lion (or a
griffin The griffin, griffon, or gryphon ( Ancient Greek: , ''gryps''; Classical Latin: ''grȳps'' or ''grȳpus''; Late and Medieval Latin: ''gryphes'', ''grypho'' etc.; Old French: ''griffon'') is a legendary creature with the body, tail, and ...
)! Thus, the zoo-keeper's preferences are non-convex: The zoo-keeper prefers having either animal to having any strictly convex combination of both. When the consumer's preference set is non-convex, then (for some prices) the consumer's demand is not connected; a disconnected demand implies some discontinuous behavior by the consumer, as discussed by
Harold Hotelling Harold Hotelling (; September 29, 1895 – December 26, 1973) was an American mathematical statistician and an influential economic theorist, known for Hotelling's law, Hotelling's lemma, and Hotelling's rule in economics, as well as Hotelling's ...
:
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.
The difficulties of studying non-convex preferences were emphasized by
Herman Wold Herman Ole Andreas Wold (25 December 1908 – 16 February 1992) was a Norwegian-born econometrician and statistician who had a long career in Sweden. Wold was known for his work in mathematical economics, in time series analysis, and in econometri ...
and again by
Paul Samuelson Paul Anthony Samuelson (May 15, 1915 – December 13, 2009) was an American economist who was the first American to win the Nobel Memorial Prize in Economic Sciences. When awarding the prize in 1970, the Swedish Royal Academies stated that he " ...
, who wrote that non-convexities are "shrouded in eternal darkness ...", according to Diewert. Nonetheless, non-convex preferences were illuminated from 1959 to 1961 by a sequence of papers in ''
The Journal of Political Economy The ''Journal of Political Economy'' is a monthly peer-reviewed academic journal published by the University of Chicago Press. Established by James Laurence Laughlin in 1892, it covers both theoretical and empirical economics. In the past, th ...
'' (''JPE''). The main contributors were Farrell, Bator, Koopmans, and Rothenberg. In particular, Rothenberg's paper discussed the approximate convexity of sums of non-convex sets. These ''JPE''-papers stimulated a paper by
Lloyd Shapley Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
and Martin Shubik, which considered convexified consumer-preferences and introduced the concept of an "approximate equilibrium". The ''JPE''-papers and the Shapley–Shubik paper influenced another notion of "quasi-equilibria", due to Robert Aumann. uses results from


Starr's 1969 paper and contemporary economics

Previous publications on non-convexity and economics were collected in an annotated bibliography by
Kenneth Arrow Kenneth Joseph Arrow (23 August 1921 – 21 February 2017) was an American economist, mathematician, writer, and political theorist. He was the joint winner of the Nobel Memorial Prize in Economic Sciences with John Hicks in 1972. In economi ...
. He gave the bibliography to Starr, who was then an undergraduate enrolled in Arrow's (graduate) advanced mathematical-economics course. 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 In macroeconomics, aggregate demand (AD) or domestic final demand (DFD) is the total demand for final goods and services in an economy at a given time. It is often called effective demand, though at other times this term is distinguished. This is ...
was the sum of convex hulls of the consumers' demands. Starr's ideas interested the mathematicians
Lloyd Shapley Lloyd Stowell Shapley (; June 2, 1923 – March 12, 2016) was an American mathematician and Nobel Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of ...
and
Jon Folkman Jon Hal Folkman (December 8, 1938 – January 23, 1969) was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation. Schooling Folkman was a Putnam Fellow in 1960. He received his Ph.D. in 1964 from P ...
, who proved their
eponym An eponym is a person, a place, or a thing after whom or which someone or something is, or is believed to be, named. The adjectives which are derived from the word eponym include ''eponymous'' and ''eponymic''. Usage of the word The term ''epon ...
ous lemma and theorem in "private correspondence", which was reported by Starr's published paper of 1969. 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 ''p''opt with the following properties: * For each quasi-equilibrium's prices ''p''opt, all consumers can choose optimal baskets (maximally preferred and meeting their budget constraints). * At quasi-equilibrium prices ''p''opt in the convexified economy, every good's market is in equilibrium: Its supply equals its demand. * For each quasi-equilibrium, the prices "nearly clear" the markets for the original economy: an upper bound on the
distance 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 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. Starr established that
"in the aggregate, the discrepancy between an allocation in the fictitious economy generated by aking the convex hulls of all of the consumption and production setsand some allocation in the real economy is bounded in a way that is independent of the number of economic agents. Therefore, the average agent experiences a deviation from intended actions that vanishes in significance as the number of agents goes to infinity".
Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used in economic theory. Roger Guesnerie summarized their economic implications: "Some key results obtained under the convexity assumption remain (approximately) relevant in circumstances where convexity fails. For example, in economies with a large consumption side, preference nonconvexities do not destroy the standard results". "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Guesnerie. The topic of non-convex sets in economics has been studied by many
Nobel laureates The Nobel Prizes ( sv, Nobelpriset, no, Nobelprisen) are awarded annually by the Royal Swedish Academy of Sciences, the Swedish Academy, the Karolinska Institutet, and the Norwegian Nobel Committee to individuals and organizations who make ou ...
: Arrow (1972), Robert Aumann (2005),
Gérard Debreu Gérard Debreu (; 4 July 1921 – 31 December 2004) was a French-born economist and mathematician. Best known as a professor of economics at the University of California, Berkeley, where he began work in 1962, he won the 1983 Nobel Memorial Prize ...
(1983),
Tjalling Koopmans Tjalling Charles Koopmans (August 28, 1910 – February 26, 1985) was a Dutch-American mathematician and economist. He was the joint winner with Leonid Kantorovich of the 1975 Nobel Memorial Prize in Economic Sciences for his work on the theory ...
(1975),
Paul Krugman Paul Robin Krugman ( ; born February 28, 1953) is an American economist, who is Distinguished Professor of Economics at the Graduate Center of the City University of New York, and a columnist for ''The New York Times''. In 2008, Krugman was t ...
(2008), and
Paul Samuelson Paul Anthony Samuelson (May 15, 1915 – December 13, 2009) was an American economist who was the first American to win the Nobel Memorial Prize in Economic Sciences. When awarding the prize in 1970, the Swedish Royal Academies stated that he " ...
(1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with
Leonid Hurwicz Leonid Hurwicz (; August 21, 1917 – June 24, 2008) was a Polish-American economist and mathematician, known for his work in game theory and mechanism design. He originated the concept of incentive compatibility, and showed how desired outcome ...
,
Leonid Kantorovich Leonid Vitalyevich Kantorovich ( rus, Леони́д Вита́льевич Канторо́вич, , p=lʲɪɐˈnʲit vʲɪˈtalʲjɪvʲɪtɕ kəntɐˈrovʲɪtɕ, a=Ru-Leonid_Vitaliyevich_Kantorovich.ogg; 19 January 19127 April 1986) was a Soviet ...
(1975), and
Robert Solow Robert Merton Solow, GCIH (; born August 23, 1924) is an American economist whose work on the theory of economic growth culminated in the exogenous growth model named after him. He is currently Emeritus Institute Professor of Economics at th ...
(1987). The Shapley–Folkman–Starr results have been featured in the economics literature: in
microeconomics Microeconomics is a branch of mainstream economics that studies the behavior of individuals and firms in making decisions regarding the allocation of scarce resources and the interactions among these individuals and firms. Microeconomics fo ...
, in general-equilibrium theory, in
public economics Public economics ''(or economics of the public sector)'' is the study of government policy through the lens of economic efficiency and equity. Public economics builds on the theory of welfare economics and is ultimately used as a tool to improve ...
(including
market failure In neoclassical economics, market failure is a situation in which the allocation of goods and services by a free market is not Pareto efficient, often leading to a net loss of economic value. Market failures can be viewed as scenarios where indiv ...
s), as well as in
game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, in
mathematical economics Mathematical economics is the application of mathematical methods to represent theories and analyze problems in economics. Often, these applied methods are beyond simple geometry, and may include differential and integral calculus, difference ...
, and in
applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemati ...
(for economists). The Shapley–Folkman–Starr results have also influenced economics research using measure and integration theory.


Mathematical optimization

The Shapley–Folkman lemma has been used to explain why large minimization problems with non-convexities can be nearly solved (with iterative methods whose convergence proofs are stated for only convex problems). The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.


Preliminaries of optimization theory

Nonlinear optimization relies on the following definitions for functions: *The ''graph'' of a function ''f'' is the set of the pairs of
argument An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialecti ...
s ''x'' and function evaluations ''f''(''x'') : Graph(''f'') = * The '' epigraph'' of a real-valued function ''f'' is the set of points ''above'' the graph : Epi(''f'') = . *A real-valued function is defined to be a ''
convex function In mathematics, a real-valued function is called convex if the line segment between any two points on the graph of the function lies above the graph between the two points. Equivalently, a function is convex if its epigraph (the set of poi ...
'' if its epigraph is a convex set. For example, the quadratic function ''f''(''x'') = ''x''2 is convex, as is the absolute value function ''g''(''x'') = , ''x'', . However, the sine function (pictured) is non-convex on the interval (0, π).


Additive optimization problems

In many optimization problems, the objective function f is ''separable'': that is, ''f'' is the sum of ''many'' summand-functions, each of which has its own argument: : ''f''(''x'') = ''f''( (''x''1, ..., ''x'' N) ) = Σ ''f''''n''(''x''''n''). For example, problems of linear optimization are separable. Given a separable problem with an optimal solution, we fix an optimal solution : ''x''min = (''x''1, ..., ''x'' N)min with the minimum value  For this separable problem, we also consider an optimal solution (''x''min, ''f''(''x''min) ) to the "''convexified problem''", where convex hulls are taken of the graphs of the summand functions. Such an optimal solution is the
limit of a sequence As the positive integer n becomes larger and larger, the value n\cdot \sin\left(\tfrac1\right) becomes arbitrarily close to 1. We say that "the limit of the sequence n\cdot \sin\left(\tfrac1\right) equals 1." In mathematics, the limi ...
of points in the convexified problem : (''x''''j'', ''f''(''x''j) ) ∈  Σ Conv (Graph( ''f''''n'' ) ). Of course, the given optimal-point is a sum of points in the graphs of the original summands and of a small number of convexified summands, by the Shapley–Folkman lemma. This analysis was published by Ivar Ekeland in 1974 to explain the apparent convexity of separable problems with many summands, despite the non-convexity of the summand problems. In 1973, the young mathematician Claude Lemaréchal was surprised by his success with
convex minimization Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization probl ...
methods on problems that were known to be non-convex; for minimizing nonlinear problems, a solution of the
dual problem In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then ...
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.: Published in the first English edition of 1976, Ekeland's appendix proves the Shapley–Folkman lemma, also acknowledging Lemaréchal's experiments on page 373. Ekeland's analysis explained the success of methods of convex minimization on ''large'' and ''separable'' problems, despite the non-convexities of the summand functions. Ekeland and later authors argued that additive separability produced an approximately convex aggregate problem, even though the summand functions were non-convex. The crucial step in these publications is the use of the Shapley–Folkman lemma. The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions. acknowledging on page 374 and on page 381:

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


Probability and measure theory

Convex sets are often studied with
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 ...
. Each point in the convex hull of a ( non-empty) subset ''Q'' of a finite-dimensional space is the
expected value In probability theory, the expected value (also called expectation, expectancy, mathematical expectation, mean, average, or first moment) is a generalization of the weighted average. Informally, the expected value is the arithmetic mean of a ...
of a
simple Simple or SIMPLE may refer to: *Simplicity, the state or quality of being simple Arts and entertainment * ''Simple'' (album), by Andy Yorke, 2008, and its title track * "Simple" (Florida Georgia Line song), 2018 * "Simple", a song by Johnn ...
random vector that takes its values in ''Q'', as a consequence of
Carathéodory's lemma In mathematics, Nevanlinna's criterion in complex analysis, proved in 1920 by the Finnish mathematician Rolf Nevanlinna, characterizes holomorphic univalent functions on the unit disk which are starlike. Nevanlinna used this criterion to prove ...
. Thus, for a non-empty set ''Q'', the collection of the expected values of the simple, ''Q''-valued random vectors equals ''Q'' convex hull; this equality implies that the Shapley–Folkman–Starr results are useful in probability theory. In the other direction, probability theory provides tools to examine convex sets generally and the Shapley–Folkman–Starr results specifically. The Shapley–Folkman–Starr results have been widely used in the probabilistic theory of random sets, for example, to prove a law of large numbers, a
central limit theorem In probability theory, the central limit theorem (CLT) establishes that, in many situations, when independent random variables are summed up, their properly normalized sum tends toward a normal distribution even if the original variables themsel ...
, and a large-deviations 
principle A principle is a proposition or value that is a guide for behavior or evaluation. In law, it is a rule that has to be or usually is to be followed. It can be desirably followed, or it can be an inevitable consequence of something, such as the l ...
. These proofs of probabilistic limit theorems used the Shapley–Folkman–Starr results to avoid the assumption that all the random sets be convex. A
probability measure In mathematics, a probability measure is a real-valued function defined on a set of events in a probability space that satisfies measure properties such as ''countable additivity''. The difference between a probability measure and the more ge ...
is a finite measure, and the Shapley–Folkman lemma has applications in non-probabilistic measure theory, such as the theories of
volume Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). ...
and of vector measures. The Shapley–Folkman lemma enables a refinement of the Brunn–Minkowski inequality, which bounds the volume of sums in terms of the volumes of their summand-sets. The volume of a set is defined in terms of the
Lebesgue measure In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wi ...
, which is defined on subsets of
Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
. In advanced measure-theory, the Shapley–Folkman lemma has been used to prove
Lyapunov's theorem In mathematics, a vector measure is a function defined on a family of sets and taking vector values satisfying certain properties. It is a generalization of the concept of finite measure, which takes nonnegative real values only. Definitions an ...
, which states that the range of a vector measure is convex. Here, the traditional term "''range''" (alternatively, "image") is the set of values produced by the function. A ''vector measure'' is a vector-valued generalization of a measure; for example, if ''p''1 and ''p''2 are
probability measure In mathematics, a probability measure is a real-valued function defined on a set of events in a probability space that satisfies measure properties such as ''countable additivity''. The difference between a probability measure and the more ge ...
s defined on the same measurable space, then the product function  is a vector measure, where  is defined for every
event Event may refer to: Gatherings of people * Ceremony, an event of ritual significance, performed on a special occasion * Convention (meeting), a gathering of individuals engaged in some common interest * Event management, the organization of ev ...
 ''ω'' by :(''p''1 ''p''2)(''ω'')=(''p''1(''ω''), ''p''2(''ω'')). Lyapunov's theorem has been used 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 anal ...
, was noted by the winner of the 1983
Nobel Prize in Economics The Nobel Memorial Prize in Economic Sciences, officially the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel ( sv, Sveriges riksbanks pris i ekonomisk vetenskap till Alfred Nobels minne), is an economics award administered ...
,
Gérard Debreu Gérard Debreu (; 4 July 1921 – 31 December 2004) was a French-born economist and mathematician. Best known as a professor of economics at the University of California, Berkeley, where he began work in 1962, he won the 1983 Nobel Memorial Prize ...
. wrote:
The concept of a convex set (i.e., a set containing the segment connecting any two of its points) had repeatedly been placed at the center of economic theory before 1964. It appeared in a new light with the introduction of integration theory in the study of economic competition: If one associates with every agent of an economy an arbitrary set in the commodity space and ''if one averages those individual sets'' over a collection of insignificant agents, ''then the resulting set is necessarily convex''. ebreu appends this footnote: "On this direct consequence of a theorem of A. A. Lyapunov, see ."But explanations of the ... functions of prices ... can be made to rest on the ''convexity of sets derived by that averaging process''. ''Convexity'' in the commodity space ''obtained by aggregation'' over a collection of insignificant agents is an insight that economic theory owes ... to integration theory. 'Italics added''
in ( "bang-bang")
control theory Control theory is a field of mathematics that deals with the control system, control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive ...
, and in statistical theory. Lyapunov's theorem has been called a
continuous Continuity or continuous may refer to: Mathematics * Continuity (mathematics), the opposing concept to discreteness; common examples include ** Continuous probability distribution or random variable in probability and statistics ** Continuous g ...
counterpart of the Shapley–Folkman lemma, which has itself been called a discrete analogue of Lyapunov's theorem.


Notes


References

* * * Republished in a
festschrift In academia, a ''Festschrift'' (; plural, ''Festschriften'' ) is a book honoring a respected person, especially an academic, and presented during their lifetime. It generally takes the form of an edited volume, containing contributions from the ...
for Robert J. Aumann, winner of the 2008
Nobel Prize in Economics The Nobel Memorial Prize in Economic Sciences, officially the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel ( sv, Sveriges riksbanks pris i ekonomisk vetenskap till Alfred Nobels minne), is an economics award administered ...
: ** * * * * * * * * * * Reprint of (1982) Academic Press. * Proceedings of 1981 IEEE Conference on Decision and Control, San Diego, CA, December 1981, pp. 432–443. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * . Reprint of the 1970 () Princeton Mathematical Series 28 * * * * English translation of the (1998) French ''Microéconomie: Les défaillances du marché'' (Economica, Paris) * * * * * * * * * * * * * * *


External links

* * * {{DEFAULTSORT:Shapley-Folkman Lemma Convex hulls Convex geometry Geometric transversal theory Additive combinatorics Sumsets General equilibrium theory Convex optimization Theorems in geometry Lloyd Shapley