Fairness Towards Groups of Agents in the Allocation of Indivisible Items

1 Introduction

Consider an academic department looking to assign incoming graduate students to advisers. It has computed a score for each potential advisor-advisee pair and cares not just about the overall score of the matching but also about a fair distribution of scores across the research clusters into which the faculty is divided. A similar trade-off between efficiency/welfare and fairness might be desirable in other planning/allocation scenarios such as public housing allocation; e.g. the Singapore Housing and Development Board imposes ethnicity quotas on the matching of tenant households to flats in its housing blocks to promote diversity [Benabbou et al., 2018] but an alternative approach could be to aim for a fair distribution of overall utility across ethnic groups.

We can model these problems as a variant of fair allocation of indivisible goods (see e.g. [Bouveret et al., 2016]): We have an underlying weighted bipartite matching problem, the nodes on the two sides corresponding to items and agents; however, the parties we are trying to be fair towards are not individual agents but subsets forming a partition over agents - we call these subsets types. An important aspect of this problem is that all agents in a type do not derive utility from all items in the bundle allocated to that type (unlike the public goods scenario [Fain et al., 2016]), each agent being assigned at most one item. Hence, the parties (types) under consideration end up violating the additive bundle-valuation assumption present in much of recent work. There are some approaches (e.g. [Lipton et al., 2004]) that achieve good fairness guarantees under mild assumptions on the (non-negative, non-decreasing) valuation function but, for that very reason, can result in allocations that are wasteful/inefficient in some way given the structure of our problem, if used na¨ıvely. These considerations necessitate novel solution concepts and techniques for our setting.

1.1 Our Contributions

We describe a new model of typewise fair allocation and define our desirable properties in Section 2 - in particular, non-wastefulness and typewise envy-freeness up to one item (TEF1) as well as a marginal envy-based variant of the latter. In Sections 3 and 4, we explore the problems of determining Pareto optimal, TMEF1 allocations and TEF1 allocations that maximize overall sum of weights/utilties respectively. In Section 5, we show experimentally that the classic algorithm of Lipton et al. [2004] equipped with a simple heuristic can produce TEF1 allocations with significantly reduced waste. Section 6 details a polynomial-time algorithm for computing a non-wasteful TEF1 allocation for binary agent-item utilities. We conclude with directions for future research in Section 7.

1.2 RelatedWork

There is a rich body of work on approaches towards the fair allocation of indivisible goods [Bouveret et al., 2016; Markakis, 2017]. A popular fairness concept is envy-freeness [Foley, 1967]. A complete envy-free (EF) allocation may not exist but a relaxation that always does is one that is envy-free up to one item (EF1) [Budish, 2011] where any envy towards an agent can be eliminated by removing an item from its bundle. The bounded-envy, polynomial-time algorithm due to Lipton et al. [2004] also produces an EF1 allocation for general valuation functions [Plaut and Roughgarden, 2018].

Extensions of envy-freeness to groups include strict envyfreeness [Zhou, 1992]; coalition fairness or group envyfreeness [Lahaie and Parkes, 2009] as well as envy-freeness of an individual/a group towards a group [Todo et al., 2011], both under monetary transfers; group fairness as defined by Conitzer et al. [2019]. Barman et al. [2018a] recently defined a groupwise extension to the maximin sharebased fairness concept. A major difference of these contributions with our model is that they deal with a σ-algebra of subsets of agents rather than an exogenously defined partition over agents. Notable papers that define fairness with respect to pre-defined groups of multiple players include Manurangsi and Suksompong [2017], Suksompong [2018], Segal-Halevi and Suksompong [2018], and Elzayn et al. [2019] whose concepts of utility and/or fairness are significantly different from ours. Recent work [Fain et al., 2016; Fain et al., 2018] has also explored non-envy-based fairness criteria in public goods allocation under additive valuations.

