Approximate Pareto Set for Fair and Efficient Allocation: Few Agent Types or Few Resource Types

1 Introduction

Fair division with its wide range of important applications has a long research history, see the book chapters by Bouveret et al. [2016] and Lang and Rothe [2015] for an overview. In this setting, we are given n agents and m indivisible resources (or items or goods), and agents express their preferences over subsets (or bundles) of items by individual value functions. One of the central tasks is to fairly allocate items to agents in an efficient manner, as motivated by real-world applications such as vehicle-request assignment in ridesourcing [Lesmana et al., 2019], bandwidth allocation [Goel et al., 2001], and load balancing [Kleinberg et al., 2001].

Various axiomatically justified notions of fairness have been studied, including envy-freeness (no one wants to swap her bundle with others), proportionality (every agent receives a value worth at least a fraction of 1/n of her value for the whole set of items), and max-min fairness (maximizing the value of the worst-off agent, i.e., egalitarian social welfare).

Widely used notions of efficiency include utilitarian efficiency (allocations that maximize the sum of the agents' values, i.e., utilitarian social welfare) and Pareto optimality (allocations in which no agent can increase her value without decreasing the value of some other agent). Pareto optimality is necessary but not sufficient for utilitarian efficiency. We will focus on max-min fairness and utilitarian efficiency.

∗Contact Author

It is unfortunate that, due to the conflict of the two criteria, allocations that are both fair and efficient do not always exist. This has motivated further research, such as to study the efficiency loss under fair allocations, which is well captured by the notion of price of fairness introduced and studied by Bertsimas et al. [2011] and Caragiannis et al. [2012].

Another remarkable research direction is to look for allocations that satisfy fairness and efficiency only to some extent [Lesmana et al., 2019; Aziz et al., 2019]. For example, Lesmana et al. [2019] study this issue in the context of ridesourcing request assignments where a set of requests need to be matched to a set of available vehicles based on a given weighted bipartite graph. They present an efficient algorithm for finding an allocation with any desired fairness and bounded efficiency. For general graphs, however, achieving such a result is well-known to be computationally hard.

This raises the question of whether one can find in polynomial time good allocations with only a small loss on both fairness and efficiency. Our goal is to answer this question by focusing on two special cases: when there are only a few agent types or a few item types. These two parameters have been the subject of intensive investigations (see, e.g., [Brˆanzei et al., 2016; Bouveret et al., 2017; Jansen and Maack, 2019; Galil and Megiddo, 1979; Brown, 1979; Krysta et al., 2013; Bredereck et al., 2019]).

We model the problem of computing fair and efficient allocations as a general bi-criteria optimization problem and identify the set of Pareto-optimal solutions from the perspective of approximation algorithms-a similar idea was used by Escoffier et al. [2013]. That is, we study an approximation of this set, called e-Pareto set, which includes approximately non-Pareto-dominated solutions: For every feasible solution p, there is a solution p ′ in the e-Pareto set that is better than p within a factor of 1-e on both criteria. The purpose of constructing an approximate Pareto set is to help the decision maker to easily find an allocation satisfying any specific level of the desired quality of efficiency and fairness.

Our contribution. For any fixed constant e > 0, we propose polynomial-time algorithms for generating an e-Pareto set, for both studied cases. When the number of item types is constant, we propose a dynamic programming algorithm that runs in time polynomial in the size of the input. Interestingly, our dynamic programming technique can also be applied to (exactly) compute allocations that are Pareto-optimal and fair, w.r.t. other notions of fairness. Notably, the technique can be employed to solve the open problem of finding a min-max allocation, as stated by Jansen and Maack [2019]. For the case when the number of agent types is constant, we give an approximation scheme whose running time is polynomial in the size of the instance. Our source of improvement in the scheme is a novel technique where we significantly extend the technique used by Jansen and Maack [2019]. In particular, by a more involved procedure involving finding a basic solution of nice structure to a mixed integer linear program, we can round it to an integral solution with only a small loss on both fairness and efficiency. We believe that this idea is universally applicable and might be applied to more general classes of objective functions.

Related work. Finding fair and efficient allocations has gained a lot of interest in the last decade-see, e.g., the work of Aumann and Dombb [2015], Bliem et al. [2016], Caragiannis et al. [2016], Bei et al. [2019], Suksompong [2019], and Igarashi and Peters [2019]. Bredereck et al. [2019] presented fixed-parameter tractable algorithms for computing envy-free and Pareto-optimal allocations, when parameterized by the number of agents and the maximum value of any item. Their result also holds for various fairness notions including max-min fairness. Barman et al. [2018] showed that one can produce an allocation that is envy-free up to one item and Pareto-optimal in pseudo polynomial time. Aziz et al. [2019] presented an algorithm for finding an envy-free up to one item allocation whose utilitarian social welfare satisfies a given efficiency goal. Considering max-min fairness and utilitarian efficiency, Lesmana et al. [2019] obtained an approximation algorithm for a restricted setting in which every allocation forms a perfect matching on a bipartite graph. Since our focus is on those cases when the number of item types or the number of agent types are constant, we will give a short overview of related work. Firstly, the case of one item type was shown to be tractable for a class of single-objective optimization problems, including for utilitarian social welfare maximization (even for concave value functions) by Galil and Megiddo [1979], and for egalitarian social welfare maximization by Brown [1979]. It still remains open if such results can be extended to the case of few item types. A similar question has been posed by Jansen and Maack [2019] in the context of machine scheduling, where the objective is to minimize the maximum value among all agents. In the same paper, the authors presented a polynomial-time approximation scheme (PTAS) for the problem of maximizing egalitarian social welfare, assuming that the number of different types of agents is fixed. This result significantly improved a previous PTAS designed for the special case when all the agents' valuations are identical [Woeginger, 1997]. Very recently, Kones and Levin [2019] proposed a framework for designing PTASes for more general classes of machine scheduling problems, which generalizes the results of Jansen and Maack [2019]. Nevertheless, their technique fails when applied to our problems.

2 Model and Notation

An instance of a fair and efficient allocation problem is often given by a triple I = (A,O,U), where A = {1, 2, . . . , n} is the set of agents, O = {1,2, . . . ,m} the set of items, and U = {u1, u2, . . . , un} the agents' valuation functions expressing their utilities over the set of items. We restrict our attention to the class of additive valuation functions which have been widely used in the context of resource allocation. A valuation function is additive if for any subset (bundle) S ⊆O, ui(S) = �j∈S ui j, where ui j is agent i's nonnegative integer value for item j. We assume that the value of the empty bundle is zero for every agent. Furthermore, by scaling if needed we can assume that if ui j ̸=0 then ui j ≥1, for all i, j. For ease of presentation, define umax = maxi, j ui j. An allocation of items among agents is a partition of the set O of items into n disjoint subsets. We denote an allocation by p = (p1, . . . , pn), where pi is the bundle allocated to agent i.

Agent types and item types. The set of agents is divided into T groups A1, . . . ,AT such that agents in each group have the same valuation function. Let [T] = {1, . . . ,T}. Let nt = |At | be the number of agents of type t, and ut, j be the value of item j for any agent inAt . Let ut,O =�j∈Out, j for t ∈ [T]. We say that two items j, j′ are of the same type if they have the same value for every agent i, i.e., ui j = ui j′ . Hence, we can divide the item set O into q classes such that items in each class are of same type. We assume that there are mj (identical) items for each item type j.

Max-min fairness and other fairness notions. The egalitarian social welfare (ESW) of an allocation p is defined as swe(p , I) = min n i=1 ui(pi). If p has maximum egalitarian social welfare among all allocations, we say that p is max-min fair (MMF). An allocation is proportional fair (PF) if every agent i gets a value of at least her proportional share of ui(O)/n, and is maximin-share fair (MSF) if every agent gets a value of at least her share when she can partition O into n bundles and then has to pick a bundle of smallest value.

Utilitarian efficiency. The utilitarian social welfare (USW) of an allocation p is defined as swu(p,I) = � n i=1 ui(pi). If p has maximum utilitarian social welfare among all allocations, p is said to be utilitarian efficient (UE). Note that if an allocation is utilitarian efficient then it is Pareto-optimal, but not vice versa. We write swu(p) and swe(p) if I is clear from the context. We now define Pareto set and its approximation.

Definition 1 (Pareto set and e-Pareto set). Given an instance I, we say that an allocation p dominates an allocation p ′ if swe(p) ≥ swe(p ′ ) and swu(p) ≥ swu(p ′ ), with at least one inequality being strict. The Pareto set of I, denoted by P(I), is the set of all allocations that are not dominated by any other allocation. For e ∈ (0,1], the e-Pareto set of I, denoted by Pe(I), is the set of allocations such that for all allocations p ′ , there is always an allocation p ∈ Pe(I) such that swe(p) ≥ (1-e)swe(p ′ ) and swu(p) ≥ (1-e)swu(p ′ ).

We will address the problem of constructing an e-Pareto set Pe(I) of bounded size for any given instance I, and for any fixed constant e > 0, when the number of item types or the number of agent types are not part of the input.

3 Few ItemTypes

We present a dynamic programming scheme that is the key ingredient in the construction of an approximate Pareto set. It can also be used as a subroutine to solve other problems.

Lemma 1. Given an instance I and a value b , one can compute in polynomial time an allocation of maximum utilitarian social welfare subject to the constraint that the value of every agent is at least b, if such an allocation exists, assuming that the number of item types is constant.

Proof. Given (I,b), we present a dynamic programming scheme, denoted by DP(I,b), for finding a required allocation in terms of a state-transition diagram. A state is defined as a (q+1)-tuple of the form S = (i,s1,s2, . . . ,sq), where i ∈ {0} ∪ [n] and s j ∈ {0} ∪ [mj], for j ∈ [q]. States are grouped into n+1 blocks B0,B1, . . . ,Bn. The first and the last blocks, B0 and Bn, contain only one state denoted by Sstart = (0,m1,m2, . . . ,mq) and Send = (n, 0, 0, . . . , 0), respectively. Block Bi, for i ∈ [n-1], contains all possible (q+1)- tuples S ensuring that the size of Bi is (m1 +1)· · ·(mq +1). Intuitively, a state s ∈ Bi gives us partial information about an allocation of items to agents. In particular, it indicates that agents 1, . . . , i have been allocated items (but we do not know which items are assigned to which agents), and s1,s2, . . . ,sq are the number of items of each type that are unallocated yet at the current state and will be assigned to the remaining agents i +1, . . . ,n at the next states. The total number of states in n+1 blocks is (n-1)(m1 +1)· · ·(mq +1)+2. We next define transitions of states between two consecutive blocks as follows. For each i ∈ [n], there is a transition from a state S = (i -1,s1,s2, . . . ,sq) ∈ Bi-1 to a state S′ = (i,s′1 ,s′2 , . . . ,s′q) ∈ Bi if and only if s j - s′j ≥ 0 holds for all j ∈ [q], and we set the value of this transition to w = � q j=1 ui j(s j -s′j ) if w ≥ b and w =-¥, otherwise. By this transition we mean that agent i is allocated a bundle of items encoded by the vector (s1 -s′1 , . . . , sq -s′q).

One can see that a (simple) path of the constructed statetransition diagram (a directed acyclic graph) above corresponds to an allocation for I, and vice versa. Our problem is therefore equivalent to computing a longest path (i.e., the path of maximum total value) in the diagram, which can be done via dynamic programming. If the path is of positive value, DP(I,b) returns a corresponding allocation p satisfying the conditions in the lemma, otherwise it returns "NO," meaning that there is no such allocation. Regarding the running time of DP, note that the number of states is bounded by O(nm q ), and for each state we have at most m q outgoing transitions. Therefore, the overall complexity of DP is O(nm O(q) ), which is polynomial in n and m, as q is constant.

Using Lemma 1 we can now prove the following theorem.

Theorem 1. Given an instance I, one can compute in polynomial time a set Pe (I) for any fixed constant e ∈ (0, 1], when the number of item types is constant.

Proof. Let I be an instance and e be a constant in (0,1]. To prove the claim in the theorem, we describe a polynomialtime algorithm as follows. The idea is to enumerate all possible lower bounds LB on the egalitarian social welfare of an allocation, that is, LB ∈ {0,1,1+e,(1+e)2 , . . . ,(1+e)k }, where k = ⌊log1+e{mini ui(O)}⌋. For each value of LB, we run the dynamic program DP(I, LB) from Lemma 1 to return an allocation p of maximum utilitarian social welfare (if there exists one), respecting the constraint on lower bound LB.

We include such an allocation p into Pe(I), for every LB. One can see that |Pe (I)| ≤ k+2. This together with the polynomial running time of DP(I,LB) implies that our algorithm runs in time polynomial in the size of the instance.

We now prove that for every allocation p, there is always an allocation p ′ ∈ Pe(I) such that swe(p ′ ) ≥ (1-e)swe(p) and swu(p ′ )≥(1-e)swu(p). Indeed, the first case swe(p)= 0 is easy to see because the allocation p ′ returned by DP(I, 0) is UE. Suppose that swe(p) ̸= 0. Let ℓ be a nonnegative integer such that swe(p) ∈ [(1+ e)ℓ ,(1+ e)ℓ+1 ). Hence, p must correspond to some path in the diagram considered by DP(I,(1+e)ℓ ). Let p ′ be the allocation returned by DP(I,(1+e)ℓ ). It must then hold that swu(p) ≤ swu(p ′ ). Moreover, from swe(p) < (1+e)ℓ+1 and swe(p ′ ) ≥ (1+e)ℓ and as e ∈ (0,1], we have that swe(p ′ ) > (1+e)-1 swe(p) or swe(p ′ ) > (1 - e )swe(p).

The dynamic programming above can be applied to compute other fair and Pareto-optimal allocations as shown in the theorem below. The proof is omitted due to space limitations and can be found in the full version of the paper.

Theorem 2. Given that the number of item types is constant, one can compute in polynomial time a fair and Paretooptimal allocation (if there exists one), w.r.t. either one of the following fairness criteria: MMF, PF, and MSF. Also, computing a min-max allocation can be done in polynomial time.

4 FewAgent Types

In this section, we present a linear-programming algorithm for constructing an e-Pareto set for an instance I where the number of different agents is small. We make use of some of the ideas from the PTAS for finding max-min fair allocations by Jansen and Maack [2019].

Theorem 3. For any constant e ∈ (0,1], one can construct an e-Pareto set in time polynomial in the size of the instance, when the number of agent types is constant.

Proof. Fix e ∈ (0,1] and let a = e/5 and t = (1-a)/2, Algorithm 1 computes an e-Pareto set for I. The lemma below indicates that it suffices to focus on allocations of some special structure. The proof, which is omitted here due to space limitations, is similar to that of Alon et al. [1998].

Lemma 2. Given an allocation p, one can find an allocation p ′ such that: i) swu(p ′ ,I) = swu(p,I) and swe(p ′ ,I) ≥ swe(p,I); ii) for each agent type t, there is a value xt such that: if there is some agent who receives an item of value ≥ xt then it is the only one she received. Moreover, every agent who did not get any such item has a value ∈ ( 1 2 xt , 2xt ).

