Applications Shapley–Folkman lemma

1 applications

1.1 economics

1.1.1 non-convex preferences
1.1.2 starr s 1969 paper , contemporary economics


1.2 mathematical optimization

1.2.1 preliminaries of optimization theory
1.2.2 additive optimization problems


1.3 probability , measure theory

applications

the shapley–folkman lemma enables researchers extend results minkowski sums of convex sets sums of general sets, need not convex. such sums of sets arise in economics, in mathematical optimization, , in probability theory; in each of these 3 mathematical sciences, non-convexity important feature of applications.

economics

the consumer prefers every basket of goods on indifference curve i3 on each basket on  i2. basket (qx, qy), budget line (shown in blue) supports i2, optimal , feasible, unlike basket lying on  i3 preferred unfeasible.

in economics, consumer s preferences defined on baskets of goods. each basket represented non-negative vector, coordinates represent quantities of goods. on set of baskets, indifference curve defined each consumer; consumer s indifference curve contains baskets of commodities consumer regards equivalent: is, every pair of baskets on same indifference curve, consumer not prefer 1 basket on another. through each basket of commodities passes 1 indifference curve. consumer s preference set (relative indifference curve) union of indifference curve , commodity baskets consumer prefers on indifference curve. consumer s preferences convex if such preference sets convex.

an optimal basket of goods occurs budget-line supports consumer s preference set, shown in diagram. means optimal basket on highest possible indifference curve given budget-line, defined in terms of price vector , consumer s income (endowment vector). thus, set of optimal baskets function of prices, , function called consumer s demand. if preference set convex, @ every price consumer s demand convex set, example, unique optimal basket or line-segment of baskets.

non-convex preferences

when consumer s preferences have concavities, consumer may jump between 2 separate optimal baskets.

however, if preference set non-convex, prices determine budget-line supports 2 separate optimal-baskets. example, can imagine that, zoos, lion costs as eagle, , further zoo s budget suffices 1 eagle or 1 lion. can suppose zoo-keeper views either animal equally valuable. in case, zoo purchase either 1 lion or 1 eagle. of course, contemporary zoo-keeper not want purchase half of eagle , half of lion (or griffin)! thus, zoo-keeper s preferences non-convex: zoo-keeper prefers having either animal having strictly convex combination of both.

when consumer s preference set non-convex, (for prices) consumer s demand not connected; disconnected demand implies discontinuous behavior consumer, discussed harold hotelling:

if indifference curves purchases thought of possessing wavy character, convex origin in regions , concave in others, forced conclusion portions convex origin can regarded possessing importance, since others unobservable. can detected discontinuities may occur in demand variation in price-ratios, leading abrupt jumping of point of tangency across chasm when straight line rotated. but, while such discontinuities may reveal existence of chasms, can never measure depth. concave portions of indifference curves , many-dimensional generalizations, if exist, must forever remain in unmeasurable obscurity.

the difficulties of studying non-convex preferences emphasized herman wold , again paul samuelson, wrote non-convexities shrouded in eternal darkness ... , according to diewert.

nonetheless, non-convex preferences illuminated from 1959 to 1961 sequence of papers in journal of political economy (jpe). main contributors farrell, bator, koopmans, , rothenberg. in particular, rothenberg s paper discussed approximate convexity of sums of non-convex sets. these jpe-papers stimulated paper lloyd shapley , martin shubik, considered convexified consumer-preferences , introduced concept of approximate equilibrium . jpe-papers , shapley–shubik paper influenced notion of quasi-equilibria , due robert aumann.

starr s 1969 paper , contemporary economics

kenneth arrow (1972 nobel laureate) helped ross m. starr study non-convex economies.

previous publications on non-convexity , economics collected in annotated bibliography kenneth arrow. gave bibliography starr, undergraduate enrolled in arrow s (graduate) advanced mathematical-economics course. in term-paper, starr studied general equilibria of artificial economy in non-convex preferences replaced convex hulls. in convexified economy, @ each price, aggregate demand sum of convex hulls of consumers demands. starr s ideas interested mathematicians lloyd shapley , jon folkman, proved eponymous lemma , theorem in private correspondence , reported starr s published paper of 1969.

in 1969 publication, starr applied shapley–folkman–starr theorem. starr proved convexified economy has general equilibria can closely approximated quasi-equilibria of original economy, when number of agents exceeds dimension of goods: concretely, starr proved there exists @ least 1 quasi-equilibrium of prices popt following properties:

for each quasi-equilibrium s prices popt, consumers can choose optimal baskets (maximally preferred , meeting budget constraints).
at quasi-equilibrium prices popt in convexified economy, every s market in equilibrium: supply equals demand.
for each quasi-equilibrium, prices clear markets original economy: upper bound on distance between set of equilibria of convexified economy , set of quasi-equilibria of original economy followed starr s corollary shapley–folkman theorem.

starr established that

in aggregate, discrepancy between allocation in fictitious economy generated [taking convex hulls of of consumption and production sets] , allocation in real economy bounded in way independent of number of economic agents. therefore, average agent experiences deviation intended actions vanishes in significance number of agents goes infinity .