We must also mention the literature on statistical fairness (also called group fairness) in the fundamentally different problem domain of classification in machine learning: the equalization of some statistical property of the classifier across groups of data instances based on sensitive/protected attributes ([Dwork et al., 2012; Hardt et al., 2016; Kearns et al., 2018] and references therein); we, on the other hand, are interested in fairness notions in terms of subjective valuations of items from the economics/social choice literature.

2 Model And Definitions

Throughout the paper, [r] will denote the set {1, 2, · · · , r} for any positive integer r. Our model, an extension of the classic framework of matching on a weighted bipartite graph [Lov´asz and Plummer, 2009], has the following ingredients:

• (i) a set N of n vertices called agents partitioned into k types N1, . . . , Nk,
• (ii) a set M of m vertices called items,
• (iii) a weight/utility u(i, j) ∈ R+ for each agent-item edge (i, j) ∈ N ×M, such that for at least one i ∈ N (resp. at least one j ∈ M), there is at least one j ∈ M (resp. each i ∈ N) with u(i, j) > 0.

For any T ⊆ N and any S ⊆ M, a (T, S)-matching is defined as a subset of the edges T ×S such that every vertex in T ∪S is incident on at most one of the edges or, equivalently, as a binary matrix X = (xij)i∈T,j∈S such that for each agent i (resp. item j), there is at most one item j (resp. agent i) with xij = 1, i.e. each item is assigned to at most one agent and each agent is assigned at most one item. The utilitarian social welfare USW(X) (or total weight) of a matching X is defined as the sum of the realized utilities of all agents under that matching: USW(X) ≜ ∑i∈T ∑j∈S xiju(i, j). An optimal matching is one that maximizes the corresponding USW.

We are interested in a (N,M)-matching that trades off some welfare/efficiency concept against some fairness criterion defined with respect to the agent types. More precisely, for every type p ∈ [k], we are given a type-value function vp : 2M → R+ which quantifies some concept of overall welfare derived by Np from some bundle or subset of items S ⊆ M in terms of the weights u(i, j), (i, j) ∈ Np × S. In this paper, we will use the following specific type-value function for every type:

Definition 1 (Utilitarian type-value function). The utilitarian type-value of any type p ∈ [k] for any bundle S ⊆ M is defined as the total weight of an optimal (Np, S)-matching:

where X(Np, S) is the collection of all (Np, S)-matchings. We will define the marginal utility ∆p(S; j) of an item j ∈ M for a type p ∈ [k] and a bundle S ⊆ M as:

Given a type p and a bundle S, there can be multiple optimal (Np, S)-matchings with the same type-value but possibly differing in other efficiency and/or fairness properties (see Example 1 at the end of this section) - with this in mind, we define an allocation in our setting as follows:

Definition 2 (Allocation). An allocation A is a collection of bundles M A 1 , · · · ,M A k , such that M A 1 ∪. . .∪M A k ⊆M and M A p ∩M A q = ∅ for all p, q ∈ [k] with p ̸= q, along with an optimal matching between each type Np and the corresponding bundle M A p for all p ∈ [k], thereby inducing a unique (N, M)-matching XA = (xAij )i∈N,j∈M .

We call M A p the allocated bundle of type p under A and M A 0 = M\ ∪p∈[k] M A p the set of withheld items (we will sometimes drop the superscript A when there is no ambiguity). Thus, item assignment within a type is socially optimal (by design) and EF1 for individual agents (since each is assigned at most 1 item). Type p envies type q if vp(M A p ) < vp(M A q ); p envies q up to ν items, ν ∈ [|M A q |], if there is a subset C ⊆ M A q such that |C| = ν and vp(M A p ) ≥ vp(M A q \C) and, for every subset C ′ ⊆ M A q with |C ′ | < ν, vp(M A p ) < vp(M A q \C ′ ). We can analogously define the envy of a type for a bundle (up to any number of items).