The construction of an e-Pareto set is described in Algorithm 1. The basic idea is to enumerate a bounded number of possible values of xt and the corresponding egalitarian social welfare qt ∈ ( 1 2 xt ,2xt), for every t ∈ [T], and try to find (if

Algorithm 1 PARETO-SET

there exists one) an allocation of maximum utilitarian social welfare, w.r.t. these values.

Enumerating possible values regarding USW. For each t ∈ [T ], consider a set Xt = {1, 1+a, . . . , (1+a)⌊log1+a ut ,O⌋}. Each xt ∈ Xt represents a possible (approximate) average value of agents in a subset A ⊆At such that every agent in At \A gets only one item of value at least xt . For each vector x = (x1, . . . , xT ), Algorithm 1 performs Steps 4-13, which are described in detail below.

Classifying items into groups. For each agent type t, we classify items in O into large items (having value bigger than a 2 xt and less than xt ), small items (having value at most a 2 xt ), and huge items (having value at least xt ). Next, we guess at most d = ⌈W/a⌉ huge items of value at least xt that are assigned to agents of this type (W is some constant that is specified in line 5 of Algorithm 1 and Lemma 3). Let Dt be the set of these guessed items. We call D = {Dt}t∈[T ] a valid guess if {Dt}t∈[T] are disjoint subsets. Given a valid guess D, huge items that are not in Dt and have values bigger than minj∈Dt ut, j should not be allocated to agents of type t.

