Fair division and the whining philosophers problem

In 2001 I moved into an apartment in Jerusalem with two friends, Naomi and Nir. The apartment had one larger bedroom and two equally-sized, smaller bedrooms. While Naomi and I were running around viewing apartments, Nir was having the time of his life in South America. Nevertheless, when he got back, he argued that he should get the larger room (and pay the same rent) because he did not have a say in choosing the apartment. Strangely enough, this outlandish argument somehow made sense at the time. Nir’s powers of persuasion did not go to waste; today he is a philosopher.

Last week the memories came rushing back when a new CMU grad student—who was attending the summer school on algorithmic economics—asked me for advice on dividing the rent between his housemates. Fortunately, now I know a bit more about fair division than I did in 2001. Here is what I told him.

There is a wonderful 1999 paper by Francis Edward Su, which presents fair division methods through Sperner’s lemma. Suppose for simplicity that there are three housemates: call them Naomi, Nir, and Ariel, and denote them by A, B, and C. We denote the price of room by , and assume that the prices are positive and the total rent is 1, so . Our goal is to divide the rent so that each person prefers a different room.

The space S of possible partitions of the rent can be represented as a triangle (or, if you want to be formal, a 2-simplex in ). Now, triangulate S, and assign ownership of each vertex to one of A, B, and C, in a way that each elementary triangle is an ABC triangle. See the figure below, which is copied from the paper.

Next, we ask the owner of each vertex to tell us which of the rooms he prefers at the prices that are represented by the vertex. In this way, we obtain a new labeling of the triangle by the labels 1, 2, and 3. If we assume that people always want a free room when one is offered to them, the labeling of the edges of the triangle is constrained (because the vertices there have a price of zero for at least one room), and in fact it looks like this:

A variant of Sperner’s lemma implies that for such a labeling, there must be an elementary 123 triangle, i.e., a “small” triangle whose vertices have different labels. But such a a triangle is nothing but three “similar” partitions of the rent in which different people choose different rooms! By choosing a sufficiently fine triangulation we can make these three vertices arbitrarily close, thereby obtaining an approximately envy-free allocation. In the limit (and under an additional mild assumption) we can obtain a completely envy-free allocation. These techniques easily generalize to the case of more than three housemates. By the way, the connection to Sperner also implies computational hardness; and in theory it’s possible to use the completely different techniques of Lipton et al. to obtain an approximately envy-free division.

Su actually went ahead and implemented his scheme as a component in his fair division calculator. It’s not much to look at, but keep in mind that it dates back to the era when Java applets were cool. One of the nicest things about the algorithm is that you just need to ask players queries of the following form: “under these prices, which room do you want?” The algorithm iteratively poses these questions to the housemates and uses the answers to refine its solution. Fair division theory has given rise to such amazingly practical and beautiful methods, and I can’t help but wonder whether a flashier fair division calculator (perhaps a smartphone app) would be used by hundreds of thousands.

(A video of Herve Moulin’s mini-course on fair division will soon be available here. For now you can check out his slides, or read a related survey that I wrote a few weeks ago for CACM.)

Advertisement