key: cord-0472678-tcigt9nd
authors: Yin, Steven; Wang, Shatian; Zhang, Lingyi; Kroer, Christian
title: Dominant Resource Fairness with Meta-Types
date: 2020-07-21
journal: nan
DOI: nan
sha: d52f3dc559bb071dda6a46d4111736637fed42f2
doc_id: 472678
cord_uid: tcigt9nd

Inspired by the recent COVID-19 pandemic, we study a generalization of the multi-resource allocation problem with heterogeneous demands and Leontief utilities. Unlike existing settings, we allow each agent to specify requirements to only accept allocations from a subset of the total supply for each resource. These requirements can take form in location constraints (e.g. A hospital can only accept volunteers who live nearby due to commute limitations). This can also model a type of substitution effect where some agents need 1 unit of resource A emph{or} B, both belonging to the same meta-type. But some agents specifically want A, and others specifically want B. We propose a new mechanism called Dominant Resource Fairness with Meta Types which determines the allocations by solving a small number of linear programs. The proposed method satisfies Pareto optimality, envy-freeness, strategy-proofness, and a notion of sharing incentive for our setting. To the best of our knowledge, we are the first to study this problem formulation, which improved upon existing work by capturing more constraints that often arise in real life situations. Finally, we show numerically that our method scales better to large problems than alternative approaches.

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 * Contact Author 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.

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.

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.

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.

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 S r . We assume that the supplies are normalized within each meta-type:

where d il 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 d il 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.

, be the set of demand groups for agent i, where g i 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 G i 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 g l instead of g i 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 w il . Having different weights for different meta-types makes the model more expressive: if we let w i1 = . . . = w iL , 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 w il = 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 x i be the allocation vector of agent i: x ir represents the assignment of resource type r to i. For each meta-type l, r∈g i l x ir 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 d il fraction of each meta-type l to finish one unit of work, u i (x i ) is the total units of work that agent i can finish given allocation vector x i . 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 w i 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: w 1 = w 2 = 1 4 , w 3 = 1 2 . 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 S r = 500 1000 = 1 2 ∀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:

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,

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:

Weighted envy-freeness. Given an allocation x j for agentj, letx i be the same allocation adjusted to agent i's weights and demand groups, i.e.,x ir = x jr

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-

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 s il be the proportion of meta-type l contributed by agent i that she can also access. We can also think of s il as the amount of "useful" resource agent i originally possessed of meta-type l (she might contribute more than s il to the pool). Prior to reallocation of resources, agent i's utility would be

where x i is the output allocation of the algorithm (i.e., all agents have incentives to share (pool) their individual resources for reallocation). 2

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. d i * 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 (DRF-MT). 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 y t so that each remaining agent i (i ∈ N t ) receives at least y t × w i * fraction of the total supply from its' dominant resource meta-type l * i , and more generally y t × w i * × d il /d i * 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 = y t . We fix the fraction of dominant meta-type l * i assigned to agent i to γ i × w i * , 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 / ∈ N t 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 N t , R t 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 d il 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). max y t s.t. (active agents allocation constraints)

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 x ir = S r for every optimal x.

By Fact 2 it is also easy to see that the set of remaining resources R t decreases over time. Definition 2. We give two equivalent definitions for eliminating agents:

• Agent i is eliminated in round t when there exists g l ∈ G i such that g l ∩ R t+1 = ∅.

• Agent i is eliminated in round t when there exists g l ∈ G i such that y t × w i * × d il di * = r∈g l

x ir for every optimal

x, y t .

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 ∈ R t and one remaining agent i ∈ N t is eliminated.

Proof. Suppose no resource is eliminated in round t, then for each r ∈ R t , there exists an optimal solution such that i∈N x ir < S r . Then the convex combination of these solutions gives us an optimal solution x * that satisfies i∈N x * i,r < S r ∀r ∈ R t . However, by Definition 2, for every remaining agent i ∈ N t , g l ∩ R t = ∅ ∀g l ∈ G i . 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 Meta-Types (DRF-MT) 1 Input: Agents N , resources R, supplies S r ∀r ∈ R, demand groups G i ∀i ∈ N , normalized demands d il ∀i ∈ N, g l ∈ G i , priority weights