Enumerating possible values regarding ESW. For each t ∈ [T], given a value xt , the algorithm considers a set Qt of possible values of the minimum value over all agents of type t in the domain (txt ,xt/t), Qt = {txt , txt 1-a , . . . , txt (1-a) p }, where p = ⌊log1-a t 2 ⌋. It is argued later that it is not necessary to consider values that do not belong to this domain.

Rounding itemvalues (line 10 of Algorithm1). The value of item j w.r.t. agents of type t ∈ [T] is rounded down to

Observation 1. By the rounding step (1) we get a new instance ˆI = (A,O, ˆU) with the same agents and items but different valuation functions. Moreover, for every t and j, it holds that ˆut, j ≥ (1-a) · ut, j.

For every t ∈ [T], let Ht , Lt , and St , respectively, be the sets of huge, large, and small rounded item values. We bound the size of Lt as follows. Since every large item has a value less than xt , from (1) it follows that the number of large rounded item values (w.r.t. agent type t) must be at most log1-a a 2 .

Configurations. For t ∈ [T], we encode a bundle of items of values in Lt as an |Lt |-dimensional vector k = (kv)v∈Lt , called a configuration, where kv denotes the number of items of value v. The value of a configuration (or a bundle) k for an agent of type t is defined as ˆut,k =�v∈Lt v ·kv. For a value qt ∈Qt , define

