Misplaced Pages

Revision as of 15:05, 4 October 2011

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)

Summary

All three reviewers have supported the nomination, and the copyscape audit has revealed no problems (and there are none, I vow). I have responded to all actionable complaints and suggestions (IMHO) inside the scope of a FA nomination.

Outside the scope of a FA nomination, imho, there remains two suggestions for expansion of applications. In optimization, Protonk requests an informal explanation of the significance of the Ekeland/Lemarechal result, which should be done in a few days (e.g., following Bertsekas's textbook). Second, in economics, Protonk's request for another example can be done in 2 days, by providing short verbal explanation of an example from Starr's 1969 paper; alas, IMHO, it is impossible to provide a graphical illustration using economic data to illustrate the SF lemma without doing original research.

Finally, I thank my reviewers for their dedication and excellent suggestions, the article's creator David Eppstein for his initiative & brilliant graphics & continued efforts, the peer reviewers Paul Nguyen, Geometry Guy, & TCO, mensch EdJohnson, for great suggestions, Mike Hardy for copyediting and help with formatting, the copy-editing of LK and others, and especially Jakob for his civilized leadership in the Good Article review, which taught me most of my WikiCraft. Thanks again.  Kiefer.Wolfowitz 16:20, 2 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)

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)

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.

  I don't think synthesis is necessary. Right now we have a one sentence introduction for the three sections. I am suggesting a few sentences more (some of which could be recapitulated later on) to give the reader a quick indication of what is to come. Protonk (talk) 17:37, 3 October 2011 (UTC)

  Perhaps you have not seen the applications-introduction after I updated it a few days ago? I provided a short overview. However, it is not possible to go into (much) more detail, because each application has a special vocabulary needing explanation.  Kiefer.Wolfowitz 12:29, 4 October 2011 (UTC)

• "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)

  DONE! I hid the graph (because 2>1).  Kiefer.Wolfowitz 15:44, 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.

  This suggestion is good, but it lies beyond the scope of this FA nomination, imho. Do you agree?  Kiefer.Wolfowitz 15:48, 2 October 2011 (UTC)

• 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.

  DONE! "Of course, the given optimal-point is a sum of points in the graphs of the original summands and of a small number of convexified summands, by the Shapley–Folkman lemma." (I have not given a further non-technical explanation, because I'm not sure what that would be, and your "maybe" question is not an actionable complaint ....)  Kiefer.Wolfowitz 16:04, 2 October 2011 (UTC)

• " 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.

  Thanks!

  I wrote the following expansion:

  "In 1973, the young mathematician Claude Lemaréchal was surprised by his success with convex minimization methods on problems that were known to be non-convex; for minimizing nonlinear problems, a solution of the dual problem problem need not provide useful information for solving the primal problem, unless the primal problem be convex and satisfy a constraint qualification. Lemaréchal's problem was additively separable, and each summand function was non-convex; nonetheless, a solution to the dual problem provided a close approximation to the primal problem's optimal value. The crucial step in these publications is the use of the Shapley–Folkman lemma."

  With this edit, I believe that I have resolved every actionable problem. Sincerely,  Kiefer.Wolfowitz 12:56, 4 October 2011 (UTC)

• 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)

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 ${\displaystyle (r,s)}$ can be multiplied ${\displaystyle (r,s)\rightarrow r\cdot s}$ and added ${\displaystyle (r,s)\rightarrow r+s}$. More generally, with two dimensions, we can consider the multiplication of a 2-dimensional vector ${\displaystyle (r_{1},r_{2})}$ by a real number ${\displaystyle s}$, which forms the scalar-vector product ${\displaystyle s\cdot (r_{1},r_{2})=(s\cdot r_{1},s\cdot r_{2})}$; every pair of 2-dimensional vectors can be added, thusly ${\displaystyle (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: Vector addition and scalar-vector multiplication". 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

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.

Economics

• 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 liked your rewording, but I made a few changes. I removed the reduction to relative prices, just because this interesting (projective-geometry, or dual-space) reduction is not needed, and may confuse some readers. I changed one "the optimal basket" to "an optimal basket", as in a non-strictly-convex example.

• 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.

  I hid the supply-and-demand graph, following your concern and Protonk's. Another editor may well consider restoring it ....  Kiefer.Wolfowitz 15:55, 2 October 2011 (UTC)

• 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.

  I agree with the abstract/aesthetic value of having the most general topic first, at least for experts. However, abstraction is a menace in popular science-exposition. ;)

  In the case of this article, it would be very bad to begin the applications with probability. That application-section is really a summary-style section that is of greatest use to students who have had at least a course in the "principles" of real analysis (the theory of calculus, like Walter Rudin's "Baby Rudin") and a basic course in probability. Leading with probability would place a road block in the way of many readers.

  The economics application deserves to come first, at least historically. The optimization application(s) could come first, mathematically. However, as discussed above with Protonk, economists have spent a century simplifying consumer theory, and it seems that the indifference-curve approach enables the article to avoid maximizing utility. (If we used utility maximization, for quasiconcave utility functions, then optimization should precede economics, in exposition as well as in abstract-to-specific ordering). K.W.

• 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.

  DONE! Thank you for the great suggestions, now and earlier.  Kiefer.Wolfowitz 15:55, 2 October 2011 (UTC)

• Overall, Support.  Volunteer Marek  20:11, 1 October 2011 (UTC)

Keifer, there is way too much bolding in this nomination. Next time, please don't bold so much within your own comments, and please do not repeat reviewer declarations. This actually makes it harder for delegates to see what is going on at a quick glance and makes it more likely that I'll miss something. I've removed some of the bolding here, but not all that should go away.

It's also unnecessary to add a summary because the delegates have to read everything through anyway. If you choose to add a summary anyway, please do it at the bottom. Karanacs (talk) 15:05, 4 October 2011 (UTC)

1. Howe (1979, p. 1): Howe, Roger (3 November 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 1 January 2011 {{citation}}: Check date values in: |accessdate= (help); Cite has empty unknown parameter: |1= (help)CS1 maint: location (link)