Update the remaining active agents N t+1 (using Claim 2) Now suppose some resource r ∈ R t 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 x ir > 0, there exists r ∈ g i 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 x ir < S r 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 R t ).

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 N t 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.

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).

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 DRF-MT 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.

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.

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.

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.

Proof. Suppose the second definition holds but the first one does not. Then by the definition of eliminated resource, there exists an optimal solution such that for every g l ∈ G i , there exists r ∈ g l such that i∈N x ir < S r . Then for every g l ∈ G i we can assign i a little more of the resource type above, and have y t ×w i * × d il di * < r∈g l x ir . This contradicts the second definition. Now suppose the first definition holds but the second definition does not. This means that there exists an optimal solution such that y t × w i * × d il di * < r∈g l x ir for every g l ∈ G i . Consider the g l such that g l ∩ R t+1 = ∅ by the first definition (every r ∈ g l is eliminated by the end of round t). We can reduce the allocation of resources in that demand group to i by a little bit without sacrificing optimality because the allocation constraints were satisfied strictly. But this means we have an optimal solution that does not use up the supply of r ∈ g l : this contradicts the elimination of these resources in the first definition.

Proof. The first part is straightforward. If q ig > 0 is the dual variable for the allocation constraint for some agent i ∈ N t , g ∈ G i , then by complementary slackness every optimal solution needs to satisfy y t × w i * × d il di * = r∈g l

x ir , which means agent i needs to be eliminated by Definition 2. Let's now rewrite the linear program solved at time t:

This LP is in canonical form, where the objective coefficient vector is c T = [0, ..., 0, 1]. Let q ig be the dual variables that correspond to the allocation constraints (constraint (4) and (5)), and q r the dual variables corresponding to the supply constraints (constraint (6)). Let y * t be the value of y t in an optimal solution to the linear program and letq be the optimal solution to the corresponding dual program. By complementary slackness we know thatq A y = c y = 1, where A y is the last column of the primal constraint matrix. Note that the entries in A y are either positive or zero. Therefore,q ig must be positive for some i ∈ N t , g ∈ G i . This finishes the proof of the second part.

Proof. Suppose x is the output of Algorithm 1 and there exists allocation x such that agent i is strictly better off while other agents have just as much utility. Let y × w i * be the fraction of the dominant resource meta-type that i receives with allocation x .

Let t be the round in which i was eliminated in Algorithm 1. Since i is strictly better off with allocation x , y > y * t . Now we construct a new allocation by scaling down agent i's allocation from x i to x i y * t y . Since we know other agents have at least as much utility as with allocation x, this new solution has an LP objective value at least as high as before, satisfies all the allocation/supply constraints, and does not use up all the resources that i cares about. This contradicts i being eliminated in round t. This concludes the proof for Lemma 1 Note that by the same argument as above we know that the allocation constraint in Equation 2 for the eliminated agents has to be satisfied with equality (otherwise we can scale this allocation down to make the constraint tight, and that agent would not have been eliminated in an earlier round).

The first inequality follows from the definition dominant resource meta-type:

The final expression is the amount of original dominant resource that agent i receives under truthful reporting.

• y * t * > y * t * and the agent is not eliminated reporting d but is eliminated reporting d . We argue that this case cannot happen. By Claim 4, we can remove the allocation constraints related to i in round t * under truthful reporting. But then we are left with two optimization problems with the same constraints, except that with untruthful reporting the optimization problem has extra allocation constraint (for agent i), and an extra non-negative term in the supply constraints. Extra constraints and extra terms in the supply constraints can only make the optimization problem harder.

• y * t * < y * t * and the agent is eliminated reporting d but not eliminated reporting d . This is the symmetric case as the previous one and so cannot happen either. Finally, a closer inspection of the above shows we did not need the group structure of agent i to stay the same, so the result holds for misreporting group structures as well.

Proof. Recall that we use s il denote the proportion that is both accessible to and contributed by agent i. Each agent might have access to other people's contributions as well. We set w il = s il . Since an agent might not have access to all of the supplies that she brings, i∈N w il might be strictly less than one. In that case we can pretend that there is a phantom agent with weight 1 − i∈N w il for each meta-type l, and that his demand vector is zero. Note that we do not need to implement this phantom agent when running the algorithm, because DRF-MT is invariant to the scale of weights. We are only adding this weight to make our definition of sharing incentive consistent with the assumption i w il = 1 Now note that r∈∪ i∈N g i l S r ≥ i∈N s il because each agent has access to her own accessible supply. By the definition of