We call Ct<qt and Ct≥qt the sets of small and big configurations, respectively. Let Ct = Ct≥qt ∪Ct<qt . We show that |Ct | is bounded by a constant. Indeed, by the fact that the value of every large item is bigger than a 2 xt and the value of every configuration is less than xt/t, it follows that a 2 xt ·�v∈Lt kv ≤ �v∈Lt v · kv < xt/t. Therefore, �v∈Lt kv ≤ 1/(ta 2 ). This together with the claim that |Lt | ≤ log1-a a 2 implies the constant size of Ct , as a and t are constant.

Mixed integer linear program (line 11 of Algorithm 1). Now, given the vectors x = (x1, . . . , xT ), q = (q1, . . . , qT ), and D = {Dt }t∈[T ], we formulate a mixed integer linear program, denoted by MILP[x,q], as follows. MILP[x,q] consists of both fractional and integer variables, and three classes of linear constraints, which are defined next. We use the following variables x = (xt, j)t∈[T ], j∈[m] and y = (yt,k )t∈[T ],k∈Ct , where

• xt, j ∈ [0,1]: denotes the fraction of item j assigned to agents of type t. Some variables xt, j are set to be either 0 or 1 according to our guessing of Dt ,
• yt,k ∈ N: denotes the number of configurations k ∈ Ct that are assigned to agents of type t.

