Wikipedia:Peer review/Shapley–Folkman lemma/archive1

Shapley–Folkman lemma

This peer review discussion has been closed.

I've listed this article for peer review because it has an exceptional graphic (better than any publication, imho) and is well-documented (although the formatting could be improved for consistency). It describes applications with greater specificity and range than the 2nd edition of Starr's "New Palgrave" article ([4]).

It does not seem helpful to duplicate proofs from the literature, which tend to be short (for mathematicians) or long (for economists).

(This is the first article that I've nominated for peer-review.) Why two peer-reviews, mathematics PR and economics (social science) PR? The Shapley-Folkman lemma is a mathematical theorem that plays a central role in mathematical economics. Listing this article for two subjects is non-standard, and I apologize for not asking for guidance before hand. Best regards, Kiefer.Wolfowitz (talk) 14:57, 31 October 2010 (UTC)

Thanks, Kiefer.Wolfowitz (talk) 04:19, 30 October 2010 (UTC)

Review by Paul M. Nguyen:

• Strengths
  • The article structure overall is very strong.
  • The lead section captures the topic well, though it could include a concise statement about Shapley and Folkman and at least the decade in which the lemma was developed. This addition would make the lead more comprehensive.
  • The article is well-referenced.
  • Appropriate images are not lacking.
  • Connectedness: other than the numerous (and appropriate) 'see also's and wikilinks, the article could use some navboxes like {{Geometry-footer}}, {{Economics}}, {{Microeconomics}}. See Category:Mathematics templates and Category:Economics templates.
• Weaknesses
  • Though the article is highly technical, more could be done to make the topic accessible to a non-technical audience without sacrificing the precision it presently contains. I recommend expanding the lead section to include a second paragraph that treats the applications in simpler terms, relating both the economics and mathematics to readers not experts in either field.
  • Mechanics of the article:
    • References should follow punctuation, not fall "inside", as is the case in numerous places.
    • The SFS abbreviation is introduced in the section on "Probability and measure theory" but the expanded form is used prior to that and the abbreviation is not used anywhere else. The abbreviation may be omitted or introduced at the first occurrence and used exclusively thereafter.
    • The statement of the lemma should be a blockquote rather than whitespace-delimited.

It was a pleasure looking at this one. I'd appreciate your input on GNOME's PR, if you're interested. Thanks! –Paul M. Nguyen (chat|blame) 16:22, 10 November 2010 (UTC)

Response by 16:58, 10 November 2010 (UTC): Thank you for the very helpful review.

I immediately incorporated some of your suggested improvements: Adding geometry and microeconomics footers and block-quoting the theorem. I plan to follow your suggestion on SFS abbreviation, and probably also to follow your suggestion about another lead paragraph (non-technical).

On the other hand, mid-sentence footnotes appear when each specifies a particular contribution, for example, in the sentence noting economic applications of the Shapley-Folkman theorem; combining such footnotes into the end section would impair their usefulness to the readers, imho. Nonetheless, I shall review the WP guidelines on footnotes, and seriously consider your suggestion for each footnote. No doubt, some of the in-sentence footnotes could be modified to follow punctuation.

Thank you for your help. I shall try to look at the GNOME article soon. Best regards, Kiefer.Wolfowitz (talk) 16:58, 10 November 2010 (UTC)

Continuing to follow your suggestions, I expanded the introduction and expanded the SFS abbreviation. Thus, only the footnotes remain unimproved despite your suggestions! Best regars, Kiefer.Wolfowitz (talk) 19:03, 10 November 2010 (UTC)

I incorporated background material on convex sets and convex hulls. It would be preferable to develop graphics that are closer to Eppstein's illustration for the Shapley Folkman lemma, of course. Thanks! Kiefer.Wolfowitz (talk) 22:47, 10 November 2010 (UTC)

I included an illustration of Minkowski addition from the Italian Wikipedia. Kiefer.Wolfowitz (talk) 01:29, 11 November 2010 (UTC)

Followup Review by Paul M. Nguyen: You're quick! A couple notes based on the revisions made since my review:

• Great job addressing connectedness.
• I was not clear enough in my comment about references. What I meant was that a reference should not fall between a word and punctuation that follows it (I suppose a dash would be an exception). Wrong example: fact^[12], next point.^[13] Correct: fact,^[12] next point.^[13] I did not notice any periods being "orphaned" by a reference, but there are several orphaned commas as in my example.
• Excellent work expanding the article. I think the convex geometry material helps.
  • The introductory sentence to the section, "Stating the Shapley–Folkman lemma requires some definitions and results." could be rephrased to be more active and declarative, like "The Shapley–Folkman lemma depends upon the following definitions and results from convex geometry."
  • The section title "Results from convex geometry" seems awkward to me. I think the article structure would be strengthened if the statement of the lemma and the requisite convex geometry definitions were to fall in the same == section, with the concepts upon which the statement of the lemma depends listed first. A more obvious (and more generic) title would need to be chosen for the top-level section, like "Definition" or even promote "Statement of the lemma" to encompass this information. The final subsection could then be titled simply "The lemma", following upon the convex geometry. I would, however, recommend keeping the theorem and Starr's corollary in a separate section, as they are presently.
• Lead section: wow! I think too much was added to the lead, though. For the present second paragraph, I recommend the following, which retains the added application-oriented context but condenses the middle as would be appropriate in a lead section:

The mathematicians Shapley and Folkman derived the Shapley–Folkman lemma to help the young economist, Ross M. Starr (1969), who was investigating the existence of economic equilibria when some consumer preferences need not be convex. Starr proved that a mathematical transformation that causes all preferences to be convex yields an economy that has general equilibria that are closely approximated by "quasi-equilbria" of the original economy. In Starr's corollary to the Shapley–Folkman theorem, Starr bounded the Euclidean distance between a Minkowski sum of nonconvex sets and the sum's convex hull; Starr's corollary is sometimes called the Shapley–Folkman–Starr theorem.

–Paul M. Nguyen (chat|blame) 02:22, 11 November 2010 (UTC)

Thanks again, Paul. You were very helpful and gave miraculously quick feedback.

Thanks especially for the clarification about footnotes. (I was needlessly afraid that I would have to change WP policy to keep in-sentence footnotes.) I shall fix the remaining footnotes tomorrow, following your examples.

Your suggestion about the lead paragraph was very helpful, and I shall incorporate it (nearly verbatim, I now believe) tomorrow.

Have a great day/night, and thanks for your help!

Yours gratefully, Kiefer.Wolfowitz (talk) 02:31, 11 November 2010 (UTC)

Dear Paul, Thanks again for your help. I incorporated your paragraph (crediting you in the edit summary), but your contributions have been so substantial that I wish that you make some official edit, so that you are credited as a contributor to the article. I also changed the footnotes to conform with the WP suggestion that footnotes follow punctuation marks. Thus, I believe that I have followed all of your suggestions. (I also incorporated an illustration of convex hulls and combined the illustrations of convex versus nonconvex sets.) Thanks very much for your excellent suggestions, which far exceed what I'd expected from this processs. Best regards, Kiefer.Wolfowitz (talk) 17:19, 11 November 2010 (UTC)

Cool! I edited a couple things just now, but nothing crazy. Cheers! –Paul M. Nguyen (chat|blame) 20:00, 11 November 2010 (UTC)

I tweaked the section/subsection(s) for the lemma and the preliminaries, trying to follow your suggestions. Thanks again. Kiefer.Wolfowitz (talk) 00:04, 15 November 2010 (UTC)

Comments from RJHall

Comment from RJHall The very first sentence of the article seems ambiguous, so I am not quite able to grasp what it is trying to say:

...the Minkowski sum of many non-convex subsets of a finite-dimensional vector space is nearly convex.

Are you saying this applies to the net sum of a sufficiently large number of non-convex subsets, or it applies to many individual instances of the sums of non-convex pairs? What is meant by "many"? It is also vague about what is meant by "nearly convex". Thanks.—RJH (talk) 16:15, 17 November 2010 (UTC)

The Shapley–Folkman lemma applies to the sum of N sets when N > D, the dimension of the sets; thus it would apply also to the sums of subsets of M sets when D < M ≤ N.

Providing a short informal summary of the theorem is difficult. I'll look at the Carathéodory's lemma on convex hulls for inspiration. Best regards, Kiefer.Wolfowitz (talk) 17:54, 17 November 2010 (UTC)

This is what Starr's lead says in the New Palgrave Dictionary of Economics:

"The Shapley–Folkman theorem places an upper bound on the size of the non-convexities (loosely speaking, openings or holes) in a sum of non-convex sets in Euclidean N-dimensional space, RN. The bound is based on the size of non-convexities in the sets summed and the dimension of the space. When the number of sets in the sum is large, the bound is independent of the number of sets summed, depending rather on N, the dimension of the space. Hence the size of the non-convexity in the sum becomes small as a proportion of the number of sets summed; the non-convexity per summand goes to zero as the number of summands becomes large."

Starr's opening is more precise than ours. I'll paraphrase Starr's.Kiefer.Wolfowitz (talk) 17:58, 17 November 2010 (UTC)

I incorporated Starr's ideas in a revised first paragraph:

In geometry and in mathematical economics, the Shapley–Folkman lemma and the closely-related Shapley–Folkman–Starr theorem suggest that the Minkowski sum of many non-convex subsets of a finite-dimensional vector space is nearly convex. The results of Shapley, Folkman, and Starr give an upper bound on the degree of non-convexity of the Minkowski sum of N non-convex sets. This bound on non-convexity depends on the dimension D and on the non-convexities of the summand-sets; however, the bound does not depend on the number of summand–sets N, when D < N. Because the sumset's non–convexity is determined by the non-convexities of only D summand sets, the average non–convexity of the sumset decreases as the number of summands N increases; in fact, the average degree of non–convexity decreases to zero as N increases to infinity.

Thanks again, Kiefer.Wolfowitz (talk) 18:47, 17 November 2010 (UTC) 23:14, 17 November 2010 (UTC)

The information is much clearer now. Thank you.—RJH (talk) 20:05, 15 April 2011 (UTC)

Comments from Ruslik0

I want point your attention to some contradictions in the first paragraph:

1. This bound on non-convexity is defined in terms of the Euclidean distance and it depends on the dimension D and on the non-convexities of the summand-sets. I would say that the (upper) bound 'depends on the dimension D and on the non-convexities of the D summand-sets'. The current phrasing means that the bound depends on non-convexities of all summand-sets.
2. The next sentence read Because the sumset's non–convexity is determined by the non-convexities of only D summand sets. I think the non-convexity itself depends on non-convexities of all summand sets as opposed to the upper bound.
3. I also noticed that you use either 'd' or 'D' for the vector space dimension. Ruslik_Zero 19:47, 22 November 2010 (UTC)

Thanks for your clear and focused comments, Ruslik0. It's late and I shall have to review the article & finish replying tomorrow.

1. Suggested phrasing (in reply): "depends on the dimension D and on the non-convexities of the collection of the sums of D summand–sets". Argument: The selection(s) of D (or fewer) convexified summands depends on the point; even pointwise, a SF-bipartition lacks uniqueness. (I did not wrote "all" but the mis-imputation of "all" should be much harder now.)
2. As noted previously, I updated the wording to emphasize "the collections of the sums of D summand sets".
3. Regarding the dimension d or D: I capitalized all occurences of the dimension as D (having previously tweaked David Eppstein's original i to n and capitalizing the upper index N).

Reviewing the article today, I added a reference to Puri & D. Ralescu's 1985 article, whose Shapley-Folman application empowers R. Cerf's article (already cited).

Thanks again for your very helpful comments and suggestions. Best regards, Kiefer.Wolfowitz (talk) 22:58, 22 November 2010 (UTC)

You have failed to address 1 and 2. Ruslik_Zero 16:34, 23 November 2010 (UTC)

Thanks for drawing my attention to the unfinished business. I appreciate your effort, and thank you!

I am sorry if I misunderstand your intention, or wrote poorly. I thought that I had addressed your comments. I am sorry if I seem irritated now when I write --- my time is very limited.

1. Your suggested phrasing errs in using the definite article "the" in "the D sets". First, the SF lemma gives the existence of a pointwise representation in terms of D convexified summand sets and N-D original summand sets. There are many problems with points having multiple representations, so uniqueness fails even pointwise. When (on some problems) the point varies, then the representation must vary, and so one needs to consider the collection of the sums of D convex hulls of summands (and N-D original summand sets). (Continued) Again, the phrasing never inserted the universal quantifier "all", so your imputation of "all" is unwarranted; as I wrote before, I tweaked the sentence so that this mis-reading should be more difficult.
2. The SF lemma and SF theorem and SFS theorem state bounds. Unless you can find a reference discussing "degree of nonconvexity" as you suggest, your suggestions seems to follow under original research.

Reading my responses, I am very unsatisfied with my progress on clarifying things. I apologize for having left a brusk & probably unclear response, now. I shall try to review and edit my response tomorrow. Thanks again for your suggestions. Sincerely, Kiefer.Wolfowitz (talk) 13:11, 24 November 2010 (UTC)