After rearranging the terms, we have

(7) For every agent i and every meta-type l, consider w i * d il di * as the "total demand" for resource meta-type l from agent i.

Then, we construct a bipartite graph as follows: for the left-hand nodes, we create a node for every unit of total demand from each agent for each resource meta-type. Thus, each node is associated with some specific agent i and resource meta-type l. For the right-hand nodes, we create a node for every unit of supply of each resource type (r ∈ R). Note that since there is a finite number of agents and resource types, there exists an small enough that it can perfectly divide up all the demands and supplies, assuming that all the weights are rational.

Next, we create an edge between each pair of left and righthand side nodes if and only if the supply side node belongs to the demand group of that agent for that meta-type: r ∈ g i l . Eq.(7) now tells us that for every subset of the demand side nodes, the number of neighbors of that subset is greater than or equal to the size of the subset. This is precisely the condition in Hall's Theorem, which states that if this condition holds, then there exists a matching in the bipartite graph such that the demand side nodes are covered.

Consider such a matching obtained via Hall's Theorem. We construct a solution x by setting x ir equal to times the number of matched edges corresponding to ir. This yields an assignment that gives each agent w i * d il di * of each meta-type. By the construction of the matching this is a legal allocation. Then, we can set y t = 1 to obtain a feasible solution to the optimization problem in (2).

This means that after the first round of DRF-MT, agent i's utility is at least

The final expression is exactly the utility agent i gets from her own supplies.

Solving for MNW is an Exponential Cone program, and solving for Discrete MNW is a Mixed Integer Exponential Cone program. Both of which did not have a reliable commercial solver until recently. This changed with the introduction of MOSEK version 9, which added support for such cones [ApS, 2020] . We implemented the MNW and Discrete MNW using the MOSEK solver and our DRF-MT approach using GUROBI. We made little effort to optimize either approach beyond the off-the-shelf implementations, and all experiments are run on a 2019 16-inch Macbook Pro with a 6 core Intel i7 processor. First we describe in more details the random instance generating procedure used in Section 5. Recall that we fixed a meta-type structure. From there, for each agent, the group structure is generated by first uniformly sample a size between 0 and |Ω l |, and randomly pick a subset of that size from Ω l as the demand group. The demands and weights (before normalization) are sampled uniformly from [1, 10] , and the number of agents range from n = 5 to n = 1000. The supply for each resource is uniformly sampled from [n × 500, n × 1000]. Using the same procedure, we also compare the running times on a larger instance (more meta-types, and more types within a meta-type). As shown in Figure 3 , the relative performances remain the same.

Next, we scale up the number of meta-types instead of number of agents, even though we think it is more natural to have problems with large number of agents. Here we assume that each meta-type has five types and fix the number of agents to 50. We see in Figure 4 again that the running time for Discrete-MNW quickly blows up while DRF-MT remains the fastest method out of the three.

Since Discrete-MNW runs much slower than DRF-MT and MNW, we next focus on the running time comparison of just MNW and DRF-MT in our next set of experiments. The setups are the same as the ones used for Figure 2 (left) and Figure 4 , except this time we scale the problem instances to much larger ones. We see from Figure 5 and Figure 6 that DRF-MT is 3-4 times faster than MNW in terms of running time.

Finally, as mentioned in Section 5, normalized difference in social welfare is calculated from subtracting the social welfare of Discrete MNW from that of DRF-MT and then divide the difference by the social welfare of Discrete MNW. Here, instead of looking at the aggregated normalized difference in social welfare as in Figure 2 (right), we group the results by the number of agents. The box plot in Figure 7 shows that in most of the trials, DRF-MT generates social welfare that is comparable to that of Discrete MNW, and sometimes even higher, with no significant variation in performance with respect to the number of agents. Readers might wonder how does Discrete DMW compare to (rounded) MNW in terms of social welfare. In Figure 8 we see that the two have virtually the same social welfare on almost all instances, with Discrete MNW having a slight edge over MNW. This means that compared to rounded MNW, our rounded DRF-MT algorithm also achieves at least 90% of the social welfare on most instances.

