The “House allocation problem” is a well known problem in algorithmic game theory. I first came across this particular problem during one of our uni classes by Mr Anjan Bandyopadhyay. The basic structure of the problem is: There are (n) number of people and each of them owns a house. Each of the individuals have a preference list about which house they want to own. The list goes from highest to the lowest preference. For example, ‘A<4,2,1,3> A:2’ denotes that person A wants house 4 and if A does not get house 4 then he wants house 2 and so on… A:2 denotes that currently A owns house 2. The aim is to design an algorithm so that the persons are allotted the best possible houses according to their preferences.
One of the possible solutions, when we ignore the fact that individuals own houses, is the Random Serial Dictatorship. This is a very simple solution to the problem. We first do an unbiased lottery that gives all the members in the game (persons) a priority value. The member with the highest priority chooses his preferred house then the member with the second highest priority chooses his preferred house from the remaining set of houses. This process continues until all the members have been allotted a house. An example case is provided below.
EXAMPLE OF RSD
Suppose that there are 4 members and 4 houses.
Members [A,B,C,D] and houses [1,2,3,4].
The preference list of the members are:
A<1,3,4,2>
B<3,4,2,1>
C<3,2,1,4>
D<2,3,4,1>
We perform a random lottery and we get a sorted list of members according to their priority.
(C,A,B,D)
Therefore, due to the priority, C gets to choose first. C chooses 3, then A chooses 1, then B chooses 4 as 3 was already taken by C and D gets 2.
RSD is a very simple procedure to allot houses. However, it is not the best solution especially when members own the houses. Suppose a member’s preference list is <3,2,1,4> and he owns house 1. For him, it will only be worthwhile to play this game if he can get house 3 or house 2.
Therefore, to make it worthwhile for all the members we need to make sure that they get a higher preferred house than the one they currently own OR at least keep their current house.
How do we accomplish such a task ? The solution is a modified “Top Trading Cycle”. As stated before, let us define the preference list and ownership of houses by M<H1,H2,…Hn> M:Hm where M denotes member, <H1,H2..Hn> denotes the list of houses and Hm denotes the m’th house that M owns.
We first note down the preference list of all the members and then we run the algorithm. It will be best if the explanation is given through an example.
Let there be 4 members. A,B,C and D. The preference list of each of the members are:
A<1,2,4,3> A:4
B<2,1,4,3> B:1
C<1,2,4,3> C:2
D<4,2,3,1> D:3
We first perform a lottery like we did in RSD. let us assume that we got (A,B,C,D) as the priority list. In this process the members point towards their highest preferred available house and the house then points to its owner. If such a case occurs where after the house points to its owner, the owner points back at the house, then that means that the owner wants the house as well as owns the house. Therefore, in such cases we allot the house to its owner & eliminate the house & the owner from our set and start the process again. The process stops when we achieve a cyclic graph structure where the last house points towards the first member. In our example set, given the choosing priority (A,B,C,D), there would be no exchange of houses. The best possible solution is that each of the members keep their respective houses. Before we see how it came to be, it will be best that I provide a decision diagram for occupying a house.
Now for our current example, in first iteration, A chooses 1, B chooses 2 but when it is C’s turn, 1 is taken, 2 is taken BUT C owns 2. Hence, C occupies 2. {C,2} is allotted and member C and house 2 is eliminated from our set. The remaining data-set becomes:
A<1,4,3> A:4
B<1,4,3> B:1
D<4,3,1> D:3
In this iteration, A chooses 1, according to the decision tree diagram B will get 1 as B owns 1. {B,1} is allotted and is eliminated from our set. The remaining set is:
A<4,3> A:4
D<4,3> D:3
Now you can tell just by looking that A will get 4 and D will get 3. Therefore, the final allocation we get from our process is {C,2} , {B,1} , {A,4} and {D,3} which is same as the ownership.
An example where an exchange of houses takes place can be demonstrated simply by changing the choosing priority of the members as (B,C,D,A). The rest of the elements remain same.
In the first iteration, B chooses 2, C chooses 1. If we draw a graph then we can see that a closed structure is formed where house 1 is pointing towards member B. This signifies that allocation is complete for them and hence, {B,2} and {C,1} is allotted and is eliminated. The job is not done yet as we have to allot D and A also.
D<4,3> D:3
A<4,3> A:4
D points towards 4 BUT A owns 4 and also wants it. Hence, A occupies 4 and D gets 3. The final allocation is {B,2} , {C,1} , {A,4} and {D,3}. We can see that this is a much better allocation than the previous one. Therefore, a drawback of this procedure is that the outcome obtained is dependent on the lottery (choosing priority), which is not ideal. Below is the visual representation of the allocation when priority is (B,C,D,A).
With this I conclude this post. I hope that you got an idea that how we can allocate houses to members. This process can be used in various areas where resource allocation is needed based on preference.
Note – You can see that we mostly need the lottery to get the process started, that is, to determine which member chooses the house first during the initialization of the process and during the time when we have completed a cyclic allotment. Take a look at ‘pic 1’. It is due to (B,C,D,A) that after allotment of {B,2} , {C,1} , member D gets the chance to choose the house. If the priority would have been (B,C,A,D) then member A would have gotten the chance. Apart from these two situations [Initialization & after completion of a cyclic graph] we don’t need the priority list generated from the lottery.
