Introduction

Homelessness represents a long-standing social problem with considerable individual and collective costs. Homeless services coordinated at the community level (i.e, local homeless systems) have limited resources and therefore struggle to keep up with demand for housing assistance, and there is little evidence to support the efficiency of current decision making in the allocation of limited housing services as the allocation decisions themselves are understudied (Brown et al., 2018;Fowler et al., 2019b;Shinn et al., 2013). Advances in machine learning and AI techniques have made it possible to apply learning algorithms to generate possible solutions to social problems ranging from raising HIV awareness (Yadav et al., 2016) to wildlife conservation (Dilkina & Gomes, 2010). In this paper, we explore the feasibility of data-driven approaches to inform policies that guide homeless service delivery. Specifically, we ask the question of whether individual predictions of success for certain types of homeless services can be leveraged to reduce the rate of re-entry into the homeless system across the population of households seeking assistance.

Background on resource allocation for social services: Public systems that coordinate responses to social problems face unique challenges at the intersection of efficiency and fairness. Social services aim to address a wide array of homeless household needs through a host of services that range in time and intensity; providers continuously make decisions on whom to serve with what service or combination of services. Moreover, constant resource constraints limit the capacity to address widespread demand for assistance. The information available for decision-making is far from perfect given the imprecision of needs assessments, as well as poor understanding of what services work for whom (Gubits et al., 2018;Shinn et al., 2017). In the context of scarcity, providers make complex decisions under great uncertainty with small margins of error. Poor decisions that either under-or over-serve homeless households waste scarce resources and miss opportunities for meeting the needs of those not served at all.

In the algorithmic decision-making literature on social service provision, the typical approach is to prioritize decisions based on risk scores. For example, Chouldechova and colleagues consider risk assessment in the context of child maltreatment to decide on which calls to a child protection hotline should be investigated further (Chouldechova et al., 2018;Brown et al., 2019). These represent classic triage situations, and deal with the problem of which cases to select given a limited budget and a risk assessment. Another context of algorithmic decision-making concerns online resource allocation -when a resource becomes available, which of various agents waiting in a queue should be allocated that resource? The most relevant studies along these lines are those of Chan et al. (2017) and Azizi et al. (2018), who consider allocation policies specifically for homeless youth. Chan et al. (2017) focus on possible improvement over the current score-based allocation system with improved human-machine collaboration using AI Decision Aids. Azizi et al. (2018) take this thought further, formulating a dynamic allocation problem between arriving homeless youth and two types of housing resources (rapid rehousing and permanent supportive housing) and consider the issues involved in fair and efficient online allocation of youth to these resources.

The market and mechanism design literature features considerable research on assignment problems, school allocation, organ allocation, refugee matching, etc. (Kominers et al. (2017) provide an excellent introduction to market design). A key focus there has been on the preferences and incentives of the participants, as well as the level of control of the mechanism in allocation decisions. In traditional assignment problems, it is assumed that the principal, the agent who chooses the payoff structure, has full control over all allocation decisions (Kuhn, 1955); much of the literature on two-sided matching seeks stable matchings that respect pairwise preferences (Roth & Sotomayor, 1990); work on school choice considers student preferences and school priorities differently (Abdulkadiroglu et al., 2005); the kidney exchange literature seeks to maximize the number of matches of incompatible pairs (Roth et al., 2005;Dickerson et al., 2016).

One of the main benefits of our approach is the possibility of increasing efficiency by exploiting gains from heterogeneity in match quality between households and services. This issue has been explored infrequently in the market design literature, perhaps because of the historical focus on ordinal preferences rather than cardinal utilities (Anshelevich & Das, 2010;Anshelevich et al., 2013), which better aligns with systems where agents have considerable control in terms of accepting and rejecting their assignment or matching. However, consideration of cardinal utilities has come up recently in the context of compatible living donor kidney transplantation (Li et al., 2019) where one can take advantage of differences in match quality between the organ and the patient and in refugee matching (e.g. Delacrétaz, Kominers, & Teytelboym, 2016;Bansak, Ferwerda, Hainmueller, Dillon, Hangartner, Lawrence, & Weinstein, 2018;Ahani, Andersson, Martinello, Teytelboym, & Trapp, 2021) where one can optimize over utilities of matchings between refugees and resettlement venues.

Recent approaches to refugee matching, roughly contemporaneous with this research, are the closest point of comparison to our work (Ahani et al., 2021;Bansak et al., 2018). Ahani et al. (2021) use a combination of machine learning and integer programming to optimize employment outcomes for resettled refugees using historical data. Following Bansak et al. (2018), Ahani et al. (2021) take advantage of the randomness present in current refugee assignment to ensure that selection bias does not affect their modeling. Though we also use machine learning and integer programming on historical data, our setting offers a different challenge given that housing services in our data are not assigned to households at random. Therefore, our observational data, which is routinely collected as part of service provision, is confounded by caseworker decisions. This magnifies the importance of causal modeling. As opposed to the types of problems that Kleinberg et al. (2015) call "prediction policy problems", or for example using machine learning predictions of loan default to manage risk (Butaru et al., 2016), we need useful counterfactual estimates of the effects of different services in order to begin defining the resource allocation problem.

