Talk:Shapley–Folkman lemma/Archive 1

Archive 1

Archive 2

Archive 3

Archive 4

Continuous parameterization?

Is it possible to apply the Shapley–Folkman lemma to simultaneously decompose all points in the convex hull of the Minkowski sum, in such a way that the decomposition is a continuous function of a point's location?

To formalize this: Let H be the convex hull of the Minkowski sum of some collection of d-dimensional nonconvex sets S_i, (1 ≤ i ≤ k), and let D be the space of k-tuples of points, d of which belong to convex hulls of sets S_i and the rest of which belong to S_i itself. Then the Shapley–Folkman lemma tells us that the function from D to H that sums each k-tuple is surjective. Does it have an inverse? That is, is there a continuous function ƒ from H to some subset of D, such that the composition of ƒ with the function that sums the points in a k-tuple is the identity function on H? Or is there some sort of topological nontriviality on the map from D to H that prevents this?

(And, if this is known in the literature, what are the references so that it may be added to our article?)

—David Eppstein (talk) 22:18, 20 October 2010 (UTC)

In the forward direction, there is some "polyhedral uniformity": Each (pointwise) SF representation will cover not just that point; the SF representation is not unique, of course.

In the reverse direction, let me thinks some more. (This question might interest Graciela Chichilnisky at Columbia, who wrote about topology and convexity in BAMS in the mid 1980s, I believe.)

I sent you a private email to your departmental address with some literature pointers. (Sorry for duplication)

Best regards, Kiefer.Wolfowitz (talk) 23:05, 20 October 2010 (UTC)

Did you know? (DYK)

Wikipedia's Did you know? listed this hook:

• . . . one of the major achievements of modern economic theory, the Shapley–Folkman–Starr theorem, was proved by Ross M. Starr while he was studying with Kenneth Arrow as an undergraduate at Stanford University?

Thanks! Sincerely, Kiefer.Wolfowitz (talk) 08:21, 19 October 2010 (UTC)

The DYK listing generated 3.6 thousand views, more than double the usual number (based on my previous experience of 2 DYK articles). Kiefer.Wolfowitz (talk) 22:00, 8 November 2010 (UTC)

Capitalization of journal titles

The Wikipedia style guide for academic journals mandates the capitalization of journal titles. This will take some time to fix. Thanks! Kiefer.Wolfowitz (talk) 15:48, 12 January 2011 (UTC)

That is for the name of an article about a journal itself; I don't believe it covers reference lists in other articles. — Carl (CBM · talk) 16:16, 12 January 2011 (UTC)

Well, I disliked citing "SIAM review" rather than "SIAM Review", so I consistently capitalized all the journal titles: I hope that this was okay. Thanks for your quick response, Carl! Best regards, Kiefer.Wolfowitz (talk) 16:51, 12 January 2011 (UTC)

Convex hull notation Conv()

I expanded the material on convex hulls, introducing the conventional notation Conv() for the convex-hull operator.

Alternative notation is unsatisfactory: The uncapitalized notation "conv()" is less-legible. Even less eligible is the French shorened notation "co()", whose only advantage is that of avoiding a French obscenity.

I shall use this (convex-hull operator) notation to simplify the statement of the lemma.

Thanks!

Sincerely, Kiefer.Wolfowitz (talk) 01:59, 15 January 2011 (UTC)

Digressions removed

Unions

I removed this digression:

These results show that Minkowski addition differs from the union operation of set theory. Indeed, while the Minkowksi sum of two convex sets is convex, the union of two convex sets need not be convex; in the preceding illustration of the convex squares [0,1]² and [1,3]², their union [0,1]² ∪ [1,3]² is non-convex, because it fails to contain the point (2, 1/2) for example.

Thanks. Kiefer.Wolfowitz (talk) 01:57, 17 January 2011 (UTC)

Hull operator

The convex hull operation has the characteristic properties of a hull operation:

extensive	Q ⊆ Conv(Q),
non-decreasing	P ⊆ Q implies that Conv(P) ⊆ Conv(Q), and
idempotent	Conv(Conv(Q)) = Conv(Q).

Thus, the convex hull operation is a proper hull operation.

Square root of two and its rational approximants

For another example, the square root of two √2 is the limit point of the sequence of the rational numbers in its decimal expansion

√2 = lim ( 1, 1.4, 1.41, 1.414, 1.4142, ... ),

but the square root of two is not a rational number. Thus, the set of decimal expansions of √2, which is a set of rational numbers, is not a closed set. This shows that the set of rational numbers is not closed. Indeed, the closure of the set of rational numbers is the set of real numbers, which is the union of the rational numbers and the set of irrational numbers.

