Modelling and Improving Social Housing Markets

Abstract

Social housing corporations in the Netherlands have a limited ability to influence the social housing market through offering houses to households outside of the regular waiting-list system, but often do not use an algorithmic strategy for utilising this freedom well. There is thus an open question of whether there exist algorithmic approaches that offer useful strategies for improving social housing markets. To investigate this question, we introduce the Social Housing Market Problem, which integrates indifference, existing tenants, numerical preferences instead of ordinal ones, and a dynamic market, into the existing Housing Allocation problem. Here we distinguish between the constrained problem variant, where property chains and cycles are not allowed, and the unconstrained variant, where they are. We utilise an objective function that maximises the average numerical fit between all families in the market and their (lack of) houses. A variety of algorithms are adapted and developed for both problem variants; some of these serve as baselines meant to resemble current strategies; some are experimental; and others are of primarily mathematical interest. In particular, we develop an original and optimal algorithm for this problem which runs in exponential time. We compare our algorithms' performances on multiple problem types. The practical applicability of our research is limited by a number of design choices meant to simplify this complex real-world problem, but our results do suggest that some of our algorithmic approaches may indeed form the basis of better strategies for improving social housing markets. Finally, we suggest a number of improvements that may be made in future research to further develop our model and algorithms.