following starr s 1969 paper, shapley–folkman–starr results have been used in economic theory. roger guesnerie summarized economic implications: key results obtained under convexity assumption remain (approximately) relevant in circumstances convexity fails. example, in economies large consumption side, preference nonconvexities not destroy standard results . derivation of these results in general form has been 1 of major achievements of postwar economic theory , wrote guesnerie. topic of non-convex sets in economics has been studied many nobel laureates: arrow (1972), robert aumann (2005), gérard debreu (1983), tjalling koopmans (1975), paul krugman (2008), , paul samuelson (1970); complementary topic of convex sets in economics has been emphasized these laureates, along leonid hurwicz, leonid kantorovich (1975), , robert solow (1987). shapley–folkman–starr results have been featured in economics literature: in microeconomics, in general-equilibrium theory, in public economics (including market failures), in game theory, in mathematical economics, , in applied mathematics (for economists). shapley–folkman–starr results have influenced economics research using measure , integration theory.

mathematical optimization

a function convex if region above graph convex set.

the shapley–folkman lemma has been used explain why large minimization problems non-convexities can solved (with iterative methods convergence proofs stated convex problems). shapley–folkman lemma has encouraged use of methods of convex minimization on other applications sums of many functions.

preliminaries of optimization theory

nonlinear optimization relies on following definitions functions:

the graph of function f set of pairs of arguments x , function evaluations f(x)


graph(f) = { (x, f(x) ) }


the epigraph of real-valued function f set of points above graph


the sine function non-convex.



epi(f) = { (x, u) : f(x) ≤ u }.


a real-valued function defined convex function if epigraph convex set.

for example, quadratic function f(x) = x convex, absolute value function g(x) = |x|. however, sine function (pictured) non-convex on interval (0, π).

additive optimization problems

in many optimization problems, objective function f separable: is, f sum of many summand-functions, each of has own argument:

f(x) = f( (x1, ..., xn) ) = ∑ fn(xn).

for example, problems of linear optimization separable. given separable problem optimal solution, fix optimal solution

xmin = (x1, ..., xn)min

with minimum value f(xmin). separable problem, consider optimal solution (xmin, f(xmin) ) convexified problem , convex hulls taken of graphs of summand functions. such optimal solution limit of sequence of points in convexified problem

(xj, f(xj) ) ∈  ∑ conv (graph( fn ) ).

of course, given optimal-point sum of points in graphs of original summands , of small number of convexified summands, shapley–folkman lemma.

this analysis published ivar ekeland in 1974 explain apparent convexity of separable problems many summands, despite non-convexity of summand problems. in 1973, young mathematician claude lemaréchal surprised success convex minimization methods on problems known non-convex; minimizing nonlinear problems, solution of dual problem problem need not provide useful information solving primal problem, unless primal problem convex , satisfy constraint qualification. lemaréchal s problem additively separable, , each summand function non-convex; nonetheless, solution dual problem provided close approximation primal problem s optimal value. ekeland s analysis explained success of methods of convex minimization on large , separable problems, despite non-convexities of summand functions. ekeland , later authors argued additive separability produced approximately convex aggregate problem, though summand functions non-convex. crucial step in these publications use of shapley–folkman lemma. shapley–folkman lemma has encouraged use of methods of convex minimization on other applications sums of many functions.

probability , measure theory

convex sets studied probability theory. each point in convex hull of (non-empty) subset q of finite-dimensional space expected value of simple random vector takes values in q, consequence of carathéodory s lemma. thus, non-empty set q, collection of expected values of simple, q-valued random vectors equals q s convex hull; equality implies shapley–folkman–starr results useful in probability theory. in other direction, probability theory provides tools examine convex sets , shapley–folkman–starr results specifically. shapley–folkman–starr results have been used in probabilistic theory of random sets, example, prove law of large numbers, central limit theorem, , large-deviations principle. these proofs of probabilistic limit theorems used shapley–folkman–starr results avoid assumption random sets convex.

a probability measure finite measure, , shapley–folkman lemma has applications in non-probabilistic measure theory, such theories of volume , of vector measures. shapley–folkman lemma enables refinement of brunn–minkowski inequality, bounds volume of sums in terms of volumes of summand-sets. volume of set defined in terms of lebesgue measure, defined on subsets of euclidean space. in advanced measure-theory, shapley–folkman lemma has been used prove lyapunov s theorem, states range of vector measure convex. here, traditional term range (alternatively, image ) set of values produced function. vector measure vector-valued generalization of measure; example, if p1 and p2 probability measures defined on same measurable space, product function p1 p2 vector measure, where p1 p2 defined every event ω by

(p1 p2)(ω)=(p1(ω), p2(ω)).

lyapunov s theorem has been used in economics, in ( bang-bang ) control theory, , in statistical theory. lyapunov s theorem has been called continuous counterpart of shapley–folkman lemma, has been called discrete analogue of lyapunov s theorem.