Shapley-Folkman-Starr Theorem

While economic theory sometimes uses advanced mathematics, such as Brouwer’s fixed point theorem, it’s less common for economic theory to lead to new mathematical developments. The Shapley-Folkman-Starr Theorem is an example of the latter. Roughly, the theorem states that the (Minkowski) sum of a large number of arbitrary sets in a finite-dimensional vector space will be close to convex. Starr was an economics undergraduate who was working on a term paper on approximating non-convex optimization problems with convex ones. This led to collaboration with Shapley (a game theorist), and Folkman (a mathematician), and the eponymous theorem.

The Tragedy of Blogging

Like most blogs, this blog gets a lot of spam, most of which gets caught by the spam filter, but not all. Some of it I have to go through manually. Sadly, I have come to learn that if a message says something like “great job”, it’s spam with probability 1. Probably the next generation of spambots will say “Completely wrong, you idiot!” and compare you to Hitler for greater verisimilitude.

Combined with the revelation that I accidentally turned down the Clay Prize, it’s been a discouraging day for this blogger.

Homomorphisms and Horn Clauses

The idea of a homomorphism extends neatly to general signatures. A function between two objects with the same signature is a homomorphism if it preserves all function and relation symbols. So φ is a homomorphism if for each n-ary function symbol f

φ( f(x1, …, xn) ) = f( φ(x1, …, φ(xn) )

and each n-ary relation symbol R

R(x1, …, xn) implies R(φ(x1, …, φ(xn))

This coincides with the usual definition of homomorphism for groups and rings. For partially-ordered sets, homomorphisms correspond to order-preserving maps.

Previous post here.

Non-standard analysis in economics

I see, via Yet Another Sheep, that nonstandard analysis has spread to mathematical economics. Robert Anderson has a book manuscript available, Infinitesimal Methods in Mathematical Economics which explains how to apply nonstandard analysis to approximate economies with large numbers of agents. The main technique is Loeb measures, which is something that I plan on writing a post on, once I actually know anything about them.

Brouwer Fixed Point Theorem

One idiosyncratic interest of mine is mathematical economics. I was looking through Volume 2 of the Handbook of Mathematical Economics when I spotted a paper by Scarf called “The Computation of Equilibrium Prices: An Exposition”. The real subject of the paper is an incredibly clear exposition of how to find fixed points of maps of the unit n-cube to itself. The Brouwer Fixed Point Theorem promises that at least one fixed point exists. I knew that there was a combinatorial approach based on Sperner’s lemma, but it had always struck me as rather technical. Not so; Scarf gives a straightforward algorithm for finding the fixed point. Sperner’s lemma is just the result that dictates that the algorithm terminates.

The proof is stated for an n-simplex, which is the n-dimensional analogue of a triangle. The algorithm works by cutting up the simplex into smaller simplices, and identifying which of the smaller simplices contains a fixed point. It then repeats, trapping the fixed point in smaller and smaller simplices until it eventually converges. What’s interesting is that the test for whether a particular simplex contains a fixed point is fantastically crude; it amounts to just checking a simple condition on the map at the vertices. (The condition is not satisfied for every simplex containing a fixed point, and in fact the algorithm will miss some fixed points. At least one fixed point will satisfy the condition, though.)

The article does everything from scratch. Brouwer’s theorem is derived as a consequence of the algorithm. It is simple enough that it could easily be included in an undergraduate analysis textbook. The whole article is so simple that it makes me wonder if there is an elementary combinatorial subject lurking under the intimidating algebra of modern-day homology theory. An interesting test case is if a constructive version of the Lefschetz fixed point theorem. (Lefschetz’ original proof was apparently combinatorial, but extremely difficult to follow. I doubt it was constructive.)

Here is two artists’ take on the Brouwer fixed point theorem.

Update. Commenter Mio spotted this elementary introduction to the topic on Herb Scarf’s web page. Poking around some more, I found the original article I mentioned above here.

Dressing to Impress Mathematicians

Brad de Long, an economist, has a post up about the significance of how he dresses for specific audiences. In particular, the consequences of wearing ties:

With math-oriented students, however, a tie tells them that I spend too little time thinking about isomorphisms.

(This inspired n-category jokes in the comments.)

2007 Nobel Prize in Economics

I was looking at an interview with Roger Myerson, one of the three winners of the 2007 Nobel Prize in Economics (technically the Sveriges Riksbank Prize). Myerson says

How would my career have been different without John Nash? What a wonderful question! My difficulty in answering it is an indication of how influential he has been in everything that I have done. I wanted to be a mathematical social scientist since I was 12 years old, when I read Isaac Asimov’s science-fiction novel Foundation. But my concept of what kinds of mathematical models should be studied was completely transformed when I read Nash’s and Harsanyi’s papers in college.

Shalizi on Econophysics

Cosma Shalizi has written a detailed posting on what’s wrong with econophysics. Econophysics is the application of certain ideas that have been influential in physics in recent years — power laws, phase transitions, nonlinear dynamics — to finance and economics. Econophysics articles are generally published in physics journals, and have not had much of an impact on economics as practiced in economics departments. If you love statistical mechanics, and you think it explains everything, then econophysics is the area for you.

Cosma also includes a section on what’s wrong with economics, because he intends on dying friendless and alone.

Chichilnisky versus Columbia

In a post on his weblog, Michael Greinecker mentioned some applications of homology to economics. While aimlessly websurfing for more information, I came across the homepage of Graciela Chichilnisky, a mathematical economist who has extensively applied topological techniques to economic questions. Chichilnisky has written nearly 200 articles, and includes PDFs on her site.

On a less happy note, Chichilnisky also links to a site dedicated to detailing her problems with Columbia University, where she is a tenured professor. Chichilnisky had successfully sued Columbia on the grounds of sex discrimination in the 90s. The two parties are now back in court over an alleged pattern of retaliation on the part of Columbia. An article on her experiences with the reviewing process also makes depressing reading.