Wikipedia:Featured article candidates/Shapley–Folkman lemma/archive1

Shapley–Folkman lemma

Shapley–Folkman lemma (edit | talk | history | protect | delete | links | watch | logs | views)

• Featured article candidates/Shapley–Folkman lemma/archive1

Nominator(s):  Kiefer.Wolfowitz 00:40, 24 September 2011 (UTC)

I am nominating this for featured article because... it is a comprehensive, well-documented, clearly written article on the Shapley-Folkman lemma and its applications and because it features two graphs (created by User:David Eppstein).  Kiefer.Wolfowitz 00:40, 24 September 2011 (UTC)

• I shall be on a 2-day WikiBreak. I shall resume editing on Monday. However, it shall be 2 weeks before I regain access to my library, and can check French preprints from the early 1970s, etc. (I apologize for the inconvenience.)  Kiefer.Wolfowitz 02:06, 1 October 2011 (UTC)

• The Nobel Prize in Economics shall be awarded on 10 October after 1:00 p.m. CET (Monday). It would be desirable to feature this article on the day on which the Nobel prize is awarded 10 October 2011 or in 2012.  Kiefer.Wolfowitz 05:35, 1 October 2011 (UTC)

Graham Colm (Copyscape review)

Copyscape review - No issues were revealed by Copyscape searches. Graham Colm (talk) 14:32, 24 September 2011 (UTC)

Thanks! :)  Kiefer.Wolfowitz 20:06, 30 September 2011 (UTC)

Protonk (provisional support)

Provisional support - I was involved in the A class review and approved of the article generally then. However the article has been expanded significantly since then. I will take a close look at the applications section but I don't feel comfortable with the rest of the text. Protonk (talk) 00:07, 28 September 2011 (UTC)

• The Applications section covers three (somewhat) conceptually distinct subjects; economics, optimization and probability theory. The text introducing the section should give the reader a mini road map of what to expect from the subordinate parts.

  True. I believe that the OR by synthesis is trivial: I am synthesizing statements made within 3 disciplines, which are obviously true, and saying that the statement is generally true, and has giving three examples of the statement.

  UPDATE: "The Shapley–Folkman lemma enables researchers to extend results for Minkowski sums of convex sets to sums of general sets, which need not been convex. Such sums of sets arise in economics, in mathematical optimization, and in probability theory; in each of these three mathematical sciences, non-convexity is an important feature of applications and the Shapley–Folkman lemma has renewed research that had been stumped by non-convex sets. In all three disciplines, the break-through application of the Shapley–Folkman lemma has been made by a young scientist" (whose innovations have then spread through the discipline ...).

  I have warned about possible minor OR by synthesis. I also want to inspire the youth to unleash their barbaric YAWP (like Lemarechal or Ekeland/Aubin or Starr or Artsein/Vitale---or Galois or Thomas Paine or Tom Kahn or The Kinks and the The Replacements).  Kiefer.Wolfowitz 03:17, 1 October 2011 (UTC)

  Conceivably, I could be asked to provide citations establishing all the authors' youth: If so, then I'd just delete the inspirational statements about young researchers shaking up things. K.W.