With these fundamentals in place, we now define the desiderata of an allocation A that we investigate in this paper. The first three are concerned with efficiency; the rest are extensions of efficiency-agnostic fairness concepts introduced by Budish [2011] and Caragiannis et al. [2016] respectively.

Definition 3 (Type-completeness). A is type-complete if ∪p∈[k]M A p =M; otherwise it is type-incomplete. 1

Definition 4 (Waste and non-wastefulness). An item j ∈ M is said to be wasted by an allocation A if it has a positive marginal utility for some type p∈[k] (i.e. ∆p(M A p ; j)>0) but is either withheld (i.e. j ∈ M A 0 ) or belongs to the allocated bundle of some type q ̸= p for which it has zero marginal utility (i.e. j ∈ M A q and ∆q(M A q ; j) = 0). A is called nonwasteful if it has no wasted item, and wasteful otherwise.

Definition 5 (Typewise Pareto optimality). Allocation A1 is said to typewise Pareto dominate another allocation A2 if vp(M A1 p ) ≥ vp(M A2 p ) for all types p ∈ [k] and vp(M A1 p ) > vp(M A2 p ) for some type p ∈ [k]. An allocation that is not typewise Pareto dominated by any other allocation is typewise Pareto optimal.

1 Type-completness does not preclude an item j ∈ M A p remaining unassigned in the (Np,M A p )-matching.

Definition 6 (Typewise envy-freeness up to one item). Allocation A is typewise envy-free up to one item (TEF1) if for any two types p, q ∈ [k], p either does not envy q or envies q up to one item, i.e. there exists an item j ∈ M A q such that vp(M A p ) ≥ vp(M A q \{j}).

Definition 7 (Typewise marginal envy-freeness up to one item). Allocation A is typewise marginally envy-free up to one item (TMEF1) if for any p, q ∈ [k], there is an item j ∈M A q such that vp(M A p )≥vp(M A p ∪M A q \{j})-vp(M A p ).

We are now ready to formulate and analyze specific problems that approach 'good' allocations in different ways. But first, we provide two problem instances that we will use as running examples in the rest of the paper.

Example 1. The types N1, N2 and items M are as shown in Figure 1 (left): u(i, j) is 1 if there is an edge between agent i and item j, and 0 otherwise. If bundles M1 = {1, 2, 6} and M2 = M\M1 are allocated to N1 and N2, there is a unique optimal (N2,M2)-matching with 3, 4, 5 assigned to b1, b2, b3 respectively; but there are two optimal (N1,M1)-matchings in both of which 2 is assigned to a2: If 1 is assigned to a1 and 6 remains unassigned, then we have a wasteful allocation since 6 could be assigned to b4 so that ∆2(M2; 6) = 1; but if 6 is assigned to a1 instead, the allocation is non-wasteful since no agent in N2 has a positive utility for item 1.

Example 2. The types and items are as shown in Figure 1 (right): All agents of the same type have the same utility for an item, equal to the integer with which the edge between that type and the item is labeled; no edge indicates zero utility.

3 Typewise Pareto Optimal TMEF1 Allocation

In this section, we will adapt a result of Caragiannis et al. [2016] to our setting. To that end, we first state without proof a property of our type-value function (Definition 1) that is part of the folklore of weighted bipartite matching.

Theorem 1. The utilitarian type-value function vp(S) is a non-additive, monotone submodular function of S ∈ 2M .

Moreover, we define the Nash type-welfare of an allocation A as the product of the type-values, i.e. ∏kp=1 vp(M A p ).

Theorem 2. Every allocation that maximizes the Nash typewelfare is typewise Pareto optimal and TMEF1.

Proof. Since each valuation function vp(·) is monotone submodular by Theorem 1, a natural extension of Theorem 3.5 of [Caragiannis et al., 2016] suffices to prove the result.

The next result establishes that non-wastefulness is a weakening of typewise Pareto optimality in our setting.

Lemma 1. Any typewise Pareto optimal allocation is nonwasteful but the converse is not true.

