Practical Algorithms for Resource Allocation and Decision Making

Abstract

Algorithms are widely used today to help make important decisions in a variety of domains, including health care, criminal justice, employment, and education. Designing \emph{practical} algorithms involves balancing a wide variety of criteria. Deployed algorithms should be robust to uncertainty, they should abide by relevant laws and ethical norms, they should be easy to use correctly, they should not adversely impact user behavior, and so on. Finding an appropriate balance of these criteria involves technical analysis, understanding of the broader context, and empirical studies ``in the wild''. Most importantly practical algorithm design involves close collaboration between stakeholders and algorithm developers. The first part of this thesis addresses technical issues of uncertainty and fairness in \emph{kidney exchange}---a real-world matching market facilitated by optimization algorithms. We develop novel algorithms for kidney exchange that are robust to uncertainty in both the quality and the feasibility of potential transplants, and we demonstrate the effect of these algorithms using computational simulations with real kidney exchange data. We also study \emph{fairness} for hard-to-match patients in kidney exchange. We close a previously-open theoretical gap, by bounding the price of fairness in kidney exchange with chains. We also provide matching algorithms that bound the price of fairness in a principled way, while guaranteeing Pareto efficiency. The second part describes two real deployed algorithms---one for kidney exchange, and one for recruiting blood donors. For each application cases we characterize an underlying mathematical problem, and theoretically analyze its difficulty. We then develop practical algorithms for each setting, and we test them in computational simulations. For the blood donor recruitment application we present initial empirical results from a fielded study, in which a simple notification algorithm increases the expected donation rate by $5%$. The third part of this thesis turns to human aspects of algorithm design. We conduct several survey studies that address several questions of practical algorithm design: How do algorithms impact decision making? What additional information helps people use complex algorithms to make decisions? Do people understand standard algorithmic notions of fairness? We conclude with suggestions for facilitating deeper stakeholder involvement for practical algorithm design, and we outline several areas for future research.