A Matching Mechanism for Provision of Housing to the Marginalized

According to the LA county COVID-19 website, project Roomkey is ”a collaborative effort by the State, County, and the Los Angeles Homeless Services Authority (LAHSA) to secure hotel and motel rooms for vulnerable people experiencing homelessness. It provides a way for people who don’t have a home to stay inside to prevent the spread of COVID-19” [12]. Eligible persons, where eligibility is determined on the basis of vulnerability to COVID-19 and a reference from a local homeless shelter or law enforcement office, are assigned temporary housing in the form of hotel and motel rooms.

The matching of eligible persons has been done by local homeless shelters that match the individuals to available hotel or motel rooms in their locality. Whether this is automated is unclear, but given the program’s failures, one would assume that the matching was NOT done by a central clearing house but rather arbitrarily without full knowledge of preferences and optimal matches.

Furthermore, the program was not clear on how individuals would be moved to permanent or transitional housing when it closes. To quote the website, ”while participants are staying at these hotels, on-site service providers are working with each client individually to develop an exit plan, with the goal of moving them to a situation that permanently resolves their homelessness. In cases where this isn’t feasible, LAHSA will use existing shelter capacity to move people into an interim housing environment or explore other options”[12]. The key part is ”on-site service providers are working with each client individually,” which implies that the matches are not automated and were made depending on whatever information was locally-available to the on-site service provider. The LA Times has highlighted some failures in the project, for example, the project was slammed for discriminating against the elderly and disabled because,” the agency deliberately excluded those who cannot handle their own basic activities, such as going to the toilet or getting out of bed”[20]. The project’s leadership cited a lack of personnel and funding as the reason it did not succeed[19]. So clearly, a cheap and automated option for matching individuals to housing options is required.

The project is now coming to an end after housing about 30% of the projected total. While the program has been reported as a failure, it allows one to imagine a real solution to homelessness in LA county and in fact, any metropolis. What the program showed is that there is room for a central matching mechanism that can help move persons from the streets into shelters and from shelters into permanent housing. What we will show below, is that this mechanism can be designed to be Pareto-optimal (assign every person their best possible option at the time of assignment), and strategy-proof (persons cannot do better by cheating in this mechanism). Given a lack of funding and personnel, we felt that an automated matching mechanism that is theoretically optimal would be a great solution.

Further analysis of project Roomkey reveals a rich structure that reinforces the need for a matching mechanism. We will give a detailed look at this structure in a later section, and only a summary here. Because of state and federal mandated lockdowns, hotels and motels found themselves with large volumes of vacant rooms, an oversupply of sorts. In the same communities as the oversupplied hotel and motel rooms are the many unhoused folks that, due to different circumstances, can not afford to access and pay for the vacant rooms but do demand shelter, more so in a pandemic with federal and state-mandated lockdowns. What we see here is an oversupply of a commodity/service, and an abundance of demand but the two sides are inaccessible to each other without the help of a third party like the local, state, or federal government. This third party is what we consider as the matching mechanism designer, something, we will argue, should have done better when matching unhoused folks to the vacant rooms. This text, therefore, intervenes at this point, to further highlight the structure of oversupply to handicapped demand, and calling for a simple but sophisticated matching mechanism that can navigate locality constraints that arose in the allocation of vacant rooms to unhoused persons.

This paper contributes to a well-established body of work on homelessness, matching markets applied towards social good and matching mechanisms specifically for housing assignment. Below we review a few key papers on the above-mentioned research topics.

While we highlight the need for a matching mechanism to mitigate homelessness in cities around the globe, there is a long history of scholars deploying matching or mechanism design towards efficient housing solutions. We will summarize some relevant and notable works here.

Theoretical scholars have been studying housing matching markets from as far back as 1974 when Shapley and Scarf put forth economic mechanism theory for the housing market with existing tenants and introduced the Gale Top Trading Cycles algorithm[16]. In 1979, Hylland and Zeckhauser set the foundation for a house allocation problem with new applicants, defining a housing market core[9]. Abdulkadiroglu and Sonmez extend the work to a model with new and existing tenants[1]. We direct the reader to [2] for a more comprehensive review of matching markets theory.

