I am running a betting pool amongst some members of the department for the upcoming World Cup. Now, I suppose that the normal thing to do would be to assign teams randomly amongst the participants sweepstakes style. But for an economist, this seems like a rather inefficient thing to do. What if one person really wants Brazil but draws Germany, and someone else really wants Germany but draws Brazil?

Fortunately, there is an entire literature on what is known as the “rental harmony problem.” In the rental harmony problem, there are a group of house mates who are renting a new house and they wish to work out who should have each room and what share of the rent each should pay. We want the outcome to satisfy a few properties:

• the outcome should be efficient
• no one should envy anyone else’s room/rent combination
• the sum of the rents should be equal to the total rent payable for the house
• the mechanism should be incentive compatible (i.e. no one should be manipulate the outcome by lying about their preferences)

Unfortunately, it is impossible to satisfy all four of these conditions at once (this can be demonstrated as an application of the Vickrey-Clarke-Groves mechanism; if we enforce strict budget balance no mechanism can be found). Therefore, we must relax one of the conditions, and the usual thing to do is to relax the last condition.

At this point, mathematicians and economists differ in their approach. Mathematicians tend to simply assume that people will tell the truth; this is the approach taken in this extremely elegant paper by Su [1]. Economists, on the other hand, tend to assume that people will lie if it is profitable, and attempt to minimize the damage caused by the lying; this is the approach taken in this paper by Abdulkadiroglu, Sonmez and Unver.

Therefore, for my World Cup betting pool I will be using the mechanism described in the Abdulkadiroglu et al paper. Each team (or group of teams) will be treated as a room in the house, and the total prize money available will be treated as the total rent for the house. Each participant will need to submit a vector of bids (one bid for each team or group of teams), and the algorithm will allocate teams and entry costs to the participants. In a follow up post I will outline the bids that were submitted and the outcome of the algorithm.

Additional notes for economists:

The Abdulkadiroglu et al mechanism has some really quite remarkable properties. Despite relaxing incentive compatibility the mechanism manages to achieve efficiency, envy-freeness and satisfy individual rationality with respect to both stated and true preferences in any equilibrium.

The implementation of the algorithm was surprisingly non-trivial. The difficulties centered around finding the full set of over demanded rooms. To do this, one first needs to find a minimal set of over demanded rooms, as in Demange, Gale and Sotomayer (1986, J Polit. Econ.). I was expecting to be able to find existing code to find the minimal set of over demanded rooms, but could not. Instead, I used some code designed to implement the Munkres algorithm (also known as the Hungarian algorithm) by Markus Buehren. This code will either find an allocation or return a (not necessarily minimal) over demanded set. Once the over demanded set is identified then we need to check for any minimal subsets. Once a minimal subset is found this subset is removed and the process is repeated until all minimal subsets have been found.

The upshot is that my code is unlikely to be optimal, but it does seem to work (unfortunately I only have three test cases where I know what the solution is, so I haven’t been able to test it thoroughly). If any one is interested in the code then shoot me an email.

[1] I have seen implementations of this paper floating around the internet a few times, advertising it as a good way to allocate rooms in a share house. Given the incentive compatibility problems, I am not convinced.