Dominant Resource Fairness with Meta-Types

1 Introduction

The recent COVID-19 pandemic has brought forward many problems that are particularly relevant to the operations research and computer science communities. Among them, an often overlooked problem is the effective and fair allocation of resources, such as volunteer medical workers, ventilators, and emergency field hospital beds.

There are several key challenges to the medical resource allocation problem in the face of an infectious disease outbreak. First, utilities from different types of resources are not additive nor linear. For example, when there are enough nurses but not enough doctors, the marginal utility of having one additional nurse on staff is very low. Second, not all resources are accessible to all hospitals (referred to henceforth as accessibility constraints). For instance, the home location of each volunteer medical worker determines where she can commute to work; thus, she can only be assigned to hospitals within her commutable radius. Third, hospitals have different capacities (big medical centers versus small hospitals) and are in different stress levels (hospitals in an epicenter versus the ones in rural areas with few cases), so they should naturally be prioritized differently.

∗Contact Author

Another setting that has the above characteristics is the compute resource sharing problem with sub-types. For example, suppose a compute server has several compute nodes, and there are different types of GPU/CPU on the various nodes (e.g. NVIDIA vs. AMD GPU, Intel vs. AMD CPU). Some users look for specific hardware configurations (e.g. accept only Intel CPU) while others might be less selective (e.g. accept all CPU brands).

In this paper, we propose a new market mechanism that tackles the three challenges outlined above and achieves desirable properties including Pareto optimality, envy-freeness, strategy-proofness, and sharing incentive. In our numerical experiments, we demonstrate that compared to the Maximum Nash Welfare (MNW), and the Discrete MNW approach, our mechanism is cheaper to compute and enjoys theoretical properties that MNW approaches do not have.

2 RelatedWork

Recently, a flurry of papers have come out of the operations research, statistics, and computer science communities addressing resource allocations in the aftermath of a pandemic. For instance, Jalota et al. [2020] proposed a mechanism for allocating public goods that are capacity constrained due to social distancing protocols, focusing on achieving a market clearing outcome. Mehrotra et al. [2020] studied the allocation of ventilators under a stochastic optimization framework, minimizing the expected number of shortages in ventilators while also considering the cost of transporting ventilators. Zenteno [2013] combined influenza modeling techniques with robust optimization to handle workforce shortfall in a pandemic. These papers differ from our work in that they do not explicitly address any fairness considerations that we study in this paper.

There has also been a growing interest in developing resource allocation mechanisms with fairness properties. Under a fairly general class of utility functions including the Leontief utility, computing market equilibrium under the fisher market setting (divisible goods) can be done using an Eisenberg-Gale (EG) convex program Eisenberg and Gale [1959]. Market equilibrium solutions satisfy Pareto optimality, proportionality, and envy-freeness. It is also known that an EG convex program implicitly maximizes Nash welfare, which is the product of all agents' utilities. However, MNW is generally not strategy-proof, and can be computationally expensive for large problems. Chen et al. [2006] studied the computation and approximation of market equilibria under the so-called "hybrid Linear-Leontief" utilities. They assume that there are m disjoint groups and each group contains several types of resources. An agent's utility is a linear combination of m Leontief utilities, each associated with a group. Note that although we use the terms "meta-type" and "group" in our problem formulation, our setting is different from theirs because there is only one Leontief utility per user in our setting.

For Leontief utilities, Ghodsi et al. [2011] introduced the Dominant Resource Fairness allocation mechanism (DRF) which in addition to the three properties satisfied by market equilibrium solutions, is also strategy-proof. Later Parkes et al. [2015] extended the setting to allow agents to be weighted and have zero demand over some resources while maintaining all four desiderata. Our paper generalizes the setting further by allowing accessibility constraints, which as mentioned in the introduction, arise naturally in many practical settings.

For indivisible resources, Caragiannis et al. [2019] showed that maximizing Nash welfare with integer constraints (Discrete MNW) satisfies envy-freeness up to one resource unit and has nice guarantees on the Max-Min Share ratio. However, similar to MNW, it is not strategy-proof and as we will see in the numerical section, it does not scale well to large number of agents and resource types. Although exact market equilibrium might not exist in indivisible settings, Budish [2011] showed that a close approximation of it exists in the unweighted, binary allocation case. This was later put into practice for course allocation in Budish et al. [2017]. However, the theory does not provide useful approximation bounds when assignments are not binary (e.g., each student only needs one seat from each class, but each hospital may require hundreds of doctors), and therefore it is not well suited to our setting.

