Sperner’s Lemma hits the popular press
Here’s an article that has been trending on the New York Times site. It’s about Sperner’s Lemma–and, amazingly, they get the technical details right! The article describes a pretty practical scheme for pairing n indivisible goods with n agents; it’s motivated by the example of matching roommates with rooms, each of which has different pros and cons that the roommates each value differently. There’s a nice discussion of the idea of fair division, a pretty thorough description of a paper by Francis Su, a shout-out to Turing’s Invisible Hand Blogger Emeritus Ariel Procaccia and his web site spliddit, a quote from Stephen Brams, an online rent division calculator, and a very nice interactive graphic of how Sperner’s Lemma works.
So, what do you all think? Do you buy it? And, have you ever used a formal fair-division algorithm to make a real-life decision?
For a slightly more technical exposition, see this blog post: https://agtb.wordpress.com/2012/08/15/fair-division-and-the-whining-philosophers-problem/.
I have a minor technical issue with the presentation, which doesn’t seem to bother anyone else. I wish the visualization would allow the reader to change the corner colors, to reflect preferences over free alternatives. As Ariel also discusses in the blog post linked above, Sperner’s Lemma does not apply to all allowed colorings, but a variant of it does. Can someone point me to a proof of this variant?
Page 12 of this pdf: http://scholarship.claremont.edu/cgi/viewcontent.cgi?article=1668&context=hmc_fac_pub.