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.)

on August 15, 2012 at 11:49 pm |Vincent ConitzerNice. This is also a good motivating example for the design of auctions that redistribute their revenue to the bidders: you want efficient allocation but not to give the landlord/landlady much more money. (In our first year of graduate school, three of us were also in such a situation and decided to auction off the nicest room, with bids in terms of rent and the revenue being applied to reduce the rent of the others. The mechanism not being strategy-proof, two of us ended up bidding each other up well past our valuations, to make the other pay more…)

on August 16, 2012 at 12:53 am |zaumkaAriel, this is probably basic and well known, but what do you do when there are many such 123 triangles? I understand each of them is envy-free, but, clearly, GIVEN THE CHOICE, different people would prefer different triangles. I know this is related to how you choose Nash Eq. when there are multiple, but maybe here there is a way to get the “best” partition?

Related, if a person somehow knows the labeling of the other (say, two) people, it is clear he cannot “game” the system?

Yevgeniy

on August 16, 2012 at 3:21 am |Ariel ProcacciaI have two partial answers to the first question (perhaps together they give a full answer). On a technical level, the algorithm uses a constructive proof of Sperner’s lemma that simply traverses the graph in a way that provably reaches a 123 triangle. I think the first such triangle that is encountered is the one that is selected. On a conceptual level, the equilibrium selection problem is an issue when you are trying to predict how people will behave (assuming that they actually play an equilibrium). In contrast, here we are simply trying to output one solution with desirable properties. That said, it may be the case that some solutions are “better” than others, and the literature indeed considers additional properties (e.g., Pareto efficiency) and asks whether they can be achieved together with envy-freeness.

Regarding the second question, you are right about the algorithm not being strategyproof. In fact, it is quite difficult to obtain strategyproofness in this domain. I discuss this in a bit more detail in Section 3 of the survey that I mentioned.

on August 20, 2012 at 1:58 pm |Tayfun SonmezAtila Abdulkadiroglu, Utku Unver and myself also have a paper on this question which explores it from a market design perspective (although envy freeness is a big part of the paper). The paper is available here:

http://econpapers.repec.org/paper/wpawuwpga/0202003.htm

It is absolutely correct that strategy-proofness along with envy-freeness in this domain is a no go.

on August 20, 2012 at 11:22 pm |Ariel ProcacciaGreat paper!

on August 20, 2012 at 11:42 pmTayfun SonmezThanks Ariel,

It is very exciting to see that economists and computer scientists are finding so many common areas of interests these days.