3 ProblemFormulation

For the remainder of the paper we use local medical personnel allocation as a running example, even though other resource allocation problems can be formulated in a similar fashion. We group resources into meta-types: doctors, nurses, ventilators, emergency field hospital beds, etc. Within each meta-type (e.g. doctors), we have types (e.g. doctors from the Bronx, doctors from Brooklyn, doctors from Manhattan, etc. 1 ). We assume that demands are given over meta-types, but each agent sometimes can only receive allocation from a subset of the resources in a meta-type because of constraints such as location (e.g. a hospital is indifferent to where doctors assigned to it come from as long as they are within commutable radius). We refer to such subsets of resource types in each meta-type as the agents' demand groups.

1 Manhattan, the Bronx, and Brooklyn are three boroughs of New York City.

Let Ω1,Ω2, . . . ,ΩL denote the meta-types. Each metatype Ωl is a collection of resource types. We assume that Ωi ∩ Ωj = ∅ for any two different meta-types i, j, which means that each resource type belongs to exactly one metatype. Let R denote the set of all resource types: R = ∪l∈[L]Ωl, and N denote the set of agents. We use m = |R| and n = |N| to denote the total number of resource types and agents. Each type of resource r has a finite supply of Sr. We assume that the supplies are normalized within each meta-type:

Each agent i ∈ N submits a demand vector [di1, . . . , diL] where dil denotes the fraction of meta-type l that agent i needs in order to get one unit of utility (one can think of this as each agent trying to complete as many units of work as possible, where each unit of work requires dil units of metatype l). Additionally, each agent has access to only a subset of resource types within each meta-type. We represent this accessibility constraint in the form of a set of demand groups. Let Gi = {gi l ⊆ Ωl : l ∈ [L], dil > 0}, be the set of demand groups for agent i, where gi l ⊆ Ωl is agent i's demand group for l, specifying the subset of resource types belonging to meta-type l that agent i can access. Note that we only include in Gi meta-types that agent i has non-zero demand of. This is to simplify notation in the later analysis. Intuitively, the introduction of meta-types models the substitution effects, and the introduction of demand groups models the accessibility constraints. When i is clear from the context, we sometimes use gl instead of gi l to simplify the notation.

Following the setup in Parkes et al. [2015], we also allow agents to be weighted differently for each meta-type and we denote the weight of agent i for meta-type l as wil. Having different weights for different meta-types makes the model more expressive: if we let wi1 = . . . = wiL, then this reduces to having a single priority weight for each agent. This weight can depend on factors such as agent i's contribution to the resource pool of meta-type l, as well as the size and stress level of agent i. In the case of medical supplies allocation, weights can represent how much each hospital is in need of extra resources. In the cloud compute setting, weights can represent how much money each user has paid for each metatype of resource. Note that weights are fixed apriori, not self reported by the agents, nor determined by the allocation algorithm. We assume that weights are normalized within each meta-type: ∑i∈N wil = 1 for l ∈ [L]. Note that weights represent agents' priorities over the meta-types, not agents' preferences. Therefore they do not appear in the agents' utility functions, as we will define next.

Let xi be the allocation vector of agent i: xir represents the assignment of resource type r to i. For each meta-type l, ∑r∈gi l xir is the fraction of the total supply of meta-type l that is assigned to agent i. The utility of agent i is then defined as:

Since agent i needs dil fraction of each meta-type l to finish one unit of work, ui(xi) is the total units of work that agent i can finish given allocation vector xi. This form of utility measure is called the Leontief utility.

We now give a concrete example, which is also illustrated in Figure 1. To keep the example simple we assume that each agent has the same weight over all meta-types: only one weight wi is defined for each agent i.