Proof. If an allocation A had a wasted item j with positive marginal utility for a type q, then, by the definition of waste, we could augment M A q with j for an improved type-value without reducing any other type-value, resulting in an allocation that Pareto dominates A. For the converse, Example 1 provides a counterexample: Take again the allocation A1 with bundles M A1 1 = {1, 2, 6}, M A1 2 =M\M A1 1 , item 1 remaining unassigned and 2, . . . , 6 assigned to a2, b1, b2, b3, a1 respectively. This is non-wasteful (and incidentally also TEF1) but is Pareto dominated by allocation A2 with bundles M A2 1 = {1, 2, 3}, M A2 2 = M\M A2 1 since v1(M A2 1 ) = 3 > 2 = v1(M A1 1 ) and v2(M A2 2 ) = v2(M A1 2 ) = 3.

This implies, in conjunction with Theorem 2, that a maximum Nash type-welfare allocation is also non-wasteful. Despite the above existence results, maximizing Nash welfare with indivisible items is known to be hard in general, and the above guarantees may break down for constant-factor approximations [Caragiannis et al., 2016]. Moreover, marginal envy-freeness up to one item (MEF1) is a relatively new fairness concept that is less intuitive than envy-freeness up to one item and not extensively used as yet. In fact, it is easy to show that EF1 implies MEF1 for monotone submodular bundle-valuation functions. Hence, we will henceforth focus on efficient TEF1 allocations. Note that an allocation maximizing Nash type-welfare is not necessarily TEF1: In Example 2, any allocation with M1 = {1, 2} and M2 = {3, 4, 5} maximizes the Nash type-welfare but is not TEF1 since v1(M1) = 4 whereas v1(M2\{3}) = v1(M2\{4}) = 5, v1(M2\{5}) = 8.

4 Assignment under TEF1 Constraints

We first study the problem of finding a TEF1 allocation A that maximizes the sum of weights of the induced matching:

This is equivalent to the assignment problem [Munkres, 1957] under TEF1 constraints specified in Definition 6. We define the decision version of the problem as follows:

Definition 8 (ASSIGNTEF1). An instance of the Assignment under TEF1 constraints (ASSIGNTEF1) problem is given by parameters (i) to (iii) of Section 2 as well as a value U ∈ R+; it is a 'yes'-instance iff it admits a TEF1 allocation A with a utilitarian social welfare at least U.

A TEF1 allocation always exists under our Definition 2 (see Section 5 for further details) but we prove next that it is hard to compute one with the maximum USW for more than 2 types. The hardness question for 2 types is open.

Theorem 3. The AssignTEF1 problem is NP-complete, even with only 3 types.

Proof. The problem is in NP: given an allocation A, we need to evaluate k type-value functions, solving the polynomialtime unconstrained assignment problem (see e.g. Kuhn [1955]) each time, and can hence verify that A satisfies all requirements in polynomial time.

We will now describe a polynomial-time reduction to ASSIGNTEF1 from the NP-complete partition problem [Garey and Johnson, 1979]. An instance of the latter is given by a set S = {sj}j∈[l] of l positive integers that sum to σ; it is a 'yes'-instance iff S can be partitioned into two subsets S1 and S2 such that both sum to σ/2. Given an instance of the partition problem, we construct an ASSIGNTEF1 instance as follows. We have a set of l +2 items M = [l +2] and a set of 2l+4 agents N partitioned into k = 3 types N1 ={ai}i∈[l+1], N2 ={bi}i∈[l+1], and N3 ={c1, c2}. The utilities are given by u(aj , j)=u(bj , j)=sj , ∀j ∈[l]; u(al+1, j)=u(bl+1, j)= σ/2, ∀j ∈ {l + 1, l + 2}; u(c1, l + 1) = u(c2, l + 2) = κ for an arbitrarily large constant κ>σ; u(i, j)=0 for every other (i, j)-pair. Finally, let U=2κ+σ.

First, we prove that, for any 'yes'-instance of the partition problem, so is the corresponding ASSIGNTEF1 instance we constructed. Given the two parts S1 and S2 of S as above, consider the bundles M1 = {j ∈ M : sj ∈ S1}, M2 = {j ∈ M : sj ∈ S2}, and M3 = {l + 1, l + 2} allocated to N1, N2, and N3 respectively, with no withheld items; evidently, assigning item j to agent aj (resp. bj) for every sj in S1 (resp. S2), l + 1 to c1, and l + 2 to c2 constitutes the unique optimal matching between each type and its allocated bundle, inducing an allocation A (Definition 2). We want to prove that A is TEF1. Note that for the above utilities, v3(M3) = 2κ > 0 = v3(Mq) for all q ∈ {1, 2}; v1(M1) = v2(M1) = ∑sj∈S1 sj =σ/2 and also v2(M2)=v1(M2)= ∑sj∈S2 sj = σ/2 from the definition of a 'yes'-instance of the partition problem; v1(M3\{j})=v2(M3\{j})=σ/2 for all j ∈ M3. Hence, each type envies any other type up to at most one item under A. Finally, USW(XA)=σ/2+σ/2+2κ=2κ+σ=U.

Now let us prove that, assuming our constructed ASSIGNTEF1 instance to be a 'yes'-instance, so is the partition instance. Let A be an allocation verifying all desiderata. Since κ>σ and the maximum sum of realized utilities that can be achieved from items j ∈ [l] is σ, the only way for USW(XA) to be at least U=2κ+σ is to have {l +1, l +2}⊆M A 3 with c1 (resp. c2) assigned to l + 1 (resp. l + 2). Moreover, since the other items must contribute a sum of realized utilities at least σ, it is also clear from the utility structure that each j ∈[l] must be assigned to either aj or bj ; hence, M3 ={l+1, l+2}, there are no withheld items, and v1(M A 1 ) + v2(M A 2 ) = σ. Now consider the sets S1 = {sj ∈ S : j ∈ M A 1 } and S2 = {sj ∈ S : j ∈ M A 2 }: It is evident that they form a partition of S such that the sum of the values in S1 (resp. S2) equals v1(M A 1 ) (resp. v2(M A 2 )). Since A is TEF1, we must have v1(M A 1 ) ≥ v1(M A 3 \{j}) for some j ∈M A 3 ; but, from our utility structure, v1(M A 3 \{j})=σ/2 for all j ∈M A 3 and so the inequality v1(M A 1 ) ≥ σ/2 holds. Arguing similarly, v2(M A 2 ) ≥ σ/2. But since v1(M A 1 ) + v2(M A 1 ) = σ, then

Since vp(·) is a particular submodular function, Theorem 3 implies the following result for the traditional indivisible item allocation setting where each agent receives a bundle.

Corollary 1. For monotone submodular agent valuation functions over bundles, it is NP-hard to compute the EF1 allocation that maximizes the sum of valuations.

One might conjecture that the maximum-USW TEF1 allocation is non-wasteful. But the following surprising result belies this intuition, and raises the question: Does a non-wasteful, TEF1 allocation always exist?

Proposition 1. The TEF1 allocation that maximizes the utilitarian social welfare may waste items, even in a problem instance that admits a non-wasteful TEF1 allocation.

Proof. In Example 2, any allocation with bundles M1 = {1, 2} and M2 = {3, 4}, and no other allocation, maximizes USW under TEF1 constraints with USW = 20. But, such an allocation is wasteful since item 5 is withheld although ∆2(M2; 5) = 1. However, any allocation with bundles M ′1 = {1, 3} and M ′2 = {2, 4, 5} is non-wasteful and TEF1 but has USW = 15.

5 TEF1 Allocation with ReducedWaste

In our quest for a TEF1 allocation with no (or, at least, low) waste, we note that it is possible to obtain a type-complete TEF1 allocation in polynomial time by a natural extension (called L hereafter) of the algorithm due to Lipton et al. [2004]: Iterate over the items j ∈ M, giving item j to a type, say p, that is currently not envied by any other type for its bundle Mp; compute an optimal matching with the augmented bundle Mp ∪ {j}; construct the envy graph where there is a directed edge from a type q to a type r whenever q envies r; eliminate any cycle in this graph by transferring the bundle of every envied type to its envying type on this cycle (to ensure that there is an unenvied type in each iteration), followed by re-matching within each such type. Although no item is withheld, it is possible for the final allocation to be wasteful: An item may be allocated to a type which has zero marginal utility for it or may become unassigned after a bundle is transferred between types.

One heuristic that could reduce waste is to allocate the item to the unenvied type that has the maximum marginal utility for it, breaking further ties uniformly at random, rather than to an arbitrary unenvied type - we call L, augmented with this heuristic, H. Unfortunately, Example 1 shows that, H can be wasteful in general. Consider the order 1, 2, · · · , 6 over items: 1 and 2 are obviously allocated to N1 while, depending on how ties are broken, 3, 4, 5 can all be given to N2. With this allocation of item 5, envy appears for the first time and N1 is the only unenvied type. Hence, 6 must go to N1, although ∆1({1, 2}; 6) = 0, and is wasted. Notice further that if 6 were allocated to N2, it would increase N2's own typevalue but make N1 envy N2 up to 2 items although N1 does not want 6 in conjunction with its current bundle! This is especially disappointing since Example 1 admits three nonwasteful TEF1 allocations, which are also typewise Pareto optimal and maximize USW, with bundles M ∗ 1 = {1, 2, 3}, {1, 2, 5}, or {1, 2, 3, 5}, and M ∗ 2 = M\M ∗ 1 (each resulting in a unique optimal matching for each type).

Nevertheless, to see how the marginal utility maximization heuristic performs in practice, we experimentally compared procedures L and H using the percentage of items wasted as our performance metric. We simulated two sets of problem instances with n = 100 agents partitioned into k = 3 types:

For each, we used m ∈ {50, 100} items; for each agent, we sampled m numbers uniformly at random from [0, 1] and normalized them to generate utilities for all m items. We report results averaged over 100 runs each.

For the UNEQUAL set, 39% (resp. 13%) of the items are wasted on average for m = 100 (resp. m = 50) by L whereas no item is wasted by H; for the EQUAL set, L wastes only 0.005% of the items with m = 100 and no item with m = 50, and again no item is wasted by H for either value of m. Thus, we can conclude that the performance of the natural extension of [Lipton et al., 2004] strongly depends on parameters such as type proportions and the number of items, whereas augmenting it with the heuristic under consideration gives surprisingly good results over a variety of input instances.

6 Binary Utilities: Non-Wasteful TEF1 Allocation

In this section, we fill focus on the binary utility model: u(i, j) ∈ {0, 1}, ∀i ∈ N, ∀j ∈ M. This captures scenarios where each agent either approves or disapproves of an item but does not distinguish among its approved items. There exists prior work on fair allocation algorithms producing allocations with binary item utilities [Barman et al., 2018b] but most assume additive bundle valuations.

Theorem 4. For any problem instance with a binary utility model, there exists a non-wasteful TEF1 allocation that can be computed in polynomial time.

Our proof is constructive: We provide and analyze an allocation algorithm for the problem (Algorithm 1). Like Lipton et al. [2004], we iterate over the items; however, we augment a type's bundle with an item not based on (the absence of) envy towards it but on the marginal utility of the type for the item. Let us call any algorithm that starts with empty bundles and follows the principle of augmenting the current bundle Mp of a type p with an item j only if p has positive marginal utility (i.e. ∆p(Mp; j)>0) a PMU algorithm.

