Talk:Shapley–Folkman lemma/GA1
GA Review
[edit]GA toolbox |
---|
Reviewing |
Article (edit | visual edit | history) · Article talk (edit | history) · Watch
Reviewer: Jakob.scholbach (talk) 10:24, 19 December 2010 (UTC) I start reviewing the article. So far I made it for sections 1 and 2. I will read the applications section soon. So far I think the article is well on its way to GA.
- Thank you very much for your initial comments and sustained help. Kiefer.Wolfowitz (talk) 20:29, 11 January 2011 (UTC)
General comments
[edit]I suggest limiting the use of "See also" and "Main article" templates to a reasonable minimum. They kind of interupt the flow of reading.
- I removed some that seemed less useful.
- However, the previous peer-review editor liked the see also () and main() links. I also like them, because they signal the reader that this article is technical; a civilian needs to pause frequently to draw pictures and absorb concepts, gainfully by consulting other articles. (C.f., George Piranian's & colleagues advice to authors, in the AMS brochure on writing articles, that he reading of mathematics is a slow and repetitive process.) A WYSIWYG benefit of ample see also() and main() sub-headings is that they hide the white space trapped by the ample graphics; perhaps I should remove the pictures of Shapley and Arrow? Kiefer.Wolfowitz (talk) 11:27, 19 December 2010 (UTC)
According to some guideline, WP is not a textbook. Because of this, things like "Definition: ..." have to be spelled out in prose. This is easy, for example the first could read: "A subset S of a real vector space is called convex if ..."
- I'll follow your suggestion.
Bold face should only be used to highlight the article title in the text. Further highlightings should be done using italics.
- I have started to italicize wrongly emboldened words. Kiefer.Wolfowitz (talk) 11:27, 19 December 2010 (UTC)
- I italicized wrongly emboldened words. Kiefer.Wolfowitz (talk) 01:38, 12 January 2011 (UTC)
- Done, I think. Kiefer.Wolfowitz (talk) 16:42, 12 January 2011 (UTC)
Section "Preliminaries"
[edit]The first image has an odd layout. Is there a better way? Maybe the two images next to each other, but on the same line?
- I used a standard template, and followed the WP instructions. Kiefer.Wolfowitz (talk) 11:32, 19 December 2010 (UTC)
- A weird layout occured when I printed out a .pdf file of the article. Maybe you have a weird browser? If the problem still occurs for you, please send me a screen-snapshot. Kiefer.Wolfowitz (talk) 16:45, 12 January 2011 (UTC)
- Hm, it still looks odd, but this may well be my browser. (The odd thing is that there is a big empty margin right to the images and their explanations.) Anyway, this is not the most important thing on earth. Jakob.scholbach (talk) 21:36, 14 January 2011 (UTC)
- A weird layout occured when I printed out a .pdf file of the article. Maybe you have a weird browser? If the problem still occurs for you, please send me a screen-snapshot. Kiefer.Wolfowitz (talk) 16:45, 12 January 2011 (UTC)
Why do you use <br> tags? I think they should not be used. It just creates huge white spaces.
- Where are they used? Kiefer.Wolfowitz (talk) 11:32, 19 December 2010 (UTC)
- In the Minkowski sum section. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- I removed the linebreak in that section. Thanks! Kiefer.Wolfowitz (talk) 14:13, 4 January 2011 (UTC)
- Done, I think! Kiefer.Wolfowitz (talk) 16:45, 12 January 2011 (UTC)
- I removed the linebreak in that section. Thanks! Kiefer.Wolfowitz (talk) 14:13, 4 January 2011 (UTC)
- In the Minkowski sum section. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
The notion of vector space is not explained. Since you nicely give explanations of many other terms, I think a brief explanation with R^2 and R^3 as examples would fit in nicely. (Strangely, in the next subsection you have the "See also" link to v.sp.
- I moved-up the "see also" link to vector spaces. Your suggestions, though valid, would require too much work for me at present, I'm sorry to say (although your positive comments have encouraged me to do more than I'd planned in the past!). Kiefer.Wolfowitz (talk) 01:44, 12 January 2011 (UTC)
- As I feared, your suggestion prompted me to improve the article! Be cautious about using such powers of persuation! ;) Kiefer.Wolfowitz (talk) 21:21, 14 January 2011 (UTC)
- OK, I like it better this way. I think the wording of the new text could still be worked on, but for now it's fine enough. Jakob.scholbach (talk) 21:36, 14 January 2011 (UTC)
- David Eppstein improved the section, which previously stated that the real plane has the form of a coordinatized plane. Kiefer.Wolfowitz (talk) 22:45, 16 January 2011 (UTC)
- OK, I like it better this way. I think the wording of the new text could still be worked on, but for now it's fine enough. Jakob.scholbach (talk) 21:36, 14 January 2011 (UTC)
- As I feared, your suggestion prompted me to improve the article! Be cautious about using such powers of persuation! ;) Kiefer.Wolfowitz (talk) 21:21, 14 January 2011 (UTC)
reformat as [0, 1] (if it appears in the text).
Is "member" a standard expression for "element"? (Per WP:EGG, links should not be disguised...)
- "Member" links to the article element (mathematics), which begins "An element or member". The noun "member" is specific while "element" is vague. Kiefer.Wolfowitz (talk) 11:36, 19 December 2010 (UTC)
I suggest putting "The operations of Minkowski summation and of forming convex hulls commute." after "the convex hull of the Minkowski sum is the Minkowski sum of the convex hulls." since some readers will not understand the word "commute".
- I followed your suggestion and did some further simplifications. Kiefer.Wolfowitz (talk) 01:44, 12 January 2011 (UTC)
Manual of Style questions
[edit]In the image caption of the Minkowski addition (and anywhere else), only mathematical variables should be italicized. For example Q1+Q2=[1,3]×[1,3] should be Q1+Q2=[1,3]×[1,3].
- The following discussion is long and moot, so I hid it. Kiefer.Wolfowitz (talk) 02:22, 17 January 2011 (UTC)
- I'll check this. LaTeX uses different conventions. Kiefer.Wolfowitz
- I don't think so. Even if it does, WP:MOSMATH is quite explicit about this (see especially the subsubsection "Variables"). Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- I followed your suggestions. I am sorry if I missed any wrongly italicized sets. Also, I consistently used the WP-hypertext formatting, and removed
allmost LaTeX, for consistency. Kiefer.Wolfowitz (talk) 04:26, 12 January 2011 (UTC)- Done! Kiefer.Wolfowitz (talk) 16:45, 12 January 2011 (UTC)
- I LaTeXed two equations, which were imho illegible in WP-markup. Kiefer.Wolfowitz (talk) 19:04, 16 January 2011 (UTC)
- Done! Kiefer.Wolfowitz (talk) 16:45, 12 January 2011 (UTC)
- I followed your suggestions. I am sorry if I missed any wrongly italicized sets. Also, I consistently used the WP-hypertext formatting, and removed
- I don't think so. Even if it does, WP:MOSMATH is quite explicit about this (see especially the subsubsection "Variables"). Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
On my talk page, Kiefer.Wolfowitz grossly misquoted Jakob.scholbach as saying on this present page that names of sets should not be italicized. Nothing that Jakob.scholbach says above suggests that. Rather, he's saying that digits, parentheses, brackets, etc., should not be italicized. WP:MOSMATH is perfectly explicit about that. That matches TeX style, and matching TeX style is a major desideratum.
Digits, parentheses, etc., should not be italicized. Variables, including those that refer to set, should be. This is explicit in WP:MOSMATH under "variables" in the subsection labeled "sets". Michael Hardy (talk) 19:13, 16 January 2011 (UTC)
- I am sorry if I misquoted Jakob. I thought that I had just cut-and-pasted this section. (I was just about to post a note to Jakob here, that he should refer to that page.) Kiefer.Wolfowitz (talk) 19:16, 16 January 2011 (UTC)
- Correction: You are correct. Jakob did italicize the Q's above. Their continued italicization was lost on me. Sorry for the confusion! Sincerely, Kiefer.Wolfowitz (talk) 19:23, 16 January 2011 (UTC)
- Michael, that said, would you change "grossly misquoted" to [optionally "grossly" or preferably "cavalierly"] "misrepresented" please? (I did not "misquote" Jakob.) Thanks Kiefer.Wolfowitz (talk) 20:37, 16 January 2011 (UTC)
- Dear Michael, I tried to strike through my comments and take responsibility for any mis-statements on your talk page. Please accept my apologies for the initial confusion and any errors in my clean-up. Sincerely, Kiefer.Wolfowitz (talk) 19:33, 16 January 2011 (UTC)
- I am sorry if I misquoted Jakob. I thought that I had just cut-and-pasted this section. (I was just about to post a note to Jakob here, that he should refer to that page.) Kiefer.Wolfowitz (talk) 19:16, 16 January 2011 (UTC)
I made the suggested changes (with tired eyes). Fresh eyes would be useful. (I also switched S_n to Q_n for consistency with the illustration of Minkowski addition.) ThanksKiefer.Wolfowitz (talk) 20:33, 16 January 2011 (UTC)
"Formal statement"
[edit]Never address the reader directly. So, "Consider ..." should be reworded to something like "The S-F lemma is concerned with ...". Similar remarks apply elsewhere, too.
- I've worked on his, and shall continue . . . . Kiefer.Wolfowitz (talk) 04:26, 12 January 2011 (UTC)
- Done! Thanks! Kiefer.Wolfowitz (talk) 16:46, 12 January 2011 (UTC)
- OK, it seems to be good now. There is still one or two "see page....", I'm not sure you absolutely have to remove these, but you could consider tweaking them too.
- Aha! I'll re-word those sentences in properly declarative form, e.g., "Our man Schneider states on page . . . . Thanks, Kiefer.Wolfowitz (talk) 21:19, 16 January 2011 (UTC)
- I removed all of the "see" commands. Thanks again! Kiefer.Wolfowitz (talk) 21:42, 16 January 2011 (UTC)
- Aha! I'll re-word those sentences in properly declarative form, e.g., "Our man Schneider states on page . . . . Thanks, Kiefer.Wolfowitz (talk) 21:19, 16 January 2011 (UTC)
- OK, it seems to be good now. There is still one or two "see page....", I'm not sure you absolutely have to remove these, but you could consider tweaking them too.
- Done! Thanks! Kiefer.Wolfowitz (talk) 16:46, 12 January 2011 (UTC)
Notation is a bit sloppy in the first sentence. I think it should be "N sets S1, S2, ..., SN"
- Done. They must all be non-empty, or the emptyset absorbs everything. Kiefer.Wolfowitz (talk) 13:24, 19 December 2010 (UTC)
"If M is the Minkowski sum of N (non-empty) subsets" is not needed again, since we have it immediately before.
- I replaced this wording, introducing appropriate notation for the sum of sets. Kiefer.Wolfowitz (talk) 04:08, 15 January 2011 (UTC)
Putting "as a sum with a similar form to the sum in the definition of M" in the middle of the statement actually distracted me. Maybe first give the sober statement and then an interpretation containing this bit?
- Agreed. I'll work on this. Kiefer.Wolfowitz (talk) 04:26, 12 January 2011 (UTC)
- Done! (Still imperfect, though.) Kiefer.Wolfowitz (talk) 16:46, 12 January 2011 (UTC)
- I don't exactly remember how it was before, but the current sentence "The Shapley–Folkman lemma states that if the set M is the Minkowski sum of N (non-empty) subsets where N > D, then every point x in the convex hull of M is a sum of points in the convex hulls of D summand-sets and N - D points in the original (possibly non-convex) summand-sets" is still very (i.e.: too) long. Mostly because you repeat things that you already said immediately before. Why not have one sentence fixing the assumptions and then the statement? Jakob.scholbach (talk) 21:36, 14 January 2011 (UTC)
- I made a major rewriting of this section. Kiefer.Wolfowitz (talk) 04:08, 15 January 2011 (UTC)
- I don't exactly remember how it was before, but the current sentence "The Shapley–Folkman lemma states that if the set M is the Minkowski sum of N (non-empty) subsets where N > D, then every point x in the convex hull of M is a sum of points in the convex hulls of D summand-sets and N - D points in the original (possibly non-convex) summand-sets" is still very (i.e.: too) long. Mostly because you repeat things that you already said immediately before. Why not have one sentence fixing the assumptions and then the statement? Jakob.scholbach (talk) 21:36, 14 January 2011 (UTC)
- Done! (Still imperfect, though.) Kiefer.Wolfowitz (talk) 16:46, 12 January 2011 (UTC)
- My updated text follows:
The preceding identity Conv( ∑ Qn ) = ∑ Conv( Qn ) implies that if the point x lies in the convex hull of the Minkowski sum of N sets
- x ∈ Conv( ∑ Qn )
then x lies in the sum of the convex hulls of the summand-sets
- x ∈ ∑ Conv( Qn ).
By the definition of Minkowski addition, this last expression means that x = ∑ qn for some selection of points qn in the convex hulls of the summand-sets, that is, where each qn∈Conv(Qn). In this representation, the selection of the summand-points qn depends on the chosen sum-point x.
The lemma of Shapley and Folkman
[edit]For this representation of the point x, the Shapley–Folkman lemma states that if the dimension D is less than the number of summands
- D < N
then convexification is needed for only D summand-sets, whose choice depends on x: The point has a representation
where qd belongs to the convex hull of Qd for D (or fewer) summand-sets and qn belongs to Qn itself for the remaining sets. That is,
for some re-indexing of the summand sets; this re-indexing depends on the particular point x being represented.[1]
Combinatorial?
[edit]It is unclear what "The (combinatorial) Shapley–Folkman lemma" means. What do you mean by combinatorial?
- I hid this remark, which is pithy and fun for mathematicians, but off-putting to the public.
- I am not sure I understand your reply. Certainly I still don't understand the meaning of "(combinatorial)" in the article. This should be clarified. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- I removed the later "combinatorial" adjective. Kiefer.Wolfowitz (talk) 04:26, 12 January 2011 (UTC)
- Done (by cowardly removing "combinatorial")! Kiefer.Wolfowitz (talk) 16:46, 12 January 2011 (UTC)
- OK. You didn't have to remove it, it just provoked a question mark on my side. Jakob.scholbach (talk) 21:36, 14 January 2011 (UTC)
- BTW: Howe's working paper labels the lemma combinatorial and the theorem(s) metric. Howe's paper has been widely cited) and is reliable and notable. Kiefer.Wolfowitz (talk) 04:58, 19 January 2011 (UTC)
- Done (by cowardly removing "combinatorial")! Kiefer.Wolfowitz (talk) 16:46, 12 January 2011 (UTC)
- I removed the later "combinatorial" adjective. Kiefer.Wolfowitz (talk) 04:26, 12 January 2011 (UTC)
- I am not sure I understand your reply. Certainly I still don't understand the meaning of "(combinatorial)" in the article. This should be clarified. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
So, what exactly is the converse statement?
- A Banach space has dimension D<∞ if and only if it satisfies the (homogeneous) SF lemma (with identical subsets being summed) with D finite; otherwise it is infinite-dimensional. (Borwein-O'Brein, which is a relatively inaccessible journal and paper; the cited proposition in Schneider doesn't worry about infinite dimensions.)
- I think it would be beneficial to put this or a similar explanation to the article. (The point of me asking questions here is not so much to answer them in the GA review page, but in the article.) Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- I added a bit more to the reference to Borwein & O'Brein, explaining their result. Kiefer.Wolfowitz (talk) 01:44, 12 January 2011 (UTC)
- David Eppstein gave an explicit statement of the converse, which I tweaked to mention the Borwein O'Brein result. Kiefer.Wolfowitz (talk) 02:08, 17 January 2011 (UTC)
- I added a bit more to the reference to Borwein & O'Brein, explaining their result. Kiefer.Wolfowitz (talk) 01:44, 12 January 2011 (UTC)
- I think it would be beneficial to put this or a similar explanation to the article. (The point of me asking questions here is not so much to answer them in the GA review page, but in the article.) Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
It's unclear to me why in the previous section the lemma is called S-F theorem and now another statement is called like this. Is the literature ambiguous (as always) here? If so, the comment "The (combinatorial) Shapley–Folkman lemma is often referred to as the "Shapley–Folkman theorem"" should be reworded accordingly.Actually I think it would even be natural to have the following section structure: "Preliminaries", "Statement(s)", "Applications"
- The (combinatorial) SF lemma states that only D sets need be convexified, and the (metric) SF theorem gives a bound on the distance between a set and its convex hull. Kiefer.Wolfowitz (talk) 10:44, 19 December 2010 (UTC)
- OK, this is a bit better now. I'll strike out this point, but I'd like to reiterate my suggestion about the section structure. The preliminaries now take quite some space (and rightfully), then suddenly we have the section title "Formal statement" and I did (no kidding!) forget what we are actually about to state. Maybe to the well-informed reader the statements of the SF lemma, the SF theorem and Starr's corollary are miles apart. However, if you see it first, they seem rather closely related, so it is unclear why there is such a big distinction (in terms of article structuring) between the first and the other two. Also Shapley-Folkman-Starr redirects here, again underlying that these three statements seem to be siblings as opposed to kids or distant relatives. Jakob.scholbach (talk) 20:29, 16 January 2011 (UTC)
- At long last, I implemented your suggested macro-structure, i.e., intro, preliminaries, statement, applications. Kiefer.Wolfowitz (talk) 21:44, 16 January 2011 (UTC)
- OK, this is a bit better now. I'll strike out this point, but I'd like to reiterate my suggestion about the section structure. The preliminaries now take quite some space (and rightfully), then suddenly we have the section title "Formal statement" and I did (no kidding!) forget what we are actually about to state. Maybe to the well-informed reader the statements of the SF lemma, the SF theorem and Starr's corollary are miles apart. However, if you see it first, they seem rather closely related, so it is unclear why there is such a big distinction (in terms of article structuring) between the first and the other two. Also Shapley-Folkman-Starr redirects here, again underlying that these three statements seem to be siblings as opposed to kids or distant relatives. Jakob.scholbach (talk) 20:29, 16 January 2011 (UTC)
d should become D.
"Inner radius" versus circumradius: Picture
[edit]![The Shapley–Folkman lemma depicted by a diagram with two panes, one on the left and the other on the right. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. Comparing the left array and the right pane, one confirms that the right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.](http://up.wiki.x.io/wikipedia/commons/thumb/7/7d/Shapley%E2%80%93Folkman_lemma.svg/300px-Shapley%E2%80%93Folkman_lemma.svg.png)
- Maybe move the "inner radius" definition up to the preliminaries? A picture would be great for this. [Jakob]
- The inner-radius definition is not used in the Shapley-Folkman lemma, whose preliminaries are quite long already, imho. I prefer the current structure, where the inner-radius definition occurs exactly at the (only) place it is used.
- :BTW, another definition of the inner-radius is the smallest (Euclidean) ball whose Minkowski-sum with the summand Q is convex. This definition is more elegant, and is used in the geometry of convex bodies. (In the Mathematics of Operations Research, Scarf, Lovasz, and Kannan study its relation to an affine-invariant version of the Banach-Mazur distance and to Hilbert's projective metric.)
I don't know of a suitable picture, unfortunately.I re-used David's graphic, which exhibits the inner-radius and circum-radius miraculously well, also. ("If it were a snake, it would have bit you", as my grandmother often said.)- The article also suffers from having a smorgåsbord of graphic-styles, none of which I could match with my Matlab or R abilities, in the next month(s). If the article goes for FA-status, then I could probably reproduce the graphics (all but David's lead graphics) in a consistent style.
- Best regards, Kiefer.Wolfowitz (talk) 15:22, 17 January 2011 (UTC)
Also, why does S_n have to be non-convex, I think "not necessarily convex" is more apt.
- This is correct. However, your phrase is more complicated, and the result is interesting only when some sets are non-convex sets. I'll try to improve things, later, if I see a chance. Kiefer.Wolfowitz (talk) 21:19, 14 January 2011 (UTC)
- OK, fair enough. Jakob.scholbach (talk) 20:29, 16 January 2011 (UTC)
- The SF lemma is now stated using convex-hull terminology, which avoids the needless restriction to non-convex sets. Kiefer.Wolfowitz (talk) 22:52, 16 January 2011 (UTC)
- OK, fair enough. Jakob.scholbach (talk) 20:29, 16 January 2011 (UTC)
I don't see why Starr's statement is a corollary. I take it that the inner radius is smaller than the circumradius? (This should also be explained at prelims). If so, Starr's statement is rather a stronger statement? Please clarify.
- Starr's corollary is labelled as his "corollary" to a proposition of Shapley and Folkman. You are right, but I thought that this had been discussed (tersely); I'll re-check it. Kiefer.Wolfowitz (talk) 10:44, 19 December 2010 (UTC)
- Thanks for explaining it here. It would be better, though, if this would be clear from reading the article alone. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- I made some improvements to the article.
- Alright. Jakob.scholbach (talk) 20:29, 16 January 2011 (UTC)
- I made some improvements to the article.
- Thanks for explaining it here. It would be better, though, if this would be clear from reading the article alone. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
Lead: "Degree of non-convexity"
[edit]What does "degree of non-convexity" mean? Is this an established term or just a philosophical idea? In the former case a definition is necessary. In the latter case it should be better explained. This notion occurs in many places throughout the article, so I think you won't want the reader to miss that point.
- "Degree of non-convexity" is a primitive concept, which can be specified in many ways. Starr's inner-radius was early and has many advantages over other concepts (discussed in chapter 4 of Schneider, for example). Kiefer.Wolfowitz (talk) 11:39, 19 December 2010 (UTC)
- The lead introduction now explains that this is an abstract term, which will be explained below --- without addressing the reader, per your advice. Kiefer.Wolfowitz (talk) 21:19, 14 January 2011 (UTC)
- This still needs work. The lead is OK, but the relevant section does not exactly convey what the lead says. Instead, it only qualifies Starr's thing as a bound on the degree of non-convexity. But I take it that you also want to say that the SF-theorem is a bound, right? Then the last but one paragraph of "Shapley–Folkman theorem and Starr's corollary" has to be reworded. Also, given that the circumradius is ≥ the inner radius, Starr's corollary is rather a strengthening of the SF-theorem? (You call it a refinement.)
- The lead introduction now explains that this is an abstract term, which will be explained below --- without addressing the reader, per your advice. Kiefer.Wolfowitz (talk) 21:19, 14 January 2011 (UTC)
- I'll work on this. Kiefer.Wolfowitz (talk) 21:22, 16 January 2011 (UTC)
- With time-travel, we could be very useful referees for Starr's paper! 40 years of hindsight allows even my eyes 20/20 acuity. Cheers, Kiefer.Wolfowitz (talk) 21:22, 16 January 2011 (UTC)
- I rewrote the lead, following your suggestions. Kiefer.Wolfowitz (talk) 16:10, 17 January 2011 (UTC)
- The lead appears next, in "hidden" state:
In geometry, the Shapley–Folkman lemma and the Shapley–Folkman–Starr theorem study the Minkowski sums of N subsets in a vector-space
- ∑ { qn ∈ Qn },
addressing the question, "how close this sum is to being convex?".[2] The Shapley–Folkman–Starr results suggest that when the number of summands N exceeds the dimension of the vector space, then their Minkowski sum is approximately convex.[1] The propositions of Shapley, Folkman, and Starr give upper bounds on the Euclidean distance of the Minkowski sum from the its convex hull, that is, the smallest convex set that contains the Minkowski sum. Their bounds on the non-convexity of the Minkowski sum depends on the dimension D and on any non-convexities of the summand-sets; however, the bound does not depend on the number of summand-sets N, when N > D. Because the sumset's non-convexity is determined by the non-convexities of a subcollection of only D summand-sets, the non-convexity of the average sumset
- 1⁄N ∑ Qn
decreases as the number of summands N increases; in fact, this bound on the non-convexity of the average sumset decreases to zero as N increases to infinity.[3]
- (unindent) I'm sorry to be so stingy and increasingly impatient, but the section on the formal statements has to make clear what the "non-convexity" of a set is. This term is repeated in many places, but I fail to see a proper explanation of this term. Is it just the maximal squared distance of some point in the convex hull to the original set? If so, why is the interpretation in the last but one paragraph correct, i.e., how is the non-convexity related to circumradius/inner radius? Jakob.scholbach (talk) 20:23, 18 January 2011 (UTC)
- Also, this section is now very choppily worded. Jakob.scholbach (talk) 20:23, 18 January 2011 (UTC)
- Jakob, you have been correct all along, and are justified in being impatient with my response. I rewrote the lead and the Statement sections to clean-up the error, which you pointed out weeks ago. Thanks for your fortitude. Kiefer.Wolfowitz (talk) 21:46, 18 January 2011 (UTC)
- OK, now I think it is fine. Jakob.scholbach (talk) 21:53, 19 January 2011 (UTC)
- Jakob, you have been correct all along, and are justified in being impatient with my response. I rewrote the lead and the Statement sections to clean-up the error, which you pointed out weeks ago. Thanks for your fortitude. Kiefer.Wolfowitz (talk) 21:46, 18 January 2011 (UTC)
Moot discussions
[edit]I think "non–convexity" should just use a hyphen, not a dash.
- I agree. However,
seniormore experienced editorsconstantlycorrectly changed my hyphens to dashes when they were used disjunctively (14:21, 4 January 2011 (UTC)), so I assume they are complying with some directive. Kiefer.Wolfowitz (talk) 10:44, 19 December 2010 (UTC)- There is no such thing as senior editors. However, we do have Wikipedia:HYPHEN#Hyphens, which is completely unambiguous about this. It has to be a hyphen, as opposed to a dash. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- You are correct, like the other editors who were correcting disjunctive hyphens (which must be dashes). 14:21, 4 January 2011 (UTC)
- I corrected all incorrect dashes (visible to me); I'm sorry if I missed any! Kiefer.Wolfowitz (talk) 19:45, 11 January 2011 (UTC)
- There is no such thing as senior editors. However, we do have Wikipedia:HYPHEN#Hyphens, which is completely unambiguous about this. It has to be a hyphen, as opposed to a dash. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
"the average degree of non–convexity decreases to zero as the number of summands N increases to infinity" -- in what sense? A stupid example that comes to mind: I keep adding the same subset again and again.
- The average non-convexity drops to zero, even with the same subset as summand. This example is important for averages of identically distributed random variables, whose supports' nonconvexity drops to zero, and to iterated sumsets studied in additive combinatorics (Mann, Freiman, Nathanson, Rusza, Tao). (Some rather distinguished economists erroneously assert that the summands being unique is important; they are correct that diversity helps in some other approaches to non-convexity, as in Troeckel's lecture notes.)Kiefer.Wolfowitz (talk) 10:44, 19 December 2010 (UTC)
Applications
[edit]Maybe the caption to the first image could be a bit longer: "Supply (S) equals demand (D) at an equilibrium".
- Agreed. I'll work on that. Kiefer.Wolfowitz (talk) 19:53, 11 January 2011 (UTC)
- Done, in an expanded form. Kiefer.Wolfowitz (talk) 01:50, 12 January 2011 (UTC)
On the one hand, the article says, progress was hindered because of non-convexity, on the other hand, the article says there was a "general" equilibrium theorem. This prompts the question: How "general" was this general theorem? Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- Interesting observation, but I know of no references containing such (apparently original) research. Kiefer.Wolfowitz (talk) 19:53, 11 January 2011 (UTC)
- Fair enough. Was just a thought. Jakob.scholbach (talk) 22:24, 14 January 2011 (UTC)
Lead of economics subsection
[edit]- I quite like this paragraph. However, this paragraph is unreferenced. I'm not sure you absolutely need a citation here, but maybe sharpening the statement of the effectivity of the previously existing equilibrium model vs. the next-generation non-convex theorem could be nicely done by quoting some reliable source?
- Thanks! I'll look for a source. Kiefer.Wolfowitz (talk) 19:53, 11 January 2011 (UTC)
- I added a reference of the famous 1975 article by Roger Guesnerie,
Page 1: Guesnerie, Roger (1975). "Pareto optimality in non-convex economies". Econometrica. Vol. 43. p. 1–29. doi:10.2307/1913410. JSTOR 1913410. MR 0443877. with "Errata". Econometrica. Vol. 43, no. 5–6. 1975. p. 1010. doi:10.2307/1911353. JSTOR 1911353. MR 0443878. {{cite news}}
: Cite has empty unknown parameter: |1=
(help)
- who discussed the general problems of non-convexity in economics briefly before focusing on non-convexities and general equilibrium theory. (I also did some slight rewording and simplification of the lead of this subsection.) Kiefer.Wolfowitz (talk) 16:53, 17 January 2011 (UTC)
History
[edit]Why is "History" part of the applications? I think this is probably best done as a separate section? Also, is there a reason that no paper of Shapley and Folkman is given in the reference list/history section? Did they not publish it, was it sort of trivial or what?
- The published history concerns economics exclusively, at least by all published sources known to me. I want to avoid OR and not discuss non economic predecessors. Kiefer.Wolfowitz (talk) 19:53, 11 January 2011 (UTC)
- An unpublished memo by Shapley and Folkman is credited by Starr. This WP article lists Starr's appendix, which reproduces the SF lemma and "theorem [originally a "corollary" to another theorem of S&F]" (before Starr's corollary). I spent an hour or more looking with Google Scholar and even the Rand Corporation database looking for a preprint/working paper, but found nothing. Kiefer.Wolfowitz (talk) 19:53, 11 January 2011 (UTC)
- I changed the title of this sub-subsection to "Preceding papers", which is more informative.
- I added the papers that Starr acknowledged and which also expanded economics to non-convexities. These additions seem imho essential to putting Starr's results in context: In particular, Shapley and Shubik also convexified preferences (like Herman Wold, if my memory be correct) and Shapley-Shubik and Aumann all studied approximate equilibria, all leitmotivs in Starr's paper (as he acknowledges). Kiefer.Wolfowitz (talk) 01:50, 12 January 2011 (UTC)
- Hm. I assume you have thought much more about it than I just do now. Nonetheless the section "3.1. Mathematical economics" remains somewhat odd to me. I see two reasons for this: first this section goes back and forth in history (both chronologically and logically) a few times. It is unclear to me why it does so, and therefore leaves a feeling of confusion. Maybe the following reorganization would render it more smooth? First point out the convex part of the story (ie, the current subsection "3.1.1 Convex sets and fixed points"). You could conclude this section by connecting "Thus, non-convexity seemed to prevent economists from proving the existence of an equilibrium (with Brouwer's fixed-point theorem)." with the non-mathematical pre-Starr papers. Their existence seems to indicate (to me) that the idea of convexity was somehow in the air, but no-one knew how to do it properly. (Or is that a misconception of mine?) Mention the unpublished work of Shapley-Folkman. Then, finally, introduce Starr (including his acknowledgement to the non-precise predecessors). This way, the reader would get a clearer feeling of what preceded what.
- The second issue I'm seeing is that currently history (i.e., how, when and why did the theorems emerge) is intermingled with applications (i.e., what did they do when they finally had it). It is clear that this research was strongly motivated by economic applications, so the advance of science and applications are ping-ponging back and forth, but I still feel it would be easier to read if you would present them separately. Concretely, you could consider moving the paragraph "Using his corollary, Starr derived a bound on the distance ..." out of this historical part (maybe in what is now section "3.1.4 Additional economic applications"), in order to get a clearer distinction between history and applications. In fact, section 3.1.1. does not (seem to?) contain a single application of the S-F lemma, it only (nicely!) sets the stage why the S-F-lemma/Starr's work would be important. Also section 3.1.3 doesn't mention a proper application. If you agree to this, it might be worth thinking of a separate "History" section (or another title) which is top-level (maybe before Applications?) and then the App's. (This whole discussion also shows that the description of the economical applications is comparatively superficial, but fine enough for GA I think). Jakob.scholbach (talk) 22:24, 14 January 2011 (UTC)
Okay, with my fever, I'll have to look at this tomorrow.Your suggestions are certainly thoughtful, and deserve better action or better response here than I can give tonight.Cheers,Kiefer.Wolfowitz (talk) 23:26, 14 January 2011 (UTC)- Nonetheless, I'll respond!
- I followed a more-or-less "inverted pyramid" journalistic style, with the most important stuff up top, followed by details. In this case, the context of preceding work is not needed to to understand the title'd SF and SFS result(s); what is essential is the role of convex sets in the Brouwer fixed point theorem, as used by McKenzie; this is commented on by Starr's original article.
- The applications of the SF/SFS results may be more important than the predecessors, but I thought that resuming the chronological order would be helpful: I think that Starr's student status and his work with Arrow and the calling on "higher powers" Folkman & Shapley (like in a 12 step program!) add human interest to the article.
- (I also have thought of adding a sentence to other issues of non-convexity in microeconomics, which are noted by Guesnerie's 1975 article; a couple of sentences would add context, and suggest that the issues of non-convexity are wider than those considered in Starr's article. I'm thinking of a sentence like the previous one mentioning applications of SF/SFS in microeconomics, with the new footnotes mentioning Starrett on externalities, Drèze on incomplete markets, Chichilnisky & Heal on international trade, Heal & Dasgupta on growth, maybe Guesnerie etc. on marginal cost pricing for public goods.) Thanks again for the great help!
- Best regards, Kiefer.Wolfowitz (talk) 23:39, 14 January 2011 (UTC)
- Implementing this declaration, I added a paragraph, sticking strictly to Guesnerie's 1975 article (page 1 again). Thus, I omitted Chichilnisky, Heal, and Dasgupta. Kiefer.Wolfowitz (talk) 21:23, 17 January 2011 (UTC)
- OK. Probably it is a matter of taste whether you want to separate the true applications and the historical remarks about how they emerge(d). Also, this is not part of the GA criteria. But about the chronological order of the papers etc.: I really disagree with you saying that the context of preceding work is not needed to understand SF(S). Of course, mathematically, it is not necessary, but to present the chain of thoughts (and papers, some unpublished) is a piece of information the reader will enjoy. The mathematics has been dealt with above, so arranging things based on the logical implications behind the theorems is unnecessary (and, I belive, unhelpful) when you describe things rather from a qualitative point of view. Jakob.scholbach (talk) 20:52, 16 January 2011 (UTC)
- Unfortunately, saying much more would be original research: I think that I've given a fair representation of the history, in greater detail than in any source known to me (apart from Starr's original paper and his reminiscence in the Arrow festschrift), so I worry that further elaboration would be fail the WP guide to give a summary. (Further elaboration would obligate me to cite additional predecessors, which have not been recognized yet, which would violate the prohibition on orginal research, if I may write honestly and openly.) Another concern is that the article is getting full-sized already, isn't it? Maybe a third opinion would be useful?
- Nothwithstanding the above objections, I'll probably implement your advice in some fashion this week, following my usual habit!
- (You should see Michael Hardy's comments, above, and on his talk page, and let me know if I should do a further correction. Sorry about misunderstanding your advice on subscripts.)
- Sincerely, Kiefer.Wolfowitz (talk) 21:08, 16 January 2011 (UTC)
- (unindent) Firstly, I guess the current ordering of the historical material does not qualify as unconcise prose or anything which is objectable on the grounds of the Good article criteria. So we can stop this discussion without affecting the outcome of this GAC. I'm striking this point. But I'd like to repeat: I'm not asking you to provide more details. It is very detailed and the mentioned facts seem to cover all that can be said about the theorem's history. The thing which strikes me as suboptimal is the ordering of the material. The text jumps back and forth in time and succession of ideas: 1) convex geometry/economics (i.e., pre-Starr) 2) Starr's work 3) again, pre-Starr. I fail to understand the reason for this and think that a reordering along the lines sketched above would be beneficial. Jakob.scholbach (talk) 20:30, 18 January 2011 (UTC)
- I implemented the chronological reordering, following your suggestion. I agree that it makes a lot more sense now, and I resolve to remember to respect the magisterium of the editor in the future! (Following your suggestion the first time would have saved everybody time!) Thanks for your help. Kiefer.Wolfowitz (talk) 22:44, 18 January 2011 (UTC)
Summary of subsection
[edit]- The rest seems to be OK. I guess if you want to move on to FA level, some of this should be explained in a little more detail, to make it a bit more accessible. As a non-economist, I had to look up, say, market failure, while a non-mathematician probably has to look up a number of things in the "probablity theory" section etc.
- WOW! Thanks for compliment, which made my day. I'll try to fix the FA-problems after the GA problems. Thanks! Best regards, Kiefer.Wolfowitz (talk) 19:53, 11 January 2011 (UTC)
Referencing
[edit]The referencing is delightfully detailed. However, I would like to suggest not to mention particular theorems of some book in the main text. So instead of "this and that claim, see Author, page title", I would do "this and that claim[4]". If you cite the same book multiple times, this can also be formatted using templates, see e.g. [1].
- ^ a b Cite error: The named reference
s69
was invoked but never defined (see the help page). - ^ Page 1: Howe, Roger (1979), On the tendency toward convexity of the vector sum of sets (PDF), Cowles Foundation discussion papers, vol. 538, Box 2125 Yale Station, New Haven, CT 06520: Cowles Foundation for Research in Economics, Yale University, retrieved 2011–01–15
{{citation}}
: Check date values in:|access-date=
(help); Cite has empty unknown parameter:|1=
(help); Unknown parameter|month=
ignored (help)CS1 maint: location (link) - ^ Cite error: The named reference
Starr08
was invoked but never defined (see the help page). - ^ Author, ...
{{citation}}
:|author=
has generic name (help), see page ... Theorem ...
- I believe that the in-text page-references are to Schneider's book. In your example (of Lang's book being multiply cited), no page references are given; I had thought page references were mandatory, at least for GA status articles. (Suggestion: Following LaTeX, WP should allow the citation by reference and page, e.g. [1:3] for the first item's page 3.) Kiefer.Wolfowitz (talk) 10:50, 19 December 2010 (UTC)
- Because of the inability to footnote within footnotes, the citation of Puri & Ralescu is repeated in the Cerf citation. Kiefer.Wolfowitz (talk) 13:29, 19 December 2010 (UTC)
- Sure, having pages is better than not having them. Especially if you cite a particular theorem. That is why I gave this link. In ref. no 6 of the logarithm article, you see how to cite the book (without any pages), in ref. no. 7 you see how to cite reference number 6 and give the particular page/theorem etc. you want to cite. I guess it is not a must fto do it this way, but since you seemed to enjoy the referencing, I just wanted to tell you this possibility. Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- Thanks. I see that you can use a "Harvard citation" template for page referencing. I'll try to use it when I return to editing. Cheers, Kiefer.Wolfowitz (talk) 10:24, 29 December 2010 (UTC)
- Reviewing the citation templates, I corrected the editors of all the volumes, which I'd previously cited in an ad-hoc way as authors. Kiefer.Wolfowitz (talk) 01:52, 12 January 2011 (UTC)
- There were some duplicated terminal periods ("..")for references, which I think I've removed. Kiefer.Wolfowitz (talk) 16:48, 12 January 2011 (UTC)
- Thanks. I see that you can use a "Harvard citation" template for page referencing. I'll try to use it when I return to editing. Cheers, Kiefer.Wolfowitz (talk) 10:24, 29 December 2010 (UTC)
- I really appreciate your help here. I've had a fever with my cold this week, and I haven't had the time to learn the page referencing with the harvard() and citation() templates, which might yield something like this.[1:34] When I feel better, I'll try to fix the page references. Kiefer.Wolfowitz (talk) 22:38, 14 January 2011 (UTC)
- Thanks! I unified all the citations, moving textual page references to footnotes, which have the page references linked via the harvard-citation templates. Kiefer.Wolfowitz (talk) 18:14, 17 January 2011 (UTC)
Conclusion
[edit]I think this article is essentially at GA level. I hope that the above comments can be adressed in some form or another; once this is done I will be happy to award the article the green plus . Jakob.scholbach (talk) 12:16, 27 December 2010 (UTC)
- Thank you for your detailed comments, which shall help this article greatly (and also have greatly improved my understanding of WP style, etc.). For the benefit of other editors and readers, I repeat my notice to Jakob that I shall return to normal editing after January 10th, so that my failure to act immediately on Jakob's other suggestions merely indicates my inaccessability rather than lack of interest. Best regards, Kiefer.Wolfowitz (talk) 10:30, 29 December 2010 (UTC)
- I've returned to (rather regular) editing of this GA nominee. Thanks for (any) patience. Kiefer.Wolfowitz (talk) 19:54, 11 January 2011 (UTC)
- IMHO, David Eppstein and I have addressed all the serious problems noted by our helpful and encouraging referee, Jakob; only some desires for rewriting the "economic history" section remain unaddressed, I believe. Thanks again to all for the great help! Cheers, Kiefer.Wolfowitz (talk) 17:02, 17 January 2011 (UTC)
- I think this gives too much credit to me — I've made a few edits recently but Kiefer.Wolfowitz has done most of the hard work. But thanks to all for the critiques and the improvements. —David Eppstein (talk) 18:42, 17 January 2011 (UTC)
- Thanks! On his talk page, editor Malleus Fatuorum raised the concern that the lead is too technical now. (It has been a struggle to give an accurate summary of the article's contents.) Kiefer.Wolfowitz (talk) 18:55, 17 January 2011 (UTC)
- I just made some edits aimed at toning down the technicality of the lead. —David Eppstein (talk) 19:17, 17 January 2011 (UTC)
- Thanks! On his talk page, editor Malleus Fatuorum raised the concern that the lead is too technical now. (It has been a struggle to give an accurate summary of the article's contents.) Kiefer.Wolfowitz (talk) 18:55, 17 January 2011 (UTC)
- I think this gives too much credit to me — I've made a few edits recently but Kiefer.Wolfowitz has done most of the hard work. But thanks to all for the critiques and the improvements. —David Eppstein (talk) 18:42, 17 January 2011 (UTC)
- IMHO, David Eppstein and I have addressed all the serious problems noted by our helpful and encouraging referee, Jakob; only some desires for rewriting the "economic history" section remain unaddressed, I believe. Thanks again to all for the great help! Cheers, Kiefer.Wolfowitz (talk) 17:02, 17 January 2011 (UTC)
(Unindent) Other editors should verify that my re-rewrite is correct and also satisfies Jakob's objection to the undefined use of "non-convexity" (throughout the article). Now it is introduced as a short-hand term for the distance from the set to its convex hull, only in the Statement section. IMHO, "shape" is an appropropriate name for the "inner-radius", whose definition is too technical for the introduction. Kiefer.Wolfowitz (talk) 21:52, 18 January 2011 (UTC)
Final comments
[edit]I'm promoting this to GA status. I think the article is gives a well-researched and well-explained exposition of the lemma/theorem and its genesis together with a quick, but informative overview about applications.
Further plausible steps would include a peer review and a general prose check (I recently found the Wikipedia:League of Copyeditors very helpful.) Moving to FA stage, an essential step to be taken seems to move from broad to comprehensive, which here probably means a more detailed exposition of the applications. This might be challenging given that we have a very particular statement, and gauging the impact of this particular statement on the general advance of economical science might be hard to pin down, but surely this is an interesting and rewarding question. For an FA nomination, it would also be wise to consult the help of a non-math / non-economics person beforehand, to review accessibility questions. Jakob.scholbach (talk) 21:53, 19 January 2011 (UTC)
- Dear Jakob,
- Thank you very much for a very thorough and helpful review. I think that your efforts could be a model for GA reviewing, particularly since you focused on improving the article (rather than running through a check-list) and proceeded by working with editors, particularly this novice editor, explaining WP policies and style with supererogatory patience and clarity.
- Sincerely and with warm regards, Kiefer.Wolfowitz (talk) 22:11, 19 January 2011 (UTC)
Copy editing
[edit]I have listed this article on the FA-team's page, although this page seems to be inactive. I have also asked some of the most careful copy-editors on WP to look at the article, and Malleus has again made good comments on the article, e.g., reinforcing your concerns about the lead and about 2 reference questions.
A notice on the page of the league of copy-editors has already provided substanial comments from TCO and an hour of high-quality copy-editing from Lfstevens. THANKS!
Individual appeals to the editors of mathematical economics have resulted in expressions of interest from Protonk and a helpful edit from Dank. THANKS! Kiefer.Wolfowitz (talk) 11:21, 20 January 2011 (UTC)
Expanded applications: Economics
[edit]I improved the optimization section, so I think it explains the SF application well (without distraction) and is self-contained. I simplified and glossed some of the probability-and-measure applications, adding a great quote by Debreu which ties the vector measure application back to economics, nicely, imho; I don't see anything else to be done with that section, which is last because it's hard to explain the SLLNs and CLT for random sets.
I have made some improvements and simplifications to economics. However, the economics section needs some work. Brouwer's theorem is applied to the the price simplex, which is convex. The problem is that fixed points of the price-mechanism mapping need not be equilibria for agents with non-convex preferences, if my memory is correct. Would an economist help with expanding that section, please? (Also, Charles Matthews correctly noted that Brouwer's theorem doesn't actually require convexity --- I'll add, no matter what the distinguished economists say! I think that a homeomorphic image of a compact convex set should work.)
Thanks, Kiefer.Wolfowitz (talk) 05:23, 22 January 2011 (UTC)
- I expanded and revised the economics section. Copy-editing would be helpful. Kiefer.Wolfowitz 15:09, 31 January 2011 (UTC)