Example 1. Consider a case of three hospitals (agents) {1, 2, 3} and two resource meta-types. The first meta-type consists of two types of doctors (resource A, B), and the second consists of two types of nurses (resource C,D): Ω1 = {A,B},Ω2 = {C,D}. The normalized weights for the three hospitals are: w1 = w2 = 1 4 ,w3 = 12 . The supply for each type of doctor and nurse is 500. Thus, the total available units of each meta-type is 500 + 500 = 1000, and Sr = 500 1000 = 12 ∀r ∈ {A,B,C,D}. All three hospitals have access to both types of doctors but hospitals 1, 2 only have access to nurse type C while the third hospital only has access to nurse type D: G1 = {g1 1 = {A,B}, g1 2 = {C}},G2 = {g2 1 = {A, B}, g2 2 = {C}},G3 = {g3 1 = {A, B}, g3 2 = {D}}. For each unit of utility, hospital 1 demands 4 doctors and 1 nurse, hospital 2 demands 1 doctor and 4 nurses, and hospital 3 demands 1 doctor and 1 nurse. Since the total units of supply for each meta-type is 1000, d1 = [ 4 1000 , 1 1000 ], d2 = [ 1 1000 , 4 1000 ], d3 = [ 1 1000 , 1 1000 ].

3.1 Desirable Properties

Now we formally define the properties studied in this paper.

Pareto optimality. An allocation mechanism is Pareto optimal if compared to the output allocation x, there does not exist another allocation x′ where some agent is strictly better off without some other agent being strictly worse off: ∃i s.t. ui(x′i ) > ui(xi) =⇒ ∃j s.t. uj(x′j ) < uj(xj).

Weighted envy-freeness. Given an allocation xj for agentj, let ˜xi be the same allocation adjusted to agent i's weights and demand groups, i.e., ˜xir = xjr wil wjl for all r ∈ gi l , l ∈ [L], and ˜xir = 0 otherwise. ui (˜xi) - ui(xi) is how much i envies j. An allocation is weighted envy free if for any i, j ∈ N this quantity is non-positive, i.e.,

Intuitively, this means an agent prefers her allocation over the allocation of any other agent scaled by the weight ratios of the two agents. Note that since there is a separate weight for every meta-type l, the allocations for each resource type r is scaled according to the corresponding weight for the metatype that it belongs to.

Strategy-proofness. In the existing literature, agents can only be strategic by misreporting their demand vector. In our setting however, agents have the additional possibility of misreporting their accessibility constraints for the meta-types (e.g. One can report that she accepts both Intel and AMD CPUs but in fact her program only runs on Intel CPU). Our definition of strategy-proofness guards against both types of misreporting. Let x be the allocation returned by the mechanism under truthful reporting from all agents. Let x′ be an allocation returned by the mechanism when all agents report truthfully except agent i reports an alternative demand vector and/or alternative demand groups. The mechanism is strategy-proof if ui(xi) ≥ ui(x′i ).

Sharing incentive. In settings where the supplies for each resource come from the participants' contribution, sharing incentive is satisfied when the resulting allocation gives each participant at least as much utility as she originally had. More specifically, for each i ∈ N and l ∈ [L], let sil be the proportion of meta-type l contributed by agent i that she can also access. We can also think of sil as the amount of "useful" resource agent i originally possessed of meta-type l (she might contribute more than sil to the pool). Prior to reallocation of resources, agent i's utility would be

Sharing incentive says that ui(xi) ≥ uoi ∀i ∈ N, where xi is the output allocation of the algorithm (i.e., all agents have incentives to share (pool) their individual resources for reallocation). 2

4 Dominant Resource Fairness with Meta-Types

Before describing the algorithm we first define some key concepts used in the algorithm:

Namely, l∗ i is the meta-type from which agent i demands the biggest proportional share, adjusted by her priority weights. We refer to l∗ i as the dominant resource meta-type for agent i.

2 A closely related concept called proportionality is also often seen in the literature. We focus on Sharing Incentive in the main paper and include a discussion of proportionality in the Appendix.

di∗ is the proportional share demanded by agent i from its dominant resource meta-type to finish one unit of work.

