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: