Article: "Rental Harmony: Sperner's Lemma in Fair Division" in American Math Monthly
Article Link: http://www.math.hmc.edu/~su/papers.dir/rent.pdf
Article Summary
Rental Harmony: Sperner’s Lemma in Fair Division by Francis Edward Su addresses how to divide the rent for a house among several housemates, each of whom will have a different room with different features. He ultimately poses and answers the question: “is there always a way to partition the rent so that each person will prefer a different room?”
To address the issue of rental harmony, Su first introduces us to Sperner’s Lemma, which is:
Any Sperner-labeled triangulation of a n-simplex must contain an odd number of fully labeled elementary n-simplicies. In particular, there is at least one.
Su proves this lemma through induction on the n = 1 case of a segmented line, and then shows that this lemma also holds for a triangulated, Sperner-labeled n-simplex S using the labels 1 through (n+1). An n-simplex is a an n-dimensional tetrahedron. For n=2, the Sperner labeled simplex is a triangle, where all the main vertices have different labels, the labels of a vertex along any edge matches the label of one of the main vertices spanning that edge, and the labels in the interior of the triangle are arbitrary.
This result of this proof is essential because it is later used to show that if we consider the cake cutting problem there is a single solution for which each person will prefer a different piece of cake, assuming that each person is hungry and any piece that is preferred for a convergent sequence of cut-sets is preferred at the limiting cut-set. Thus, the solution set of all possible cuts can be represented by a Sperner labeled triangulation, and the elementary simplicies represent cut-sets for which player chooses a different piece.
With a few twists, the cake cutting solution can be generalized to form a solution for dividing rooms and rent. The problem is that rooms are indivisible, and the rental payments are attached to specific rooms, so the cake-cutting solutions cannot be directly applied. We will first ccreate a simplex that we can use to show there is one solution to the rental-division problem that leaves evyerone happy. First, suppose there are n housemates, and n rooms to assign, numbered 1,…,n. Let xi denote the price of the i -th room, and suppose the total rent is 1. Then x1+x2…+xn=1. From this we see that the set of all pricing schemes S foms an (n-1)-simplex in Rn. Now triangulate this simplex by barycentric subdivision of small mesh size. Label it with a fully labelled vertex labelling by the names of the housemates (the same scheme as suggested for cake-cutting). The name at each vertex will be considered the ""owner" of that vertex; recall that each vertex corresponds to some
pricing scheme for the rooms. Construct a new labelling from the old by asking the owner at each vertex in the triangulation: "If the rent were to be divided according to this pricing scheme, which room would you choose?"
The problem with this labeling is that it is not a Sperner labeling. One way to overcome this problem is to dualize the simplex S to form a new simplex S*. This new labeling is a Sperner-labeled simplex, so we can use our previous theorems to show that there is any envy-free way to divide the rooms. For an exensive treatment of dualization, refer to J. W. Vick, Homology Theory. Springer-Verlag, New York, 1994.
Connection to Real Analysis
This question is interesting because it provides a real-world application for Real Analysis. Edward Su’s article involves real analysis because it uses convergent sequences to show that there is indeed a fair division of rent and rooms so that no housemate feels slighted. It is also a problem that most people, particularly undergraduates have faced at some point in time. Since it is possible to divide a set of rooms and the corresponding rent in such a way that each tenant prefers a different room, then it is possible to divide the rent so that no one feels slighted by their roommates, which will surely prevent future conflict.
Broader Context
The issue of rental harmony falls under the larger field of fair-division problems. Some similar problems that fall under the field of fair division are the cake-cutting dilemma of fairly dividing a cake among n people, as well as the chore-division problem of dividing a set of undesirable tasks.
For more information on fair division, read Fair Division: from Cake-Cutting to Dispute Resolution by S. J. Brams and A. D. Taylor, or read Cake Cutting Algorithms: Be Fair If You Can, by J. M. Robertson and W. A. Webb.