Let Ot,v = { j ∈ O| ut, j = v} and Gt = ∪v∈Ht Ot,v, for t ∈ [T ]. The objective of MILP[x , q ] is to maximize

subject to the following classes of constraints. In the first class of constraints, we require that, for every type t ∈ [T], the total number of configurations and huge items assigned to agents of this type is exactly the number of agents:

For the second class of constraints, we first ensure that every item j ∈O is assigned to exactly one agent type:

For every t ∈ [T ] and for every v ∈ Lt , we must have that the total number of items of value v that are assigned to the group of agents At is at least the total number of items of the same value used in the chosen configurations:

The third class of constraints guarantees that, for t ∈ [T], the total value of the small configurations and small items assigned to agents of type t is at least qt times the number of agents owning small configurations:

An optimal basic (fractional) solution (BFS) to MILP[x,q], if there exists one, is denoted by (x∗ ,y∗ ). We now show how to convert it into an allocation with the desired properties.

Lemma 3. A basic solution (x∗ ,y∗ ) to MILP[x,q] has at most W =2(2+log1-a a 2 ) ·T fractional components.

Proof. It suffices to prove the x∗ has at most W fractional components. Since the number of nontrivial constraints of MILP[x,q] is h = 2T +�t∈[T] |Lt | +m, x∗ has at most h positive components. Consider the family of constraints (3). In each of these constraints, there are only two cases: (i) there is exactly one positive component x∗ t, j = 1, and (ii) there are at least two nonintegral components. Denote by ℓ1 and ℓ2, respectively, the number of constraints (3) in each case. Then we have that ℓ1 + ℓ2 = m. The total number of positive components of x∗ is at least ℓ1 + 2ℓ2 = 2m-ℓ1. By an earlier argument, we must have that 2m-ℓ1 ≤ h = 2T +�t∈[T] |Lt | +m or, equivalently, ℓ1 ≥ m-2T -�t∈[T] |Lt |. Therefore, the number of nonintegral components of x∗ is at most h- (m-2T -�t∈[T] |Lt |) = 2 (2T +�t∈[T] |Lt |) ≤ 2 (2+log1-a a 2 ) · T, as |Lt | is upperbounded by log1-a a 2 .

