Fairness criteria for allocating scarce resources

Singh, Bismark Article — Published Version Fairness criteria for allocating scarce resources Optimization Letters Provided in Cooperation with: Springer Nature Suggested Citation: Singh, Bismark (2020) : Fairness criteria for allocating scarce resources, Optimization Letters, ISSN 1862-4480, Springer, Berlin, Heidelberg, Vol. 14, Iss. 6, pp. 1533-1541, https://doi.org/10.1007/s11590-020-01568-1 This Version is available at: https://hdl.handle.net/10419/288726 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ Optimization Letters (2020) 14:1533–1541 https://doi.org/10.1007/s11590-020-01568-1 ORIGINAL PAPER Fairness criteria for allocating scarce resources Bismark Singh1 Received: 15 June 2019 / Accepted: 4 March 2020 / Published online: 13 March 2020 © The Author(s) 2020 Abstract We develop an optimization model to provide a fair allocation of multiple resources to multiple users. All resources might not be suitable to all users. We develop a notion of fairness, and then provide a general class of functions achieving it. Next, we develop more restricted notions of fairness—special cases of which exist in literature. Finally, we distinguish between scarce and abundant resources, and show that if a resource is abundant, all users seeking it achieve the maximum possible coverage. Keywords Proportional fairness ·Equity ·Optimization ·Welfare ·Resource allocation ·KKT conditions Notation Sets and indices i∈ITypes of users k∈KTypes of resources i∈IkSubset of users eligible to receive resource k k∈KiSubset of resources eligible for user i Data and parameters niPopulation of user i,ni>0 bkAmount of resource k,bk>0 fiOriginal coverage of user i,0≤fi<1 wiWeight of user i,wi>0 Decision variables xik Amount of resource kallocated to user i yiFinal coverage of user i BBismark Singh [email protected] 1Discrete Mathematics, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany 123 1534 B. Singh 1 Background We study the problem of allocating different kinds of substitutable resources to different populations seeking them. This is related to a fundamental problem in economics—how should different resources be produced and made available to agents; see, e.g., [10]. Our aim is to allocate resources in a fair manner, a term we make precise below, and we develop a class of optimization models that achieve specific notions of fairness. This work finds applications in resource allocation problems that have been studied in specific settings; see, e.g., distribution of coal among power companies [2], several military and defense examples [11], multiperiod manufacturing of high-tech products [12], wireless networks [9], healthcare [6], education [3], and conservation of threatened species [8]. Special cases of this general problem include the so-called waterfilling algorithm; see, e.g., [13]. We present general results, based on the KKT optimality conditions, that provide essential conditions for fair allocation of resources, as well as special cases in which resources are abundant. For an introduction to resource allocation problems, see, e.g., [7]. An excellent introduction to different concepts in fairness is available in Bertsimas et al. [1]. Similar to our study, the authors consider a central decision planner seeking to allocate resources in a “fair” manner. The authors describe several concepts of fairness based on utilities of each user, and primarily distinguish between max-min fairness and proportional fairness. Our work differs from this existing body of literature in the following sense. We do not seek to maximize utilities, but rather to ensure equitable coverages (or, shortages) when allocating scarce resources with varying priorities (or, claims) for users. Bertsimas et al. [1] call this as an Aristotle’s equity principle, which they do not analyze; see also [4,14]. To this end, we develop mathematical models and analyze their properties under specific notions of fairness that are significantly different from the existing literature. As with Aristotle’s equity principle, our models serve to answer the question: how should allocation decisions be conducted when resources are due to users with pre-existing claims? 2 Mathematical models for fairness We consider a set of user types (henceforth simply users), i∈I, seeking a set of resources, k∈K. Define a subset of resources, k∈Ki, as the set of resources that user iis eligible to receive. Define a subset of users, i∈Ik, as the set of users that are eligible to receive resource k. Define the population of user iand an associated weight as ni>0 and wi>0, ∀i∈I, respectively, and the availability of resource k as bk>0, ∀k∈K. The prior coverage of user iis denoted by 0 ≤fi<1, where we assume fiis defined relative to the same population of size ni.Letxik ≥0bethe amount of discretionary resource kallocated to user i. We denote the final coverage, after allocation of all resources, by yi, where fi≤yi≤1. Our resources are partially substitutable in the sense that user iis equally able to make use of any resource in Ki, but can make no use of a resource in K\Ki. 123 Fairness criteria for allocating scarce resources 1535 Consider the following optimization model: min x,y i∈I winiF(yi)(1a) s.t.  i∈Ik xik ≤bk,∀k∈K:νk(1b) fi+1 ni k∈Ki xik =yi,∀i∈I:αi(1c) yi≤1,∀i∈I:λi(1d) xik ≥0,∀k∈Ki,i∈I,:−μik,(1e) where F:[0,1]→Ris a loss function. The dual multipliers indicated in constraints (1b)–(1e) satisfy νk≥0,λ i≥0 and μik ≥0, respectively. Model (1) provides an optimal allocation, denoted x∗ ik, and, in turn, the optimal final coverage of each user population, denoted y∗ i=fi+n−1 ik∈Kix∗ ik. The objective function in model (1) seeks to minimize the weighted sum of the users’ loss values. Constraint (1b) ensures that the allocated resources of type kdo not exceed what is available. Constraints (1c) and (1d) indicate that the maximum final coverage is at most 1 for every user type. Constraint (1e) ensures non-negative allocation of resources. In the rest of this article, we drop the superscript, (·)∗, on the optimal solution for simplicity. We start with the following notion of priority which is fundamental to our notions of fairness. Definition 1 (Priority) In an optimal solution to model (1)ifwi≥wi, then iis said to have a priority over i.Ifihas a priority over iand yi≤yi(with at least one inequality strict), then ihas an inappropriate priority, denoted by ii;while,if ihas a priority over iand yi≥yi(with at least one inequality strict) then ihas an appropriate priority, denoted by i≫i. In the above definition, “with at least one inequality strict” means that both the weights and the coverages cannot be equal. Definition 1distinguishes two kinds of priorities. “Inappropriate” can be understood as follows: a user has a larger weight, but receives a lower coverage; “Appropriate” refers to a larger weight and a larger coverage. Excluding the trivial case of wi=wi,yi=yi, we have the following four exclusive cases (i) ii, (ii) ii, (iii) i≫i,or(iv)i≫i. In Sect. 2.1,we study the first two cases, while in Sect. 2.2 we study the latter two. 2.1 Fairness: inappropriate priorities Definition 2 (Fairness) In an optimal solution to model (1)ifiiimplies xik =0 for all k∈Ki∩Kiand all i,i∈Iwith yi<1, then the solution is said to be fair. We can interpret Definition 2by understanding whether the inappropriately prioritized user ican “complain” about the allocation given to user i; i.e., the distribution being not fair. According to Definition 2,userican have a justifiable complain only if: (a) user ihas coverage less than 100%, (b) there is a user, i, over which ihas 123 1536 B. Singh an inappropriate priority, and (c) user ireceived positive allocation from a resource shared with user i. The following theorem provides a class of functions, F(·), that provide fairness for model (1). Theorem 1 If F :[0,1]→Ris continuously differentiable, decreasing, and strictly convex, then optimization model (1) achieves fairness. Proof The feasible region of model (1) is nonempty and compact, and hence the model has a finite optimal solution. The constraints are linear, and Fis differentiable and convex, and so an optimal solution is characterized by the KKT conditions of primal feasibility, i.e., constraints (1b)–(1e) along with multipliers that satisfy the following conditions: λi+αi+winiF(yi)=0,∀i∈I(2a) νk−αi ni −μik =0,∀k∈Ki,i∈I(2b) νk≥0,∀k∈K,λ i≥0,∀i∈I,μ ik ≥0,∀k∈Ki,i∈I(2c) and νk⎛ ⎝ i∈Ik xik −bk⎞ ⎠=0,∀k∈K(3a) αi⎛ ⎝fi+1 ni k∈Ki xik −yi⎞ ⎠=0,∀i∈I(3b) λi(yi−1)=0,∀i∈I(3c) μikxik =0,∀k∈Ki,i∈I.(3d) Because Fis strictly convex and decreasing, we have wiF(yi)≥wiF(yi), with strict inequality if either yi>yior wi>w i.(4) Assume that the optimal solution is not fair. Hence, there exists at least one user pair, with ii,yi<1, and with k∈Ki∩Ki=∅such that xik >0. From the complementary slackness conditions (3c) and (3d), we have λi=0 and μik =0. From Eqs. (2a) and (2b), we obtain wiF(yi)=−νk−λi niand wiF(yi)= μik−νk. Thus, wiF(yi)+λi ni+μik=wiF(yi), and because λi,μ ik≥0, we have wiF(yi)≤wiF(yi). Given that yi>yior wi>w i, inequality (4) implies the contradiction of wiF(yi)>w iF(yi). Examples of functions that satisfy the hypothesis of Theorem 1include F(z)= (1−z)m, where m>1; F(z)=−ln(z+ε), where ε>0; and, F(z)=e−z. 123 Fairness criteria for allocating scarce resources 1537 2.2 Proportional fairness: appropriate priorities The previous notion of fairness covers the case of inappropriate priorities. A stronger notion of fairness can be developed by a slight change in the definition of fairness. This encompasses the case when the prioritized user ireceives a larger coverage than i; i.e., the priority is appropriate. We term this notion as proportional fairness. Before we explain the motivation for this term, we define another term as follows. Definition 3 (Balance) An optimal solution to model (1) satisfying wiF(yi)= wiF(yi)is said to be balanced between users iand i. In other words, a balance between two users requires their marginal losses to be in inverse proportion to their weights. The following lemma proves that excluding the trivial case of wi=wi,yi=yi, only an appropriate priority could result in a balanced coverage. Lemma 1 Let F :[0,1]→Ris continuously differentiable, decreasing, and strictly convex. Then, an optimal solution to model (1) with an inappropriate priority cannot be balanced. Proof Since wi,w  i>0 and Fis decreasing, wiF(yi)=wiF(yi)cannot hold if either ior ihas an inappropriate priority.  Definition 4 (Proportional fairness) Consider a balanced optimal solution to model (1). If yi<1 and xik >0fork∈Ki∩Kiimplies and is implied by yi<1 and xik>0, then the solution is said to be proportionally fair between user i and i. This stronger notion encompasses the situation when a user has an appropriate priority, did not receive 100% coverage, and yet the other user received a positive allocation of the shared resource. According to Definition 4, a user ican have a justifiable complain only if: (a) ihas coverage less than 100%, (b) another user, i, received a positive allocation from a resource shared with i, (c) the coverages of the two users are balanced, and (d) idid not receive any allocation of this shared resource or user ireceived 100% coverage. We note from Lemma 1that statement (c) can hold only for the case of appropriate priorities. The following theorem shows that the same class of functions as Theorem 1,but with an additional condition, provide proportional fairness for model (1). Theorem 2 Let F :[0,1]→Ris continuously differentiable, decreasing, and strictly convex. If an optimal solution to model (1) is balanced and satisfies strict complementary slackness, then it is proportionally fair. Proof The proof is similar to that of Theorem 2. Equations (2a) and (2b) yield wiF(yi)+λi ni −μik =wiF(yi)+λi ni −μik. From Definition 4, consider an (i,i)pair satisfying yi<1 and xik >0fork∈ Ki∩Ki. We prove that yi<1 and xik>0. Because the optimal solution satisfies 123 1538 B. Singh strict complementary slackness yi<1 implies λi=0 and xik >0 implies μik =0. Since the solution is balanced, we have μik=− λi ni. Because the dual multipliers are non-negative, strict complementary slackness further implies yi<1 and xik>0.  Most interior point algorithms yield solutions that satisfy strict complementary slackness; see, e.g., [16]. Also note, the assumption of differentiability ensures we can compute the gradients of F, and the assumption of convexity on Fensures the KKT conditions are necessary and sufficient. We thus have the following central results for model (1) for the chosen class of F: 1. An optimal solution with an inappropriate priority is fair. 2. An optimal balanced solution with an appropriate priority that satisfies strict complementary slackness is proportionally fair. 2.3 Scarce and abundant resources We define a resource kto be abundant if i∈Ikxik is strictly less than bk, and scarce if i∈Ikxik is equal to bk. Since Fis decreasing, we expect that if bkis sufficiently large, all users sharing resource kachieve 100% coverage; i.e., yi=1,∀i∈Ik. Since this is the maximum possible coverage, no user should complain; the hypotheses of both Definitions 2and 4are not satisfied and there is no concept of fairness. However, if there exists even a single user with less than 100% coverage, then we expect a complete allocation of all resources the user is eligible for. And then, the user can justifiably complain and seek fairness. The following theorem makes this precise. Theorem 3 Abundant resources: In an optimal solution to model (1), if resource k is not completely allocated, i.e., i∈Ikxik <bk, then yi=1,∀i∈Ik. Scarce resources: In an optimal solution to model (1), if yi<1for some i ∈I , then i∈Ikxik =bk,∀k∈ Ki. Proof Abundant resources: Consider a resource k∈Ksuch that i∈Ikxik <bk. From Eq. (3a), we have νk=0. Assume that there exists some i∈Ikwith yi< 1. Then, by Eq. (3c), we have λi=0. From Eqs. (2a) and (2b) we have for this (i,k):μik =wiF(yi). Since F(yi)<0 and wi>0, we have μik <0 which is a contradiction of Eq. (2c). Scarce resources: Assume that there exists some i∈Ikwith yi<1. Then, by Eq. (3c), we have λi=0. From Eqs. (2a) and (2b), we have for all kin Ki:μik −νk= wiF(yi). Since wi>0,F(yi)<0 and μik ≥0, we have νk>0. From Eq. (3a)we have i∈Ikxik =bk,∀k∈Ki. The proof of Theorem 3uses the KKT conditions for model (1). However, we can also prove the same without requiring the assumptions of convexity or differentiability. Consider an optimal solution, (x∗,y∗), and resource kis abundant. Assume that yi<1forsomei∈Ik. We show that this is not possible. Consider another solution, (x,y), as follows: x ik=x∗ ik+δand x ik =x∗ ik for all other (i,k)pairs; y i=y i+δ ni and y i=y∗ ifor all other i.Here0<δ<min{bk−i∈Ikx∗ ik,ni(1−y∗ i)}. Then, this solution is feasible to model (1). Further, since Fis decreasing and y i>y∗ i,we 123 Fairness criteria for allocating scarce resources 1539 Table 1 Mapping between model (1) and model (3.1) of [15] Model (1) Model (3.1) of [15] i∈I(i,j)∈(I×J) k∈Kk∈K i∈Ik– k∈Kik∈Kj ninij bkbk fifij,or k∈Kjmijk nij wiwij xik Qijk yifij +k∈KjQijk nij ,or1−sij have F(y i)<F(y∗ i). This contradicts the hypothesis that (x∗,y∗)is optimal. The analogous proof for scarce resources mirrors this. 3 A motivating example This research was motivated by a collaboration with the Texas Department of State Health Services, aimed at allocating a limited amount of vaccines in an equitable manner during an influenza pandemic [5,6,15]. Here, we use model (3.1) from [15]to allocate four types of vaccines to five different population groups seeking them. In this example, vaccines are scarce at the start of the pandemic. The allocation ensures an equitable access to vaccines across all five population priority groups in 254 different counties of Texas. Vaccine types constitute our “resources” and the five priority groups across the 254 counties of Texas constitute our “users”. Table 1presents a map between our notation and that of [15]. Singh’s optimization model in [15] presents a special case of model (1), with F(yi)=(1−yi)2. A similar loss function is used in [5,6]. This loss function, F(z)=(1−z)2, satisfies the hypothesis of Theorem 2and hence achieves fairness for inappropriately prioritized users per Definition 2. Next, Theorem 3.2.1 of [15] provides sufficient conditions for a balanced solution wiF(yi)=wiF(yi):(i) yi<1 and yi<1, and (ii) xik >0 and xik>0forsomek∈Ki∩Ki. Then, the solution is proportionally fair per Definition 4for the given loss function. Singh [15] thus proves the special cases of inappropriate priorities and appropriate priorities with balance, using the quadratic loss function. 4 Conclusion We develop a general optimization model to study the allocation of partially substitutable resources to different classes of users seeking them. Not all resources are suitable to all classes of users, and different classes of users have different priorities. 123 1540 B. Singh When a resource is abundant, all users seeking it achieve the maximum possible coverage. When resources are scarce, we provide different notions of fairness depending on the priorities between users. And, we provide a class of objective functions as well as restrictions that achieve these notions of fairness. Inappropriate priorities always result in fairness. Appropriate priorities, with two additional restrictions of balance and complementary slackness, always result in proportional fairness. Future research could establish what happens when these two restrictions are not met, as well as sufficient and/or necessary conditions to guarantee a balanced solution. Finally, we demonstrate how our model is reducible to an existing model for equitable allocation of vaccines during an influenza pandemic. Acknowledgements Open Access funding provided by Projekt DEAL. I sincerely thank David Morton for helpful and long discussions as well as for structuring this article. I also thank an anonymous reviewer for correcting an error in an earlier version of a proof. Anything overlooked in the manuscript is, of course, my responsibility. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References 1. Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17–31 (2011) 2. Brown, J.R.: The sharing problem. Oper. Res. 27(2), 324–340 (1979) 3. Byrne, E.M.: Planning and educational inequality: a study of the rationale of resource-allocation. Tech. rep., ERIC (1974) 4. Hoffman, R.L.: Defining, measuring, and implementing equity. Tech. rep., Metron Aviation (2003) 5. Huang, H.C.: Stockpiling and resource allocation for influenza preparedness and manufacturing assembly. Ph.D. thesis, The University of Texas at Austin (2014) 6. Huang, H.C., Singh, B., Morton, D.P., Johnson, G.P., Clements, B., Meyers, L.A.: Equalizing access to pandemic influenza vaccines through optimal allocation to public health distribution points. PloS One 12(8), e0182720 (2017) 7. Ibaraki, T., Katoh, N.: Resource allocation problems: algorithmic approaches. MIT Press, Cambridge (1988) 8. Joseph, L.N., Maloney, R.F., Possingham, H.P.: Optimal allocation of resources among threatened species: a project prioritization protocol. Conserv. Biol. 23(2), 328–338 (2009) 9. Julian, D., Chiang, M., O’Neill, D., Boyd, S.: QoS and fairness constrained convex optimization of resource allocation for wireless cellular and ad hoc networks. In: Proceedings Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, pp. 477–486 (2002). https://doi.org/10.1109/INFCOM.2002.1019292 10. Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manag. Sci. 6(4), 366–422 (1960) 11. Kaplan, S.: Application of programs with maximin objective functions to problems of optimal resource allocation. Oper. Res. 22(4), 802–807 (1974) 12. Klein, R.S., Luss, H., Rothblum, U.G.: Multiperiod allocation of substitutable resources. Eur. J. Oper. Res. 85(3), 488–503 (1995) 123