Talk:Shapley–Folkman lemma

The article defines the distance between two sets, and mixes two distances. One is the infimum of distances between 2 points, which is zero, if two sets have a common point (this is what's defined in the article). The other is Hausdorff distance, which involves both suprema and infima. While the article uses the first definition, it uses properties of Hausdorff distance later. — Preceding unsigned comment added by 160.76.7.2 (talk) 15:37, 18 November 2024 (UTC)

Draft lede for front page

I trust that the article should soon receive FA status,

I just HAD to open my big mouth! Famous last words! (KW 14:04, 8 October 2011 (UTC))

and so I started drafting a main-page lede. I favor the blue graphic, because the primary graphic with its 5 panes does not appear well at 100 pix.

 Kiefer.Wolfowitz 13:58, 4 October 2011 (UTC)

In geometry and economics, the Shapley–Folkman lemma describes the Minkowski addition of sets. Lemmas are steps in a mathematical proof of a theorem. Minkowski addition is defined as the addition of the sets' members: for example

{0, 1} + {0, 1} = {0+0, 0+1, 1+0, 1+1} = {0, 1, 2}.

The Shapley–Folkman lemma provides an affirmative answer to the question, "Is the sum of many sets close to being convex?" A set is defined to be convex if every line segment joining two of its points is a subset in the set: For example, the solid disk $\bullet$ is a convex set but the circle $\circ$ is not, because the line segment joining two distinct points $\oslash$ is not a subset of the circle. The Shapley–Folkman lemma suggests that if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum is approximately convex. The lemma has many applications in economics, where non-convexity is associated with market failures, that is, with inefficient or non-existent economic equilibria. Non-convex sets have been studied by many winners of the Nobel Prize in Economics: Arrow (1972), Aumann (2005), Debreu (1983), Hurwicz (2007), Kantorovich (1975), Koopmans (1975), Krugman (2008), Samuelson (1970), and Solow (1987). (more…)

Featured article issues

The featured-article review elicited many good suggestions, which I was able to act upon to improve the article.

Additional suggestions were made that needed additional time to address. These suggestions are copied here for ease of reference. Kiefer.Wolfowitz 11:28, 5 November 2012 (UTC)

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

Weak oppose. Let me first add to the praise above for the meticulous work that has gone into this well-referenced and carefully explained article on an important technical topic. The article has much improved since February (where I contributed a partial peer review). Nevertheless, on reading the article closely (having not done so since February), I find that it falls short of the demanding FA criteria in several respects, and so cannot support its promotion at present. Areas where I believe improvements could be made include: clarity of exposition, engaging/brilliant prose, comprehensiveness and organization. I will add detailed remarks shortly, most of which I hope can be easily addressed. Geometry guy 21:41, 7 October 2011 (UTC)

I thank you for your past comments. I shall address whatever suggestions you make to the best of my ability. (I am away from my office until next week, however.)  Kiefer.Wolfowitz 22:08, 7 October 2011 (UTC)

• Leading issues. The first few sentences of the lead already illustrate some of the issues (numbered so that it should not be necessary to interleave replies).
  1. The repetition "In geometry and economics... In mathematics..." is clunky; despite comments made above about readers not knowing what a lemma is, an entire sentence is overkill – why not simply wikilink "Shapley-Folkman Lemma"?
  2. The article does not explain what the Shapley-Folkman-Starr theorem is: it discusses their results, including a Shapley-Folkman theorem and Starr's corollary, but no theorem with that name.
  3. The lead sentence does not define the topic: the Shapley-Folkman(-Starr) results do not describe the Minkowski addition of sets in a vector space (the definition of Minkowski addition does that); they describe the extent to which the Minkowski sum of many sets is approximately convex.
  4. The distinction between "addition" and "sum" is important. "Addition" is a synonym for "summation", the process of adding, not a synonym for "sum", the result of the addition. (We do not say "5 is the addition of 2 and 3".) The lead needs to make this distinction clear for Minkowski addition/sums, so that the terms can be selected and used for maximum clarity in the article.
  5. The lead uses terms such as "summand(-)set" and "sumset" without defining or wikilinking them. A particularly problematic example is "average sumset". I was completely unclear about what this meant until I read section 3.2.
  6. Theorems do have ("hypotheses" and) "conclusions", and I am relaxed about the idea that a theorem may "address" or "concern" a particular question. "The Shapley–Folkman–Starr results suggest..." is a bit too loose for me, however. A naive reviewer might ask "suggest to whom?", but the point of the sentence is to provide an intuitive summary of the results, not make suggestions.
  7. "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." Unnecessary repetition: "its convex hull (the smallest convex set containing it)".
  8. "Their bound on the distance..." Antecedent missing/unclear.
  9. Final paragraph: here and elsewhere, "The Shapley-Folkman do-dah..." is used far too much as the subject of the sentence. Try turning sentences around by looking for other subjects, and cut down on the tiresome "also"s.

"The topic of non-convex sets in economics has been studied by many Nobel laureates..."

I left this to last, as it may be a more substantial issue. This segment of the lead is repeated in the article, but does not really summarize anything. The comprehensiveness criterion really bites here: "it neglects no major facts or details and places the subject in context". The legacy of the Shapley-Folkman Lemma is that results previously confined to convex economics and optimization (relatively easy) could be extended to the non-convex domain (much harder) by averaging (e.g., assuming many agents); this needs to be discussed to place the article in context. The applications section contains some such discussion, but is primarily pedagogical/technical and mixes mathematical, historical and evaluative material. The segment "Starr's 1969 paper and contemporary economics" then ends with a list which cries out for elaboration. Overall the treatment of the economics background, history and legacy for the results falls short of what I would hope for in a featured article. Geometry guy 23:18, 7 October 2011 (UTC)

• Mathematics issues. Considerable effort has been made to explain the mathematics behind the S-F Lemma. This is commendable and appropriate as none of the mathematics is particularly hard (at least in the context of plane geometry), so it ought to be possible to explain it to a wide readership. There are some minor shortcomings in this respect.
  1. Introductory example. (This should not begin "For example": the section title suffices.) I read this having forgotten the statement of the Shapley-Folkman Lemma and found it didn't help me very much. It isn't clearly laid out as an example of Minkowski addition of two or more sets, and quickly goes on to discuss averages, where I had not yet got the point. There are also little distractions such as describing {0,1,2} as a subset of the integers, which seems irrelevant. At some point, the article should probably introduce the averaged Minkowski sum (and motivate why it is a useful notion).
  2. Real vector spaces. Is it necessary to use the language of vector spaces if they are all viewed as Rⁿ? Maybe, but readers could easily be put off. Perhaps it is more natural to use vector spaces, but not completely so: the natural setting for convexity is affine geometry, and later on, the theory makes use of Euclidean distance.
  3. Convex sets... "a non-empty set Q is defined to be convex if, for each pair of its points, every point on the line segment that joins them is a subset of Q". This sentence is incorrect (unless points are viewed as subsets), possibly because of a partial attempt to simplify the exposition. It can be simplified further: "a non-empty set Q is convex if, for each pair of points in Q, every point on the line segment joining them is in Q". In general, it is helpful to unpack the language of subsets, as set membership is easier to discuss in a non-technical way. A small amount of copyediting would be helpful here (and elsewhere).
  4. Convex sets. "Mathematical induction" disrupts the flow and is only need for one implication in the "if and only if". Why not define convex combinations before using them to characterize convexity?
  5. Convex hull... "is the minimal convex set that contains Q. Thus Conv(Q) is the intersection of all the convex sets that cover Q." Here the word "cover" is incorrect: its use implies a collection of sets whose union contains Q. Conv(Q) is the intersection of all convex sets containing Q, and the the fancy word "minimal" can be replaced by "smallest" by the uniqueness (well-definedness) of this set. It may be helpful to introduce the word "convexification" here as a synonym.
  6. Minkowski sum. The "principle of mathematical induction" again. It isn't needed to define the sum of a family, only to show that an iterated binary sum is equal to the sum of the family (and hence is associative).
  7. Convex hulls and Minkowski sums. Yet more induction! Why is it relevant to discuss a snippet of the proof?
  8. Statements. This begins in a somewhat pedestrian fashion with "x in Y and Y=Z implies x in Z". Repetition may be pedagogical, but encyclopedic writing should be concise and to the point.
  9. Statements/lemma. It may be helpful to use a different letter for an element of Conv(Q_n) than for an element of Q_n. This would help to emphasize the point of writing the sum in two parts.
  10. Shapley–Folkman theorem and Starr's corollary. There is a sudden jump in complexity and sophistication here. The article has been holding the reader's hand up to the lemma, but then says "okay, now you're on your own". A short subsection on Euclidean distance, distnace to a subset, circumradius and inner radius would help a lot.
  11. Starr's corollary. Is this really a corollary to the Shapley-Folkman theorem? It provides a sharper estimate. Also, why is "non-convexity" an abuse?
  12. Proofs and computations. "The original proof of the Shapley–Folkman lemma established only the existence of the representation..." What representation? This needs to be clarified. An idea of the proof of the lemma would be nice too.

There are a few math issues in the applications section, but I will discuss that separately. Geometry guy 16:27, 8 October 2011 (UTC)

• Further issues. It remains to discuss the Applications section.
  1. "The Shapley–Folkman lemma enables researchers...and the Shapley–Folkman lemma has renewed research that had been stumped by non-convex sets.'" Why "researchers"? Had "research" really been "stumped"? This informal present/perfect tense approach needs to be backed up or replaced by historical legacy material.
  2. "In all three disciplines, the break-through application of the Shapley–Folkman lemma has been made by a young scientist." This is an editorial observation; such synthesis should be sourced or cut.
  3. "On this set of baskets, an indifference curve is defined for each consumer..." suggests there is only one curve per consumer, whereas in fact the space is foliated by such curves: there is one through each basket.
  4. "An optimal basket of goods occurs where the budget-line supports a consumer's preference set, as shown in the diagram..." There is too much unexplained economics jargon here. What is a budget-line, price vector and endowment vector, and how is the budget line defined in terms of the other quantities? What is an optimal basket? A feasible one? Is the optimal basket really a function? It looks like it could be multi-valued or only partially defined even in the convex case.
  5. I remain uncomfortable with the griffin example. Apart from the question as to whether it is encyclopedic, it is distracting and confusing. What is meant by half a lion or half an eagle? It only makes sense when discussing dead creatures. Why not have a lion for six months of the year and an eagle for the other six? And surely a contemporary zoo keeper would value a griffin much more highly than a lion or an eagle, because of the fortune to be made out of visiting Harry Potter fans. Finally, the footnote gives a perfectly sensible and completely sourced example (an automobile and a boat) so why not use that?
  6. "Previous publications on non-convexity and economics were collected in an annotated bibliography by Kenneth Arrow." This is a slightly odd start to a section. Previous to what? Wouldn't it be better to start with Starr?
  7. "who proved their eponymous lemma and theorem in 'private correspondence' ". No they didn't: they communicated it to Starr in private correspondence or he quoted it thusly.
  8. The mathematical optimization section spends rather a lot of time defining convex functions. The caption to the diagram is more concise.
  9. The opening of the probability and measure theory section is confusing. The essence of the discussion is that if random quantity only takes values in Q, then its average, being a convex combination, must belong to the convex hull of Q.

That completes my review. Geometry guy 17:10, 8 October 2011 (UTC)

Reply to Geometry Guy

I have drafted initial replies in my user space. I agree with most of his comments and I concede merit to the others. In general, I would argue that disagreements remain where I am trying to help first-time readers, with less mathematical background, by repetition.

I acknowledge that GG may well wish that this article was longer and contained more information, but I reply that FA articles need not be perfect; this article contains far more information and has better graphics than any other treatment in world literature. Readers wanting more treatment of e.g. economics should consult the sources given in the article (most of which are missing from even the union of previous articles on this topic), such as Mas-Colell's article on non-convexity and economics (in .pdf format on his home page).

I thank Geometry Guy again for his careful and conscientious scrutiny.  Kiefer.Wolfowitz 10:46, 8 October 2011 (UTC)

You're welcome. My comments are generally provided "as is" for you and the delegates to make what you will of them. However, I see from your initial response that I need to clarify Leading issues#3 (on the lead sentence). The Shapley-Folkman lemma involves two fundamental ingredients of similar importance: Minkowski addition and convexity. The current lead sentence treats these ingredients differently, referring to Minkowski addition and then defining it, while postponing discussion of the role of convexity. This is not defining. It should not be too difficult to work convexity into the lead sentence, e.g., "In geometry and economics, the Shapley–Folkman lemma describes the extent to which the Minkowski sum of a sets in a vector space is approximately convex." I'm sure you can do better than me, but a good lead paragraph should mention both Minkowski addition and convexity in the first sentence, then define them both. Geometry guy 17:39, 8 October 2011 (UTC)

Agreed. The muse was not whispering in my ear, but I'm beginning to hear an improved first sentence.

If you look at my responses in user space (in history), you will notice that I tend to agree with you after first raising some initial (token) resistance.

I can probably return to this Monday-Tuesday.  Kiefer.Wolfowitz 17:59, 8 October 2011 (UTC)

• Oppose. Here are some issues with the article as it stands:
  1. The article never defines "sumset". It begins using the term in the lead, but the non-expert reader may not realize this is meant to be the Minkowski sum.
  2. In the paragraph where the lead discusses the Shapley–Folkman–Starr theorem, the claim is first made that "[t]heir bound on the distance" does not depend on "the number of summand-sets N, when N > D". It goes on to say that "as the number of summands increases to infinity, the bound decreases to zero". My first thought was that these could not both be true, and that the article was in error. It turns out that I was wrong, because I missed the word "average". I think I won't be the only reader to make this error, so I think the paragraph needs to make a bigger contrast between sumsets and average sumsets.
  3. Still in the lead: It's not clear to me what a convexified economy is, not even vaguely. Nor is it clear what kind of equilibrium is meant (a Nash equilibrium, I guess?) or how that's different from a quasi-equilibrium.
  4. In general, the lead spends a lot of time trying to explain the statement of the Shapley–Folkman lemma (and its relatives). That's not the right direction. What the reader needs to learn is, "Why do I care?" Imagine, for example, that I'm a layman who has read a pop economics book, and I know what supply and demand are and what economies are, but I don't know what a convex set or a Minkowski sum is. Why should I learn about the Shapley–Folkman lemma? The lead does not answer this question. The closest it comes is near the end, where it explains that a lot of famous and successful economists have said that the study of non-convex situations is important (the lead has already made it clear that the Shapley–Folkman lemma is important for these). But essentially it's a proof by authority: All these Nobel laureates think it's important, so you should, too! This will not entice a novice reader to continue.
  5. In general, the article is structured like (I almost hate to say this) a math article. First it describes some preliminary notions (real vector spaces, convex sets, Minkowski sums, etc.). Then it states a theorem. Then it states applications. Kind of like "Definition–Theorem–Proof–Corollary". I realize that we all write this way (including me), but we shouldn't, and we especially shouldn't in an encyclopedia article.
  6. Right now, the article lacks a history section. I am going to suggest (this is only a suggestion, and there may be better ways of doing this) that you move some of the material from the Economics subsection of the Applications section into a new "History and Motivation" section immediately following the lead. This could put foundational material (like convexity) into a historical context: Before the Shapley–Folkman lemma, economists studied convex economies. Convexity is ..., and these are economies in which ... and they were important because of ..., but non-convex economies, which are ..., were important because ..., and prior to the Shapley–Folkman lemma nothing was known about non-convex economies. If you combine the foundational material with historical context, you make it more interesting and easier to grasp: It comes with vivid examples of what used to be cutting-edge research. By the time you are done with the historical context, you should have managed to introduce the prerequisite material for the Shapley–Folkman lemma. Then you can state it (and its corollaries and variations). Once that's done, you can move on to other applications.
  7. The optimization section has the same "Definition–Theorem–Proof–Corollary" feel. Again, I think it would be more effective to weave together the history and the prerequisite material.
  8. I was surprised at how short the section on probabilistic applications is. I don't know how important the Shapley–Folkman lemma is in such work, but you mention that it can be used to prove some analogs of standard results for real-valued random variables (like a law of large numbers and a central limit theorem). It would be good to include some more detail about these so that the reader at least knows how the Shapley–Folkman lemma is relevant (you don't necessarily have to state the theorems to prove this).
  9. Also, it might be good to explain in more detail how Lyapunov's theorem is related to the Shapley–Folkman lemma.
• Ozob (talk) 02:33, 8 October 2011 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Same illustration used twice

File:Shapley–Folkman lemma.svg is used in the article twice. Please choose one location and remove the other, as it is redundant to have it in the article twice. Kaldari (talk) 09:40, 11 November 2012 (UTC)

The picture has different captions. In the lede, it illustrates the SF lemma. In the early body, it illustrates the convex hull of a Minkowski sum of sets.

The repeated image is informative each time, and apparently this repetition is accepted by the other readers (many of whom have been reviewers).

Thanks, 10:06, 11 November 2012 (UTC) — Preceding unsigned comment added by Kiefer.Wolfowitz (talk • contribs)