Economics

Supply and demand

At an equilibrium price P0, the quantity supplied S(P0) equals the quantity demanded D(P0). The excess demand equals the demand minus the supply.

Fixed points

A quarter turn of the convex unit disk leaves the point (0,0) fixed but moves every point on the non-convex unit circle.

Before Starr's paper, the standard model of general equilibrium was the Arrow–Debreu model. A general equililbrium was proved to exist by Lionel W. McKenzie, who used Brouwer's theorem on the fixed points of a continuous function from a compact, convex set into itself. In McKenzie's approach to the Arrow–Debreu model, convexity seemed essential, because such fixed-point theorems can fail for non-convex sets. For example, the rotation of the unit circle by 90 degrees lacks fixed points, although this rotation is a continuous transformation of a compact set into itself; although compact, the unit circle is non-convex. In contrast, the same rotation applied to the convex hull of the unit circle leaves the point (0,0) fixed. This example suggests why non-convexity was a problem for economists wanting to prove the existence of an equilibrium (with Brouwer's fixed-point theorem).

Hyphens

We should achieve consensus on the use of hyphens in phrases like "real vector-spaces", "finite-dimensional vector-space", and "simple random-variable". As these examples indicate, I favor hyphens to avoid ambiguity. Moreover, such hyphenation seems (to me) to be mandatory by the Manual of Style (and by Michael Dummett's Grammar & Style, etc.). However, I recognize that most editors prefer fewer hyphens, because many of my hyphens have been replaced with spaces. Kiefer.Wolfowitz (talk) 19:05, 17 January 2011 (UTC)

I think "vector space" and "random variable" are standard modern usage, and "vector-space" and "random-variable" read like a throwback to the 19th century. There's an interesting discussion of the same topic by Fields medalist Timothy Gowers here. —David Eppstein (talk) 19:26, 17 January 2011 (UTC)

Thanks. Even the renowned editor Malleus Fatuorum removed the hyphen from a subheading "Real vector-spaces". Agreeing that such usages are established, we can live in peace with the MOS. (I'll remove hyphens another day, then.)

I'll read Gowers's discussion of hyphens with pleasure; I've read a couple of thoughtful and well-written essays by him already. Kiefer.Wolfowitz (talk) 19:50, 17 January 2011 (UTC)

That was very entertaining & informative, particularly the following quote (Kiefer.Wolfowitz (talk) 19:58, 17 January 2011 (UTC)):

The author of the style-book of the Oxford University Press of New York (quoted in Perrin’s Writer’s Guide) strikes the same note when he says “If you take hyphens seriously you will surely go mad”.

References

In the next hour few hours, I'll add some references. Kiefer.Wolfowitz (talk) 00:28, 18 October 2010 (UTC) Done! Kiefer.Wolfowitz (talk) 04:38, 18 October 2010 (UTC)

I'm sorry that I cannot see the long dashes. Thanks David and Michael Hardy for fixing them. Kiefer.Wolfowitz (talk) 05:06, 18 October 2010 (UTC)05:23, 19 October 2010 (UTC)

Mathematical economists

Andreu Mas-Colell

Andreu Mas-Collel remains a broken link, in the hope that a red-link will prompt an editor to write an article.

While Professor at Harvard, Mas-Colell became one of the world's leaders in microeconomics/mathematical economics, and wrote an influential monograph of global-analysis economics (Sard & Baire, in the style of Debreu and Smale). His textbook rivals Varians for use, although it is heavier. In Catalan and Europe, Mas-Colell has been University President (I believe, from memory), and is apparently a senior minister on research in Catalan and in Europe (from his CV).

So he deserves an article.

Thanks! Best regards, Kiefer.Wolfowitz (talk) 02:41, 19 October 2010 (UTC)

There's nothing about being a university president in his cv but he does very clearly deserve an article in any case. —David Eppstein (talk) 04:28, 19 October 2010 (UTC)

I remember something about him upgrading the research at his Catalan university, if I remember the (typically condescending, alas) article in the AMS Notices. Kiefer.Wolfowitz (talk) 05:21, 19 October 2010 (UTC)

Not only does Mas-Colell deserve an article but his textbook (with Whinston and Green) probably deserves an article by itself as it is pretty (in)famous among economists and economics students. Also I'm wondering if there shouldn't be an article on Starr as well. Volunteer Marek  20:40, 17 January 2011 (UTC)

I agree with your comments. I think that Starr has notable status also for his contributions to monetary economics and economics education (with his friendly textbook on general equilibrium theory). Kiefer.Wolfowitz (talk) 21:21, 17 January 2011 (UTC)

Ok, I started an article Andreu Mas-Colell, clearing one of the redlinks from this article. I don't know enough about economics to say much of intelligence about his actual research accomplishments, though, so the article is currently lacking in that respect. —David Eppstein (talk) 22:19, 17 January 2011 (UTC)

Well done, again, David! (I lifted a bit from the mathematical economics article, adding a reference to Debreu's Theory of Value for the "deprecation of differential calculus" claim; I'm too tired to add the page number from the preface.) Thanks again! Kiefer.Wolfowitz (talk) 00:23, 18 January 2011 (UTC)

Graciela Chichilnisky

I also added an article (not quite as fully fleshed out) on Graciela Chichilnisky. So as of now there are no redlinks left. —David Eppstein (talk) 22:16, 18 January 2011 (UTC)

Read my previous praises 3 times, David! WOW!

Just to keep you from getting complacent, I introduced a new red-link in Chichilnisky's article, for Geoffrey M. Heal a.k.a. Geoff Heal aka G. M. Heal. :P

I need to get back to sleeping and writing research now. Cheers, Kiefer.Wolfowitz (talk) 05:54, 19 January 2011 (UTC)

Indeed impressive. I think Ross Starr still needs an article - since I'm just pointing out the redlinks here I will try to be constructive rather than destructive and in the near future start that one (also if I remember Chichlinsky's article on trade between developed and developing countries correctly it had more to do with ill defined property rights rather than just increasing returns to scale). Volunteer Marek  06:12, 19 January 2011 (UTC)

Hi Marek! Your contributions have been constructive all along, and I hope that you'll continue. I am ignorant of monetary economics, alas, and don't think that I can be of any help with the research on Starr. About Chichilnisky, I wrote the synopsis after a quick skimming of the last chapter of Chichilnisky and Heal's The evolving international economy, which emphasizes increasing returns to scale and which has a lot of pictures of non-convexities, I'll add. I don't remember "property rights" being a focus, but you should be bold and correct any mis-statements you find. (I don't think I wrote "just": Please remove "just" if I did.) Best regards, Kiefer.Wolfowitz (talk) 06:39, 19 January 2011 (UTC)