Proportionality is defined as follows: Proportionality An allocation x satisfies proportionality if

can be explicitly written out as

In the existing resource allocation literature, sharing incentive and proportionality are often used interchangeably. Indeed, when the priority weights are set according to the agents' accessible contributions to the resource pool (w il = s il ), the two notions are equivalent in settings where there are no accessibility constraints. With accessibility constraints, however, they are not the same. Under our definition of proportionality, the amount of accessible resource meta-type l that agent i receives is s il × r∈g i l S r . Since r∈g i l S r < 1 if agent i cannot access the entire supply of meta-type l, u i (x ) can be smaller than u o i . Therefore when priority weights are set according to agents' contributions, proportionality is a weaker notion than sharing incentive. However, since proportionality can be defined for arbitrary weights, regardless of whether or not we are in a setting where agents bring their own supplies, it is a more flexible concept. Unfortunately proportionality does not hold generally. We prove proportionality under the following assumption: Assumption 1. The proof is very similar to that of Lemma 4, but we first give some intuition for Assumption 1.

Hospital 1 (w 1 = 1/4) Hospital 2 (w 2 = 1/4) Since r∈g i l S r ≤ 1 for every i, l, and min l w il d il = wi * di * for every i, the right hand side of Assumption 1 is upper bounded by 1.

r∈∪ i∈N g i l S r is the union of the acceptable supply of resource meta-type l from every agent in N .

is the total weighted demand from agents in set N . Note that d il ≤ d i * . So, what the condition says intuitively is that whenever there is a group of agents who have a large combined weighted demand on meta-type l, they need to also collectively have access to/accept a large fraction of the total supply of l.

To provide more intuition for this assumption, we look at two examples. First we check that Example 1 satisfies Assumption 1. The RHS of the assumption evaluates to 1 (with hospital 1 and resource meta-type 1). One can check that the minimum on the LHS is achieved by picking N = N and l = 1 which gives us 16 15 > 1. Thus Assumption 1 is satisfied. The resulting allocation and utilities using DRF-MT is given in Table 1 . Clearly our allocation is better for everyone than the proportional allocation.

However, by adjusting the weights of the hospitals we can also construct an example that does not satisfy Assumption 1. Take the same parameters of Example 1 with the following modification on weights: w 1 = 0.49, w 2 = 0.49, w 3 = 0.02. The RHS value of Assumption 1 does not change. However, because the weights of hospitals 1, 2 now dominate the market, the minimum of LHS is achieved with N = {1, 2} and l = 2, which gives us 1/2 0.49×1+0.49×1/4 < 1. So the assumption is violated. Intuitively, the problem with this setup is that even though hospitals 1 and 2 account for vast majority of the weighted demand for the nurse meta-type, they are both severely constrained to the same half of the total supply of nurses.

Under this setup, the DRF-MT assignments/utilities do not change. With proportional allocation however, the utilities for the three agents are [122.5, 61.25, 10.0] . So Agent 1 received more utility under proportional allocation than the allocation given by DRF-MT, at the expense of significantly hurting the social welfare: the sum of the utilities is less than 200, compared to 700 generated by the DRF-MT allocation. Now we prove Lemma 5

Course match: A largescale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation

Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types

Markets for efficient public good allocation. ArXiv, abs

Beyond dominant resource fairness: Extensions, limitations, and indivisibilities

Models for managing surge capacity in the face of an influenza epidemic

