User:Kiefer.Wolfowitz/Sandbox/SFS
From Wikipedia, the free encyclopedia
In geometry, the Shapley–Folkman lemma and the Shapley–Folkman–Starr theorem study the Minkowski addition of sets in a vector space. Minkowski addition is defined by the addition of the sets' members; for example, adding the set consisting of the integers zero and one to itself yields the set of the integers zero, one, and two:
- {0, 1} + {0, 1} = {0+0, 0+1, 1+0, 1+1} = {0, 1, 2}.
The Shapley–Folkman–Starr results address the question, "Is the sum of many sets close to being convex?"[2] A set is defined to be convex if every line segment joining two of its points is a subset in the set: For example, a solid disk is convex but a circle is not, because the line segment joining two distinct points is not a subset of the circle. The Shapley–Folkman–Starr results suggest that if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum is approximately convex.[1]
The Shapley–Folkman–Starr theorem states an upper bound on the distance between the Minkowski sum and its convex hull—the convex hull of the Minkowski sum is the smallest convex set that contains the Minkowski sum. This distance is zero exactly when the sum is convex. Their bound on the distance depends on the dimension D and on the shapes of the summand-sets, but not on the number of summand-sets N, when N > D. The shapes of a subcollection of only D summand-sets determine the bound on the distance between the average sumset and its convex hull; thus, as the number of summands increases to infinity, the bound decreases to zero (for summand-sets of uniformly bounded size).[3]
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 that do not require consumer preferences to be convex.[1] In his paper, Starr proved that a "convexified" economy has equilibria that are closely approximated by "quasi-equilibria" of the original economy; moreover, he proved that every quasi-equilbrium 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. "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Roger Guesnerie.[4]
The Shapley–Folkman lemma has been applied also to optimization and probability theory.[3] In optimization theory, the Shapley–Folkman lemma has been used to explain the solution of minimization problems that are sums of many functions.[5][6] The Shapley–Folkman lemma has been used also in proofs of the "law of averages" for random sets, a theorem that had been proved for only convex sets.[7]