How to Divide Your Rent Fairly
https://www.nytimes.com/2014/04/29/science/to-divide-the-rent-start-with-a-triangle.html
To start the year, seven of my friends and I moved into a house on Cook Street in College Town. A huge challenge the eight of us faced in doing so was to figure out which person was to get which room and for how much. After much arguing and little critical thinking, I went over to my computer and quickly Googled “how to divide rent.” The first link that popped up was a link to the “Divide Your Rent Fairly” calculator widget produced by the New York Times. I showed the rest of the group the widget and we all agreed to use it. As of now, we are two months into the school year and are all content with our rooms and our monthly rent for said rooms. Looking back, I wondered how the widget was able to select the rooms so that all of my housemates were happy. The calculator linked to the article above to explain.
In this New York Times article, Albert Sun discusses the work of Francis Su, which led him to developing the calculator widget. To begin, Albert describes a similar situation to mine in which he and two of his friends had to choose rooms and rent for their $3,000 per month Manhattan apartment. While researching a fair way for the three of them to split the apartment, he stumbled upon Francis Su’s paper “Rental Harmony: Sperner’s Lemma in Fair Division.” Su describes that the best way to choose rooms is based on a procedure in which everyone acts in their own self-interest. The best case scenario would result when at some given price for each room, every tenant would prefer a different room.
To reach this point, Su explains, you want to start with an equilateral simplex, or a grouping of connected triangles to some dimension where each is equilateral. The simplest simplex in this case will be an equilateral triangle made up of smaller ones. This is applied when there are three participants, as is the case for Albert and his roommates. The vertices of each triangle are nodes and the sides are edges. Each node is labelled so that every small triangle is made up of 3 different nodes:
Next, the sum of the “heights” of all nodes is set to the total rent due. A “height” is defined as the shortest distance from the given node to a side of the largest triangle. Thus, each “height” can then be defined as the price for a certain room. How the calculator works then is each participant (A,B or C) is randomly asked which room they would choose given 3 price values. Let’s say we randomly chose the following node C, i.e. asking person C his preference:
The left side, which is green, denotes room 1, the bottom red side denotes room 2 and the blue right side denotes room 3. For the $3,000 rent example, the widget will display room 1 costs $3,000* (1 height/5 height total) = $600, room 2 costs $3,000* (1 height/5 height total) = $600 and room 3 costs $3,000*(3 height/5 height total) = $1,800. Let’s also say then person C prefers room 2 and we therefore shade his node red. By following this algorithm for each node in the network, we can triangulate the prices at which each participant will prefer a different room, denoted by three different colors forming a triangle, for example:
With this triangulation, offering a price for each room that falls within this triangle should result in the three tenants choosing different rooms given consistent pricing. If the tenants cannot agree, the triangulation should become more exact as more triangles are added (making each one smaller) and thus make the heights/prices offered become more and more precise until an agreement is reached. This process of triangulation via Sperner’s Lemma is behind the NYT calculator widget that has helped many people, such as myself, divide their rent fairly.
This article connects to our class discussion in many ways. First, the triangles above made of smaller triangles can be viewed as an undirected network that satisfies the Strong Triadic Closure Property. Since all edges of the network form complete triangles, i.e. there are no two edges that share a node that do not also share an edge, STCP is satisfied. Next, the “height” values above can also be described as the diameters from the specified node to each side of the largest triangle. For example, from the specified node C above, the diameter from C to the right side of the triangle is C → A → B → C, equal to three. Though there are many paths from which you can get from node C to the right side of the triangle, this path is the shortest possible path and is thus the diameter.
Furthermore, the above article is particularly relevant to our discussion of market-clearing prices. The rent values at which each tenant will prefer a different room is, by definition, an example of market-clearing prices. Each seller (the room) is perfectly matched to a buyer (the tenant) in the preferred-seller graph. What makes this scenario different than the examples we solved in class that involved finding the MCPs is that there are no clear/quantified valuations provided by the buyers. In real life, it would be oversimplifying and arbitrary to place a numerical value you have on a certain room. What would a room receiving a valuation of 8 mean? Does it have a lot of room? Good view? Nice furniture? Big bed? Also, how can you compare one person’s inherent valuation to another? If two people both liked one room the best, how could you objectively say that one liked it better than the other? To avoid this oversimplification to numerical valuation, the Sperner’s Lemma procedure and, by extension, the calculator learn in real time the tenant’s preferences at different prices. Also, because the true valuations by the tenants are not known, the usual algorithm for finding MCPs cannot accurately apply. This may result in fluctuating prices when triangulating MCPs, while the algorithm we learnt in class only had the prices going up. Thus, Sperner’s Lemma/the New York Times “Divide your Rent Fairly” widget provide an realistic method for finding market-clearing prices. I highly recommend it to anyone who is facing a similar predicament.