Converting (¯x∗ ,y∗ ) into an allocation. We first show how to round (x∗ , y∗ ) to an integer solution (¯x∗ , y∗ ). We need only to round x∗ (or, more precisely, the fractional components of x∗ ) since y∗ is already integral. We find a nonnegative basic (integer) solution to the following linear program (LP):

in which we set zt, j = x∗ t, j for all t, j such that x∗ t, j is integral. One can see that LP has the form of Ax ≥ b, where A has only 0- or 1-entries while b is an integer vector. Furthermore, every column of A contains exactly two nonzero entries. Hence, A is a totally unimodular matrix, making every basic solution of LP integral. It is well-known that a basic solution z∗ of LP can be found in polynomial time. We set ¯ x∗ t, j = z∗ t, j if x∗ t, j is fractional, and ¯ x∗ t, j = x∗ t, j otherwise. One can check that the obtained solution (¯x∗ ,y∗ ) fulfills the constraints (2), (3), and (4), though it may violate the constraints (5). We will show later that this violation does not affect much the quality of the rounded solution. Finally, we apply Algorithm 2 for each t ∈ [T] to convert (¯x∗ ,y∗ ) into an allocation.

Algorithm 2 CONVERT( ¯x∗ , y∗ , At )

• 1: Allocate item j to group At if ¯ x∗ t, j = 1, for all j, and follow the next steps to assign items to agents in this group.
• 2: Huge items: we allocate each huge item to at most one agent such that nobody gets more than one huge item.
• 3: Large items: agents who have not received any huge item are assigned exactly one configuration each, and we further allocate large items to each of them based on y∗ t ,k .
• 4: Small items: we greedily allocate small items among groups of agents having a configuration of value less than (1-3a)qt . Pick an arbitrary agent from this group and assign small items to her (one-by-one) until her value exceeds (1-3a)qt . Remove the last item assigned to her and repeat this process with the remaining agents and remaining items. At the end of the process, if there still remain some items, we allocate them arbitrarily to agents.