Proposition 2. Under the binary utility model, we have vp(S) ≤ min{|Np|, |S|}, ∀p ∈ [k], ∀S ⊆ M. In particular, any type's value for its allocated bundle at any stage of a PMU algorithm is equal to the cardinality of the bundle, i.e. vp(Mp) = |Mp|, ∀p ∈ [k].

2 These numbers roughly follow the proportions of Chinese, Malay, and Indian/Other residents of Singapore according to the 2010 census report [Department of Statistics, Singapore, 2010].

Algorithm 1: PMURR({Np}p∈[k] , M, (u(i, j))i∈N,j∈M )

Withheld set M0 ← M;

Temporary set MT ← ∅;

Allocated bundles Mp ← ∅ ∀p ∈ [k].

repeat

Proof. The first part follows directly from the fact that, for binary utilities, any item can contribute either 1 or 0 to the type-value of a bundle, i.e. ∆p(S; j) ∈ {0, 1} for any p ∈ [k], S ⊆ M, and j ̸∈ S. For the second part, note that each type starts with an empty bundle (hence zero type-value) and increases its type-value by 1 every time it acquires an item under a PMU algorithm; moreover, since all positive utilities are equal, the only way for an item j to improve the type-value of p is to ensure that every item is assigned to an agent in every (Np,Mp ∪{j})-matching - hence, if an item is revoked, both the bundle-size and type-value diminish by 1.

Corollary 2. A type p ∈ [k] with |Mp| = |Np| under a PMU algorithm cannot envy any bundle S⊆M since vp(S)≤|Np|.

If after receiving a new item, a type is still envied by all other types up to at most 1 item, no further action is necessary in that iteration. But a PMU approach by itself cannot ensure that no type will start envying the recipient up to more than 1 item if the latter was already envied up to 1 item. If envy does exceed the acceptable limit, we execute a special revocation and reallocation (RR) subroutine repeatedly until we restore the TEF1 property - hence, we call our algorithm PMURR. The functioning of the RR subroutine depends on the following result:

Proposition 3. At any stage of a PMU algorithm, if type p envies type q up to ν or more items, then |Mq| ≥ |Mp| + ν.

Proof. It follows from the definition of envy up to ν (or more) items: For any subset C ⊆ Mq with |C| = ν - 1, vp(Mp) < vp(Mq\C). But, from Proposition 2 (and since C ⊆ Mq), we have vp(Mq\C) ≤ |Mq\C| = |Mq| - |C| = |Mq| - ν + 1.

Corollary 3. Type p can envy another type q only if q has an allocated bundle of a larger size than p which, in turn, implies that there can be no cycles in the envy graph among types for binary utilities under a PMU algorithm.

Next, we prove that the existence of envy is sufficient for having an item that can be revoked and reallocated.

Lemma 2. At any stage of a PMU algorithm, if type p envies type q, then there exists an item j in the bundle Mq which has a positive marginal utility for p, i.e. ∆p(Mp; j) = 1.

Proof. By Proposition 2 and Corollary 2, if N ′p is the subset of agents who are assigned items in the current (Np,Mp)- matching, then we must have vp(Mp) = |Mp| = |N ′p | < |Np| for p to envy q. Now, if N q p is the subset of agents who would be assigned items in a (Np,Mq)-matching, we must have |N q p | = vp(Mq) > vp(Mp) = |N ′p |, so that |N q p \N ′p | ≥ |N q p | - |N ′p | > 0. Since N q p \N ′p ⊆ Np\N ′p , each agent in N q p \N ′p is assigned no item under the current matching but has a positive utility for a distinct item in Mq.

A revocation from q (resp. a reallocation to r) decrements (resp. increments) its type-value, thus reducing the envy of r towards q; but it is not obvious how it affects all envy relations (types that already envied r up to 1 or more items, those that q might start envying up to 1 or more items, etc.) and whether we could trigger a never-ending chain reaction. Our final lemma dispels such doubts.

Lemma 3. The revocation and reallocation subroutine produces a TEF1 allocation in a polynomial number of steps.