We now present our fair allocation mechanism, which we call Dominant Resource Fairness with Meta-Types (DRFMT). The mechanism proceeds in rounds and agents are gradually "eliminated". In each round t, we use the linear program described in (2) to maximize a fractional value yt so that each remaining agent i (i ∈ Nt) receives at least yt ×wi∗ fraction of the total supply from its' dominant resource meta-type l∗ i , and more generally yt × wi∗ × dil/di∗ of each demanded meta-type l. 3 Based on this solution, we eliminate at least one resource and one agent using Definition 1 and 2 (although the algorithm only needs to explicitly maintain a list of active/eliminated agents, not resources). For each agent i eliminated in round t, we set γi = yt. We fix the fraction of dominant meta-type l∗ i assigned to agent i to γi ×wi∗, without fixing the specific allocations of the resources. We first observe the following fact (proof is in the Appendix):

Fact 1. In any round t of Algorithm 1, the allocation constraints in Equation 2 for i /∈ Nt are tight for optimal solutions.

This fact implies that when an agent is eliminated, her utility in the final allocation is fixed, even though the exact allocation is not. Not fixing the allocation is a deliberate algorithmic design choice because agents who are flexible with their demand groups should accommodate agents who are more restrictive (e.g. if agent 1 accepts both type A and B, and agent 2 only accepts type A, then we should allocate agent 1 mostly type B resource, and leave type A resource for agent 2). When the number of agents and resource types is large, it is difficult to characterize such dynamics explicitly. So it is crucial to not fix the allocation to the agents until the last iteration.

We will show that there is at least one new resource and one agent being eliminated in each round. Thus our algorithm requires at most min(m, n) rounds (in practice it often terminates in 2-3 rounds even with a large number of resources types and agents). Since each round requires solving a polynomial-sized linear program, the overall procedure can be run in polynomial time.

Let Nt,Rt be the set of active agents and resources at the beginning of round t. The LP for round t is defined in (2). Note that the ratio dil di∗ is simply making sure that there is no waste in the allocation. For an agent who has been eliminated, γiwi∗ di∗ is her final utility. If agent i is not yet eliminated after round t, then ytwi∗ di∗ represents how much utility she is currently guaranteed to receive (it will never decrease in later rounds, see Fact 2).

3 We also considered an alternative design that did not yield a strategy-proof and envy-free algorithm. See Appendix D .

max yt

s.t. (active agents allocation constraints)

(eliminated agents allocation constraints)

(supply constraints)

(non-negativity constraints)

Fact 2. The optimal value for Equation 2 is non-decreasing over rounds: y∗ 1 ≤ y∗ 2 ≤ ..., where y∗ t is the optimal objective function value of the LP in round t.

This follows because the constraints on eliminated agents are less restrictive than the constraints on active agents, and the set of active agents is decreasing over time.

Definition 1. Resource r is eliminated in round t if t is the first round in Algorithm 1 in which ∑i∈N xir = Sr for every optimal x.

By Fact 2 it is also easy to see that the set of remaining resources Rt decreases over time.

Definition 2. We give two equivalent definitions for eliminating agents:

• Agent i is eliminated in round t when there exists gl ∈ Gi such that gl ∩Rt+1 = ∅.
• Agent i is eliminated in round t when there exists gl ∈ Gi such that yt ×wi∗ × dil di∗ = ∑ r∈gl xir for every optimal x, yt.

Intuitively, both definitions are saying that agent i can not improve her utility further in later rounds. Due to space constraint we defer the proof of their equivalence, and most of the other results to the Appendix. We include the proof of Claim 1 here because it is a good representation of the flavor of arguments used in other proofs. First we address the question of whether the DRF-MT can be efficiently implemented.

Claim 1. In each round t of Algorithm 1, at least one remaining resource r ∈ Rt and one remaining agent i ∈ Nt is eliminated.

Proof. Suppose no resource is eliminated in round t, then for each r ∈ Rt, there exists an optimal solution such that ∑i∈N xir < Sr. Then the convex combination of these solutions gives us an optimal solution x∗ that satisfies ∑i∈N x∗i,r < Sr ∀r ∈ Rt. However, by Definition 2, for every remaining agent i ∈ Nt, gl ∩ Rt ̸= ∅∀gl ∈ Gi. So if we assign a little more of every active resource to every active agent, then the overall objective value would be higher. This contradicts the optimality of the LP.

Algorithm 1: Dominant Resource Fairness with MetaTypes (DRF-MT)

