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), 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 \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 const ...
 \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 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 ...
, 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  D can be viewed as the set 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 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 \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 const ...
 \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 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 ...
,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), 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 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 o ...
. 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 \) = 1/4 = d( , 2 \)^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, Schneider, etc. An abstract and elegant proof by
Ekeland Ekeland is a surname. Notable people with the surname include: * Arne Ekeland (1908–1994), Norwegian painter * Ivar Ekeland (born 1944), French mathematician of Norwegian descent * Jostein Ekeland (born 1997), Norwegian footballer *Tor 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/exsistenti ...
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 and Jon Folkman was first published by the economist Ross M. Starr, who was investigating the existence of economic equilibria while studying with
Kenneth Arrow 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 Roger Guesnerie is an economist born in France in 1943. He is currently the Chaired Professor of Economic Theory and Social Organization of the '' Collège de France'', Director of Studies at the École des hautes études en sciences sociales, a ...
. 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 ...
: 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 P ...
(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 "h ...
(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 Sovie ...
(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 analy ...
, 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 o ...
; 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 analy ...
, a consumer's
preferences In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between wikt:alternative, alternatives. For example, someone prefers A over B if they would rather choose A than B. Preferences are centra ...
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 In economics, demand is the quantity of a good that consumers are willing and able to purchase at various prices during a given time. The relationship between price and quantity demand is also called the demand curve. Demand for a specific item ...
''. 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 Latin, Late and Medieval Latin: ''gryphes'', ''grypho'' etc.; Old French: ''griffon'') is a legendary creature with the body, tail ...
)! 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 econometric ...
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 "h ...
, 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'' (''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 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 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 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 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 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 ...
: 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 P ...
(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 "h ...
(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 Sovie ...
(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, 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 improv ...
(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 ...
s), as well as in game theory, 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 a ...
, 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 mathemat ...
(for economists). The Shapley–Folkman–Starr results have also influenced economics research using measure and
integration theory Integration may refer to: Biology * Multisensory integration * Path integration * Pre-integration complex, viral genetic material used to insert a viral genome into a host genome *DNA integration, by means of site-specific recombinase technolo ...
.


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 In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear. An optimization problem is one of calculation of the extrema (maxima, minima or st ...
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 dialect ...
s ''x'' and function evaluations ''f''(''x'') : Graph(''f'') = * The '' epigraph'' of a
real-valued function In mathematics, a real-valued function is a function whose values are real numbers. In other words, it is a function that assigns a real number to each member of its domain. Real-valued functions of a real variable (commonly called ''real ...
 ''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 poin ...
'' 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 In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cos ...
 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 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 t ...
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 A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are i ...
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 o ...
. 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 random vector that takes its values in ''Q'', as a consequence of Carathéodory's lemma. Thus, for a non-empty set ''Q'', the collection of the expected values of the simple, ''Q''-valued random vectors equals ''Q'' 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 thems ...
, and a large-deviations  principle. 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 g ...
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). Th ...
and of
vector measure 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 and ...
s. 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 ...
, 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 Euclidean sp ...
. In advanced measure-theory, the Shapley–Folkman lemma has been used to prove Lyapunov's theorem, which states that the range of a
vector measure 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 and ...
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 g ...
s defined on the same measurable space, then the product function  is a vector measure, where  is defined for every event ''ω'' 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 analy ...
, was noted by the winner of the 1983 Nobel Prize in Economics,
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 P ...
. 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 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 the system to a ...
, and in
statistical theory The theory of statistics provides a basis for the whole range of techniques, in both study design and data analysis, that are used within applications of statistics. The theory covers approaches to statistical-decision problems and to statisti ...
. Lyapunov's theorem has been called a continuous 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: ** * * * * * * * * * * 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