David Kempe
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
David Kempe has a total of 49 co-authors. Here are the top co-authors by number of shared publications:
- Siddhartha Banerjee
School of Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
4 shared publications - Aleksandra Korolova
Princeton University
3 shared publications Ehsan Emamjomeh-Zadeh
Department of Computer Science, University of Southern California, Los Angeles, California 90089
3 shared publications- Siddartha Devic
University of Southern California
3 shared publications - Vatsal Sharan
University of Southern California
3 shared publications Fatih Erdem Kizilkaya
University of Southern California
2 shared publications
Latest Publications
- 1 March 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 74 (2) , 730-751
Technical Note—Active Learning for Nonparametric Choice Models
Understanding consumer preferences is crucial for designing better products, optimizing assortments, and personalizing recommendations. In “Active Learning for Nonparametric Choice Models,” Fransisca Susan, Negin Golrezaei, Ehsan Emamjomeh-Zadeh, and David Kempe present an active learning approach that efficiently uncovers the most informative patterns in the choices made by members of a heterogeneous population. Instead of relying solely on historical transaction data, their method strategically selects sets of products to offer and then uses the responses to construct a directed acyclic graph (DAG) representation of preferences. This DAG captures the top k choices, their probabilities, and how they relate to each other as k changes. Experiments on synthetic and real‐world data show that the method learns preferences more accurately—and with fewer data points—than leading offline techniques. This work advances both the theory and practice of preference learning, with implications for retail, online platforms, and artificial intelligence agents that need to model human decision making.
- 1 March 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 74 (2) , 730-751
Technical Note—Active Learning for Nonparametric Choice Models
Understanding consumer preferences is crucial for designing better products, optimizing assortments, and personalizing recommendations. In “Active Learning for Nonparametric Choice Models,” Fransisca Susan, Negin Golrezaei, Ehsan Emamjomeh-Zadeh, and David Kempe present an active learning approach that efficiently uncovers the most informative patterns in the choices made by members of a heterogeneous population. Instead of relying solely on historical transaction data, their method strategically selects sets of products to offer and then uses the responses to construct a directed acyclic graph (DAG) representation of preferences. This DAG captures the top k choices, their probabilities, and how they relate to each other as k changes. Experiments on synthetic and real‐world data show that the method learns preferences more accurately—and with fewer data points—than leading offline techniques. This work advances both the theory and practice of preference learning, with implications for retail, online platforms, and artificial intelligence agents that need to model human decision making.
- Open Access
An External Fairness Evaluation of LinkedIn Talent Search
We conduct an independent, third-party audit for bias of LinkedIn's Talent Search ranking system, focusing on potential ranking bias across two attributes: gender and race. To do so, we first construct a dataset of rankings produced by the system, collecting extensive Talent Search results across a diverse set of occupational queries. We then develop a robust labeling pipeline that infers the two demographic attributes of interest for the returned users. To evaluate potential biases in the collected dataset of real-world rankings, we utilize two exposure disparity metrics: deviation from group proportions and MinSkew. Our analysis reveals an under-representation of minority groups in early ranks across many queries. We further examine potential causes of this disparity, and discuss why they may be difficult or, in some cases, impossible to fully eliminate among the early ranks of queries. Beyond static metrics, we also investigate the concept of subgroup fairness over time, highlighting temporal disparities in exposure and retention, which are often more difficult to audit for in practice. In employer recruiting platforms such as LinkedIn Talent Search, the persistence of a particular candidate over multiple days in the ranking can directly impact the probability that the given candidate is selected for opportunities. Our analysis reveals demographic disparities in this temporal stability, with some groups experiencing greater volatility in their ranked positions than others. We contextualize all our findings alongside LinkedIn's published self-audits of its Talent Search system and reflect on the methodological constraints of a black-box external evaluation, including limited observability and noisy demographic inference.
Open AccessAn External Fairness Evaluation of LinkedIn Talent Search
We conduct an independent, third-party audit for bias of LinkedIn's Talent Search ranking system, focusing on potential ranking bias across two attributes: gender and race. To do so, we first construct a dataset of rankings produced by the system, collecting extensive Talent Search results across a diverse set of occupational queries. We then develop a robust labeling pipeline that infers the two demographic attributes of interest for the returned users. To evaluate potential biases in the collected dataset of real-world rankings, we utilize two exposure disparity metrics: deviation from group proportions and MinSkew. Our analysis reveals an under-representation of minority groups in early ranks across many queries. We further examine potential causes of this disparity, and discuss why they may be difficult or, in some cases, impossible to fully eliminate among the early ranks of queries. Beyond static metrics, we also investigate the concept of subgroup fairness over time, highlighting temporal disparities in exposure and retention, which are often more difficult to audit for in practice. In employer recruiting platforms such as LinkedIn Talent Search, the persistence of a particular candidate over multiple days in the ranking can directly impact the probability that the given candidate is selected for opportunities. Our analysis reveals demographic disparities in this temporal stability, with some groups experiencing greater volatility in their ranked positions than others. We contextualize all our findings alongside LinkedIn's published self-audits of its Talent Search system and reflect on the methodological constraints of a black-box external evaluation, including limited observability and noisy demographic inference.
- Open Access
$k$-Approval Veto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection
In the context of single-winner ranked-choice elections between $m$ candidates, we explore the tradeoff between two competing goals in every democratic system: the majority principle (maximizing the social welfare) and the minority principle (safeguarding minority groups from overly bad outcomes).To measure the social welfare, we use the well-established framework of metric distortion subject to various objectives: utilitarian (i.e., total cost), $α$-percentile (e.g., median cost for $α= 1/2$), and egalitarian (i.e., max cost). To measure the protection of minorities, we introduce the $\ell$-mutual minority criterion, which requires that if a sufficiently large (parametrized by $\ell$) coalition $T$ of voters ranks all candidates in $S$ lower than all other candidates, then none of the candidates in $S$ should win. The highest $\ell$ for which the criterion is satisfied provides a well-defined measure of mutual minority protection (ranging from 1 to $m$). Our main contribution is the analysis of a recently proposed class of voting rules called $k$-Approval Veto, offering a comprehensive range of trade-offs between the two principles. This class spans between Plurality Veto (for $k=1$) - a simple voting rule achieving optimal metric distortion - and Vote By Veto (for $k=m$) which picks a candidate from the proportional veto core. We show that $k$-Approval Veto has minority protection at least $k$, and thus, it accommodates any desired level of minority protection. However, this comes at the price of lower social welfare. For the utilitarian objective, the metric distortion increases linearly in $k$. For the $α$-percentile objective, the metric distortion is the optimal value of 5 for $α\ge k/(k+1)$ and unbounded for $α< k/(k+1)$. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of $k$.Open Access$k$-Approval Veto: A Spectrum of Voting Rules Balancing Metric Distortion and Minority Protection
In the context of single-winner ranked-choice elections between $m$ candidates, we explore the tradeoff between two competing goals in every democratic system: the majority principle (maximizing the social welfare) and the minority principle (safeguarding minority groups from overly bad outcomes).To measure the social welfare, we use the well-established framework of metric distortion subject to various objectives: utilitarian (i.e., total cost), $α$-percentile (e.g., median cost for $α= 1/2$), and egalitarian (i.e., max cost). To measure the protection of minorities, we introduce the $\ell$-mutual minority criterion, which requires that if a sufficiently large (parametrized by $\ell$) coalition $T$ of voters ranks all candidates in $S$ lower than all other candidates, then none of the candidates in $S$ should win. The highest $\ell$ for which the criterion is satisfied provides a well-defined measure of mutual minority protection (ranging from 1 to $m$). Our main contribution is the analysis of a recently proposed class of voting rules called $k$-Approval Veto, offering a comprehensive range of trade-offs between the two principles. This class spans between Plurality Veto (for $k=1$) - a simple voting rule achieving optimal metric distortion - and Vote By Veto (for $k=m$) which picks a candidate from the proportional veto core. We show that $k$-Approval Veto has minority protection at least $k$, and thus, it accommodates any desired level of minority protection. However, this comes at the price of lower social welfare. For the utilitarian objective, the metric distortion increases linearly in $k$. For the $α$-percentile objective, the metric distortion is the optimal value of 5 for $α\ge k/(k+1)$ and unbounded for $α< k/(k+1)$. For the egalitarian objective, the metric distortion is the optimal value of 3 for all values of $k$. - Open Access
- 12 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 1288-1294
iFlow - An Interactive Max-Flow Min-Cut Algorithms Visualizer
The Max-Flow/Min-Cut problem is a fundamental tool in graph theory, with applications in many domains, including data mining, image segmentation, transportation planning, and many types of assignment problems, in addition to being an essential building block for many other algorithms. The Ford-Fulkerson Algorithm for Max-Flow/Min-Cut and its variants are therefore commonly taught in undergraduate and beginning graduate algorithms classes. However, these algorithms - and in particular the so-called residual graphs they utilize - often pose significant challenges for students. To help students achieve a deeper understanding, we developed iFlow, an interactive visualization tool for the Ford-Fulkerson Algorithm and its variants. iFlow lets users design or import flow networks, and execute the algorithm by hand. In particular, the user can select an augmentation path and amount, and then update the residual graph. The user is given detailed feedback on mistakes, and can also have iFlow auto-complete each step, to use it as a demonstration tool while still in the initial learning stages. iFlow has been made publicly available and open-sourced. We deployed iFlow in an undergraduate algorithms class, and collected students' self-reported learning benefits via an optional survey. All respondents considered the tool at least somewhat useful and engaging, with most rating it either as useful/engaging or very useful/engaging. Students also generally reported a significant increase in understanding of the algorithm.
- 12 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 1288-1294
Open AccessiFlow - An Interactive Max-Flow Min-Cut Algorithms Visualizer
The Max-Flow/Min-Cut problem is a fundamental tool in graph theory, with applications in many domains, including data mining, image segmentation, transportation planning, and many types of assignment problems, in addition to being an essential building block for many other algorithms. The Ford-Fulkerson Algorithm for Max-Flow/Min-Cut and its variants are therefore commonly taught in undergraduate and beginning graduate algorithms classes. However, these algorithms - and in particular the so-called residual graphs they utilize - often pose significant challenges for students. To help students achieve a deeper understanding, we developed iFlow, an interactive visualization tool for the Ford-Fulkerson Algorithm and its variants. iFlow lets users design or import flow networks, and execute the algorithm by hand. In particular, the user can select an augmentation path and amount, and then update the residual graph. The user is given detailed feedback on mistakes, and can also have iFlow auto-complete each step, to use it as a demonstration tool while still in the initial learning stages. iFlow has been made publicly available and open-sourced. We deployed iFlow in an undergraduate algorithms class, and collected students' self-reported learning benefits via an optional survey. All respondents considered the tool at least somewhat useful and engaging, with most rating it either as useful/engaging or very useful/engaging. Students also generally reported a significant increase in understanding of the algorithm.
- Open Access
- 12 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 645-651
dpvis: A Visual and Interactive Learning Tool for Dynamic Programming
Dynamic programming (DP) is a fundamental and powerful algorithmic paradigm taught in most undergraduate (and many graduate) algorithms classes. DP problems are challenging for many computer science students because they require identifying unique problem structures and a refined understanding of recursion. In this paper, we present dpvis, a Python library that helps students understand DP through a frame-by-frame animation of dynamic programs. dpvis can easily generate animations of dynamic programs with as little as two lines of modifications compared to a standard Python implementation. For each frame, dpvis highlight the cells that have been read from and written to during an iteration. Moreover, dpvis allows users to test their understanding by prompting them with questions about the next operation performed by the algorithm. We deployed dpvis as a learning tool in an undergraduate algorithms class, and report on the results of a survey. The survey results suggest that dpvis is especially helpful for visualizing the recursive structure of DP. Although some students struggled with the installation of the tool (which has been simplified since the reported deployment), essentially all other students found the tool to be useful for understanding dynamic programs. dpvis is available at https://github.com/itsdawei/dpvis.
- 12 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 645-651
Open Accessdpvis: A Visual and Interactive Learning Tool for Dynamic Programming
Dynamic programming (DP) is a fundamental and powerful algorithmic paradigm taught in most undergraduate (and many graduate) algorithms classes. DP problems are challenging for many computer science students because they require identifying unique problem structures and a refined understanding of recursion. In this paper, we present dpvis, a Python library that helps students understand DP through a frame-by-frame animation of dynamic programs. dpvis can easily generate animations of dynamic programs with as little as two lines of modifications compared to a standard Python implementation. For each frame, dpvis highlight the cells that have been read from and written to during an iteration. Moreover, dpvis allows users to test their understanding by prompting them with questions about the next operation performed by the algorithm. We deployed dpvis as a learning tool in an undergraduate algorithms class, and report on the results of a survey. The survey results suggest that dpvis is especially helpful for visualizing the recursive structure of DP. Although some students struggled with the installation of the tool (which has been simplified since the reported deployment), essentially all other students found the tool to be useful for understanding dynamic programs. dpvis is available at https://github.com/itsdawei/dpvis.
- Open Access
Active Learning for Non-Parametric Choice Models
We study the problem of actively learning a non-parametric choice model based on consumers' decisions. We present a negative result showing that such choice models may not be identifiable. To overcome the identifiability problem, we introduce a directed acyclic graph (DAG) representation of the choice model. This representation provably encodes all the information about the choice model which can be inferred from the available data, in the sense that it permits computing all choice probabilities. We establish that given exact choice probabilities for a collection of item sets, one can reconstruct the DAG. However, attempting to extend this methodology to estimate the DAG from noisy choice frequency data obtained during an active learning process leads to inaccuracies. To address this challenge, we present an inclusion-exclusion approach that effectively manages error propagation across DAG levels, leading to a more accurate estimate of the DAG. Utilizing this technique, our algorithm estimates the DAG representation of an underlying non-parametric choice model. The algorithm operates efficiently (in polynomial time) when the set of frequent rankings is drawn uniformly at random. It learns the distribution over the most popular items among frequent preference types by actively and repeatedly offering assortments of items and observing the chosen item. We demonstrate that our algorithm more effectively recovers a set of frequent preferences on both synthetic and publicly available datasets on consumers' preferences, compared to corresponding non-active learning estimation algorithms. These findings underscore the value of our algorithm and the broader applicability of active-learning approaches in modeling consumer behavior.
Open AccessActive Learning for Non-Parametric Choice Models
We study the problem of actively learning a non-parametric choice model based on consumers' decisions. We present a negative result showing that such choice models may not be identifiable. To overcome the identifiability problem, we introduce a directed acyclic graph (DAG) representation of the choice model. This representation provably encodes all the information about the choice model which can be inferred from the available data, in the sense that it permits computing all choice probabilities. We establish that given exact choice probabilities for a collection of item sets, one can reconstruct the DAG. However, attempting to extend this methodology to estimate the DAG from noisy choice frequency data obtained during an active learning process leads to inaccuracies. To address this challenge, we present an inclusion-exclusion approach that effectively manages error propagation across DAG levels, leading to a more accurate estimate of the DAG. Utilizing this technique, our algorithm estimates the DAG representation of an underlying non-parametric choice model. The algorithm operates efficiently (in polynomial time) when the set of frequent rankings is drawn uniformly at random. It learns the distribution over the most popular items among frequent preference types by actively and repeatedly offering assortments of items and observing the chosen item. We demonstrate that our algorithm more effectively recovers a set of frequent preferences on both synthetic and publicly available datasets on consumers' preferences, compared to corresponding non-active learning estimation algorithms. These findings underscore the value of our algorithm and the broader applicability of active-learning approaches in modeling consumer behavior.
- Open Access
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (9) , 9815-9823
Proportional Representation in Metric Spaces and Low-Distortion Committee Selection
We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gamma
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (9) , 9815-9823
Open AccessProportional Representation in Metric Spaces and Low-Distortion Committee Selection
We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gamma
- 6 March 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 11 (4) , 3305-3316
Structural Stability of a Family of Spatial Group Formation Games
We introduce and study a group formation game in which individuals form groups so as to achieve high collective strength. This strength could be group identity, reputation, or protection, and is equally shared by all group members. The group's strength is derived from its access to resources possessed by its members, and is traded off against the geographic dispersion of the group; spread-out groups are costlier to maintain. We seek to understand the properties of stable groupings in such a setting. We define several types of equilibria, where a member wishing to join a new group requires the acceptance of that group, and may further require permission to leave its current group. We show that under natural assumptions on the group utility functions, some of these equilibria always exist, and that any sequence of improving deviations by agents (or subsets of agents in the same group) converges to an equilibrium. In characterizing the properties of these equilibria, We show that an “encroachment” relationship — which groups have members in the territory of other groups — always gives rise to a directed acyclic graph (DAG). We relate our model to observations of well-established groups in a real-world dataset.
- 6 March 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 11 (4) , 3305-3316
Structural Stability of a Family of Spatial Group Formation Games
We introduce and study a group formation game in which individuals form groups so as to achieve high collective strength. This strength could be group identity, reputation, or protection, and is equally shared by all group members. The group's strength is derived from its access to resources possessed by its members, and is traded off against the geographic dispersion of the group; spread-out groups are costlier to maintain. We seek to understand the properties of stable groupings in such a setting. We define several types of equilibria, where a member wishing to join a new group requires the acceptance of that group, and may further require permission to leave its current group. We show that under natural assumptions on the group utility functions, some of these equilibria always exist, and that any sequence of improving deviations by agents (or subsets of agents in the same group) converges to an equilibrium. In characterizing the properties of these equilibria, We show that an “encroachment” relationship — which groups have members in the territory of other groups — always gives rise to a directed acyclic graph (DAG). We relate our model to observations of well-established groups in a real-world dataset.
- Open Access
Stability and Multigroup Fairness in Ranking with Uncertain Predictions
Rankings are ubiquitous across many applications, from search engines to hiring committees. In practice, many rankings are derived from the output of predictors. However, when predictors trained for classification tasks have intrinsic uncertainty, it is not obvious how this uncertainty should be represented in the derived rankings. Our work considers ranking functions: maps from individual predictions for a classification task to distributions over rankings. We focus on two aspects of ranking functions: stability to perturbations in predictions and fairness towards both individuals and subgroups. Not only is stability an important requirement for its own sake, but -- as we show -- it composes harmoniously with individual fairness in the sense of Dwork et al. (2012). While deterministic ranking functions cannot be stable aside from trivial scenarios, we show that the recently proposed uncertainty aware (UA) ranking functions of Singh et al. (2021) are stable. Our main result is that UA rankings also achieve multigroup fairness through successful composition with multiaccurate or multicalibrated predictors. Our work demonstrates that UA rankings naturally interpolate between group and individual level fairness guarantees, while simultaneously satisfying stability guarantees important whenever machine-learned predictions are used.
Open AccessStability and Multigroup Fairness in Ranking with Uncertain Predictions
Rankings are ubiquitous across many applications, from search engines to hiring committees. In practice, many rankings are derived from the output of predictors. However, when predictors trained for classification tasks have intrinsic uncertainty, it is not obvious how this uncertainty should be represented in the derived rankings. Our work considers ranking functions: maps from individual predictions for a classification task to distributions over rankings. We focus on two aspects of ranking functions: stability to perturbations in predictions and fairness towards both individuals and subgroups. Not only is stability an important requirement for its own sake, but -- as we show -- it composes harmoniously with individual fairness in the sense of Dwork et al. (2012). While deterministic ranking functions cannot be stable aside from trivial scenarios, we show that the recently proposed uncertainty aware (UA) ranking functions of Singh et al. (2021) are stable. Our main result is that UA rankings also achieve multigroup fairness through successful composition with multiaccurate or multicalibrated predictors. Our work demonstrates that UA rankings naturally interpolate between group and individual level fairness guarantees, while simultaneously satisfying stability guarantees important whenever machine-learned predictions are used.
- Open Access
- 7 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 209-240
Allocating with Priorities and Quotas: Algorithms, Complexity, and Dynamics
In many applications such as rationing medical care and supplies, university admissions, and the assignment of public housing, the decision of who receives an allocation can be justified by various normative criteria (ethical, financial, legal, etc.). Such settings have motivated the following priority-respecting allocation problem: several categories, each with a quota of interchangeable items, wish to allocate the items among a set of agents. Each category has a list of eligible agents and a priority ordering over these agents; agents may be eligible in multiple categories. The goal is to select a valid allocation: one that respects quotas, eligibility, and priorities and ensures Pareto efficiency. We provide a complete algorithmic characterization of all valid allocations, exhibiting a bijection between sets of agents who can be allocated and maximum-weight matchings under carefully chosen rank-based weights. While prior work provides a polynomial-time algorithm to locate a valid allocation, our characterization admits a simpler algorithm that enables two wide-reaching extensions: 1. Selecting valid allocations that satisfy additional criteria: Via three examples --- inclusion/exclusion of some chosen agent; agent-side Pareto efficiency vs. welfare maximization; and fairness from the perspective of allocated vs. unallocated agents --- we show that finding priority-respecting allocations subject to some secondary constraint straddles a complexity knife-edge; in each example, one problem variant can be solved efficiently, while a closely related variant is NP-hard. 2. Efficiency-envy tradeoffs in dynamic allocation: In settings where allocations must be made to T agents arriving sequentially via some stochastic process, we show that while insisting on zero priority violations leads to an Ω(T) loss in efficiency, one can design allocation policies ensuring that the sum of the efficiency loss and priority violations in hindsight is O(1) (under mild regularity conditions on the arrival process).
- 7 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 209-240
Open AccessAllocating with Priorities and Quotas: Algorithms, Complexity, and Dynamics
In many applications such as rationing medical care and supplies, university admissions, and the assignment of public housing, the decision of who receives an allocation can be justified by various normative criteria (ethical, financial, legal, etc.). Such settings have motivated the following priority-respecting allocation problem: several categories, each with a quota of interchangeable items, wish to allocate the items among a set of agents. Each category has a list of eligible agents and a priority ordering over these agents; agents may be eligible in multiple categories. The goal is to select a valid allocation: one that respects quotas, eligibility, and priorities and ensures Pareto efficiency. We provide a complete algorithmic characterization of all valid allocations, exhibiting a bijection between sets of agents who can be allocated and maximum-weight matchings under carefully chosen rank-based weights. While prior work provides a polynomial-time algorithm to locate a valid allocation, our characterization admits a simpler algorithm that enables two wide-reaching extensions: 1. Selecting valid allocations that satisfy additional criteria: Via three examples --- inclusion/exclusion of some chosen agent; agent-side Pareto efficiency vs. welfare maximization; and fairness from the perspective of allocated vs. unallocated agents --- we show that finding priority-respecting allocations subject to some secondary constraint straddles a complexity knife-edge; in each example, one problem variant can be solved efficiently, while a closely related variant is NP-hard. 2. Efficiency-envy tradeoffs in dynamic allocation: In settings where allocations must be made to T agents arriving sequentially via some stochastic process, we show that while insisting on zero priority violations leads to an Ω(T) loss in efficiency, one can design allocation policies ensuring that the sum of the efficiency loss and priority violations in hindsight is O(1) (under mild regularity conditions on the arrival process).