Proof. First note that computing a type-value for any bundle is polynomial-time and so is checking whether r envies q up to more than 1 item (i.e. vr(Mr) < vq(Mq\{j}) for some j ∈ Mq). Now, for an iteration of the RR subroutine to occur, we must have a type r envying a type q up to 2 or more items, so that |Mq| ≥ |Mr| +2 by Proposition 3. For any collection of bundles M = {M1, . . .M2}, define the potential function Φ(M) ≜ ∑p∈[k] |Mp|2 , and let M ′ = {M ′1 , . . .M ′2 } be the collection of bundles after revocation from q and reallocation to r. Hence, |M ′q | = |Mq| - 1 and |M ′r | = |Mr| + 1 (by Proposition 2) but |M ′p | = |Mp| for every other type p. Thus,

i.e. Φ strictly decreases with each RR iteration, and obviously lies between 0 and m2 (since ∑p∈[k] |Mp| ≤ m). Hence, RR terminates after a polynomial number of iterations; by the stop criterion, the final allocation is TEF1.

We are now ready to prove the main result of this section.

Proof of Theorem 4. To prove that the final allocation is nonwasteful, note that by construction, no bundle-augmentation and revocation-and-reallocation allow an item in an allocated bundle to remain unassigned; by Corollary 3, no envy cycles are ever formed in the envy graph among types, hence bundles are never passed between types (unlike in the decycling procedure of [Lipton et al., 2004]) and so no item once assigned can become unassigned (or transferred to the temporary set). However, within the "for" loop, the revocation(s) might result in an agent becoming unassigned who has a positive utility for a currently withheld item that was put in the temporary set because it previously had zero marginal utility for each type (hence this item now becomes a wasted item). This necessitates the outer "repeat" loop whose stop criterion ensures that there are no wasted items in the withheld set at the end of the algorithm.

Lemma 3 ensures that the allocation is TEF1 after every iteration of the "for" loop, hence upon termination.

For proving the polynomial time-complexity, recall that computing vp(·) and ∆p(·), verifying envy up to more than 1 item, and finding an item to revoke and reallocate are all polynomial-time; Lemma 3 ensures that each iteration of the "for" loop takes polynomial time. With each iteration of the outer "repeat" loop, the size of the withheld set, which starts at m, strictly decreases (if it does not, it must mean that each withheld item has zero marginal utility for every type - a stop criterion), hence we have a linear number of iterations.

7 Discussion And FutureWork

We have introduced and investigated typewise fairness and efficiency concepts for the allocation of indivisible goods. The major open question is whether a non-wasteful TEF1 allocation always exists for arbitrary agent-item utilities. Important properties (e.g. the equality of bundle size and type-value) do not carry over from binary to arbitrary utilities, hence extensions of our PMURR algorithm to general utility models remain elusive. An alternative would be to have heuristic approaches such as the one in Section 5 with provable upper bounds on the amount of waste.

We considered one type-value function vp(·) (Definition 1) here; the average utilitarian type-value ˆ vp(S) ≜ vp(S)/|Np| is equivalent to vp(S) for all intents and purposes in this paper. More complex functions such as OWA operators [Yager, 1988] or those that address fairness within a type (e.g. [Bouveret and Lang, 2011]) merit further analysis.

Other possible directions for future research include nonenvy-based fairness concepts (egalitarian type-welfare, proportionality, maximin share etc.) as well as strategic implications of typewise fair allocation algorithms.

Acknowledgments

Chakraborty and Zick were supported by the Singapore MOE grant R-252-000-625-133 and the Singapore NRF Research Fellowship R-252-000-750-733, Benabbou by the ANR project 14-CE24-0007-01-Cocorico-CoDec, and Elkind by the ERC grant 639945 (ACCORD). The authors would like to thank the anonymous reviewers of IJCAI 2019 and the reviewers and attendees of FAMAS 2019 for their feedback.