• "On this set of baskets, an indifference curve is defined for each consumer..." the two paragraphs in Economics feel somewhat out of order. Given the context of this article, we don't need to resort to describing preferences as indifference curves before bringing to bear the topological intuition. I would introduce the concepts of baskets of goods and constraints. Then note that optimal choices among those goods under those constraints under the assumption of convexity leads to relatively simple and painless intuition and graphical explanation. Then segue into indifference curves. After that you can return to the last few sentences in the second paragraph. Now you are set up for explaining why non-convex preferences might need another solution.

  Using indifference curves allows us to work with convex sets. If we work with maximizing utility, then we have to introduce quasi-concave functions (having convex upper-levelsets), which is a more complicated approach, imho; if we discuss maximizing quasi-concave functions, then economics should follow optimization. (I first took this material from existing articles and then reworked it with precise references. I thought that our explanation was similar to Varian's Intermediate Economics, which I read 20 years ago: My memory has failed me before.) K.W.

  No, you're correct. Let me think about how to better explain my concern with this paragraph, which are almost entirely about ordering. Protonk (talk) 00:08, 1 October 2011 (UTC)

• The non-convex preferences section is ok, but I would like to see a more general explanation to begin with. You give a good example of non-connected demand (though it is basically copied from the summary article) and the Hotelling quote is handy. However you might want to open up a bit more generally or offer some examples from more well behaved areas where preferences are non-convex. If you prefer you could shorten the section a bit.

• Just 'okay'!?!!! ;) What does your "summary article" refer to? (Certainly not Ross M. Starr's New Palgrave survey, which has no examples of anything!) My example was similar to examples given from Wold, Morgenstern, etc., and inspired by Harry Potter's Hogwart's school and by memories of Dungeons and Dragons! :D (I remember Starr's Econometrica article having some nice examples.) This may be a matter of taste; students should use this while they are looking at an intermediate or M.A. textbook in microeconomics, and most of these have examples of non-convexities; more advanced students and researchers will find my literature collection (with references and precise page numbers) very valuable, I hope. I think that one example and pointers to good textbooks should suffice for the general public, particularly because we have an article on the convexity of preferences. K.W.

• I mean that section looks identical to Non-convexity (economics), both of which you wrote. I didn't mean to imply that you did anything malign. Protonk (talk) 00:11, 1 October 2011 (UTC)

• Okay, now I understand. :) I emboldened my wink above, and added a smiling face. :D Actually, the non-convex economy article was a spin-off from this. I realized that Sraffa and company's contributions to non-convexities and production economics discussed problems besides aggregation (and this article was becoming long).

• "The previously noted papers were listed" I'm not sure which papers you mean.

  The JPE, Shapley-Shubik, and Aumann papers were discussed by Starr's Econometrica paper. K.W.

  Improved: "Previous publications on non-convexity and economics were collected in an annotated bibliography by Kenneth Arrow. He gave the bibliography to Starr, who was then an undergraduate enrolled in Arrow's (graduate) advanced mathematical-economics course." K.W.