There has been significant recent progress in causal modeling from a machine learning perspective (Johansson, Shalit, & Sontag, 2016, e.g.). Bayesian counterfactual approaches offer particular promise for informing social services delivery (Hill, 2011), since Bayesian models can provide coherent probabilistic estimates of heterogeneous treatment effects, and thus, allow predictions of individual outcomes under counterfactual predictions (Chipman et al., 2007(Chipman et al., , 2010)). Therefore, we test a promising Bayesian model for this purpose. While our primary goal is to use it in the counterfactual prediction setting, we also compare it with other learning algorithms using standard machine learning metrics on the typical out-of-sample prediction task.

Ours is one of the first studies to consider using machine learning-based estimates of counterfactual outcome probabilities to estimate the value of, and thus inform, allocation decisions for social services, specifically interventions for homeless households. We present this work as a proof-of-concept, based on a real administrative dataset across the whole range of homeless populations in a metro area, to address the following question: By optimizing allocations based on predicted outcomes, how much could we potentially improve outcomes, and what would be the distributional effects of these improvements?

Problem setup: Local homeless systems coordinate community-wide services that address housing crises. In the United States, services range in intensity from time-limited nonresidential supports to ongoing rental assistance with intensive case management (United States Congress, 2009). Each service is capacity constrained, given the constant widespread demand for affordable housing. Thus, homeless providers allocate many households to many services that each vary in availability at any given time. Homeless services aim to stabilize households and reduce future demand for assistance.

National policies currently focus evaluation of homeless service delivery on whether households use additional homeless services within two years of entry into the system; counts are generated from administrative data that record entries and exists across homeless services (HUD, 2012). However, routine capacity constraints make it challenging to measure success, since those in need may not be able to receive services. Missing information impedes service improvements in most communities across the United States (Fowler et al., 2019b).

In this work, we take advantage of unique local administrative records that capture community-wide demand and receipt of homeless assistance across time. The data we use link homeless service records with requests for assistance through a regional homeless hotline. Operators at the central hotline field all requests for services, as well as make referrals to appropriate and available services. Households call back if they are in need of additional services, and a digital trail captures subsequent requests, regardless of eligibility or delivery of services. This extensive data collection exceeds federal requirements and allows for a comprehensive assessment of homeless services impossible for most communities.

We test several machine learning methods for predicting outcomes of matching households to different interventions, and choose to use BART (Bayesian Additive Regression Trees) because it is competitive in out-of-sample performance with other methods, allows for meaningful probability distributions over outcomes, and has been established as a powerful method for causal inference with observational and complex data (Hill, 2011). Using BART, we build and evaluate counterfactual models for whether a household would have reentered the homeless system within 2 years if they had been assigned to a different service, and solve a capacitated assignment problem in order to minimize the number of households re-entering the system within two years, subject to capacity constraints on each service.

Preview of results: Using administrative data on a weekly basis over the course of 166 weeks, we estimate counterfactual predictions of reentry into homeless services for each household within two years. Models appear well-calibrated; we predict (out-of-sample), in expectation, that 2855 (28.43%) households would re-enter the system, whereas 2765 (27.53%) actually re-entered. In the optimized assignment, we find the BART model predicts that only 2611 households would re-enter the system, a reduction of 244 households (5.57%) in expectation. Thus, there may be benefits achievable (by this re-entry metric) from improving the combined prediction-allocation mechanism. However, these benefits come with tradeoffs. The allocations are not Pareto-improving; 21 percent of households increase their probability of re-entry according to the predictions. We formulate and solve a constrained version of the allocation problem that guarantees no household increases the probability of re-entry by more than 5 percentage points in the new allocation. This leads to only a small change in the predicted number of re-entering households compared with the unconstrained optimization.

Implications: Our work serves as a proof of concept through a case study. We bring administrative data to bear on the question of how much AI techniques can improve social service provision, with full awareness that the precise results presented may depend on specific modeling choices, and the reliability of the counterfactual estimates. This work contributes to the emerging dialogue on social service delivery based on machine learning predictions. We emphasize the importance of considering fairness, ethics, and the longterm dynamics of systems that use these kinds of predictive models, while at the same time believing that engaging these questions with actual data and estimates can contribute to resolving the lack of evidence guiding current social service delivery.

Ethics and Fairness