1 Input: Agents N, resources R, supplies Sr ∀r ∈ R, demand groups Gi ∀i ∈ N, normalized demands dil ∀i ∈ N, gl ∈ Gi, priority weights wil ∀i ∈ N, l ∈ [L] 2 Initialize N0 = N 3 for t ← 0, 1, 2, ... do 4 y∗ t ←Solve (2) 5 Update the remaining active agents Nt+1 (using Claim 2) 6 for agent i eliminated in this round do 7 γi ← y∗ t 8 end 9 if Nt+1 = ∅ then 10 Solve Equation 2 and assign resources according to xir with rounding 11 break 12 end 13 end

Now suppose some resource r ∈ Rt is eliminated in round t but no agent is eliminated. Suppose this resource type is part of meta-type l. By the first definition in Definition 2, this means that for every i such that xir > 0, there exists r′ ∈ gi l such that r′ is not eliminated. By the same convex combination argument above, we know that there is an optimal solution such that ∑i xir′ < Sr′ for every such r′ . Then for every such agent we can remove ϵ allocation of r from her and replace it with ϵ allocation of the corresponding r′ . This gives us an allocation that has the same objective as before without using up the entire supply of r, contradicting r being eliminated.

This result shows that DRF-MT can be implemented efficiently by solving at most min(m, n) number of polynomialsize linear programs. However, it does not tell us how to find the eliminated agents. The following theorem says that we can do so by looking at the dual variables of the LP. Note that the algorithm does not need to explicitly maintain a list of active resources (Equation 2 does not depend on Rt).

Claim 2. This claim has two parts:

• If the shadow price of an allocation constraint of an active agent in round t is positive, then its corresponding agent is eliminated in round t.
• In each round t, at least one allocation constraint corresponding to an agent in Nt has a positive shadow price.

Now we state our main results.

Lemma 1. DRF-MT is Pareto optimal. Lemma 2. DRF-MT is weighted envy-free.

Lemma 3. DRF-MT is strategy-proof.

The proofs for these three lemmas all involve a case analysis of different scenarios and showing that the undesirable outcomes violate either the optimality of the LP or the definition of eliminated resources/agents, similar to the arguments presented in the proof of Claim 1.

Lemma 4. Assume that demands, weights and supplies are all rational numbers. If priority weights of the algorithm are set according to the each agent's accessible contribution to the resource pool (for each meta-type), then DRF-MT satisfies sharing incentive.

In resource pooling settings, having a separate weight for each meta-type is crucial in proving this result (e.g. contributing a ton of hard drive space but no GPU should not give the agent high priority if GPU is its dominant/bottleneck resource type). The proof constructs a bipartite graph of supplies and demands of the resources, then uses Hall's Theorem Hall [1935] to show that there exists a feasible solution to the first round's LP that already gives every agent at least as much utility as they could get without participating in the pool. Since agents' utilities only increase in later rounds, the final allocation must also satisfy sharing incentive.

4.1 Integral Allocation fromRounding

So far we have implicitly assumed that the resources are divisible, and all fairness results are stated with respect to the fractional assignment output of Algorithm 1. In practice we round down the output to obtain the final assignment, since resources such as ventilators are indivisible. Each agent loses at most 1 unit of each type of resource through rounding. Since we focus on problems where each agent receives hundreds of units of each resource, the performance loss due to rounding is small. For example, starting with an envy-free fractional allocation, one agent can envy another by at most 2m items after rounding. In Example 1, m is 4, while the total allocations each agent receives are in the hundreds. So an envy of 2m items is not significant. Note that such divisibility assumption is also standard in existing DRF literature, which often focus on the compute resource sharing problem: even though CPU cores are discrete, it's common to treat the problem as a continuous problem since there is a large quantity of cores in a compute cluster.

There are many existing algorithms that focus on fair allocation of indivisible goods (e.g. Discrete MNW from Caragiannis et al. [2019]). Indivisible resource allocation is particularly important when the quantities of the resources are small (e.g. fairly assigning a car, a house, and a ring to two people). However, as is the case with most discrete optimization problems, these algorithms do not scale well to the sizes that we deal with in a pandemic with hundreds of hospitals and many types of resources. In settings where each agent receives hundreds of units of each resource, the performance loss due to rounding is often small compared to the dramatic increase in computational cost for solving Mixed Integer Programs (see Section 5 for a numerical comparison).

