Aida Rahmattalabi
ABSTRACT
We study the problem of learning, from observational data, fair and interpretable policies that effectively match heterogeneous individuals to scarce resources of different types. We model this problem as a multi-class multi-server queuing system where both individuals and resources arrive stochastically over time. Each individual, upon arrival, is assigned to a queue where they wait to be matched to a resource. The resources are assigned in a first come first served (FCFS) fashion according to an eligibility structure that encodes the resource types that serve each queue. We propose a methodology based on techniques in modern causal inference to construct the individual queues as well as learn the matching outcomes and provide a mixed-integer optimization (MIO) formulation to optimize the eligibility structure. The MIO problem maximizes policy outcome subject to wait time and fairness constraints. It is very flexible, allowing for additional linear domain constraints. We conduct extensive analyses using synthetic and real-world data. In particular, we evaluate our framework using data from the U.S. Homeless Management Information System (HMIS). We obtain wait times as low as an FCFS policy while improving the rate of exit from homelessness for underserved or vulnerable groups (7% higher for the Black individuals and 15% higher for those below 17 years old) and overall.
- Ivo Adan and Gideon Weiss. 2014. A skill based parallel service system under FCFS-ALIS — steady state, overloads, and abandonments. Stochastic Systems 4, 1 (2014), 250–299. https://doi.org/10.1214/13-ssy117Google Scholar
Cross Ref
- Philipp Afèche, René Caldentey, and Varun Gupta. 2021. On the Optimal Design of a Bipartite Matching Queueing System. Operations Research (2021). https://doi.org/10.1287/opre.2020.2027Google ScholarCross Ref
- Nick Arnosti and Peng Shi. 2019. How (Not) to Allocate Affordable Housing. AEA Papers and Proceedings 109 (2019). https://doi.org/10.1257/pandp.20191031Google ScholarCross Ref
- Nick Arnosti and Peng Shi. 2020. Design of Lotteries and Wait-Lists for Affordable Housing Allocation. Management Science 66, 6 (2020). https://doi.org/10.1287/mnsc.2019.3311Google ScholarDigital Library
- Bariş Ata and Mustafa H. Tongarlak. 2013. On scheduling a multiclass queue with abandonments under general delay costs. Queueing Systems 74, 1 (2013), 65–104. https://doi.org/10.1007/s11134-012-9326-6Google ScholarDigital Library
- Mohammad Javad Azizi, Phebe Vayanos, Bryan Wilder, Eric Rice, and Milind Tambe. 2018. Designing fair, efficient, and interpretable policies for prioritizing homeless youth for housing resources. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10848 LNCS. Springer, Cham, Delft, The Netherlands, 35–51. https://doi.org/10.1007/978-3-319-93031-2_3Google ScholarDigital Library
- Chaithanya Bandi, Nikolaos Trichakis, and Phebe Vayanos. 2019. Robust multiclass queuing theory for wait time estimation in resource allocation systems. Management Science 65, 1 (2019), 152–187. https://doi.org/10.1287/mnsc.2017.2948Google ScholarDigital Library
- Dimitris Bertsimas, Jack Dunn, and Nishanth Mundru. 2019. Optimal Prescriptive Trees. INFORMS Journal on Optimization 1, 2 (2019), 164–183. https://doi.org/10.1287/ijoo.2018.0005Google ScholarCross Ref
- Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. 2013. Fairness, efficiency, and flexibility in organ allocation for kidney transplantation. Operations Research 61, 1 (2013), 73–87. https://doi.org/10.1287/opre.1120.1138Google ScholarDigital Library
- Francisco Castro, Hamid Nazerzadeh, and Chiwei Yan. 2020. Matching queues with reneging: a product form solution. Queueing Systems 96, 3-4 (2020), 359–385. https://doi.org/10.1007/s11134-020-09662-yGoogle ScholarDigital Library
- Hau Chan, Eric Rice, Phebe Vayanos, Milind Tambe, and Matthew Morton. 2017. Evidence from the past: AI decision AIDS to improve housing systems for homeless youth. In AAAI Fall Symposium - Technical Report, Vol. FS-17-01 - FS-17-05. AAAI Press, Stanford University, United States.Google Scholar
- Alexandra Chouldechova. 2017. Fair Prediction with Disparate Impact: A Study of Bias in Recidivism Prediction Instruments. Big Data 5, 2 (2017), 153–163. https://doi.org/10.1089/big.2016.0047Google ScholarCross Ref
- Department of Housing and Urban Development. 2021. Restoring Affirmatively Furthering Fair Housing Definitions and Certifications. Technical Report. Office of Fair Housing and Equal Opportunity, HUD.Google Scholar
- John P. Dickerson and Tuomas Sandholm. 2015. FutureMatch: Combining human value judgments and machine learning to match in dynamic environments. In Proceedings of the National Conference on Artificial Intelligence, Vol. 1. AAAI press, Austin, Texas, United States, 622–628.Google Scholar
- Yichuan Ding, S. Thomas McCormick, and Mahesh Nagarajan. 2021. A fluid model for one-sided bipartite matching queues with match-dependent rewards. Operations Research 69, 4 (2021). https://doi.org/10.1287/opre.2020.2015Google ScholarDigital Library
- Miroslav Dudik, John Langford, and Hong Li. 2011. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011. Omnipress 2600 Anderson St Madison WI United States, Bellevue Washington USA, 1097–1104.Google Scholar
- Mohammad M. Fazel-Zarandi and Edward H. Kaplan. 2018. Approximating the first-come, first-served stochastic matching model with Ohm’s law. Operations Research 66, 5 (2018), 1423–1432. https://doi.org/10.1287/opre.2018.1737Google ScholarDigital Library
- Vincent A. Fusaro, Helen G. Levy, and H. Luke Shaefer. 2018. Racial and Ethnic Disparities in the Lifetime Prevalence of Homelessness in the United States. Demography 55, 6 (2018), 2119–2128. https://doi.org/10.1007/s13524-018-0717-0Google ScholarCross Ref
- Steven N. Goodman, Sharad Goel, and Mark R. Cullen. 2018. Machine learning, health disparities, and causal reasoning. https://doi.org/10.7326/M18-3297Google ScholarCross Ref
- Meghan Henry, Tanya de Sousa, Caroline Roddey, Swati Gayen, Thomas Joe Bednar, and Abt Associates. 2020. AHAR: Part 1—PIT Estimates of Homelessness in the US HUD Exchange. Technical Report. The U.S. Department of Housing and Urban Development, Office of Community Planning and Development.Google Scholar
- Miguel a Hernán and James M Robins. 2013. Causal Inference Book. Http://Www.Hsph.Harvard.Edu/Miguel-Hernan/Causal-Inference-Book/(2013).Google Scholar
- C Hill, H Hsu, M Holguin, M Morton, H Winetrobe, and E Rice. 2021. An examination of housing interventions among youth experiencing homelessness: an investigation into racial/ethnic and sexual minority status. Journal of Public Health(2021). https://doi.org/10.1093/pubmed/fdab295Google ScholarCross Ref
- Nathanael Jo, Sina Aghaei, Andres Gomez, and Phebe Vayanos. 2021. Learning Optimal Prescriptive Trees from Observational Data. (2021).Google Scholar
- Edward Harris Kaplan. 1984. Managing the Demand for Public Housing. Ph.D. Dissertation. MIT.Google Scholar
- Moniba Keymanesh, Tanya Berger-Wolf, Micha Elsner, and Srinivasan Parthasarathy. 2021. Fairness-aware Summarization for Justified Decision-Making.Google Scholar
- Shakeer Khan and Elie Tamer. 2010. Irregular Identification, Support Conditions, and Inverse Weight Estimation. Econometrica 78, 6 (2010), 2021–2042. https://doi.org/10.3982/ecta7372Google ScholarCross Ref
- Amanda Kube, Sanmay Das, and Patrick J. Fowler. 2019. Allocating interventions based on predicted outcomes: A case study on homelessness services. In 33rd AAAI Conference on Artificial Intelligence, AAAI 2019, 31st Innovative Applications of Artificial Intelligence Conference, IAAI 2019 and the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019. AAAI Press, Honolulu, Hawaii, United States, 622–629. https://doi.org/10.1609/aaai.v33i01.3301622Google ScholarDigital Library
- Avishai Mandelbaum and Alexander L. Stolyar. 2004. Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cμ-rule. Operations Research 52, 6 (2004), 836–855. https://doi.org/10.1287/opre.1040.0152Google ScholarDigital Library
- Norweeta Milburn, Earl Edwards, Dean Obermark, and Janey Rountree. 2021. Inequity in the Permanent Supportive Housing System in Los Angeles: Scale, Scope and Reasons for Black Residents’ Returns to Homelessness. Technical Report. California Policy Lab.Google Scholar
- John Monahan and Jennifer L. Skeem. 2016. Risk Assessment in Criminal Sentencing. Annual Review of Clinical Psychology 12 (2016). https://doi.org/10.1146/annurev-clinpsy-021815-092945Google ScholarCross Ref
- Matthew H. Morton, Amy Dworsky, Jennifer L. Matjasko, Susanna R. Curry, David Schlueter, Raúl Chávez, and Anne F. Farrell. 2018. Prevalence and Correlates of Youth Homelessness in the United States. Journal of Adolescent Health 62, 1 (2018). https://doi.org/10.1016/j.jadohealth.2017.10.006Google ScholarCross Ref
- Quan Nguyen, Sanmay Das, and Roman Garnett. 2021. Scarce Societal Resource Allocation and the Price of (Local) Justice. In Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press, Virtual Conference, 5628–5636.Google ScholarCross Ref
- U.S. Dept. of Housing, Office of Policy Development Urban Development, and Research. 2007. The applicability of housing first models to homeless persons with serious mental illness: Final report. Technical Report. OFFICE OF POLICY DEVELOPMENT AND RESEARCH (PD&R).Google Scholar
- Orgcode. 2015. Transition Age Youth – Vulnerability Index – Service Prioritization Decision Assistance Tool (TAY-VI-SPDAT): Next Step Tool for Homeless Youth. Technical Report. http://ctagroup.org/wp-content/uploads/2015/10/Y-SPDAT-v1.0-Youth-Print.pdf.Google Scholar
- OrgCode. 2020. The Time Seems Right: Let’s Begin the End of the VI-SPDAT.Google Scholar
- Aida Rahmattalabi, Shahin Jabbari, Himabindu Lakkaraju, Phebe Vayanos, Max Izenberg, Ryan Brown, Eric Rice, and Milind Tambe. 2021. Fair Influence Maximization: A Welfare Optimization Approach. In Proceedings of 35th AAAI Conference on Artificial Intelligence. AAAI Press, New York, United States, 11630–11638.Google ScholarCross Ref
- Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. 2019. Exploring algorithmic fairness in robust graph covering problems. In Advances in Neural Information Processing Systems, Vol. 32. MIT Press, Vancouver, Canada, 15776–15787.Google Scholar
- John Rawls. 1999. Theory of justice. Revised Edition.Google Scholar
- Eric Rice. 2017. Assessment Tools for Prioritizing Housing Resources for Homeless Youth.Google Scholar
- Eric Rice, Monique Holguin, Hsun-Ta Hsu, Matthew Morton, Phebe Vayanos, Milind Tambe, and Hau Chan. 2018. Linking Homelessness Vulnerability Assessments to Housing Placements and Outcomes for Youth. CITYSCAPE 20, 3 (2018), 69–86.Google Scholar
- Lisa Rice and Deidre Swesnik. 2012. Discriminatory effects of credit scoring on communities of color.Google Scholar
- Donald B Rubin. 2005. Causal Inference Using Potential Outcomes. J. Amer. Statist. Assoc. 100, 469 (2005), 322–331. https://doi.org/10.1198/016214504000001880Google ScholarCross Ref
- Tom Simonite. 2020. Meet the secret algorithm that’s keeping students out of college.Google Scholar
- United States Interagency Council on Homelessness. 2015. Opening doors: Federal strategic plan to prevent and end homelessness. Technical Report. US Interagency Council on Homelessness.Google Scholar
- Stefan Wager and Susan Athey. 2018. Estimation and Inference of Heterogeneous Treatment Effects using Random Forests. J. Amer. Statist. Assoc. 113, 523 (2018), 1228–1242. https://doi.org/10.1080/01621459.2017.1319839Google ScholarCross Ref
Index Terms
- Learning Resource Allocation Policies from Observational Data with an Application to Homeless Services Delivery
Index terms have been assigned to the content through auto-classification.
Recommendations
A resource-allocation queueing fairness measure
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systemsFairness is a major issue in the operation of queues, perhaps it is the reason why queues were formed in the first place. Recent studies show that the fairness of a queueing system is important to customers not less than the actual delay they ...
A resource-allocation queueing fairness measure
Fairness is a major issue in the operation of queues, perhaps it is the reason why queues were formed in the first place. Recent studies show that the fairness of a queueing system is important to customers not less than the actual delay they ...
Comments