Since we are considering a problem of allocating scarce, shared societal resources using algorithmic approaches, it is important to foreground the discussion of ethical issues and fairness concerns. The use of techniques from machine learning and artificial intelligence (and more broadly, algorithmic approaches) in different societal contexts increasingly raise concerns regarding fairness, accountability, and transparency (O'Neil, 2016, among others). Although they demonstrate potential for improvements in efficiency, fundamental questions exist as to whether data-driven allocations introduce or perpetuate systematic biases that contribute to inequities, and moreover, whether the inherent complexity of decision-making impedes timely detection and correction of these inequities. A number of recent studies justify these concerns, demonstrating racial disparities in credit lending, hotspot policing, and crime sentencing (Ensign et al., 2018;Pleiss et al., 2017;Corbett-Davies et al., 2017); each example shows that marginalized, underrepresented minorities disproportionately suffer from unfair algorithmic decisions. The unintended consequences require that we carefully consider how to design adequate protections against systematic misuses.

The European Union recently passed legislation in response to concerns about ethics, fairness, and privacy. The "General Data Protection Regulation" (GDPR) imposes restrictions on how individual data can be used for algorithmic decision making in ways that "significantly affect" users. The GDPR coincides with a broader argument for not just full transparency, but rather human interpretability regarding how decisions are derived from algorithmic approaches to ensure adequate assessment of fairness. However, requirements for human interpretability could also diminish the potential of AI to solve societal problems. Algorithmic approaches generate novel solutions that may not correspond to human intuition; requirements for full explainability of these complex processes limits the inherent value of applications to thorny social problems.

David Weinberger presents a compelling example related to autonomous vehicles in a Wired op-ed (Weinberger, 2018). If self-driving automobiles lowered the number of vehicular fatalities by 90%, would it really be worth losing that benefit because of the difficulty of explaining (or legal liabilities that may be associated with) the remaining crashes? Certainly, the answer partly depends on whether the remaining crashes disproportionately affect some portion of the population as well as other considerations. Weinberger goes on to argue that while the regulation of AI applied to social problems is critical, it can be achieved through existing processes for resolving policy issues (Weinberger, 2018). Governance provides formal and informal methods for establishing rules and norms applied to collective problems, which also include sustainable approaches for mutual accountability. According to Weinberger, the right approach towards AI regulation involves specification of appropriate optimization goals arrived through the social processes of policy-making that consider both efficiency and equity. However, with a few exceptions (Chouldechova et al., 2018, e.g.) there has not been much empirical investigation probing the tradeoffs that emerge when incorporating fairness considerations into algorithmic decisions, especially in the context of scarcity.

Background and Data

Homelessness represents a complex public health challenge for communities across the United States. Federal guidelines define homelessness as residence in unstable and nonpermanent accommodations. This includes shelters, places not meant for habitation (eg., cars, park, abandoned buildings), as well as being at imminent risk for eviction. Annual counts since 2007 estimate that more than 550,000 people experience homelessness on a single January night across the United States (Henry et al., 2018), while approximately 1.5 million people use homeless services at some point during each year (Henry et al., 2018). Families with children under 18 years of age comprise more than one-third of homeless households (Henry et al., 2018). Experiences of homelessness and associated turmoil carries life long implications, as well as significant social costs in lost productivity, compromised health, and compensatory social service expenditures (Khadduri et al., 2010;Culhane et al., 2011;Fowler et al., 2019a).

The homeless system represents the primary community-wide service response to housing crises. Funds allocated by Congress on an annual basis support the delivery of five types of homeless assistance. Service types vary in intensity, and relatedly, availability. The most intensive service -Permanent Supportive Housing -provides long-term rental assistance plus comprehensive case management to address barriers to stability, such as mental health and substance abuse treatment; it is reserved for the highest risk households and consumes the greatest amount of financial resources. Similarly to Permanent Supportive Housing, Transitional Housing also offers comprehensive case management but only up to 24 months in congregate settings. Rapid Rehousing allows up to 24 months of rental assistance without additional intensive case management. At the end of two years, households in Transitional Housing or Rapid Rehousing either move on their own or step-up to Permanent Supportive Housing, if available. Emergency Shelters offer immediate accommodations for those with no other place to go, and typically serve a large number of households for a brief period of time. Shelters are intended to stabilize households and divert high-risk families to the longer-term housing services. Finally, Homelessness Prevention provides households at imminent risk for homelessness with short-term and non-reoccurring assistance to mitigate housing crises. Local non-profit provider networks determine the delivery of day-to-day services within general structures determined by federal funding priorities. During the study period, providers offered services to eligible households on a first-come-first-served basis.

Despite substantial investments, homeless rates remain high in the United States (Fowler et al., 2019a). An enormous challenge is that of matching service types to need. While federal guidelines mandate that local agencies provide services based on risk assessments (United States Congress, 2009), existing tools fail to discern high and low risk households reliably and accurately (Brown et al., 2018;Shinn et al., 2013). Homeless service providers have limited evidence for adapting responses to observed and unobserved household characteristics (Fowler et al., 2019b). Moreover, there are no tools that assess the impact of service matches on overall system performance in reducing reentries.foot_0

Data Collection

Data for this work come from the homeless management information system (HMIS) of a major metropolitan area from 2007 through 2014. The HMIS records all housing services provided to individuals and families seeking federally funded homelessness assistance. Local service providers enter information on requests and receipt of services in real time through a web-based platform in accordance with federal mandates for collection of universal elements. A local non-profit organization contracted with the homeless system hosts the platform and provides support, including user training, technical assistance, and active quality control.

Records provide information on the characteristics and services delivered to households in contact with the homeless system. Household-level characteristics include an array of information on demographics, housing risk, and eligibility determinations. Services include entry and exit dates from the five federally defined types of homeless assistance: homelessness prevention, emergency shelter, rapid rehousing, transitional housing, and permanent supportive housing. In addition, the metropolitan area coordinates requests for assistance through a homeless hotline, and household-level data record information on every call, including dates and referral for services. Household identifiers allow linkages of information across time. Data sharing agreements with regional homeless systems allow access to deidentified records in accordance with the relevant Institutional Review Board, which made a non-human subjects determination. Regardless, all information was transferred, stored, and analyzed according to best practices in data security. This includes ethics training in research for all research team members.

Data Cleaning and Feature Selection

For this project, we extract data provided by 75 different homeless agencies and link participants across programs by a unique, anonymous identification number. We then aggregate data by household over time using a unique household identification number. This results in a dataset of households containing household characteristics available upon entry into the system, as well as information on all entries and exits from different homeless services. We exclude permanent supportive housing for the present study because the service was rarely used as an initial response for first time entries into the homeless system during the study period. The primary outcome (the label we are trying to predict) is reentry into the homeless system. Operationally, reentry is defined as requesting services within two years of exit from the system, regardless of whether services were actually received. We do this using hotline call records to determine whether a household requested additional housing assistance after the initial service. This ensures that we capture further need, and not just availability of services. When transitions between services (e.g. homeless shelter to rapid rehousing) occur on the same day, we assume that they represent a continuation of homeless services and do not count this as a reentry. We consider households to have exited from the system when the time between leaving one service and entering another exceeds one day. Our analyses include households who entered the homeless system after the start of 2007 and exited before the end of 2012 to provide a minimum two-year follow-up for all households. Since the data captures homeless services across time, it contains both time-invariant (e.g., race, gender, ethnicity) as well as time-variant (e.g., monthly income, age) features. We select values of time-variant features that are collected at the time of first entry into the homeless system and have adequate amounts of available data for use in modeling. Most of the variables we selected were categorical, and missing values are treated as a separate category in these cases. Table 1 shows a summary and examples of the features included. A more complete summary of the dataset is included in Table 8 in the Appendix.

Data Characteristics

The dataset includes records on 13940 households. The target variable, or label, is a binary indicator of whether households reentered the homeless system, defined as requesting and/or receiving homeless services within 2 years of initial exit. Of the 13940 households, 3987 (28.60%) reentered the homeless system within two years; among reentries, 2066 (51.82%) were placed in a subsequent service, while 1921 (48.18%) called the hotline to request services, but by the end of the two year period had not been placed in another service. Reasons for failing to receive additional services varied; most commonly, services were unavailable and clients were referred to other services (79.13%) or clients did not follow up on referrals (17.67%).

Table 2 shows the number of households initially assigned to each homeless service type, as well as the percentage of reentries within 2 years for each service. Models use a single feature vector, which consists of service assignment plus additional covariate data collected at first entry into the system.

Eligibility for Prevention

Based on conversations with our community partner, it became apparent that prevention services are not considered for many households due to their current housing circumstances.

If a household's prior residence is one of the following: psychiatric facility, detox center, hospital, jail or prison, hotel or motel, staying with a friend or family member, foster care or group home, rental by client, or owned by client or if their prior residence was unknown but they are not considered homeless by federal definitions, we consider that household to be eligible for prevention. Otherwise, they are deemed ineligible for prevention and prevention is not considered as a potential service for that household in our analyses. Of the 13940 households in our data, 10492 (75.27%) were eligible for prevention.

Analyzing Services

This application requires a method that can handle the challenges of counterfactual inference using observational data, while simultaneously providing a well-grounded probabilistic model. Bayesian Additive Regression Trees (BART), an ensemble model that outperforms propensity score and nearest neighbor matching algorithms for causal inference on observational data, especially when the data are complex (Hill, 2011), is a promising method for mitigating this challenge, (Chipman et al., 2007(Chipman et al., , 2010)). Bayesian nonparametric modeling for causal inference has a number of advantages that fit this application (Chipman et al., 2010;Hill, 2011;Johansson et al., 2016). Such models are capable of providing robust estimates of treatment effects using observational data like administrative service records. They can handle a large number of features or predictors, as well as complex data that include interactions and nonlinearities seen in prior studies of homeless service delivery (Shinn et al., 2013). In the following section, we compare the predictive performance of BART on our dataset to that of several other popular machine learning algorithms: random forests, logistic regression, LASSO, and gradient boosted trees.

Model Comparison

We compared the out-of-sample predictive performance of BART to four commonly used machine learning algorithms using 10-fold cross validation. First, we implemented BART using the default parameters provided by the model creators (Chipman et al., 2010). Then, we implemented simple logistic regression and LASSO using 10-fold cross validation to choose the value of lambda, the regularization parameter. We also implemented random forests with 500 trees, a minimum node size of 1, and considering 6 variables for each split (Breiman, 2001). Lastly, we implemented gradient boosted trees with 100 trees with a maximum depth of 1, 10 observations per node minimum, and a learning rate of 0.1. As we are comparing to BART using the default parameters, these hyperparameters were chosen because they are commonly used default parameters/implementations for each method. We assess predictive performance using multiple metrics: AUC (Area Under the ROC Curve), Misclassification Error, Precision, Recall, and Calibration which we operationalize as Expected Reentries/True Reentries. The results of this analysis are shown in Table 3. We also assess calibration individually for each service type operationalized in the same manner in Table 4. BART either outperforms or performs equally to each of the other methods and is well-calibrated across services. As stated previously, it also mitigates the issue of confounder bias that may be present in our observational data and allows for the estimation of household-specific treatment effects. For these reasons we conduct all further analyses in this paper using BART. All model fitting and counterfactual inference that follows is done using the R package BayesTree written by the model's creators (Chipman et al., 2010)

Counterfactual Estimation of Heterogeneity in Match Quality

Using BART, we built models to produce out-of-sample counterfactual estimates of reentry probabilities if households received each homeless service (i.e., prevention, rapid rehousing, shelter, transitional housing). 2 For those households that are ineligible for prevention, we did not consider prevention as a potential service. For most of the 10492 households eligible for prevention, homelessness prevention produced the lowest probability of reentering the system within two years (10030 households are predicted to do best in prevention). Three households were predicted to do best in emergency shelter, 323 in transitional housing, and 136 in rapid rehousing. Most of these households were predicted to have the highest probability of reentry if placed in emergency shelter (7126 households) with less predicted to do worst in transitional housing (1990 households), rapid rehousing (1374 households), and prevention (2 households).

For most of the 3448 households ineligible for prevention, transitional housing produced the lowest probability of reentering the system (2324 households). One-hundred-ninety-two households were predicted to do best in emergency shelter and 932 in rapid rehousing. Again, most of these households were predicted to have the highest probability of reentry if placed in emergency shelter (2119 households) with less predicted to do worst in transitional housing (476 households) and rapid rehousing (853 households). For each household, we determined which services are predicted to outperform others and developed a relative ordering of service effectiveness. Table 5 illustrates this ordering of service effectiveness. Summing across households, almost one-third (31.3%) do best in prevention followed by transitional housing, rapid rehousing, and shelter. Another 17.3% would benefit most in prevention, followed by rapid rehousing, transitional housing, and shelter. For a small proportion of households (11.2%), transitional housing followed by rapid rehousing, and shelter would be best as they are ineligible for prevention. These patterns demonstrate the heterogeneity in treatment effects we hope to leverage to improve the efficiency of allocations.

The probabilities estimated by BART allow us to perform an initial examination of the possibility of optimizing homeless service delivery. If all households were placed in the service in which they have the lowest predicted probability of reentry, we predict 25.00% of households would reenter in expectation. This is a 12.59 percent decrease from the 28.60% who actually reentered. However, it represents an oversimplification of the allocation problem, which in reality is subject to capacity constraints on the number of households that can be served by a particular service at any given time. In the following section, we formulate the optimal allocation problem including these service capacity constraints.

Optimal Allocation Using Estimated Personalized Treatment Effects

In order to frame the optimal allocation problem, we need two main sets of variables estimated from the data. First are the predictions of probability of reentry for households given they are placed in each of the possible services. For this, we use out-of-sample BART predictions. Second are the capacities of the different services mentioned in the previous section -that is, the number of households that can be accommodated at a given time due to space or monetary limitations. In order to estimate these, we aggregate data on a weekly basis, and set the capacity of a service equal to the number of households who truly entered into the service in that week. One week is granular enough to give some flexibility to the optimizer, while also not leading to waits that are outside the tolerance of the system. We note here that we solve the problem in a static manner every week, although there could, of course, be interesting dynamic matching issues at play (Akbarpour et al., 2020;Anshelevich et al., 2013).

The Optimization Problem

We solve an Integer Program for each week of data. Our objective is to minimize the expected number of reentries, ensuring that every household is assigned exactly one service and that no service is assigned more households than its estimated capacity as described above. Let x ij be a binary variable representing whether or not household i is placed in service j. Then, the Integer Programming problem is given by min

where p ij is the probability of household i reentering if they are placed in service j and C j is the capacity of service j.

We use this IP framework and Gurobi optimization software to find an optimal allocation for households who entered the system during each week.

In the following section, we show this can be re-formulated as a weighted bipartite b-matching problem, known to admit a polynomial time solution.

Reduction to Weighted Bipartite b-matching

Weighted Bipartite b-Matching is the following problem: Given a weighted bipartite graph G with positive, real-valued edge weights, find a subgraph H of G with maximum total weight such that every vertex i in H is incident to at most b i edges (Chen et al., 2016).

Given an instance of the current optimization problem, we create an instance of Weighted Bipartite b-Matching as follows. First, create a bipartite graph G such that there are four nodes representing the four services on the right and a single node representing each household on the left. Between each household node i and each service node j, create an edge and give that edge weight 1 -p ij . For each household node i, let the degree constraint b i of node i be 1. For each service node j, let the degree constraint b j of node j be C j . Then, the allocation of households to services that minimizes expected re-entries while respecting capacity constraints is given by a maximum weighted bipartite b-matching on graph G.

Claim: An optimal weighted bipartite b-matching solution of maximum weight on graph G gives an allocation of households to services that solves the current optimization problem.

Proof: Assume there exists an optimal weighted bipartite b-matching solution of maximum weight on graph G that does not give an allocation of households to services that minimizes expected re-entries while respecting capacity constraints.

We know that each household i is going to be matched to exactly one service j since each household node in G has capacity 1 and not fulfilling that capacity can only reduce the total weight of the solution. Similarly, each service j must be at capacity, since leaving any household unmatched would only result in a solution of smaller total weight. Therefore, if there is an improvement to be made to the optimal allocation of households to services, it must be due to swapping some pair of edges. Now, suppose household h is assigned to service k and h ′ to service k ′ . Suppose swapping them so that h were assigned to k ′ and h ′ to k would improve the re-entry minimization objective. Then it must be the case that

Therefore, swapping them would increase the total weight of the weighted bipartite bmatching solution.

This contradicts the assumption that our solution to the weighted bipartite b-matching problem was of maximum weight. Therefore, the allocation of households to services that minimizes expected re-entries while respecting capacity constraints must be given by a maximum weighted bipartite b-matching on graph G. ■

This shows that the solution to our optimization problem can be found in polynomial time. In practice, the optimization is extremely fast in Gurobi (0.03 seconds on average), and time requirements are dominated by running BART, therefore we use the IP formulation.

Optimization Results

Only households who entered the homeless system between October, 2009 (after initial implementation of the rapid rehousing service) through December, 2012 were included in the optimization. This results in tracking 10043 households across 166 separate weeks optimized. 3 For households ineligible for prevention, their predicted probability if placed in prevention is set to 1 so as to eliminate the possibility of the algorithm placing that housing in prevention.

Over the 166 weeks, 2765 out of 10043 households (27.53%) actually reentered the homeless system. Summing BART predictions to estimate how many households would reenter in expectation produces an estimate of 2855 households (28.43%), suggesting that the predicted reentry probabilities given by BART are reliable. Using these predicted probabilities to find an optimal allocation, predicted reentries reduce to 2611 households (26.00%). Thus, the optimal allocation framework reduces the predicted number of reentries into the homeless system by 5.57% over this period. Also recall that the best that could be achieved by assigning each household to its optimal service, without any capacity constraints, was a reentry rate of 25.00%, so our allocation gets us much closer to the best possible reentry rate for this formulation.

Fairness Considerations

An immediate question is whether the optimal allocation is capturing some inherent inefficiency in the allocation system, and is therefore Pareto-improving or at least improving allocations for a substantial portion of the population.

Figure 1 shows the distribution of changes in predicted probability of reentry based on our BART model in the optimal service versus predicted probability of reentry for the actual service allocation. In the optimal allocation, 3522 (35.07%) individual households are allocated to a service in which they have a lower probability of reentry than the service in which they actually participated (shown by the area of the histogram to the right of 0). Another 4388 (43.69%) are allocated to the same service they were originally assigned. Importantly, 2133 (21.24%) households are allocated to a service in which they have a higher probability of reentry (shown by the area of the histogram to the left of 0). Therefore, a substantial fraction of households are being hurt by the reassignment, even though more are being helped. Table 6 shows the average percentage point difference in probability of reentry for households moving from one service in the original allocation to a different service in the optimal allocation. The mainly positive non-zero off diagonals suggest potential improvements from optimization that range from small (e.g., rapid rehousing to shelter) to larger changes, especially reassignment to transitional housing. Although BART shows homelessness prevention homeless providers simultaneously shifted services to comply with federal requirements for coordinated entry into homeless services; the result, in effect, unpaired prevention from other homeless services. represents the best option for most households, the percentage point gains are relatively modest; those who are moved out of prevention typically have worse outcomes.

Figure 2 shows the mechanism of improvement, given capacity constraints. It maps the changes in allocation between the different services in the optimal allocation, as compared with the original. Figure 2a shows the number of households who moved from each service to another in the optimal allocation and Figure 2b shows the net flows of households moving between services. It is clear that the main mechanisms of improvement are flows where a significant number of households are being placed in transitional housing rather than rapid rehousing and in prevention rather than transitional housing; in order to make room for these, households move from prevention to shelters. This flow indicates a potentially complex mechanism for improving outcomes, since it is not simply a two-way swap between services.

We explore further who benefits in optimization to assess potential inequities. We build random forest models using the default hyperparameter values listed for the classification problem of predicting whether a household has a higher or lower probability of reentry after optimal allocation. We chose random forests due to the ease of producing measures of variable importance from a random forest model. The models have access to the entire original set of features, but ignore service type. The relative importance of each feature for prediction (calculated using the mean decrease in accuracy of features -a standard permutation test used in random forest feature importance) provides insights into the key characteristics that differentiate those who improve or worsen their reentry probability. The out-of-bag error for the random model was 0.09 and the AUC was 0.97. Figure 3 plots the 30 most influential variables. Some of the most important features are prior residence, housing status at entry, and the number of hotline calls prior to entry.

Figure 3: Plot of the mean decrease in accuracy of features for predicting whether the optimal allocation will increase or decrease a household's probability of reentry Perhaps the most striking discovery to emerge from the analysis is that the optimal allocation seems to help those who stand out as being more in need. Households benefited most by reallocation disproportionately are homeless upon entry and make frequent calls to the hotline for help; they also are more likely to reside in non-federally funded homeless ser-vices (primarily provided through local religious organizations), substance abuse treatment facilities, or with family. Moreover, reallocation benefits households more likely to report a disability who wait longer for entry into services. Households harmed by optimization, on the other hand, are more likely to be at risk or at imminent risk upon entry, first time hotline callers with briefer waits for services, and in their own or rental units; household heads also are somewhat older and more likely to have children. The no change group also experience stable housing in their own units upon entry. Table 7 summarizes comparisons of household characteristics by reallocation outcomes. All differences in continuous variables between the group who improved versus harmed were tested using a Student's t-test and have p-valus at or below 3.21e-14. Table 7: Summary statistics for the most influential features for determining which households will benefit from the optimal allocation (due to the large number of prior residence categories, those making up less than 5% of the population were omitted from the table ) Overall, these results suggest an ability to improve upon the allocation rules used by the homeless system. To note, although more than one optimal solutions could exist, we find evidence only for a single solution across runs. Interestingly, the efficiency gains are achieved primarily through "shuffling" households between emergency shelters (which is a uniformly poor service), prevention (which may be appropriate for more vulnerable households than previously believed), and transitional housing (an intense and expensive service with higher efficacy). There is clearly some household-level heterogeneity that could potentially be exploited to achieve gains.

Constraining Increased Probability of Reentry

Another important dimension of fairness raised in algorithmic decision-making pertains to the local costs of redistributing resources. Inefficiencies in the original allocation may be because decision-makers are prioritizing equity by assigning more vulnerable households to more intensive services (whether the measurement of vulnerability corresponds to the actual notion we care about is a separate question) (Fowler et al., 2019a). Of course, this idea may be flawed in that some of these "more vulnerable" households may actually be equally well-served by less intensive services.

One way to potentially deal with fairness concerns like these is to make them explicit in the optimization. As an example, we consider what happens if we add a constraint that prevents any household from suffering too high a predicted cost, in terms of predicted increases in probability of reentry, from the change in allocation. For example:

where each y ij is a binary variable representing whether or not household i was originally placed in service j. And δ is a constraint which keeps households from being allocated to a service in which their predicted probability of reentry is more than δ percentage points higher than that of the service they participated in originally.

To illustrate the results of the allocation when this constraint is added, Figure 4 shows the distribution of changes in the the new allocation when δ is set to 5 points. The hard prevents any negative changes of greater than 5 percentage points. When we include this constraint, the solution to the optimization problem yields an allocation with a predicted 2644 households (26.25%) reentering the system within two years. This is just a bit higher than the optimized allocation without the constraint, but still a 4.36% decrease compared to the predicted reentry number for the original allocation. Looking again at individual households, 2619 (26.08%) are allocated into a service that lowers probability of reentry, 5746 (57.21%) are allocated into the original assignment, and 1678 (16.71%) are allocated into a service that increases probability of reentry. The majority of households who do worse suffer very small penalties.

We empirically investigate the influence of imposing more and less restrictive fairness constraints on reentry rates. Figure 5 shows the percentage reduction in expected reentries as a function of δ (how much each household's predicted reentry probability is allowed to increase in the optimal allocation). That is, how much predicted cost households are allowed to incur from the change in allocation. An interesting result from this investigation is that, even when the constraint is set to 0.01 and barely allows any household's predicted reentry probability to increase, we achieve a modest reduction in expected reentries. Therefore, we can produce gains in efficiency even in the presence of strict fairness constraints.

Discussion

Our work tests the feasibility of using data-driven counterfactual approaches to inform policies that guide homeless service provision. We analyze the potential for different allocation mechanisms to improve outcomes using counterfactual estimates of probability of reentry into the system. Our results suggest that optimal weekly assignments reduces system reentries. However, optimization of system-wide service delivery withholds useful services for one-third of households. Although the average harm to households is small in comparison to the benefits for other households, the results emphasize that optimal reallocation of services fails to improve the outcomes of all households in the homeless system. Assuming the original allocation to be fair, models explore the imposition of an approximate fairness con- straint that avoid households from being reallocated to services that worsen the probability of reentry into the system compared to the original allocation. Results show smaller but meaningful reductions in reentries into the homeless system using fair data-driven allocations of services.

Our findings demonstrate the critical importance fairness and justice considerations in the design of algorithmic allocations of homeless services delivery. The assumptions, implications, and potential unintended consequences must be thoroughly analyzed and addressed before implementing data-driven decision-making. One potential solution allows workers to override certain allocation decisions. The idea has previously been adopted as part of a homelessness prevention screening instrument used in New York City (Shinn et al., 2013). Shinn and colleagues note that analysis of the reasons behind these overrides can help to inform future models of this type. The addition of potential override reasons to an allocation model could help to increase fairness and inform re-calibrations of models. It also makes the transition to an allocation program smoother by allowing homeless service workers to maintain control over allocations.

The results presented here must be considered in the context of limitations of this kind of study. It is difficult to rule out all potential confounds for treatment estimates. Our models leverage all available data from homeless services for predictions, and extensive sensitivity analyses provide some confidence in the results. However, the observational nature of the Figure 5: Graph showing percent decrease in expected number of reentries as a function of constraint on how much a household's predicted reentry probability is allowed increase in the optimal allocation data constrains modeling for variables we were not aware of or to which we did not have access. If the estimated treatment effects are biased, this would inherently worsen efficiency gains by introducing unreliability.

Another key limitation concerns the potential for unobserved inequities in homeless service delivery. Administrative records only collect information on services provided; models remain vulnerable to service decisions that intentionally (i.e., explicit bias) or unintentionally (i.e., implicit bias) disadvantage specific groups. As illustrated in prior applications, algorithmic decision making risks perpetuating systematic inequalities captured in the data (Ensign et al., 2018;Pleiss et al., 2017;Corbett-Davies et al., 2017). Surprisingly, initial tests in the present study suggest optimal allocation disproportionately advantages more vulnerable households. The unexpected findings potentially reveal counterproductive assumptions guiding service delivery. Currently, homeless policies prioritize scarce intensive services for more vulnerable households, whereas the data-driven allocation maximizes timely receipt of preventive services for first time entries into the homeless system (United States Congress, 2009). These findings are consistent with a growing body of evidence on community-wide benefits of homelessness prevention (Fowler et al., 2019b). Insights from the present study introduce new avenues for future work that informs data-driven homeless service delivery. Further investigation into heterogeneous effects of different homeless services offers opportunities to ask key policy questions of what works for whom. This is especially true for prevention services that unexpectedly show promise at first time entry. In addition, deeper investigation into winners and losers of data-driven allocation needs to test for potential disparities. Fairness considerations must extend to assess whether specific groups are being disproportionately reassigned to certain services (e.g. shelter versus prevention). Answering questions like this would help us learn how to decrease the number of households harmed by this type of service allocation.

In sum, our study demonstrates both the potential of, and the need for caution in, datadriven homeless service delivery. Although machine learning improves efficiency, fairness considerations arise that require careful implementation in practice. Data-driven insights also raise questions regarding policies that underlie service delivery -fitting an algorithmsin-the-loop process (Green & Chen, 2019). This study opens new lines of inquiry for designing and testing computational approaches that promote social good.