Correctness of Algorithm1. One needs to prove that, for a given feasible allocation p, there is an allocation p ∗ ∈ Pe (I) such that swe(p ∗ ,I) ≥ (1-e)swe(p,I) and swu(p ∗ ,I) ≥ (1-e)swu(p,I). By Lemma 2, one can transform p into some allocation p ′ of the desired structure, without decreasing the egalitarian social welfare of the former one while keeping the utilitarian social welfare unchanged. If some agent gets nothing in p then swe(p,I) = 0. Therefore, this allocation must be dominated by ¯p ∈ Pe (I). Hence, we now consider the case when every agent gets at least one item in p. From p ′ one can easily determine the value xt for every t ∈ [T], and let qt = mini∈At ui(p ′ i ) ∈ ( 1 2 xt ,2xt). Let x ∗ t be a lower bound of xt such that x ∗ t ≤ xt < (1+a)x ∗ t . This lower bound is considered at Step 3 of Algorithm 1. Also, let Gt be the set of huge items assigned to agents of type t by allocation p ′ . Then a set Dt of the d highest-value huge items in Gt is considered by the loop in line 7 of Algorithm 1. If |Gt | ≤ d, Dt is exactly Gt . Let ˆ qt =mini∈At ˆui(p ′ i ). From (1) it follows that (1-a)qt ≤ ˆ qt ≤ qt . Hence, ˆ qt ∈ ( 1-a 2 xt ,2xt) or ˆ qt ∈ (tx ∗ t ,x ∗ t /t), where t = (1-a)/2. Then there must be a lower bound q ∗ t ∈ (tx ∗ t ,x ∗ t /t) of ˆ qt , considered by the loop at line 8 of Algorithm 1, such that q ∗ t ≤ ˆ qt < q ∗ t 1-a . Let x ∗ = (x ∗ 1 , . . . ,x ∗ T ) and q ∗ = (q ∗ 1 , . . . ,q ∗ T ). Now the Algorithm 1 tries to solve the MILP[x ∗ ,q ∗ ] to obtain some allocation with the desired properties as claimed in Lemma 4.

Lemma 4. There exists an integer solution to MILP[x ∗ ,q ∗ ]. Also, a rounded solution of an optimal BFS to MILP[x ∗ ,q ∗ ] corresponds to an allocation p ∗ such that swu(p ∗ ,I) ≥ (1e)swu(p,I) and swe(p ∗ ,I) ≥ (1-e)swe(p,I).

Proof. The construction of an integer solution to MILP[x ∗ ,q ∗ ] from p ′ is not difficult to verify, and we omit it here due to lack of space. We now prove the second part of the lemma. Let (x∗ ,y∗ ) be an optimal BFS of MILP[x ∗ ,q ∗ ] returned by Step 10 of Algorithm 1, and (¯x∗ ,y∗ ) be its rounded solution. One can see that (¯x∗ ,y∗ ) satisfies all the constraints because of the LP constraints, except (5).

In the following we will show how much the rounding step (line 11 of Algorithm 1) violates the constraints (5). Due to the last family of constraints of LP, it holds that �j∈Ot,v ¯ x∗ t, j ≥ � j∈Ot ,v x∗ t, j -1. Let Lt =�v∈St v�j∈Ot,v x∗ t, j . For every agent type t and for every item value v, we have that:

The second inequality follows from the definition of St . Consider the constraints (5). Let Kt = nt -�j∈Gt x∗ t, j - �k∈Ct≥qt y∗ t,k . Since (x∗ ,y∗ ) satisfies (5), from (6) we have:

since x ∗ t < q ∗ t /t and t = (1-a)/2 > 1/3 for a < 1/3.

Let Ut =�j∈Gt ˆut, j ¯ x∗ t, j +�k∈Ct y∗ t,k ˆut,k +�v∈St v�j∈Ot,v ¯ x∗ t, j . For every t, it suffices to consider the case when |Gt | > d, and thus Dt ⊂ Gt . Let s = argminj∈Dt ut, j and G ′ t ⊆ Gt be the set of items j for which x∗ t, j was fractional but rounded down to 0 by the rounding (line 11 of Algorithm 1). By Lemma 3, we have that |G ′ t | ≤W. Hence,

From (6) and (8) one can show, for every t ∈ [T], that

Now the integer solution (¯x∗ ,y∗ ) is converted into an allocation p ∗ by line 12 of Algorithm 1. By converting, we have that swu(p ∗ , ˆI) =�t∈[T]Ut ≥ (1-3a) f (x∗ ,y∗ ) ≥ (13a)swu(p ′ , ˆI) ≥ (1-4a)swu(p,I). The third inequality is due to the fact that p ′ can be converted into a feasible solution to MILP[x ∗ ,q ∗ ], whose value is equal to the utilitarian social welfare of p ′ w.r.t. ˆI.