Proof. For any pair of agents i, j ∈ N , we will show that i does not envy j. Let x be the allocation returned by Algorithm 1. Starting from the LHS of the definition of weighted envy-freeness: The first equality is the definition of Leontief utility in (1). The second equality holds because x jr = 0 for r ∈ Ω l but r / ∈ g j l (If the output allocation does contain inaccessible resources then we can simply remove them without affecting the utilities of agents). The inequality follows from nonnegativity of x jr . Now let t i , t j be the rounds in which agent i and j are eliminated respectively. Note that from the LP in Equation 2, we know r∈g j l x jr = y * tj w j * d jl /d j * . Sowhere the inequality follows from the definition of dominant resource meta-type (If y * tj ≤ y * ti (which means t j ≤ t i , by Fact 2 and Fact 1), we haveNow suppose y * tj > y * ti (which means t j > t i ), and that i envies j. Note that this implies that for every group g i l ∈ G i , there exists at least one r ∈ g i l such that x jr > 0. Consider an alternative allocation x that scales the allocation to agent j tox j while keeping the allocations to other agents the same as in x, namely,This alternative allocation gives every agent as much utility as they had before in round t i while maintaining slack in at least one resource from each demand group of G i . This contradicts the definition of t i because agent i was eliminated in round t i (see Definition 2).

Our proof approach is adapted from [Parkes et al., 2015] with important modifications. We first introduce some new notations and prove two helpful results. Let i be the only agent who reports her demands untruthfully. Let d be the true demand vector for all agents and d be an alternative demand where only the elements belonging to agent i might be different. Let t * be the first round in which agent i is eliminated in Algorithm 1, either with truthful or untruthful reporting (minimum of the two). Let N t , N t , and y * t , y * t represent the remaining active agents at the beginning of round t, and the optimal LP objective in round t, under d and d respectively, Claim 3. If agent i is not eliminated in round t, then if we remove the allocation constraint for agent i and omit the variables related to agent i from the supply constraints in Equation 2, the optimal value as well as agents eliminated in that round do not change.Proof. First we show that x ir = 0 if r is one of the eliminated resources in that round. Suppose x ir > 0. Since i is not eliminated, there must exist another resource r in the same demand group of r for agent i that is not eliminated. This means that we could replace some of the allocation of r with a little more allocation of r . But this would then contradict r being an eliminated resource. Note that by the same logic x ir = 0 holds in all future rounds too. This allows us to remove x ir from the supply constraints. Now the allocation constraint can be written asSince the remaining resources are not constrained by supply, this inequality can always hold without posing limits on other variables. So we can remove this constraint completely.Claim 4. For all t ≤ t * , N t = N t . For all t < t * , y * t = y * t .Proof. We use proof by induction. t = 0 holds trivially. We assume the claim holds for t. Suppose t+1 < t * . Then by Claim 3, we can remove the constraints related to agent i from the optimization problem. But the only differences between these two optimization problems are those related to agent i, so they have the same solutions and we are eliminating the same agents. Now we prove Lemma 3.

Proof. Letŷ denote the RHS of Assumption 1. After rearranging we have for all N ⊆ N and l ∈ {1 . . . L}:For every agent i and every meta-type l, consider yw i * d il /d i * as the "total demand" for resource meta-type l from agent i.Then we construct a bipartite graph and apply Hall's theorem the same way as in the proof of Lemma 4. This yields an assignment that gives each agent at leastŷw i * d il /d i * of each meta-type. By the definition ofŷ, it follows that the utility of each agent after the first round is at least:Note that the right-most quantity is the utility of the proportional allocation. This means that after the first round, every agent already achieves at least as much utility as the proportional allocation. Fact 2 finishes the proof.

Instead of the algorithm described in Section 4, an alternative is to make each remaining agent receive a y t × w i * × d il /d i * fraction of the total supply from each of its resource group g l * i (instead of the supply from the entire meta-type). This idea might seem more intuitive since agent i can only derive utilities from resources in g l * i ⊆ Ω l * i . To do so, we can multiply the left hand side of the allocation constraints in Equation 2 by r∈g i l S r . This alternative setup, however, does not lead to a mechanism with envy-freeness and strategy-proofness.As a simple example, assume that there are five agents 1, 2, 3, 4, 5 of equal weights, one meta-type, and two resource types A, B that fall under this meta-type, with equal supply. Agent 1, 2 accept only type A; agent 3, 4, 5 accept only type B. With simple calculation, we have that the largest y 1 we can get is 1/3: everyone receives 1/3 of their accepted supply. The only possible allocation to achieve that is by assigning 1/3 of A each to agents 1,2, and 1/3 of B each to agents 3, 4, 5. However, if agent 2 strategically stated that he could take both A and B, the resulting allocation would be assigning 1/3 of A to agent 1, 2/3 of A to agent 2, and 1/3 of B each to agents 3, 4, 5. In this new allocation, the largest y 1 is still 1/3, but since the total accepted supply for agent 2 is larger, he receives more. Furthermore, agent 1 would now envy agent 2.