Will do shortly (btw, this is the paper I was thinking of [1]). Volunteer Marek  16:48, 19 January 2011 (UTC)

Ross Starr

I've stubbed Starr here Ross Starr. Hopefully I'll have some time to expand it a bit but any help, particularly in regard to the information of this article would be much welcome. Volunteer Marek  23:50, 20 January 2011 (UTC)

Missing subtopics

When I look at this article, there are (at least) two things I'd like to find out that aren't really discussed at all.

• How are the lemma and the theorem proved? I don't know that we need a detailed rigorous proof here, but it would be good to have an outline of the main ideas, at the level that one might expect a competent grad student to be able to fill in the rest. If there are multiple proofs, how do they differ and what is their chronology?

I comment below. A rather short proof appears in Anderson's lecture notes, which establishes a lemma implying Shapley-Folkman and Carathéodory. Howe has a conceptual, inductive proof that is probably too sophisticated to appear here. I noted proofs similar to Starr (1969), and (at risk of OR) mentioned two proofs by induction (Howe and Anderson). Kiefer.Wolfowitz (talk) 17:03, 30 January 2011 (UTC)

• How constructive is the proof? What assumptions about the sets are needed in order to compute a Shapley–Folkman decomposition of a given point in the Minkowski sum, what algorithm or algorithms are used to perform the decomposition, and how efficient is that computation?

—David Eppstein (talk) 00:00, 19 January 2011 (UTC)

SSSSSSSSSSSHHHHHHHHHHHHHHHHHHHHHHHHHHHHH! I sent you a preprint! Kiefer.Wolfowitz (talk) 00:51, 19 January 2011 (UTC)

Seriously, I can add a reference to a "conceptual algorithm" (really a conceptual method) of Starr. Kiefer.Wolfowitz (talk) 00:52, 19 January 2011 (UTC) Almost all of the proofs use Shapley's theory of the facial dimension, going back to his work with Karlin.

I think the linked lecture notes by Anderson give a clean proof. I forget Howe's approach, because his other results are more interesting. Starr's approach is motivated by the idea of finding an approximation algorithm/method for the problem.

Starr, Ross–M. (1981). "Approximation of points of convex hull of a sum of sets by points of the sum: An elementary approach". Journal of Economic Theory. Vol. 25, no. 2. pp. 314–317. doi:10.1016/0022-0531(81)90010-7. MR 0640201.

Sincerely, Kiefer.Wolfowitz (talk) 01:06, 19 January 2011 (UTC)