O’Flaherty goes beyond economic game theory to provide a full economic “theory of the housing market that includes homelessness and relates it to measurable phenomena”[13]. He later extends the work to answering “when and how operators of shelters should place homeless families in subsidized housing”[14] and also updates the economics of ”homelessness under a dynamic stochastic framework in continuous time”[15].

Sharam gives a comprehensive breakdown of how matching markets have been applied towards the provision of new subsidized multifamily housing for low-income families in Australia[18]. Sharam also illustrates ways in which the use of digital platforms for matching could help improve the optimality of matching in housing assistance[17]. To the best of our knowledge, [18] and [17] are the only texts that explore the use of a matching mechanism for the provision of low-income housing. Sharam, however, does not extend the work to marginalized groups and only considers the Australian effort whereas we look to create a mechanism that not only looks at low-income multifamilies but all unhoused persons.

Because of the overwhelmingly unstable labor and the housing market at the present, Hanratty’s work on the impact of local economic conditions on homelessness using Housing and Urban Development(HUD) data from 2007-2014[7] is also very relevant to our research. Mansur et al., which examines policies to reduce homelessness, will be useful for the future work in this research that concerns itself with policy recommendation[11].

Building from all this past work and the unique structure of the project Roomkey, we provide a matching mechanism for better interim and/or permanent housing assignments for unhoused individuals. This mechanism is derived from those explored in [16],[9], and [1]. We show that this mechanism is also Pareto-optimal and strategy-proof. We also present a clear picture of that unique structure underlying project Roomkey and invite scholars to pay attention to other areas where this structure presents itself, for example, the food industry.

The goal then is to design a mechanism that matches the $n$ persons to the $m$ housing options according the preference lists and priority ranking while considering that $n=m$, $n>m$, or $n<m$. Because we intend to implement this model with local policy makers, we have the additional goals of minimizing cost of implementation and personnel required.

With a model defined and a research goal specified, the next section details how this goal is attained using a simple matching algorithm.

Let us assume that $X$ is not Pareto-optimal. This means $X$ is dominated by another matching assignment $X^{\prime}$ in which at least one agent $j$ must have a better and different allocation $a$. But we know that $X$ assigns every agent their best available preference at the time of assignment. So if $j$ indeed has a better assignment in $X^{\prime}$, this would mean that an agent $i$ (who got the assignment $a$ in $X$) earlier in the priority queue also has a different assignment in $X^{\prime}$. Observe that agent $i$’s assignment is either worse in $X^{\prime}$ or must be an assignment that was awarded to another agent earlier in the priority queue in $X$. One can follow this cycle until at least one agent gets a worse off assignment in $X^{\prime}$. This presents a contradiction because now we see that either $j$ does better and another agent does worse in $X^{\prime}$ or $j$ themselves gets a different option that is not their best available option, in which case they would do worse in $X^{\prime}$. Therefore, it is impossible that $X^{\prime}$ dominates $X$. To illustrate this better, we provide a few examples below.

Given an agent set ${i,j,k}$, and housing options ${a,b,c}$. With a priority queue: $i-j-k$ and preference lists:

Our algorithm would assign housing options as follows, ${x_{i}=a,x_{j}=b,x_{k}=c}$. All three agents would get their best options and so any other algorithm must either produce the same assignment or at least one agent would be worse off.

if we altered the preference lists to:

Our algorithm would assign housing options as follows, ${x_{i}=a,x_{j}=c,x_{k}=b}$. Observe that in this case $j$ and $k$ do not get their best possible assignment but get the best available assignments. If another algorithm gave $j$ housing option $a$, then $i$ must get a different assignment and hence be worse off.

We ask the reader to try out different permutations of the preference lists and check to see that in each, no other assignment would dominate that produced by algorithm 1 given in this text.

For the case where, $m<n$ , the same algorithm is employed but this time the $n-m$ remaining agents in the priority queue simply maintain their existing housing options or, more harshly put, do not get a new housing option.

Consider an agent set ${i,j,k,l}$, and housing options ${a,b,c}$. With a priority queue: $i-j-k-l$ and preference lists:

Our algorithm would assign housing options as follows,
${x_{i}=a,x_{j}=b,x_{k}=c,x_{l}=None}$. Any algorithm that gives $l$ any of the options $a,b,c$ would leave another agent worse off, unless the number of housing options increased.

If we assume that the priority queue is out of the agents’ control and decided by a third party like a policy-making entity or shelter management according to some standard criteria like period of time spent waiting for a housing option, then it’s easy to see that agents can not cheat by misreporting their preferences. The only way an agents their best option is if this option is correctly placed in their preference order and is available when their assignment turn comes.

A quick example; let us assume we have three agents ${i,j,k}$ with that exact order in the priority queue,i.e; $i-j-k$. With housing options ${a,b,c}$, lets also assume their true preferences are as follows;

The algorithm would assign housing options as follows, ${x_{i}=c,x_{j}=b,x_{k}=a}$ (The reader can check for Pareto optimality). But if agent $j$ misreports their preferences as $j:a\succ b\succ c$, they would get $a$ when their best option $c$ was available. In fact, if $j$ alters their preference list in any way, they would get most likely miss out on getting their best option. We, therefore, can say this algorithm 1 is strategy-proof.

We will assume that the LAHSA has two local homeless service providers in different localities under the project Roomkey. Homeless service provider, $P$ has housing options, ${a,b,c}$ available. While homeless service provider, $Q$ has housing options, ${x,z}$. We additionally assume an eligible person $i$ seeking a housing option with the following preference list generated from their needs:

Under algorithm 2, we have two possible outcomes that depend on whether the LAHSA sends $i$ to $P$ or $Q$.

• •

  If $P$, then $i$ will most likely be assigned housing option $b$

• •

  And if $Q$, then $i$ probably gets their most preferred option $z$

Observe that because of locality, $i$ could be assigned to an option that does not best fit their needs. This means that there exists cases where algorithm 2 can be dominated by another algorithm that can guarantee a better housing option to $i$.

One such algorithm is algorithm 1 where we would have all the available housing options ${a,b,c,x,z}$ in one database. We would then assign $i$ their most preferred housing option $z$. Algorithm 1 clearly Pareto dominates algorithm 2 in this example. As a counter-example, one could ask, what if there was another person $j$ in the locality of $Q$ that also preferred $Z$? Assigning $z$ to $i$ would sure leave $j$ worse off. Let us set up this example and see why this is not a valid counter-example.

We will assume that the LAHSA has two homeless service providers in different localities under the project Roomkey. Homeless service provider, $P$ has housing options, ${a,b,c}$ available. While homeless service provider, $Q$ has housing options, ${x,z}$. We additionally assume two eligible persons $i\&j$ seeking housing with the following preference list generated from their needs:

Under algorithm 2, we assume that LAHSA sends both to the homeless service provider of their respective locality, that is, $i$ to $P$ and $j$ to $Q$, $j$ would then be assigned their most preferred option $z$ but $i$ would get $b$. However, if $i$ has higher priority, then we see that algorithm 2 would never properly honor that priority while algorithm 1 would rightfully assign $z$ to $i$ and $a$ to $j$ which are their best possible outcome given a descending priority ordering of $i-j$.

We will assume that the LAHSA has two homeless service providers in different localities under the project Roomkey. Homeless service provider, $P$ has housing options, ${a,b,c}$ available. While homeless service provider, $Q$ has housing options, ${x,z}$. We additionally assume two eligible persons $i\&j$ in the localities of $P\&Q$ respectively, seeking housing with the following preference list generated from their needs:

Under algorithm 2, If $j$ misreported their locality, they would have a shot at getting their most preferred option $a$, but if the priority queue of $i-j$ is followed, they would end up with $x$.

Observe that under algorithm 1, it would not matter if $j$ misreports or not, they would get option $x$ either way while $i$ will always get option $a$ (which would be their rightful assignments according to the priority queue).

This simple example shows us that, indeed, persons can improve their chances by misreporting their preferences and locality in algorithm 2, which could leave them worse off whereas algorithm 1 protects against such incidents.