4.2 Connection to Previous Dominant Resource Fairness Algorithms

The core difference between our problem setup and the existing DRF settings (Ghodsi et al. [2011], Parkes et al. [2015]) is the addition of accessibility constraints. When |Ωl| = 1

for each l ∈ [L], both our problem formulation and the DRFMT algorithm reduce to the problem and algorithm studied in those papers. Note that in this simplified setting one can write out the closed form solutions to the LPs, so no actual optimization needs to be performed. However, it is natural that resources come in different "flavors" and that agents have different constraints/preferences over these variations. So our formulation captures a much wider range of problems encountered in practice.

4.3 Alternative Fair AllocationMechanisms

As discussed in Section 2 and Section 4.1, the other most suitable approaches in our setting are MNW and Discrete MNW. When the weights are equal, MNW is also commonly referred to as the Competitive Equilibrium with Equal Income (CEEI) approach. Without the accessibility constraints, MNW is known to be Pareto optimal, envy-free and satisfy sharing incentive. However, unlike DRF-MT, it is known that MNW is not strategy-proof (see Section 6 of Ghodsi et al. [2011] for an example). We show in Section 5 that our DRF-MT mechanism achieves almost as much social welfare (i.e. sum of utilities of all agents) as MNW, and also runs faster in practice.

4.4 Extension to Arbitrary Group Structure

We currently assume that resources and demands follow a meta-type/group/type structure. One might be interested in a general group structure where a demand group can contain any subset of all possible resources (not necessarily from a single meta-type). The problem with this kind of flexible group structure is that it opens up possibilities for people to cheat the system by misreporting their true demand structure (e.g. instead of reporting that they are indifferent to resource A and B, and that they only need one unit of either one to finish a unit of work, agents can claim that they need one unit each from both A and B to finish one unit of work). In particular, Dominant Resource Fairness based approaches will likely not work, since it is unclear how one would even define the dominant resource under such a general setting. We leave this as an open question for future work.

5 Numerical Experiments

We compare the algorithms on running time, normalized max envy, and social welfare. Normalized max envy is the maximum envy (see Section 3.1) between any pair of agents normalized as a fraction of each agent's allocated utility. Social welfare is the sum of utilities of all agents. We fix a metatype structure (Ω1 = {0}, Ω2 = {1, 2}, Ω3 = {3, 4, 5}, Ω4 = {6, 7, 8, 9}) and randomly generate the demands, group structures, and weights for the agents. For each choice of number of agents, we ran 16 trials. All three algorithms Allocations are rounded down for MNW and DRF-MT. All three algorithms allow specifying different agent weights and also observe the accessibility constraints. Gurobi [2021] and Mosek (Aps [2020]) are used to implement the algorithms. More details on the experimental setup and additional experiments can be found in Appendix B .

First we investigate scalability. As shown in Figure 2 (left), the running time for Discrete MNW quickly explodes while MNW and DRF-MT are much more scalable. DRF-MT runtime in particular grows very slowly. The error region represents one standard deviation from the mean.

Recall that DRF-MT is envy-free before rounding. We now investigate envy when the solution is rounded. Without accessibility constraints, MNW is also envy-free before rounding, and Discrete MNW satisfies envy-free up to one good. Figure 2 (middle) shows that all three algorithms have small max envy after rounding in practice (< 4% in most trials).

Finally, we compare the social welfare obtained under DRT-MT and Discrete MNW. Figure 2 (right) shows that in roughly 95% of the trials, DRF-MT obtained at least 90% as much social welfare as Discrete MNW. In Appendix B we show that MNW has slightly lower social welfare than Discrete MNW, so the above conclusion holds when DRF-MT is compared to rounded MNW as well.

In conclusion, compared to both Discrete MNW and MNW, DRF-MT 1) achieves almost as much social welfare, 2) has comparable level of max envy, 3) has the additional property of strategy-proofness (in the fractional case), and 4) is more scalable. An interesting avenue for future work is to determine the properties of the rounded variant of DRF-MT. A particularly interesting question would be whether one can show that approximate strategy-proofness holds when there is large supply of each item.