We now prove that swe(p ∗ ,I) ≥ (1-5a)swe(p,I). Notice that the assignment of small items at Step 4 of Algorithm 2 is doable due to (7). Let A′ t be the set of agents who received configurations of values less than (1-3a)q ∗ t due to this algorithm, for all t ∈ [T]. Let i be such an agent. By the greedy assignment, the small items are assigned to her until her value exceeds (1-3a)q ∗ t . Suppose that j is the last item assigned to her. Then it must be that the value of the agent before getting the last item is at least (1-3a)q ∗ t - ˆut, j ≥ (1 - 3a)q ∗ t -a 2 x ∗ t > (1-3a)q ∗ t - 2a 2 1-a q ∗ t ≥ (1-4a)q ∗ t , for a < 1/3. The first inequality is because j is a small item and the second inequality follows from the fact that 1-a 2 x ∗ t ≤q ∗ t . Therefore, swe(p ∗ , ˆI)≥mint∈[T]{(1-3a)q ∗ t }. Note that q ∗ t ≥ (1-a) ˆ qt ≥ (1-a)2 qt ≥ (1-2a)qt . Hence, swe(p ∗ , ˆI) ≥mint∈[T]{(1-3a)(1-2a)qt}≥mint∈[T]{(15a)qt } = (1 - 5a)swe(p ′ , I) ≥ (1 - 5a)swe(p , I).

Note that by rounding down item values, it holds that ui(p ∗ i ) ≥ ˆui(p ∗ i ) for all i. Hence, swe(p ∗ ,I) ≥ swe(p ∗ , ˆI) ≥ (1 - 5a)swe(p,I), and swu(p ∗ ,I) ≥ swu(p ∗ , ˆI) ≥ (1 - 4a)swu(p , I).

Finally, by choosing a = e 5 we have completed the proof of Lemma 4.

Complexity analysis of Algorithm 1. It is not difficult to see that the overall running time of Algorithm 1 is upperbounded by T = O(P1 · P2 · P3 · P4) in which P1, P2, and P3, respectively, are the sizes of the sets X, Q, and Q, while P4 is the amount of time needed for solving MILP[x,q] and for solving the linear program LP. We have that P1 = O(log T (m· umax)), P2 is at most |H1|d × · · · × |HT |d = O(m T( W a +1) ) (which is polynomial in m since T, W, and a are constants), and P3 = O(1). To estimate P4, note that MILP[x,q] has many variables but a constant number of integer ones and thus can be solved in time polynomial in the size of input (see Lenstra [1983]). In addition, computing a basic (integer) solution to LP can be also done in polynomial time. Hence, T is a polynomial in the size of I. This completes the proof of Theorem 3.

5 Conclusions

We have studied the problem of computing approximately max-min fair and utilitarian efficient allocations for additive valuation functions. In particular, we have modeled the problem as a bi-criteria optimization problem and presented two polynomial-time algorithms for constructing approximate Pareto sets, in two special but nontrivial settings when there are a few agent types or there are a few item types. Our first algorithm is based on a dynamic programming scheme that has been shown to be very useful in solving other fair and efficient allocation problems. In fact, one of our results regarding finding min-max allocations for the constant-item-type case answers an open problem raised by Jansen and Maack [2019] in the context of machine scheduling. Our second algorithm is achieved by applying a linearprogramming method, which can be seen as a significant extension of Jansen and Maack's method. We believe that our technique can be potentially applied to a wider class of resource allocation problems with more general objectives, e.g., the ones considered by Alon et al. [1998]. This would be an interesting direction for future work. Another idea is to see whether we can obtain similar results to what we have done in this paper with respect to the criterion of envy-freeness.

Acknowledgments

We thank the anonymous reviewers for their very helpful comments and suggestion. Part of this work has been done when the first author was visiting Vietnam Institute for Advanced Study in Mathematics and their support is kindly acknowledged. This work was partially supported by the Stay-Connected@HHU Programme and DFG grants RO 1202/14-2 and RO 1202/21-1.