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.
Wow, thank-you for pointing this out.
I’m heading into graduate studies in economics in the fall and I’ve had trouble with some of the work around Arrow’s Impossibility theorom and other things because of a lack of an understanding of the Fixed Point Theorom, this should be a big help if I can get my head around it.
It’s amazing how often fixed point theorems come up. Every existence theorem for nonlinear PDEs that I know of ultimately relies on a fixed point theorem.
I’m a bit confused, the proof you describe sounds exactly like the proof via the Sperner Lemma (with is really a lot like the bisection method in numerical analysis). Are you just saying that in previous expositions you were familiar with you found the proof technical but not in Scarf’s exposition?
Omar: Yes, the proof Scarf gives is the Sperner lemma one. Normally, when I read the statement of Sperner’s lemma, and I think “wow, that sounds drily technical”. For example, I had that reaction reading the Sperner’s lemma Wikipedia page when I linked to it. Scarf just explains it very clearly, and makes it explicitly algorithmic.
There’s a publicly accessible American Scientist article
http://cowles.econ.yale.edu/~hes/pub/fixed%20point%20theorems.pdf
linked to from Scarf’s publication page, on this same topic.
Actually, while the algorithm is guaranteed to find a completely labeled subsimplex, such a subsimplex does not necessarily contain an exact fixed point. All we can claim is that it contains an approximate fixed point, i.e. a point x such that f(x) is close to x.
Note that Sperner’s Lemma cannot be recursively applied to a completely labeled subsimplex, because Sperner’s Lemma requires that a subdivision of the simplex to be “properly labled”, i.e. there are constraints on the labels of points on the boundary of the simplex, e.g. for a triangle, points along the (1,2) edge have to be labeled either 1 or 2. This is generally not satisfied by a completely labeled subsimplex.
The step from Sperner’s Lemma to existence of fixed point (Brouwer) is non-constructive: as we take finer and finer subdivisions of the entire simplex, the sequence of completely labeled subsimplexes might not converge, but it must contain a convergent subsequence (due to compactness).
I missed that. That’s really disappointing.
If the Scharf article caught your fancy, then you should check out some of Francis Su’s papers (http://www.math.hmc.edu/~su/papers.html). He applies combinatorial versions of fixed point theorems, such as Sperner’s lemma, to fair division problems. Also, his exposition is very clear and easy to read.
Thanks for the link, John. Su has some very interesting papers.
[...] from spheres to discs, Walt at Ars Mathematica gives us a post on the Brouwer Fixed-Point Theorem. He mentions Sperner’s Lemma, which gives [...]
the links provided are really interesting to bridge the gap between mathematics and economics especially the scarfs papers on FPT.
When fixed points vanish is Sperner’s Lemma realistic?