# efficient_and_fair_healthcare_rationing__b9bd5b13.pdf Journal of Artificial Intelligence Research 81 (2024) 337-358 Submitted 06/2023; published 10/2024 Efficient and Fair Healthcare Rationing Haris Aziz haris.aziz@unsw.edu.au UNSW Sydney, Australia Florian Brandl florian.brandl@uni-bonn.de University of Bonn, Germany The rationing of healthcare resources has emerged as an important issue, which has been discussed by medical experts, policy-makers, and the general public. We consider a rationing problem where medical units are to be allocated to patients. Each unit is reserved for one of several categories, and each category has a priority ranking over the patients. We present a class of allocation rules that respect the priorities, comply with the eligibility requirements, allocate the largest feasible number of units, and do not penalize agents for rising in the priority ranking of a category. The rules characterize all possible allocations that satisfy the first three properties and are polynomial-time computable. 1. Introduction The COVID-19 pandemic emerged as one of the major challenges the world faced. It resulted in a frantic race to produce the most effective and safe vaccine to stem the devastating effects of the pandemic. While the creation, testing, and approval of vaccines proceeded at an unprecedented pace, the initial scarcity posed the question of how to distribute them efficiently and fairly. The same problem arises for other scarce or costly healthcare resources such as ventilators and antiviral treatments. The issue of fair allocation of scarce societal resources is also essential in artificial intelligence (see, e.g., Das (2022), Aziz (2020)). One approach to allocating resources is to assign patients to priority groups, which capture how much a patient needs treatment. For example, medical practitioners and policy-makers highlighted three priority groups: healthcare workers, other essential workers and people in high-transmission settings, and people with medical vulnerabilities associated with poorer COVID-19 outcomes (Persad, Peek, & Emanuel, 2020; Truog, Mitchell, & Daley, 2020). Other concerns that have been discussed include racial equity (Bruce & Tallman, 2021). It is, however, not enough to identify priority groups. There is also a need to algorithmically and transparently make allocation decisions based on the priorities (Emanuel, Persad, Upshur, Thome, Parker, Glickman, Zhang, Boyle, Smith, & Phillips, 2020; WHO, 2020). In a New York Times article, the issue has been referred to as one of the hardest decisions health organizations must make (Fink, 2020). Since the decisions need to be justified to the public, they must be aligned with ethical guidelines, such as respecting the patients priorities. These decisions are not straightforward, especially when patients are eligible for multiple categories. In that case, the decision of which category is used to serve a patient can have compounding effects on what categories other agents can use. A competing objective is allocating the resources efficiently to maximize their social benefit. For example, no medical unit should be left unallocated. Thus, the following fundamental question arises. 2024 The Authors. Published by AI Access Foundation under Creative Commons Attribution License CC BY 4.0. Aziz & Brandl How should we allocate scarce medical resources fairly and efficiently while accounting for various ethical principles and priority groups? The problem of healthcare rationing has recently been formally studied by market designers. Pathak, S onmez, Unver, and Yenmez (2020, 2023) were among the first to frame the problem as a two-sided matching problem in which patients are on one side, and the resource units are on the other side. Thus, they linked the healthcare rationing problem with the rich field of two-sided matching (Roth & Sotomayor, 1990). Pathak et al. (2020, 2023) suggested dividing the units into different reserve categories, each with a subset of agents eligible for that category and its own priority ranking over the patients. The categories and the category-specific priorities represent the ethical principles and guidelines that a policymaker may wish to implement.1 For example, a category for senior people may prioritize the eldest citizens, or a category for healthcare workers may rank ICU personnel ahead of medical workers not directly exposed to the disease. Having a holistic framework that considers different types of priorities has been termed important in healthcare rationing.2 The approach of Pathak et al. (2020, 2023) has been recommended or adopted by various organizations, including the NASEM (National Academies of Sciences, Engineering, and Medicine) Framework for Equitable Vaccine Allocation (NASEM-National Academies of Sciences, Engineering, and Medicine, 2020) and has been endorsed in medical circles (Persad et al., 2020; S onmez, Pathak., Unver, Persad, Truog, & White, 2020). The approach has been covered widely in the media, including the New York Times and the Washington Post.3 Pathak et al. (2020, 2023) proposed the Smart Reserves algorithm for category priorities consistent with a baseline priority ordering.4 It computes a maximum size matching satisfying the basic axioms (eligibility compliance, respect of priorities, and non-wastefulness). The Smart Reserves algorithm carefully decides which category each patient should use to achieve the maximum size property. However, the literature has not addressed the problem with possibly heterogeneous priorities. Allowing heterogeneous priorities for categories is very much in the spirit of incorporating different ethical values. For example, it seems desirable that the priority ordering in the category of older people can be different from the priority ordering in the category of front-line workers. The former may rank individuals by age, and the latter may favor energetic medical professionals.5 In this paper, we set out to address this issue and answer the following research problem. 1. See, for example, the book by Bognar and Hirose (2014) on the ethics of healthcare rationing that discusses many of these principles. 2. In a report issued by the Deeble Institute for Health Policy Research, Martin (2015) writes that To establish robust healthcare rationing in Australia, decision-makers need to acknowledge the various implicit and explicit priorities that influence the process and develop a decision-making tool that incorporates them. 3. https://www.covid19reservesystem.org/media 4. The priority ranking of a category is consistent with a baseline priority ordering if it ranks the agents eligible for it according to the baseline priority. 5. Even in other contexts such as immigration, where rationing policies are applied, respecting heterogeneous priorities can be important. For example, if a country has a quota for admitting engineers, the top engineering applicant who satisfies basic eligibility requirements may have a good case to be issued a visa. Efficient and Fair Healthcare Rationing For healthcare rationing with heterogeneous priorities, how should we allocate resources in a fair, economically efficient, and computationally tractable way? Contribution We consider healthcare rationing with heterogeneous priorities. Our first contribution is introducing a class of allocation rules called Reverse Rejecting rules, which (i) comply with the eligibility requirements, (ii) respect the priorities of the categories (for each category, patients of higher priority are served first), (iii) yield a maximum size matching (one that allocates the largest feasible number of units to eligible patients), (iv) are non-wasteful (no unit is unused but could be used by some eligible patient), (v) respect improvements (do not penalize patients for rising in the priority ranking of a category), and (vi) are strongly polynomial-time computable. We prove that Reverse Rejecting rules characterize all outcomes that satisfy the first three properties. We show how Reverse Rejecting rules can be used to obtain the Smart Reverse Rejecting rule, which processes a given number of unreserved units first and last and which incorporates the additional goal of allocating the largest feasible number of units from a designated subset of categories called preferential categories. The Smart Reverse Rejecting rule satisfies a new axiom we call order preservation, which is parameterized by how many unreserved units are processed first and last. Moreover, it generalizes two wellknown reserves rules over-and-above and minimum-guarantees (Galanter, 1961, 1984) that are understood in the context of preferential categories having consistent priorities. Finally, we discuss how our algorithms and their properties extend to soft reserves. Reverse Rejecting rules also apply to the school choice problem when students are only interested in being matched to one of their acceptable schools and to hiring settings when applicants are interested in one of the positions and each department has its own priorities. Lastly, they apply to other rationing scenarios, such as allocating limited slots at public events or visas to immigration applicants. 2. Related Work The paper is related to an active area of research on matching with distributional constraints (see, e.g., Kojima (2019), Aziz, Bir o, and Yokoo (2022)). One general class of distributional constraints examined in matching market design pertains to common quotas over institutions such as hospitals (Kamada & Kojima, 2015, 2017; Bir o, Fleiner, Irving, & Manlove, 2010a; Goto, Iwasaki, Kawasaki, Kurata, Yasuda, & Yokoo, 2016). Within the umbrella of work on matching with distributional constraints, particularly relevant to healthcare rationing is the literature on school choice with diversity constraints and reserve systems (Hafalir, Yenmez, & Yildirim, 2013; Ehlers, Hafalir, Yenmez, & Yildirim, 2014; Echenique & Yenmez, 2015; Kurata, Hamada, Iwasaki, & Yokoo, 2017; Aziz & Brandl Ayg un & Turhan, 2020; Ayg un & B o, 2020; Aziz, Gaspers, & Sun, 2020; Gonczarowski, Nisan, Kovalio, & Romm, 2019; Dur, Kominers, Pathak, & S onmez, 2018; Dur, Pathak, & S onmez, 2020). Categories in healthcare rationing correspond to affirmative action types in school choice. We suggest the book chapter by Heo (2019) for a brief survey. Except for the special case in which students have precisely one type (see, e.g., Ehlers et al. (2014)), most of the approaches do not achieve diversity goals optimally, whereas, for the healthcare rationing problem we consider, we aim to find matchings that maximize the number of units allocated to eligible patients. This literature also considers optimization approaches for diverse matchings but for different models and objectives (see, e.g., Ahmed, Dickerson, and Fuge (2017), Dickerson, Sankararaman, Srinivasan, and Xu (2019), Ahmadi, Ahmed, Dickerson, Fuge, and Khuller (2020)). Pathak et al. (2020, 2023) were the first to frame a rationing problem with category priorities as a two-sided matching problem in which agents are interested in a single unit of resource, and the resources are reserved for different categories. They show that artificially endowing agents with strict preferences over the categories and running the Deferred Acceptance algorithm results in desirable outcomes for the rationing problem. They note, however, that this approach may lead to matchings that are not Pareto optimal (cf. Remark 4.5). By contrast, Reverse Rejecting rules always allocate the largest feasible number of units and thus give a Pareto optimal allocation. Pathak et al. (2020, 2023) also consider a setting where given numbers of unreserved units must be allocated before or after allocating the units reserved for categories. They propose to use the Smart Reserves approach of S onmez and Yenmez (2020) for the restricted problem when all categories have consistent priorities. The thereby obtained class of Smart Reserve rules includes two extreme approaches with widespread appeal. The first approach is based on minimum-guarantees specifying the minimum number of units kept for a particular agent group. The second approach is over-and-above; it sets aside the specified number of units for an agent group and only uses them once all the unreserved units are allocated (for which the agent group is eligible as well).6 Pathak et al. (2020, 2023) assume that all the priorities of categories are consistent with a baseline ordering. In contrast, we allow the priorities of categories to be heterogeneous. Our Smart Reverse Rejecting rule achieves the features of the Smart Reserves rule for heterogeneous priorities. In follow-up work, Grigoryan (2020) considers optimization approaches for variants of the problem but does not present polynomial-time algorithms. In this paper, we attempt to compute particular maximum size stable matchings. The problem of computing such matchings is NP-hard if both sides have strict preferences (priorities, respectively) (Bir o, Manlove, & Mittal, 2010b). In our problem, the agents have dichotomous preferences (categories they are/are not eligible for), which allows us to obtain a polynomial-time algorithm for the problem. Computing outcomes that match as many agents as possible has also been examined in related but different contexts (see, e.g., Aziz (2018), Andersson and Ehlers (2020), Abraham, Blum, and Sandholm (2007), Bogomolnaia and Moulin (2015)). Sonmez and Yenmez (2024) model an affirmative action program in India for positions in the public service. In this model, individuals are to be assigned to job types based on 6. Both the minimum-guarantees and over-and-above approaches have been discussed in the context of reserves systems in India (see, e.g., Galanter (1961, 1984)). Efficient and Fair Healthcare Rationing their preferences over job types. Each individual belongs to a single category and has a merit score for each job type (and thus, priorities are heterogeneous across job types). A number of positions in each job type are reserved for each category. Additionally, they consider traits of individuals, which we ignore in this discussion. One way of comparing our settings is to identify their job types with our categories, assume that all individuals are indifferent between all their acceptable job types, and assume that no individual belongs to any of their categories. Then, the mechanism they propose complies with the eligibility requirements, respects priorities, and is non-wasteful; however, Sonmez and Yenmez (2024) do not consider the maximum size property or respect of improvements. In their setting with non-indifferent individuals, their mechanism is strategyproof. Other ways of identifying the two settings result in homogeneous priorities and thus miss out on an essential component of our model. Similarly, Sonmez and Yenmez (2022) examined the particular model of an affirmative action program implemented in India. In the paper, the priorities are not heterogeneous. Balinski and S onmez (1999) introduced the respecting improvements property in the college admissions model of Gale and Shapley (1962). In that context, it states that students should not be penalized for higher priority among the colleges (e.g., because of better test scores). They show that the student proposing the Deferred Acceptance algorithm is the unique stable mechanism that respects improvements. We adopt the model of Pathak et al. (2020, 2023) with two generalizations: we do not assume that the categories priorities are consistent with a baseline ordering and we allow the priorities to be weak rather than strict. There are q identical and indivisible units of some resource, a finite set C of categories, and a set N of agents with |N| = n. Each category c has a quota qc N with P c C qc = q and a priority ranking c, which is a weak order on N { }. An agent i is eligible for category c if i c . We denote by Nc the set of agents who are eligible for c. We say that I = (N, C, ( c)c C, (qc)c C) is an instance (of the rationing problem). We will write ( c) and (qc) for profiles of priorities and quotas in the sequel. A matching µ: N C { } is a function that maps each agent to a category or to and satisfies the capacity constraints: for each c C, |µ 1(c)| qc. For an agent i N, µ(i) = means that i is unmatched (that is, does not receive any unit), and µ(i) = c means that i receives a unit reserved for category c. When convenient, we will identify a matching µ with the set of agent-category pairs {{i, µ(i)}: µ(i) = }.7 We introduce four axioms in the context of allocating medical units that are wellgrounded in practice. For further motivation of these axioms, we recommend the detailed discussions by Pathak et al. (2020, 2023). The first axiom requires matchings to comply with the eligibility requirements. It specifies that a patient should only take a unit of a category for which the patient is eligible. For example, a young person should not take a unit from the units reserved for older people. We sometimes refer to a matching that complies with the eligibility requirements as a feasible matching. 7. In graph theoretic terms, µ is a b-matching because multiple edges in µ can be adjacent to a category c. Aziz & Brandl Definition 3.1 (Compliance with eligibility requirements). A matching µ complies with the eligibility requirements (or is feasible) if for any i N and c C, µ(i) = c implies i c . The second axiom concerns the respect of priorities of categories, and it is the central fairness concept we consider. It rules out that a patient is matched to a unit of some category c while some other agent with a higher priority for c is unmatched. Definition 3.2 (Respect of priorities). A matching µ respects priorities if for any i, j N and c C, µ(i) = c and µ(j) = implies j c i. If there exist i, j N and c C with µ(i) = c, µ(j) = , and j c i, we say that j has justified envy towards i for category c. An astute reader who is familiar with the theory of stable matchings will immediately realize that respect of priorities is equivalent to justified envy-freeness in the context of school-choice matchings (Abdulkadiro glu & S onmez, 2003). Next, non-wastefulness requires that if an agent is unmatched despite being eligible for a category, then all units reserved for that category are matched to other agents. Definition 3.3 (Non-wastefulness). A matching µ is non-wasteful if for any i N and c C, i c and µ(i) = implies |µ 1(c)| = qc. Not all non-wasteful matchings allocate the same number of units. In particular, some may not allocate as many units as possible. A stronger efficiency notion prescribes that the number of allocated units is maximal subject to compliance with the eligibility requirements. Definition 3.4 (Maximum size matching). A matching µ is a maximum size matching if it has maximum size among all matchings complying with the eligibility requirements. These four axioms capture the first guideline put forth in the report by the National Academies of Sciences, Engineering, and Medicine: ensure that allocation maximizes benefit to patients, mitigates inequities and disparities, and adheres to ethical principles (NASEM-National Academies of Sciences, Engineering, and Medicine, 2020). Requiring matchings to be of maximum size is aligned with the principle to gain the best value we possibly can from the expenditure of that resource (Dawson, Isaacs, Jansen, Jordens, Kerridge, Kihlbom, Kilham, Preisz, Sheahan, & Skowronski, 2020). It will be useful to associate a graph BI, called a reservation graph, with an instance I. BI = (N C, E) is a bipartite graph with an edge from i to c if i is eligible for c. That is, E = {{i, c}: i c }. If BI is any reservation graph, we denote by ms(BI) the number of edges in a maximum size matching of BI subject to given quotas (qc). A maximum size matching of a bipartite graph can be computed in polynomial time (more precisely, cubic time in the number of vertices of the graph) by any of several well-established methods such as Kuhn s algorithm (Kuhn, 1955) or the Hopcroft-Karp-Karzanov algorithm (Hopcroft & Karp, 1973; Karzanov, 1973).8 8. For example, Kuhn s algorithm proceeds as follows. An alternating path with respect to a matching µ is a path in G in which edges alternate between those in µ and those not in µ. An augmenting path is an alternating path that starts and ends with an edge not in µ. Kuhn s algorithm repeatedly applies Berge s lemma, which states that a matching has maximum size if and only if there is no augmenting path with respect to that matching. Hence, starting with any matching and repeatedly alternating it along an augmenting path as long as an augmenting path exists results in a maximum size matching. The polynomial runtime follows from the fact that augmenting paths can be found in polynomial time and each alteration increases the size of the matching by one edge. Efficient and Fair Healthcare Rationing 2 c1 3 c1 c1 1 2 c2 c2 1 c2 3 Figure 1: The instance I described in Example 3.5. The reservation graph BI on the left has an edge from i to c if i is eligible for c. The priority rankings of the categories are depicted on the right. The following example illustrates the definitions above. Example 3.5. Suppose there are three agents and two categories with one reserved unit each. N = {1, 2, 3}, C = {c1, c2}, qc1 = 1, qc2 = 1. The priority ranking of c1 is 2 c1 3 c1 c1 1 and the priority ranking of c2 is 2 c2 c2 1 c2 3. Figure 1 illustrates this instance I of the rationing problem. Note that agent 1 is not eligible for any category, agent 2 is eligible for c1 and c2, and agent 3 is eligible only for c1. Thus, the following matchings comply with the eligibility requirements. µ1 = µ2 = {{2, c1}} µ3 = {{2, c2}} µ4 = {{3, c1}} µ5 = {{2, c2}, {3, c1}} All of these matchings except for µ4 respect priorities. Only µ2 and µ5 are non-wasteful. The only maximum size matching is µ5. We are interested in allocation rules, which, for each instance, return a matching. Definition 3.6 (Allocation rule). An allocation rule maps every instance I to a matching for I. We say that an allocation rule f satisfies one of the axioms in Definitions 3.1 to 3.4 if f(I) satisfies the axiom for all instances I. An allocation rule respects improvements if it never hurts an agent to rise in the categories priorities. More precisely, suppose an agent is assigned a unit for a given priority profile. Then this agent should still be assigned a unit if her priority for each category increases or stays the same and the priorities among all other agents stay the same. This property has been introduced by Balinski and S onmez (1999) for two-sided matching problems. More formally, let ( c) and ( c) be priority profiles and i N. We say agent i s priority increases from ( c) to ( c) if for all j, k = i and c C, j c k if and only if j c k i c j implies i c j and i c j implies i c j Aziz & Brandl That is, the priority rankings over agents other than i are the same in both profiles and i can only move up in the priority rankings from ( c) to ( c). We also say that i s priority increases from I = (N, C, ( c), (qc)) to I = (N, C, ( c), (qc)). Respecting improvements requires that if i is matched under I, then i is also matched under I . Definition 3.7 (Respecting improvements). An allocation rule f respects improvements if f(I)(i) = implies f(I )(i) = whenever i s priority increases from I to I . Remark 3.8 (Strategyproofness). In healthcare rationing, priorities are based on verifiable characteristics (such as age, occupation, or pre-existing health conditions). However, agents may be able to hide some of these characteristics (for example, a pre-existing health condition) and thereby lower their priority for some categories. Respecting improvements can thus be interpreted as a notion of strategyproofness: assuming that agents prefer receiving a unit to not receiving a unit, each agent s dominant strategy is to declare all characteristics that increase her priority. The restricted version of respecting improvements requiring only that it is never beneficial for an agent to become ineligible for a category has been referred to as incentive compatibility by Ayg un and B o (2020). 4. Reverse Rejecting Rules We introduce the class of Reverse Rejecting rules. Each Reverse Rejecting rule is based on a linear order π, over the agents. The Reverse Rejecting rule based on π (REV π) considers the agents in ascending order of π. It rejects an agent if the agents who have not been rejected thus far can form a maximum size matching (among matchings in the reservation graph) for which none of the rejected agents has justified envy towards a matched agent. The second constraint is implemented by removing those edges from the reservation graph BI that would cause justified envy by rejected agents. That is, if agent i is rejected, we cannot allow any agent j to be matched to a category c if i c j, and so remove the edge {j, c} from BI. More generally, if R is the set of rejected agents, B R I = ((N \ R) C, E) with E = {{j, c} : j c and there is no i R such that i c j} is the corresponding reduced reservation graph. Note that if R R , then B R I is a subgraph of B R I . In particular, B R I is a subgraph of BI. The REV π rule then works as follows: Let the set of rejected agents R be empty at the start and consider the agents in ascending order of π. When considering agent i, add i to the rejected agents R if and only if ms(B (R {i}) I ) = ms(BI). After the last agent has been considered, let RI be the final set of rejected agents and choose a maximum size matching of the reduced reservation graph B RI I . The methodology of Reverse Rejecting rules is different from the Horizontal Envelope rule of S onmez and Yenmez (2020) and the Smart Reserves rule of Pathak et al. (2020, 2023). In contrast to iteratively or instantly selecting agents that will be matched, Reverse Rejecting rules proceed in ascending order of order over agents and decide which agents to reject. More importantly, Reverse Rejecting rules work for heterogeneous and weak priorities. Efficient and Fair Healthcare Rationing (b) B {4} I (c) B {3,4} I (d) B {2,4} I (e) B {1,2,4} I Figure 2: Graphs for the instance I in Example 4.1. Example 4.1 (Illustration of Reverse Rejecting rules). Consider an instance with N = {1, 2, 3, 4}, C = {c1, c2}, qc1 = qc2 = 1 The priorities are 1 c1 4 c1 2 c1 and 1 c2 3 c2 . For 1 π 2 π 3 π 4, let us simulate the REV π rule. The reservation graph BI is depicted in Figure 2a. It has a maximum size matching of size 2. First agent 4 is considered. Since the graph B {4} I depicted in Figure 2b admits a matching of size 2, agent 4 is placed in R. Next, agent 3 is considered and not placed in R since the graph B {3,4} I depicted in Figure 2c does not admit a matching of size 2. The graph B {2,4} I depicted in Figure 2d admits a matching of size 2. Hence, agent 2 is placed in R. Lastly, since B {1,2,4} I depicted in Figure 2e does not admit a matching of size 2, agent 1 is not placed in R. The final outcome is a maximum size matching of the graph B {2,4} I as depicted in Figure 2d. Theorem 4.2 (Properties of Reverse Rejecting rules). For each linear order π over agents, the REV π rule (i) complies with eligibility requirements, (ii) respects priorities, (iii) returns a matching of maximum size among feasible matchings, (iv) respects improvements, and (v) can be computed in strongly polynomial time. Aziz & Brandl Proof. (i) Compliance with eligibility requirements. The outcome is a matching of B RI I , which is a subgraph of BI. Any edge {i, c} of BI is such that i c . Therefore the outcome satisfies eligibility requirements. (ii) Respect of priorities. Let µ be the matching returned by the REV π rule for the instance I. First, we claim that µ provides no justified envy for any agent in RI. If j RI, i N, and c C with µ(i) = c and j c i, then {i, c} was deleted from the reservation graph when rejecting j and is thus not an edge of B RI I . Since µ is a matching of B R I , it does not match i to c. Second, we show that µ matches all agents in N \RI. In particular, no agent in N \RI can have (justified) envy. Assume for contradiction that |µ| < n |RI|. This means that ms(B (RI {i}) I ) < ms(BI) = ms(B RI I ) = |µ| for all i N \ RI. Among all maximum size matchings of B RI I , let µ be one that is Pareto optimal with respect to the priorities. If there were i, j N \ RI so that j has justified envy towards i in µ (µ (i) = c, µ (j) = , and j c i), then the matching µ \ {{i, c}} {{j, c}} would Pareto dominate µ with respect to the priorities, which cannot be. Thus, µ respect priorities, so that for j N \ RI with µ (j) = , µ is a matching of B (RI {j}) I . It follows that ms(B (RI {j}) I ) = ms(B RI I ), which contradicts that the REV π rule rejects none of the agents in N \ RI. (iii) Maximum size matching. The returned matching is by construction a matching of size ms(BI) and hence of maximum size among all matching complying with the eligibility requirements. (iv) Respecting improvements. For simplicity, suppose π is 1 π 2 π π n. Let i N and I, I be instances so that i s priority increases from I to I . Assume that i is unmatched in REV π(I ). We need to show that i is unmatched in REV π(I). Note that ms(BI) = ms(BI ) since the edge set of BI is a subset of the edge set of B I and REV π(I ) does not match i. Let Ri I = {j RI : i π j} be the agents who are unmatched in REV π(I) and are lower in the order π than i. Define Ri I similarly. We first show that Ri I = Ri I . To this end, we prove by induction that j Ri I if and only if j Ri I for j = n to i + 1 The base case is trivial since the set of rejected agents is the empty set at the start of the algorithm under both instances I and I . For the induction step, let j > i and suppose j Ri I if and only if j Ri I for j = n to j + 1. We prove that j Ri I if and only if j Ri I . Denote by R the set of rejected agents at the beginning of the round where agent j is considered. Note that R = Ri I {j + 1, . . . , n} = RI {j + 1, . . . , n}. If j Ri I , this is because there exists a matching µ of B (R {j}) I with |µ| = ms(BI ). Since RI {j, . . . , n} R {j}, µ does not match any agent in RI {j, . . . , n}. Since i is unmatched in REV π(I ), it follows that i RI , and we can assume that µ does not match i. Now consider B (R {j}) I . For each k N \(R {j} {i}) and c C, {k, c} is an edge of B (R {j}) I if and only if {k, c} is an edge of B (R {j}) I since the priorities for all agents other than Efficient and Fair Healthcare Rationing i are the same in I and I . It follows that µ is also a feasible matching of B (R {j}) I . Therefore j Ri I. For the other direction, suppose j Ri I. Hence, there exists a matching µ of B (R {j}) I with |µ| = ms(BI) = ms(BI ). As above, for each k N \ (R {j} {i}) and c C, {k, c} is an edge of B (R {j}) I if and only if {k, c} is an edge of B (R {j}) I . For i and any c C, note that if {i, c} is an edge of B (R {j}) I , then {i, c} is an edge of B (R {j}) I . Hence µ is also a feasible matching of B (R {j}) I . Thus, j Ri I . This completes the proof that Ri I = Ri I . Now we prove that i is unmatched in I, that is, i RI. Since i RI , it follows that ms(B (Ri I {i}) I ) = ms(BI ). Moreover, B (Ri I {i}) I is a subgraph of B (Ri I {i}) I since Ri I = Ri I and i s priority increases from I to I . Hence, ms(B (Ri I {i}) I ) = ms(B (Ri I {i}) I ) = ms(BI ). Therefore i RI. (v) Polynomial time computability. The rule makes at most n calls to computing a maximum size matching of the underlying reservation graphs. Thus, it runs in strongly polynomial time. Remark 4.3 (Relation to school choice). Theorem 4.2 can be rephrased in the context of school choice (see e.g., Abdulkadiro glu and S onmez (2003)). Agents correspond to students and categories correspond to schools. Suppose each student finds a subset of schools acceptable and is indifferent between all acceptable schools (which is a restrictive assumption). The schools have priorities over the students. Then, Theorem 4.2 reads as follows. Theorem. Consider the school choice problem where the students partition the schools into acceptable and unacceptable schools. Then, there is an allocation rule that only matches students to acceptable schools, admits no justified envy, matches the maximal feasible number of students, and does not penalize students for rising in the schools priorities or incentivize students to hide that they find a school acceptable. Note that among the matchings that comply with the eligibility requirements, respect priorities, and have maximum size among feasible matchings, REV π returns one that matches the set of agents that is maximal according to the upward lexicographic ordering on subsets of agents induced by π. Hence, the outcome of REV π depends heavily on the order π. We show that in fact, every matching satisfying these three properties is an outcome of REV π for some order π. Thus, these properties characterize all possible outcomes of Reverse Rejecting rules. Theorem 4.4 (Characterization of outcomes of Reverse Rejecting rules). A matching complies with the eligibility requirements, respects priorities, and has maximum size among feasible matchings if and only if it is a possible outcome of REV π for some order π. Proof. Consider a matching µ with the three properties. Suppose it matches the set of agents S N. Our first claim is that µ is feasible matching of B (N\S) I . Since µ satisfies the eligibility requirements, it is a matching of the graph BI constrained to the vertex set Aziz & Brandl S C. Since µ respects priorities, there exists no edge {i, c} µ such that j c i for some j N \ S. Therefore, it follows that µ is a matching of B (N\S) I . Now consider an order π such that i π j for all i S and j N \ S. Denote by RI the set of unmachted agents in REV π(I). We claim that RI = N \ S. Since |µ| = ms(BI) by assumption and µ is a matching of B (N\S) I as shown above, it follows that N \ S RI. The inclusion cannot be strict since then ms(B RI I ) < |µ| = ms(BI). Thus, RI = N \ S. Since µ is a maximum size matching of B (N\S) I , REV π(I) = µ is possible. The converse follows from Theorem 4.2. Remark 4.5 (Characterization of outcomes of the Deferred Acceptance algorithm). Pathak et al. (2020, 2023) obtain a result analogous to Theorem 4.4 for the Deferred Acceptance algorithm. More precisely, they show that a matching complies with the eligibility requirements, respects priorities, and is non-wasteful if and only if there is a profile of strict preferences for the agents over the categories so that the matching is the outcome of the Deferred Acceptance algorithm applied to the resulting two-sided matching instance. Note that not every matching with these properties has maximum size.9 5. Treating Reserved and Unreserved Units Asymmetrically Various reserves problems share two features. First, there is a designated category cu C interpreted as the unreserved category to which every agent has access, and the remaining categories Cp are preferential categories to which only some agents have access. For example, only some minority groups may qualify for the preferential categories in affirmative action programs. Second, there is a baseline ordering π over agents. For job selection under diversity concerns, the baseline ordering can be interpreted as an order of merit, or for healthcare rationing and school choice, the baseline ordering could be the need for treatment or the score in a central entrance exam, respectively. We assume that the priority ranking for the unreserved category equals the baseline ordering and refer to the units reserved for the unreserved category as unreserved units. In this section, we explain why the asymmetry between the unreserved category and the preferential categories is helpful to capture common policy goals, which we formalize by a new axiom called order preservation. We then adapt Reverse Rejecting rules to incorporate this asymmetry, resulting in Smart Reverse Rejecting rules, which are shown to satisfy order preservation in addition to the properties they inherit from Reverse Rejecting rules. As in the previous section, the emphasis lies on finding matchings that maximize the benefit to the agents. This is captured by maximum beneficiary assignments, which maximize the number of agents matched to preferential categories.10 Definition 5.1 (Maximum beneficiary assignment). A matching µ is a maximum beneficiary assignment if it maximizes the number of agents matched to a preferential category. 9. For the instance in Example 3.5, assume that all agents prefer c1 to c2. Then applying the Deferred Acceptance algorithm results in the matching µ2 = {{2, c1}}, which does not have maximum size. 10. In our context, the combination of maximum beneficiary assignment and non-wastefulness implies maximum size. Efficient and Fair Healthcare Rationing We observe that applying the REV rule to the preferential categories Cp and then allocating the unreserved units among the unmatched agents, say, according to the baseline ordering, yields a maximum beneficiary assignment. 5.1 Order Preservation Certain policy goals may require allocating a designated number of unreserved units before allocating the units reserved for preferential categories. For example, the rationale for the over-and-above reserves approach is that agents first get a bite at the designated unreserved units before they utilize the preferential category units for which they are eligible. By contrast, the minimum-guarantees reserves approach first assigns agents to preferential categories and then matches the remaining agents to the unreserved units. We first define minimum-guarantees and over-and-above reservation rules (Chapter 13, Part B, Galanter (1984)) when the agents are eligible for at most one preferential category and all categories have priorities that are consistent with the baseline ordering in the sense that the agents that are eligible for a category are ranked according to the baseline ordering.11 Minimum-guarantee Consider the agents in the order of the baseline ordering. For each agent, match her to a preferential category if (i) the agent is eligible for a preferential category and (ii) not all units reserved for this category have been allocated. Otherwise, match the agent to the unreserved category if an unreserved unit remains.12 Over-and-above Consider the agents in the order of the baseline ordering. For each agent i, match her to the unreserved category only if (i) an unreserved unit remains, and (ii) agent i is eligible for some preferential category, say, c, and there are still at least qc agents from Nc other than i who are unmatched. Then, fill up the preferential categories as follows: for each c Cp, the min{qc, |Nc|} highest priority unmatched agents are given one unit each from c.13 We present an example adapted from the book of Galanter (1984) to illustrate the difference between the minimum-guarantees and the over-and-above approach.14 Example 5.2. Consider the case where N = {1, 2, 3, 4}, C = {c, cu}, qc = qcu = 1, Nc = {1, 4}, and 4 π 3 π 2 π 1. The outcome of the minimum-guarantees rule is that agent 3 and 4 are selected and the matching is {{3, cu}, {4, c}}. The outcome of the over-andabove rule is that agents 1 and 4 are selected and the matching is {{1, c}, {4, cu}}. In the 11. Galanter (1961, 1984) was one of the first to study the differences between the minimum-guarantees and over-and-above reservation rules in depth. 12. There is another version of the minimum-guarantees rule called the Partha method that gives an equivalent outcome but operates differently as an algorithm. In the Partha method, the units are allocated according to the baseline ordering and preferential reservation is only enforced if the reserves are not maximally used (Galanter, 1984). 13. Note that in the first stage, agents may be matched to the unreserved category but not to a preferential category. Hence, in the second stage, for any preferential category c, there are qc units left. 14. Galanter (1984) studied minimum-guarantees and over-and-above in the context of job allocation in India where the baseline ordering represents the merit ranking and the preferential categories are historically disadvantaged groups. He observes that the minimum-guarantees rule insures that the amount of effective reservation is somehow commensurate with the backwardness that inspired it. On the other hand, he observes that the minimum-guarantees rule may overstate the effective amount of reservation especially if the disadvantaged groups are doing well enough on merit (page 461). Aziz & Brandl example, the minimum-guarantees rule coincides with the rule that solely uses the baseline ordering. On the other hand, the over-and-above rule provides additional representation of agents from the preferential category c. We note that the minimum-guarantees approach allocates the unreserved units at the end whereas the over-and-above approach allocates the unreserved units first. We now explicitly distinguish between unreserved units that are processed earlier and later. To be precise, let C = Cp {c1 u, c2 u}, where c1 u represents the unreserved units to be treated first and c2 u the unreserved units to be treated at the end. We view c1 u and c2 u as subcategories of the unreserved category cu and the qcu slots for cu as being partitioned into qc1u slots for c1 u and qc2u slots for c2 u. Hence, qc1u + qc2u = qcu and c1u = c1u = π. If an agent is matched to c1 u or c2 u, we say that she receives an unreserved unit. Pathak et al. (2020, 2023) formulated a family of rules, called Smart Reserves rules, that allow agents to be eligible for multiple preferential categories and generalize the minimumguarantee and over-and-above rules to this case. In this section, we capture these approaches via an axiom for matchings called order preservation and then propose a new rule that also works for heterogeneous priorities. Order preservation is parametrized by the number of unreserved units that are placed in categories c1 u and c2 u. It captures the idea that there is an order of the categories (c1 u, Cp, and then c2 u), and no two agents should be able to swap their matches so that eligibility requirements are not violated, and an earlier category gets a higher priority agent after the swap. Definition 5.3 (Order preservation). Consider a matching µ of agents to categories in Cp {c1 u, c2 u}. We say that µ is order preserving (with respect to c1 u and c2 u) for the baseline ordering π if for any two agents i, j N, (i) µ(i) Cp {c2 u}, µ(j) = c1 u, and j is eligible for category µ(i) implies j π i, and (ii) µ(j) Cp {c1 u}, µ(i) = c2 u, and i is eligible for category µ(j) implies j µ(j) i.15 There are two extreme ways unreserved units can be treated under order preservation. The first is if qc1u = 0 and qc2u = qcu. The other is if qc1u = qcu and qc2u = 0. The conceptual contribution of Definition 5.3 is that instead of describing over-and-above and minimumguarantees rules as consequences of certain sequential allocation methods, order preservation captures a key property of their resulting matchings. It is formulated so that it allows for heterogeneous priorities or agents being eligible for multiple categories. We collect some of the properties of the minimum-guarantees rule and the over-andabove rule when each agent is eligible for at most one preferential category and categories have consistent priorities. These properties characterize the minimum-guarantees rule for the corresponding notion of order-preservation. Proposition 5.4 (Properties of minimum-guarantees and over-and-above). Assume each agent is eligible for at most one preferential category and all categories have consistent priorities. Then, the outcome of the minimum-guarantees (over-and-above) rule 15. The qualification that i is eligible for category µ(j) is could be omitted without altering the content of the definition since if i is not eligible for µ(j), j µ(j) i holds trivially. We keep it to maintain the symmetry with (i). Efficient and Fair Healthcare Rationing (i) complies with the eligibility requirements, (ii) is a maximum beneficiary assignment, (iii) respects priorities, (iv) is non-wasteful, and (v) satisfies order preservation for qc1u = 0 and qc2u = qcu (qc1u = qcu and qc2u = 0). Moreover, the outcome of the minimum-guarantees rule is the unique matching satisfying (i) to (v) with qc1u = 0 and qc2u = qcu. Proof. First consider the minimum-guarantees rule. It complies with the eligibility requirements and is non-wasteful. It also yields a maximum beneficiary assignment because for each preferential category, the maximum possible number of agents is matched. The unreserved units are matched later to the unmatched agents. Therefore, the matching respects priorities and satisfies order preservation for qc1u = 0 and qc2u = qcu. We prove that there is exactly one matching satisfying (i) to (v) with qc1u = 0 and qc2u = qcu. Hence, the outcome of the minimum-guarantees rule is the unique such matching. Suppose for contradiction there are two such matchings µ and µ . Since each agent is eligible for at most one category in Cp and µ and µ satisfy maximum beneficiary assignment, it follows that |µ (c)| = |µ (c)| for all c Cp. We prove that for either of µ and µ , the agents matched to c Cp are the min{qc, |Nc|} highest priority eligible agents for c. Suppose this is not the case for µ . Then, there exist i, j Nc such that µ (j) = c, µ (i) = c, and i c j. If µ (i) = , then µ does not respect priorities. If µ (i) = c2 u, then µ does not satisfy order preservation as i and j can swap their matches without violating eligibility requirements. We have established that for each c Cp, µ (c) = µ (c). Respect of priorities, non-wastefulness, and the fact that every agent is eligible for c2 u imply that the agents matched to c2 u for either of µ and µ are the highest priority agents who are not matched to categories in Cp. Hence, µ (c2 u) = µ (c2 u). Now consider the over-and-above rule. It complies with the eligibility requirements and is non-wasteful. It also yields a maximum beneficiary assignment because for each preferential category, the maximum possible number of agents are matched. The unreserved units are matched to the highest priority agents possible subject to enabling a maximum beneficiary assignment. Therefore, the matching respects priorities and satisfies order preservation for qc1u = qcu and qc2u = 0. Remark 5.5 (Non-uniqueness of over-and-above). The outcome of the over-and-above rule is not necessarily the unique matching satisfying (i) to (v) with qc1u = qcu and qc2u = 0. Let N = {1, 2, 3, 4} and C = {c1 u, c1, c2} with each category having capacity 1. Suppose the priorities are 4 c1u 3 c1u 2 c1u 1 c1u , 4 c1 2 c1 , and 3 c2 1 c2 . Then, the outcome of the over and above rule is {{4, c1 u}, {2, c1}, {3, c2}}. Another matching that satisfies the properties is {{3, c1 u}, {4, c1}, {1, c2}}. Aziz & Brandl S REV π Smart Reserves DA compliance with eligibility requirements maximum beneficiary assignment respect of priorities respects improvements n/a order preservation polynomial-time computability Table 1: Properties satisfied by S REV π, the Smart Reserves rule of Pathak et al. (2020, 2023), and the Deferred Acceptance algorithm described in Remark 4.5. An asterisk indicates that the property holds if priorities are strict and consistent with the baseline ordering. N/a indicates that the rule assumes homogenous priorities but the property allows for changes in the priorities that may result in inhomogeneous priorities. 5.2 The Smart Reverse Rejecting Rule The Smart Reserves rule of Pathak et al. (2020, 2023) gives agents the unreserved units from c1 u as long as the set of remaining agents can be matched to get a maximum beneficiary assignment. Whereas Reverse Rejecting rules are not equipped to handle unreserved categories, the Smart Reserves rule is not designed to handle heterogeneous priorities. The ideas of both approaches can be combined to obtain the Smart Reverse Rejecting (S REV π) rule. S REV π first determines which agents get an unreserved unit from c1 u, then allocates the units reserved for preferential categories to the remaining agents using the REV π rule, and gives the c2 u units to the remaining agents according to the baseline ordering. More precisely, S REV π works as follows. Let the set of agents to be given unreserved units from c1 u, N1, be empty at the start and consider the agents in order of the baseline ordering in descending order. When agent i is considered, add i to N1 if N1 contains fewer than qc1u agents and the agents in N \ (N1 {i}) can form a maximum beneficiary assignment. After the last agent has been considered, give each agent in N1 an unreserved unit from c1 u. Use REV π to allocate the units reserved for the preferential categories Cp to the remaining agents. Lastly, give the unreserved units from c2 u to the remaining agents in descending order of the baseline ordering. We show that S REV π preserves the properties of REV π while allowing to treat reserved and unreserved units asymmetrically. Note that part of S REV π is applying the Reverse Rejecting rule for the baseline order π rather than some arbitrary order over agents. This is required for S REV π to respect improvements. Table 1 summarizes the properties of S REV π, the Smart Reserves rule, and the approach based on the Deferred Acceptance algorithm described in Remark 4.5. Theorem 5.6 (Properties of the Smart Reverse Rejecting rule). The S REV π rule (i) complies with eligibility requirements, Efficient and Fair Healthcare Rationing (ii) yields a maximum beneficiary assignment, (iii) respects priorities, (iv) respects improvements, (v) satisfies order preservation, and (vi) is polynomial-time computable. Proof. (i) and (ii) are clear by construction. Note that a maximum beneficiary assignment is a maximum size matching of agent to all categories in C = Cp {c1 u, c2 u} since every agent is eligible for c1 u and c2 u. (iii) We first prove that no unmatched agent can have justified envy for an agent matched to c1 u. Suppose an unmatched agent i has higher baseline priority than an agent j matched to c1 u. Then, i would have been considered before j when determining which agents get units from c1 u. The chosen matching shows that neither i nor the agents in N1 (at the time i was considered) are needed a form a maximum beneficiary assignment. Hence, i would have been added to N1 and received a unit from c1 u, which is a contradiction. Second, no unmatched agent can have justified envy towards an agent matched to c2 u because each unmatched agent comes later in the baseline ordering than each agent matched to c2 u. Finally, no unmatched agent can have justified envy towards an agent matched to a category in Cp as this would contradict the fact that REV π respects priorities. (iv) Suppose that i s priority decreases from I to I and i is unmatched under S REV π(I). We show that i is unmachted under S REV π(I ). We first show that agent i is not matched to c1 u under S REV π(I ). Each time an agent j is added to N1, it is because the agents in N \ (N1 {j}) can be matched to Cp to obtain a maximum beneficiary assignment. Since i is not matched under S REV π(I), i is not needed to obtain a maximum beneficiary assignment for I, which implies that i is not needed to obtain a maximum beneficiary assignment for I . Hence, i cannot affect the selection of agents preceding her in the baseline ordering that are added to N1 and hence matched to c1 u. Since i is not matched to c1 u under S REV π(I), it means that when i was considered to be added to N1, the qc1u units of c1 u had already been used up. Therefore, i cannot get matched to c1 u under S REV π(I ). We have shown that i cannot affect the set N1, that is, which agents are matched to c1 u. Since i is not matched to a category in Cp under S REV π(I) and REV π respects improvements, i is not matched to a category in Cp under S REV π(I ) . To show that i is not matched to c2 u under S REV π(I ), we observe the following. (i) Since agent i is not matched to a category in Cp under S REV π(I) and REV π yields a maximum size matching, agent i cannot affect the number of agents matched to categories in Cp. (ii) As observed in the proof that REV π respects improvements, the set of agents lower in the baseline ordering (who compete with i to be matched to c2 u) is the same under I and I .16 16. This is the only point in the proof where we use that the Reverse Rejecting rule parameterized by the baseline ordering is used. Aziz & Brandl The above two facts imply that the number of agents higher up baseline ordering than i who are not matched to a category in Cp {c1 u} and hence compete to be matched to c2 u is the same under I and I . Therefore, i is not matched to c2 u under S REV π(I ). (v) Consider a matching µ returned by S REV π. Suppose it does not satisfy order preservation. Then there exist two agents i, j N such that one of the following holds: (i) µ(i) = c1 u, µ(j) = c1 u, j µ(i) i, and i is eligible for category µ(j). (ii) µ(j) = c2 u, µ(i) Cp {c1 u}, j µ(i) i, and j is eligible for category µ(i). We first consider the violation of the first type: µ(i) = c1 u, µ(j) = c1 u, j π i, and i is eligible for category µ(j). We examine the step at which i is considered when determining which agents get units from c1 u. Since µ(i) = c1 u, agent i is added to N1. Thus, a maximum beneficiary assignment of the agents in N \ (N1 {i}) exists. One such matching is µ. The matching µ obtained from µ by swapping the matches of i and j is a maximum beneficiary assignment (since i is eligible for µ(j)) for the agents in N \(N1 {j}). Since j π i and N1 weakly increases in every step, N1 cannot have been larger when the algorithm considered agent j. Hence, at this earlier step, µ was also a maximum beneficiary assignment for agents in N \ (N1 {j}). But the existence of such a matching is the condition for adding j to N1, which contradicts that µ(j) = c1 u. Next we consider a violation of the second type: µ(j) = c2 u, µ(i) Cp {c1 i }, j π i, and j is eligible for category µ(i). Since a violation of the first type cannot happen, we may assume that µ(i) Cp. But since j is not matched to a category in Cp, this implies that the REV rule does not respect priorities, a contradiction. (vi) When agents are added iteratively to N1, the algorithm requires checking if there exists a maximum beneficiary assignment of agents in N \(N1 {i}). This can be checked in polynomial time by algorithms for computing a maximum size b-matching. Once N1 is fixed, we call the REV rule, which we have already shown to be polynomial-time computable. After that the remaining units can be allocated in linear-time by going down the baseline ordering. Remark 5.7 (Soft reserves). We assumed that only matchings that satisfy the eligibility requirements are feasible. The disadvantage of this approach is that some preferential category units may not be utilized even though some agents are unmatched. If we do not impose eligibility requirements as hard constraints, the setting is referred to as the case of soft reserves . In that case, we can first compute a matching that complies with the eligibility requirements using S REV π. If the resulting matching leaves some units from Cp unassigned, we allocate those to unmachted agents in order of the baseline ordering π. Assuming the preferential categories priorities over ineligible agents are consistent with the baseline ordering, the resulting rule satisfies all the properties in Theorem 5.6 except for hard compliance with the eligibility requirements. It also respects improvements by an argument similar to the proof of Theorem 5.6(iv). (Decreasing the priority of an agent does not affect the number of unmatched agents higher up in the baseline ordering.) The natural analog of Theorem 4.4 to the setting with unreserved units a matching complies with the eligibility requirements, respects priorities, is a maximum beneficiary Efficient and Fair Healthcare Rationing assignment, and satisfies order preservation if and only if it is a possible outcome of S REV π for some baseline ordering π fails. This is because order preservation is defined relative to a baseline ordering, leaving no freedom in choosing an ordering to be used for S REV π. Acknowledgements This material is based on work supported by the Deutsche Forschungsgemeinschaft under the Excellence Strategy EXC-2047 and the Grant BR 5969/1-1 and by the NSF-CSIRO grant on Fair Sequential Collective Decision-Making (Grant No. RG230833). An extended abstract of this paper appeared in the proceedings of the 22nd ACM Conference on Economics and Computation (2021). The authors thank Adi Ganguly, Tayfun S onmez, and the participants of the following events for helpful comments: Online Social Choice and Welfare Seminar Series, Hong Kong Summer School on Game Theory and Social Choice, Bonn BGSE Workshop, and COMSOC Video Seminar. The authors are furthermore indebted to the editor and anonymous referees for their constructive feedback. Abdulkadiro glu, A., & S onmez, T. (2003). School choice: A mechanism design approach. American Economic Review, 93(3), 729 747. Abdulkadiro glu, A., & S onmez, T. (2003). Ordinal efficiency and dominated sets of assignments. Journal of Economic Theory, 112(1), 157 172. Abraham, D., Blum, A., & Sandholm, T. (2007). Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM Conference on Electronic Commerce (ACM-EC), pp. 295 304. ACM Press. Ahmadi, S., Ahmed, F., Dickerson, J. P., Fuge, M., & Khuller, S. (2020). An algorithm for multi-attribute diverse matching. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pp. 3 9. Ahmed, F., Dickerson, J. P., & Fuge, M. (2017). Diverse weighted bipartite b-matching. In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pp. 35 41. AAAI Press. Andersson, T., & Ehlers, L. (2020). Assigning refugees to landlords in sweden: Efficient, stable, and maximum matchings. The Scandinavian Journal of Economics, 122(3), 937 965. Ayg un, O., & B o, I. (2020). College admission with multidimensional privileges: The Brazilian affirmative action case. American Economic Journal: Microeconomics. Ayg un, O., & Turhan, B. (2020). Dynamic reserves in matching markets: Theory and applications. Journal of Economic Theory, 188. Aziz, H. (2018). Mechanisms for house allocation with existing tenants under dichotomous preferences.. Journal of Mechanism and Institution Design. Aziz, H. (2020). Developments in multi-agent fair allocation. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 13563 13568. Aziz & Brandl Aziz, H., Bir o, P., & Yokoo, M. (2022). Matching market design with constraints. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 12308 12316. Aziz, H., Gaspers, S., & Sun, Z. (2020). Mechanism design for school choice with soft diversity constraints. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pp. 153 159. Balinski, M., & S onmez, T. (1999). A tale of two mechanisms: Student placement. Journal of Economic Theory, 84(1), 73 94. Bir o, P., Fleiner, T., Irving, R. W., & Manlove, D. F. (2010a). The college admissions problem with lower and common quotas. Theoretical Computer Science, 411(34), 3136 3153. Bir o, P., Manlove, D. F., & Mittal, S. (2010b). Size versus stability in the marriage problem. Theoretical Computer Science, 411(16-18), 1828 1841. Bognar, G., & Hirose, I. (2014). The Ethics of Health Care Rationing: An Introduction. Routledge. Bogomolnaia, A., & Moulin, H. (2015). Size versus fairness in the assignment problem. Games and Economic Behavior, 90, 119 127. Bruce, L., & Tallman, R. (2021). Promoting racial equity in covid-19 resource allocation. Journal of Medical Ethics. Das, S. (2022). Local justice and the algorithmic allocation of scarce societal resources. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pp. 12250 12255. AAAI Press. Dawson, A., Isaacs, D., Jansen, M., Jordens, C., Kerridge, I., Kihlbom, U., Kilham, H., Preisz, A., Sheahan, L., & Skowronski, G. (2020). An ethics framework for making resource allocation decisions within clinical care: Responding to covid-19. Journal of Bioethical Inquiry, 17(4), 749 755. Dickerson, J. P., Sankararaman, K. A., Srinivasan, A., & Xu, P. (2019). Balancing relevance and diversity in online bipartite matching via submodularity. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, pp. 1877 1884. Dur, U., Kominers, S. D., Pathak, P. A., & S onmez, T. (2018). Reserve Design: Unintended Consequences and the Demise of Boston s Walk Zones. Journal of Political Economy, 126(6), 2457 2479. Dur, U., Pathak, P. A., & S onmez, T. (2020). Explicit vs. statistical targeting in affirmative action: Theory and evidence from Chicago s exam schools. Journal of Economic Theory, 187, 104996. Echenique, F., & Yenmez, M. B. (2015). How to control controlled school choice. American Economic Review, 105(8), 2679 94. Ehlers, L., Hafalir, I. E., Yenmez, M. B., & Yildirim, M. A. (2014). School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory, 153, 648 683. Efficient and Fair Healthcare Rationing Emanuel, E. J., Persad, G., Upshur, R., Thome, B., Parker, M., Glickman, A., Zhang, C., Boyle, C., Smith, M., & Phillips, J. P. (2020). Fair allocation of scarce medical resources in the time of covid-19. New England Journal of Medicine, 382(21), 2049 2055. Fink, S. (2020). The hardest questions doctors may face: Who will be saved? who won t?. The New York Times, March 21. Galanter, M. (1961). Equality and protective discrimination in India. Rutgers Law Review, 16(1), 42 74. Galanter, M. (1984). Competing Equalities: Law and the Backward Classes in India. Univ of California. Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9 15. Gonczarowski, Y. A., Nisan, N., Kovalio, L., & Romm, A. (2019). Matching for the Israeli Mechinot gap year: Handling rich diversity requirements. In Proceedings of the 20th ACM Conference on Economics and Computation, pp. 321 321. Goto, M., Iwasaki, A., Kawasaki, Y., Kurata, R., Yasuda, Y., & Yokoo, M. (2016). Strategyproof matching with regional minimum and maximum quotas. Artificial intelligence, 235, 40 57. Grigoryan, A. (2020). Effective, fair and equitable pandemic rationing. Tech. rep. 3646539, SSRN. Hafalir, I. E., Yenmez, M. B., & Yildirim, M. (2013). Effective affirmative action in school choice. Theoretical Economics, 8(2), 325 363. Heo, E. J. (2019). Equity and diversity in college admissions. In Laslier, J., Moulin, H., Sanver, R., & Zwicker, W. (Eds.), The Future of Economic Design. Springer. Hopcroft, J. E., & Karp, R. M. (1973). An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2(4), 225 231. Kamada, Y., & Kojima, F. (2015). Efficient matching under distributional constraints: Theory and applications. The American Economic Review, 105(1), 67 99. Kamada, Y., & Kojima, F. (2017). Recent developments in matching with constraints. The American Economic Review, 107(5), 200 204. Karzanov, A. V. (1973). An exact estimate of an algorithm for fnding a maximum flow, applied to the problem on representatives. Problems in Cybernetics, 5, 66 70. Kojima, F. (2019). New directions of study in matching with constraints. In Laslier, J.-F., Moulin, H., Sanver, R., & Zwicker, W. S. (Eds.), The Future of Economic Design. Springer-Verlag. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1 2), 83 97. Kurata, R., Hamada, N., Iwasaki, A., & Yokoo, M. (2017). Controlled school choice with soft bounds and overlapping types. Journal of Artificial Intelligence Research, 58, 153 184. Aziz & Brandl Martin, E. (2015). Rationing in healthcare. Tech. rep. 8, Deeble Institute. NASEM-National Academies of Sciences, Engineering, and Medicine (2020). Framework for Equitable Allocation of COVID-19 Vaccine. Tech. rep., Washington, DC. Pathak, P. A., S onmez, T., Unver, M. U., & Yenmez, M. B. (2020). Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Health Care Rationing. Boston college working papers in economics 1015, Boston College Department of Economics. Pathak, P. A., S onmez, T., Unver, M. U., & Yenmez, M. B. (2023). Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Healthcare Rationing. Management Science. Persad, G., Peek, M. E., & Emanuel, E. J. (2020). Prioritizing groups for access to covid-19 vaccines. JAMA, 324(16), 1601 1602. Roth, A. E., & Sotomayor, M. A. O. (1990). Two-Sided Matching: A Study in Game Theoretic Modelling and Analysis. Cambridge University Press. S onmez, T., Pathak., P. A., Unver, M. U., Persad, G., Truog, R. D., & White, D. B. (2020). Categorized priority systems: A new tool for fairly allocating scarce medical resources in the face of profound social inequities. CHEST. S onmez, T., & Yenmez, M. B. (2020). Affirmative action with overlapping reserves. Manuscript. Sonmez, T., & Yenmez, M. B. (2022). Affirmative Action in India via Vertical, Horizontal, and Overlapping Reservations. Econometrica, 1143 1176. Sonmez, T., & Yenmez, M. B. (2024). Constitutional Implementation of Affirmative Action Policies in India. Tech. rep., ar Xiv. Truog, R. D., Mitchell, C., & Daley, G. Q. (2020). The toughest triage allocating ventilators in a pandemic. New England Journal of Medicine, 382(21), 1973 1975. WHO (2020). A global framework to ensure equitable and fair allocation of COVID-19 products and potential implications for COVID-19 vaccines.. Tech. rep..