• I know I said this in the A class review but the article really doesn't need File:Price of market balance.gif.

  It is nice to show a demand function, because our consumer theory lacks a demand function. Showing an equilibrium can only help non economists. (I agree that the illustration is not essential, and wouldn't object if another editor and you removed it.) K.W.

  Volunteer Marek also finds this graph sub-optimal, for another reason. The graph shows only one market, whereas our article discusses general equilibria (for N markets where N is a positive integer). However, N=1 is a special cases of general equilibria, so I discount VM's vote in this instance. Again, if anybody wants to remove the graph, then I would not object.  Kiefer.Wolfowitz 10:24, 2 October 2011 (UTC)

• "Following Starr's 1969 paper..." This paragraph can be extended (at the expense of the non-convexity section if you wish). We get (or at least I get) the immediate implication for general equilibrium models but the article should offer some other more concrete examples.

• This may be a matter of taste. I think that the article is rather long (although much of the length is due to the meticulous referencing, which may turn off some readers); I am skeptical about the value of more applications. I would rather have more pictures, perhaps an animation of the set I mentioned on the talk page of the article (similar to Mas-Colell's example).  Kiefer.Wolfowitz 03:15, 1 October 2011 (UTC)

  On second thought, I agree that an example of another economic application would be useful. I suppose that the aggregation of non-convex budget sets would be interesting, and I am aware of estimated (non-convex) budget sets for Swedish consumers.

  However, I do not know of any public-domain graphics for single consumers. I do not have access to my library for 2 weeks, but the references I gave were all rather mathematical. I am afraid that it may be difficult to give an empirical example of an application of the SF lemma (using a real-world agent's estimated budget set or production set or preferences) without doing OR. K.W.

• In that same paragraph you should remove the references to mathematical optimization and measure theory, as you are about to explain those in detail.

  I believe you are referring to Aubin's book on mathematical techniques for game theory and economics and then Trockel's book, which uses 2-3rd year Ph.D.-level mathematical analysis (ergodic theory, differential geometry/topology) to study economics. Aubin's book has a lot of non-probabilistic mathematics, and an extensive and original treatment of game theory and some economic models; I do cite it later in optimization, of course, because of the results with Ekeland. These two books (Aubin and Trockel) don't fit in the later sections (although your conjecture was very reasonable).  Kiefer.Wolfowitz 03:15, 1 October 2011 (UTC)

• Should the optimization section link to Knapsack problem?

• Lemarechal's problem was different. K.W.

• "An application of the Shapley–Folkman lemma represents..." Maybe this sentence should be followed by a quick non-technical explanation.

• I thought I gave one! ;) The muse fails me now. I shall return Monday and look at these sentences.

• " In 1973, the young mathematician Claude Lemaréchal was surprised by his success..." this is a neat bit of information. Perhaps some elaboration would help. Explain to the reader why Lemaréchal's results could be surprising without Shapley-Folkmann but are understandable with it. The text kind of does this now but it might help to make it more clear.

  I was afraid of losing the "summary style" if I went into more detail. I could quote Gill/Murray/Wright's warning that duality transforms are not general purpose tools for non-convex problems (and I could footnote their fallacious/worse-casitis claim that people should not use dual methods unless the problem is known to be convex). Also, Bertsekas's already cited monograph or textbook might be a better reference.

• the probability section is dense, but good. I get the feeling that there is a deep connection between measure theory and Shapley-Folkmann but I can't pin it down.

  Searching for "Shapley Folkman" and "vector measure" on Google Scholar/Books will give you more food for thought. I thought that our treatment was appropriate for a summary style. Also, ending with the discussion by Vind, Debreu, Mas-Colell nicely ties the abstract mathematics with economics, imho.  Kiefer.Wolfowitz 19:49, 30 September 2011 (UTC)

Malleus Fatuorum (support)

Comments. I'm no mathematician, but I have a few observations nevertheless. This isn't particularly advanced mathematics, so we shouldn't be scared of it. (That was a rallying cry to other FA reviewers who may be as much math dunces as I am.)

• I think it's important that the lead is accessible to the general reader, who may not understand what a lemma is.

  New second sentence in lede: "In mathematics, lemmas are propositions that are steps in a proof of a theorem."  Kiefer.Wolfowitz 00:58, 28 September 2011 (UTC)

• "The Shapley–Folkman–Starr results address the question ...". No, they don't. Results don't address anything.

  "The Shapley–Folkman–Starr results provide an affirmative answer to the question, "Is the sum of many sets close to being convex?"  Kiefer.Wolfowitz 01:04, 28 September 2011 (UTC)

• "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 ...". What does "central results" mean?

  Updated"; for example, quasi-equilibria closely approximate equilibria of a convexified economy." (This rephrases a phrase only a few sentences earlier. I suspect that repetition may help readers rather than bore them.) K.W.

• "Minkowski addition is defined by the addition of the sets' members". Is it defined by it or as it?

• Sharply observed, MF! It should be "as". (Three corrections on page) K.W.

• "A real vector space of two dimensions can be given a Cartesian coordinate system in which every point is identified by a list of two real numbers". A list isn't two.

  I can substitute ordered pair. (DONE) K.W.

• "This distance is zero exactly when the sum is convex". What does that mean? Exactly zero when the sum is convex? Why "exactly"?

  "exactly" is a conversational way of writing "if and only if". I'll change it (because temporal "when" is distracting). (DONE) The word "exactly one" recurs in the image's alternative caption, because the statement that there exists 1 dollar in my bank account is true even when I have 2 or more dollars there. K.W.

• "The Shapley–Folkman–Starr theorem states that 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." Something's gone wrong with the punctuation or grammar there.

• That is weird. I'll check the history in case my keyboard mistyping deleted something important. It could be fixed by deleting "that", although the long dash is jarring. K.W. AHA! The "that" was inserted by MF! :D *LOL* I think that "the theorem states an upper bound" is proper grammatically and conventional mathematically: Other word choices should be considered.  Kiefer.Wolfowitz 04:22, 28 September 2011 (UTC)

• Oops! Malleus Fatuorum 18:30, 29 September 2011 (UTC)

Real vector spaces

• "More generally, any real vector space of (finite) dimension D can be viewed as the set of all possible D-tuples of D real numbers { (v₁, v₂, . . . , v_D) } together with two operations". How can a real vector space be viewed as two operations?

  First, we have the real numbers, which can be considered to a vector space over itself. This means that every pair of real numbers $(r,s)$ can be multiplied $(r,s)\rightarrow r\cdot s$ and added $(r,s)\rightarrow r+s$. More generally, with two dimensions, we can consider the multiplication of a 2-dimensional vector $(r_{1},r_{2})$ by a real number $s$, which forms the scalar-vector product $s\cdot (r_{1},r_{2})=(s\cdot r_{1},s\cdot r_{2})$; every pair of 2-dimensional vectors can be added, thusly $(r_{1},r_{2})+(s_{1},s_{2})=(r_{1}+s_{1},r_{2}+s_{2})$. The operations for higher-dimensional vector-spaces are defined analogously (elementwise).  Kiefer.Wolfowitz 18:39, 30 September 2011 (UTC)

  I understand that a real vector space is a set of real number pairs, but it's the "together with two operations" I'm unhappy about. The operations are specifically addition and multiplication, not any old operations, and they're applied to the vector spaces. Malleus Fatuorum 20:12, 30 September 2011 (UTC)

":::Done! "A set on which two operations are defined: Blah1 and Blah2". K.W.

Shapley–Folkman theorem and Starr's corollary

• "Starr used the inner radius to strengthen the conclusion of the Shapley–Folkman theorem". Theorems don't have conclusions.

  The SF theorem is a conditional theorem with an if-then statement: "If the number of sets is greater than the dimension, then ... an inequality is satisfied." K.W.

  Then that probably ought to be explained, because right now it makes no sense to anyone other than a mathematician. Malleus Fatuorum 00:43, 1 October 2011 (UTC)

  That's an excellent point. I'll fix it.  Kiefer.Wolfowitz 01:45, 1 October 2011 (UTC)

• Support I've now read the whole article, and although it's not an easy read, and I'm not a mathematician, I'm persuaded that it's an accurate account that meets the FA criteria. Malleus Fatuorum

Volunteer Marek (support)

• Comments
• For the article as a whole, I'm impressed with the meticulous care that has been taken with both the references and with the explanations of mathematical concepts and issues intended at the average reader. I think there were (there always are) some minor issues with "translating math into English" but I think Malleus caught most if not all of that.
• Other than that I can really only make detailed comments about the "Economics" section. Again, I see no major problems here. There was some slightly awkward wording, as noted above, in the explanation of the graphical derivation of demand from the indifference curves and budget constraints which I reworded somewhat. Someone should probably make sure that in the rewording I didn't solve one problem by creating another. I also agree with the comment above that the "supply and demand" graph in the article is not really necessary. The application of the lemma in economics is to a general equilibrium but the graph depicts a partial equilibrium situation. This is fairly minor though.
• One final thing - though this is more of a matter of taste - in some ways I think it would make more sense to have the "Probability and measure theory" section precede the "Mathematical optimization" section as the first is more general. Along the side lines, shouldn't Shapley's photo be moved up in the article, perhaps to the section "Starr's 1969 paper and contemporary economics"? I understand that there are aesthetic issues involved as that may make one section over cluttered with images.
• Overall, Support.  Volunteer Marek  20:11, 1 October 2011 (UTC)