Complexity of Efficient and Envy-Free Resource Allocation: Few Agents, Resources, or Utility Levels

1 Introduction

Fair allocation of resources is a major theme in society and technology [Walsh, 2015]. In this work, following Bouveret and Lang [2008], we focus on finding fair allocations of indivisible resources (for general information and an overview, refer to the recent survey by Bouveret et al. [2016]); herein, fairness translates into "envy-freeness" and (Pareto-)efficiency, two of the most common requirements.

Our general setting is as follows. We are given a set of indivisible resources and a set of agents; each agent may specify preferences in such a way that for any two subsets of the resources we can tell which one (if any) she prefers to the other. The goal is to assign resources to agents such that some fairness criteria are met. We focus on the criteria of being envy-free and efficient. An allocation of resources to agents is called envy-free if each agent likes her subset of assigned goods (i.e., her resource bundle) at least as much as the bundles assigned to other agents. Since assigning every agent nothing would be envy-free, it is necessary to add a second requirement: efficiency. More precisely, we search for a Pareto-efficient allocation, that is, an allocation of resources where one cannot make any agent better off without making

Robert Bredereck and Rolf Niedermeier

TU Berlin, Germany ¶robert.bredereck,rolf.niedermeier♦@tu-berlin.de

at least one agent worse off. Finally, a few words about the agents' preferences: As Bouveret and Lang [2008] pointed out, allowing for arbitrary preference orders comparing all possible bundles would lead to exponential-size encodings. Hence, more compact representations are needed. We focus on monotonic dichotomous preferences and monotonic additive preferences. The former means that bundles are either acceptable or not, and the acceptable bundles are characterized by monotonic Boolean formulas; the latter means that each bundle has a utility score that is the sum of utilities of the individual resources contained, and each individual utility is non-negative. Refer to Section 1 for formal definitions.

It is not always possible to achieve both Pareto-efficiency and envy-freeness at the same time (e.g., if there are fewer resources than agents and each agent accepts all non-empty bundles). Our central computational problem is as follows.

EEF-ALLOCATION

Input: A set A of n agents and a set R of m resources. Each agents has preferences over the subsets of R. Question: Is there an allocation of the resources

in R to the agents from A that is Pareto-efficient and envy-free?

Previous results. For both monotonic dichotomous and monotonic additive preferences, EEF-ALLOCATION is known to be complete for S P 2 , which is a class on the second level of the Polynomial Hierarchy and consists of all problems that can be solved in nondeterministic polynomial time given an oracle for NP. Bouveret and Lang [2008] also showed intractability (mostly NP-hardness) and polynomial-time solvability of many restricted cases. Further computational complexity studies were performed for the case of incomplete preferences, achieving mostly intractability results [Aziz et al., 2014; Bouveret et al., 2010]. A further slightly different line of research softens the strict requirement of envy-freeness by investigating how to decrease the degree of envy, in this sense taking an "approximate view" on fairness [Lipton et al., 2004; Nguyen and Rothe, 2013]. In summary, considering its high practical relevance, there are comparatively few studies on the computational complexity of EEF-ALLOCATION. In this work, we add to the complexity knowledge by performing a first systematic parameterized complexity analysis for EEFALLOCATION.

Our results. We survey our (mostly parameterized) computational complexity results in Table 1. Compared to the focus on classic computational complexity investigations in previous work, we obtain a more fine-grained picture of the complexity landscape. The three parameters we consider are the number n of agents, the number z of numbers for additive preferences (only in combination with n), and the number m of resources. Moreover, for the additive case, we distinguish between unary versus binary encodings of the utility values, and consider the special cases of agents having 0/1 preferences or identical preferences.

A result particularly interesting from a technical point of view is that, using the Boolean Hierarchy, we provide almost tight upper and lower bounds concerning the number of NP oracle calls needed to solve EEF-ALLOCATION with n agents and monotonic dichotomous preferences. Our results further include parameterized hardness results (W[1]- hardness/completeness), and encouraging fixed-parameter tractability (FPT) results, sometimes based on integer linear program formulations exploiting a famous result due to Lenstra [1983] (referred to as ILP-FPT). Since for all parameters even small values may occur in practice (even the case n = 2 is frequently studied), our classification results give hope for practically feasible, exact algorithms for the in general S P 2 -complete problems. Due to space constraints, we omit many proof details.

Preliminaries on Resource Allocation. We now formalize the notions required for our study of EEF-ALLOCATION.

Definition 1. An allocation of a set of resources R to a set of agents A is a mapping p : A!2 R such that p(a) and p(a0 ) are disjoint whenever a 6= a0 . For any agent a 2 A, we call p(a) the bundle of a under p. We call p complete if Sa2A p(a) = R.

In our setting, each agent is associated with a preference relation, which we call the agent's preferences.

Definition 2. A preference relation ⪯ over a set of resources R is a total preorder over 2 R . We call ⪯ monotonic if X ⪯Y holds for any X ✓Y ✓ R. We write X ≺Y if X ⪯Y but not Y ⪯ X.

To allow for a succinct representation of preferences, we first consider the restriction that agents either like a bundle or not, according to a Boolean formula over the resources.

Definition 3. We call a preference relation ⪯ over a set of resources R dichotomous if it is represented by a Boolean formula j⪯ over R such that for any X↪Y ✓ R it holds that X ⪯Y if and only if X ♣= j⪯ implies Y ♣= j⪯. We say an allocation p satisfies agent a if p(a) ♣= j⪯a .

For dichotomous preferences, ⪯ is monotonic if and only if j⪯ contains only the connectives _ and ^ (in particular no ≻).

In the second restriction of preference relations we consider, agents give a utility value to each individual resource. The utility of a bundle is then the sum of the utilities of its elements.

Definition 4. We call a preference relation ⪯ over a set of resources R additive if there is a utility function u : R!Z such that for any X↪Y ✓R it holds that X ⪯Y if and only if u(X)  u(Y), where u(X), for X ✓ R, is defined as Âr2X u(r).

For additive preferences, ⪯ is monotonic if and only if the values of u are non-negative. We call additive preferences 0/1 if each utility function maps to ¶0↪1♦, and identical if each agent has the same utility function.

Given the preferences of each agent, we can define our two desired criteria for allocations.

Definition 5. Let R be a set of resources, let A be a set of agents, and let ⪯a denote the preference relation of agent a 2 A. We call an allocation p of R to A envy-free if for each pair of agents a↪b 2 A it holds that p(b) ⪯a p(a). We say that an allocation p 0 of R to A dominates another allocation p if for all a 2 A it holds that p(a) ⪯a p 0 (a), and for some a 2 A it holds that p(a) ≺a p 0 (a). We call p Pareto-efficient if there is no allocation of R to A that dominates p, and we call p an EEF allocation if it is both Pareto-efficient and envy-free.

Preliminaries on Complexity. To study the parameterized complexity [Cygan et al., 2015; Downey and Fellows, 2013; Flum and Grohe, 2006; Niedermeier, 2006] of EEFALLOCATION, we declare some part of the input the parameter (e.g., the number of agents or the number of resources). We call a parameterized problem fixed-parameter tractable if it is in the class FPTof problems solvable in time f (r) · ♣I♣O(1) , where ♣I♣ is the size of a given instance encoding, r is the value of the parameter, and f is an arbitrary computable (typically super-polynomial) function. We use the O⇤ notation that omits factors polynomial in the input size to emphasize or to compare the super-polynomial factors in the running time. To obtain parameterized intractability, we use a hierarchy of classes of parameterized problems, FPT ✓ W[1] ✓ W[2] ✓ · · · ✓ XP. It is widely believed that the first inclusion is proper. The notions of hardness and completeness for parameterized classes are defined through parameterized reductions similar to classical polynomial-time many-one reductions. For this paper, it suffices to additionally ensure that the value of the parameter in the problem we reduce to depends only on the value of the parameter of the problem we reduce from.

The class XP contains all problems that can be solved in ♣I♣O(r) time for a function f solely depending on the parameter r. Note that containment in XP ensures polynomial-time solvability when r is a constant, whereas FPT additionally ensures that the degree of the polynomial is independent of r. Unless P = NP, membership in XP can be excluded by showing that the problem is NP-hard for a constant parameter value (for short, we say the problem is para-NP-hard). If the problem is in NP, then we can solve it by one call to an NP oracle (in practice, this means that one can solve the problem with one call of a SAT or Integer Linear Program (ILP) solver).

To show that one oracle call may not suffice, we use manyone reductions to classes BHn of the Boolean Hierarchy. The class BH2k can be defined as the class of problems P for which there are problems P1↪ ▷ ▷ ▷Pk, which are in NP, and Q1↪ ▷ ▷ ▷ ↪Qk, which are in coNP, such that an instance I of P is a yes-instance if and only if for some i it holds that I is a yes-instance instance of both Pi and Qi [Wagner, 1987]. To solve BHn-complete problems, one needs O(n) oracles calls in parallel or O(log(n)) oracle calls in a sequential manner (allowing other computations in between).

2 Basic Observations

We start with some observations and introduce some concepts that simplify our investigations in later sections.

For monotonic additive preferences, we assume that for every resource r there is at least one agent a that assigns positive utility to it, that is, ua(r) > 0. Resources that do not satisfy this condition can be safely ignored. We may also assume that no agent assigns utility 0 to all resources because such agents can safely be given nothing as they will not envy anyone and will never be relevant for Pareto-efficiency. Furthermore, we can use an alternative definition of an EEF allocation.

Definition 6. Given an agent set A, a resource set R, and utility functions ua : R!Z encoding the preferences of each agent a 2 A, an allocation p : A!2 R is Pareto-efficient if

and envy-free if

If we further restrict the preferences to be identical or 0/1preferences, then Pareto-efficiency essentially boils down to completeness. (Note that Bouveret and Lang [2008] use similar observations.) The key insight is that with preferences being identical or 0/1, there is in fact no agent that assigns higher utility to some resource r than the agent to which resource r is allocated. So, by the pigeonhole principle, in order to increase the sum of utilities for one agent, we have to decrease the sum of utilities for another agent.

Observation 1. In case of monotonic additive identical preferences or 0/1 preferences, an allocation is Pareto-efficient if and only if it is complete and every resource r is allocated to an agent that assigns positive utility to r.

3 FewResources

In this section, we discuss the complexity of finding EEF allocations in case of few resources.

Recall from Section 2 that, for monotonic additive preferences, in order to find an EEF allocation, we can safely remove every agent that assigns utility 0 to all resources and every resource to which all agents assign utility 0. Hence, together with a simple preprocessing and brute-force algorithm, we end up with the following. To this end, we say two EEFALLOCATION instances are equivalent if they are either both yes-instances or both no-instances.

Proposition 1. Given an instance of EEF-ALLOCATION with monotonic additive preferences and m resources, one can compute an equivalent instance with m resources and at most m agents in linear time. In particular, one can solve EEF-ALLOCATION in O⇤ (m 2m) time.

Proof. As we have seen, we may assume that no agent assigns utility 0 to each resource and no resource is assigned utility 0 by all agents. If there are now more than m agents, one will necessarily envy another in every Pareto-efficient allocation. Otherwise we generate each of at most m m allocations p and check in O⇤ (m m) time whether another allocation dominates p to ensure Pareto-efficiency. If p is not dominated, then check in m 2 time whether it is also envy-free.

After preprocessing, both the number n of agents and the number m of resources are linearly bounded in terms of our parameter in case of additive preferences. In contrast, for dichotomous preferences we give an exponential upper bound on the number of agents and show that under reasonable complexity assumptions, no polynomial upper bound exists.

Proposition 2. Given an instance of EEF-ALLOCATION with monotonic dichotomous preferences and m resources, one can compute an equivalent instance with m resources and at most 2 m · (m+1) agents in quadratic time. Unless NP ✓ coNP◁poly, one cannot compute an equivalent instance of size polynomial in m in polynomial time.

Proof. We assume formulas to be non-tautological (otherwise we could just ignore the respective agents) and to be in CNF or DNF, which allows us to test equivalence by syntactic equality after efficiently removing redundant terms [Mundhenk and Zeranski, 2011]). As the key concept for this proof, we define a maximal set of agents having the same preferences as agent class. Observe that there are at most 2 m bundles of resources and an agent can either like a bundle or not. Thus, there are at most 2(2 m ) agent classes and we can also compute all agent classes in polynomial time (by n 2 tests for equivalence).

Let p be an envy-free allocation and let A0 ✓ A be an agent class. Note that either all agents from A0 are satisfied, i.e., 8a0 2 A0 : p(a0 ) ♣= j⪯a0 or no agent from A0 is satisfied, i.e., @a0 2A0 : p(a0 ) ♣=j⪯a0 . If ♣A0 ♣ >m, only the latter can happen because we cannot satisfy more than number of resources m many agents. To obtain an equivalent instance whose size only depends on a function in m, we exhaustively apply the following simple data reduction rule: If there is some agent class with more than m+1 agents, then keep arbitrary m+1

of them and remove the rest. In terms of parameterized algorithmics, this instance is a (super-polynomial sized) problem kernel with respect to the number m of resources.

For the kernelization lower bound, we use the or-crosscomposition framework by Bodlaender et al. [2014] with SAT as our source language, using ideas from the proof of Theorem 2. We omit the details due to lack of space.

By simple brute-force search on this kernel, we obtain fixedparameter tractability. However, naive brute-force comes with running time O⇤ ((2 m · (m+1))2m). Fortunately, by using a smarter algorithm that combines brute-force with the computation of perfect matchings in auxiliary graphs, we can significantly lower the running time. Similar ideas also help improve for additive preferences in case of identical preferences or 0/1 preferences. We summarize our findings as follows.

Theorem 1. EEF-ALLOCATION with monotonic dichotomous preferences can be solved in O⇤ (B(m)2 ) time; EEFALLOCATION with monotonic additive preferences can be solved in O⇤ (S(m↪n)2 · n!) time; EEF-ALLOCATION with additive 0/1 preferences or with monotonic additive identical preferences can be solved in O⇤ (S(m↪n)) time, where B(m) 2 O(m m) denotes the m-th Bell number, and S(m↪ n) 2 O(m m◁m!) denotes a Stirling number of the second kind.

Theorem 1 basically provides FPT-classification results which might be practically relevant for very small values for m. Nevertheless, the corresponding running-time bounds support our impression that more restrictive preference classes simplify the task of finding an EEF allocation.

4 FewAgents

In this section, we discuss the complexity of finding EEF allocations in case of few agents.

Bouveret and Lang [2008] already showed NPcompleteness for EEF-ALLOCATION with monotonic dichotomous preferences and only n = 2 agents. Although this excludes hope for fixed-parameter algorithms with respect to n, the NP-membership indicates that one might be able to solve EEF-ALLOCATION with only few calls to an NP oracle. Providing almost tight upper and lower bounds, we show how many calls to an NP oracle are needed to solve EEF-ALLOCATION with n agents. This is in line with recent research by de Haan and Szeider; Endriss et al. [2014; 2015], which, motivated by the practical success of SAT solvers, investigates whether certain problems can be solved by an algorithm having access to a SAT oracle using FPT time.

Theorem 2. EEF-ALLOCATION with monotonic dichotomous preferences and n ≥ 5 agents is in BH 2 n+1 and BH 2 n-4 - hard.

Proof. Membership. Note that the fact that each instance has n agents allows us to assume that the set A of agents is the same over all instances (albeit the preferences may differ). Let A1↪ ▷ ▷ ▷ ↪A2 n denote all subsets of A. Now, for any 1  i  2 n , let Pi be the problem of deciding whether there is an envy-free allocation satisfying exactly the agents in Ai, and let Qi be the problem of deciding whether there is no allocation p : A!2 R satisfying all agents in Ai and one additional agent.

Pi is in NP: We can clearly check in polynomial time if an allocation satisfies exactly the agents in Ai and is envy-free.

The complement of Qi is in NP: We can check in polynomial time if an allocation satisfies Ai and an additional agent.

Obviously there is an EEF allocation for an instance if and only if this instance is a yes-instance for some Pi (indicating that an envy-free allocation p satisfies exactly Ai) and at the same time for Qi (indicating that no allocation dominates p).

Hardness (construction only). We set n0 := 2 n -5 and provide a polynomial-time reduction from the following BH2n0 -hard problem [Wagner, 1987]: Given Boolean formulas c1↪ ▷ ▷ ▷ ↪cn0 and y1↪ ▷ ▷ ▷ ↪yn0 , we ask whether for some i it holds that ci is satisfiable while yi is unsatisfiable. We assume w.l.o.g. that the variables of any pair of formulas are disjoint and formulas are non-empty. We also assume that each formula is in negation normal form, i.e., no binary connectives other than _ and ^ occur, and negation occurs only directly in front of variables. Given any set S, we write S0 to denote ¶v0 ♣ v 2 S♦. For any Boolean formula a, we denote the set of variables in a by Var(a), and for any i we define Vi = Var(ci)[Var(yi) as well as Li =Vi [V 0 i . Let c ⇤ i and y ⇤ i be the result of replacing each literal of the form≻v by v0 in ci and yi, respectively.

In the following, we construct an EEF-ALLOCATION instance with agents 1↪ ▷ ▷ ▷ ↪ n having as preferences j1↪ ▷ ▷ ▷ ↪ jn, respectively. Let the set of resources be ¶x↪y♦[L1 [· · ·[Ln0 .

The intuition behind the remaining n-5 agents is that after satisfying them, only the literals for at most one pair of formulas c ⇤ i ↪y ⇤ i are left for distribution. If n0 = 4, for example, we realize this by means of an additional agent that claims L1 [L2 or L3 [L4, and another agent that claims L1, L2, L3, or L4. This can be generalized such that one agent claims one half of all literals, the next claims one quarter, and so on. Formally, for 1  i  n-5 and 0  j  2 i -1, we define Pi↪ j = L j·n0 ◁2 i+1 [· · ·[L j·n0 ◁2 i+n0 ◁2 i . For 1  i  n-5, we now define j5+i = x_ W2 i-1 j=0 Vl2Pi↪ j l. This reduction is doable in polynomial time since n is logarithmic in n0 . The resulting EEF-ALLOCATION instance is a yes-instance if and only if some ci is satisfiable while yi is unsatisfiable. Due to lack of space, we only give some intuition: Agent 1 must receive x in any EEF allocation p, which forces p to satisfy all agents except 4 and 5. Agent 3's bundle encodes a model for some ci, as the agents 6↪ ▷ ▷ ▷ ↪ n-5 and 2 prevent her from getting both v and v0 for any variable v. If yi were satisfiable, there would be envy between agents 4 and 5 under p since p is efficient.

This result entails that the parameter n does not allow us to reduce the problem to, e.g., SAT in FPT time, which would have been good news due to the S P 2 -completeness of the general problem. In fact, membership in BH 2 n+1 enables us to solve an EEF-ALLOCATION instance with 2 n+1 parallel NP oracle calls or O(n) sequential NP oracle calls. If we are not only interested in solving the decision problem but, e.g., also in computing a solution, there are good (rather technical complexity-theoretic) reasons to believe that the number of sequential oracle calls may further increase [Jenner and Tor´an, 1995]. Actually, O(n 2 m) sequential NP oracle calls are sufficient for finding an EEF-allocation: Consider the extended version of EEF-ALLOCATION where the input additionally specifies a partial allocation of some resources to agents and one asks for an EEF-allocation that extends the partial allocation. Start with the empty partial allocation and extend it step by step to a complete EEF-allocation as follows. Iteratively take an unallocated resource r j and find an agent to which r j can be allocated in an EEF-allocation by solving the extended EEF-ALLOCATION problem (using O(n) sequential NP oracle calls each time). To see that the extended EEFALLOCATION problem can indeed be solved with only O(n) sequential NP oracle calls, one can use a BH 2 n+1 -membership proof that works analogously to the proof of Theorem 2.

We next consider the case of additive preferences, for which Bouveret and Lang [2008] have shown NP-hardness even in the case of identical preferences and n = 2 agents. However, their hardness result relies on preferences encoded in binary, which leaves the possibility open that a pseudopolynomial-time algorithm exists. We show that the problem with preferences encoded in unary is W[1]-complete if all agents have the same preferences, which implies NP-hardness and W[1]-hardness for the parameter n if the agents may have different preferences. In Theorem 4, we will show that the latter W[1]-hardness can be complemented by showing that the problem can be solved in polynomial time for constant n.

Theorem 3. EEF-ALLOCATION with monotonic additive preferences encoded in unary is W[1]-complete with respect to the number n of agents if all agents have the same preferences.

Proof. For W[1]-hardness, we give a parameterized reduction from the UNARY BIN PACKING problem, which is W[1]-hard with respect to the number b of bins [Jansen et al., 2013].

UNARY BIN PACKING

Input: Positive integers w1↪ ▷ ▷ ▷ ↪wm↪ b↪C in unary. Question: Is there an assignment of m items with weights w1↪ ▷ ▷ ▷ ↪wm to at most b bins such that none

of the bins exceeds weight capacity C?

The set of resources consists of a set R := ¶r1↪ ▷ ▷ ▷ ↪rm♦ of item resources and a set D := ¶d1↪ ▷ ▷ ▷ ↪dq♦ of dummy resources, where q := b ·C-Â1imwi is the total amount of "unused capacity". Create agents a1↪ ▷ ▷ ▷ ↪ab such that each agent ai has a utility function ui that sets ui(dj) = 1 for any dummy resource dj and ui(r j) =wj for each item resource r j.

We show that there is an assignment of m items with weights w1↪ ▷ ▷ ▷ ↪wm to at most b bins such that none of the bins exceeds capacity C if and only if there is an EEF allocation.

"Only if" direction: Assume that there is an assignment of m items with weights w1↪ ▷ ▷ ▷ ↪wm to at most b bins such that none of the bins exceeds capacity C. For each bin j, let P( j) denote the set of items assigned to j and letW( j) :=Âi2P( j) wi denote the total weight of the items assigned to j. We create an EEF allocation p as follows. For each 1  j  b, p( j) contains all item resources corresponding to the items from P( j) and further C-W( j) dummy resources. First, no agent envies any other agent since each receives a bundle with utility sumC. Second, p is also Pareto-efficient by Observation 1, since p is complete and all utilities are positive.

"If" direction: Assume that there is an EEF allocation p. Recall that p must be complete due to Observation 1, so the total sum of utilities over all bundles in p is exactly b·C. Since p is Pareto-efficient and envy-free, the total utility Âr j2p(i) ui(r j) of the bundle allocated to agent i is exactly C: It is the same for each agent because the agents have the same preferences and the allocation is envy-free. Hence, assigning all items corresponding to the resource items of bundle p(i) to bin i is a solution for the UNARY BIN PACKING instance. This completes the W[1]-hardness proof. For W[1]-membership we can reuse ideas from the hardness proof.

5 Few agents and FewUtility Levels

In this section, we focus on instances of EEF-ALLOCATION with monotonic additive preferences where the utility functions of the agents have only few different values. To this end, let z denote the number of different values that occur in the utility functions (c.f. [Fellows et al., 2012]), and let zmax denote the maximum number that occurs in any utility function. Since EEF-ALLOCATION is NP-hard already for additive 0/1 preferences (z = 2 and zmax = 1) [Bouveret and Lang, 2008], we further assume that there are only few agents to obtain positive results.

The decisive advantage of monotonic additive preferences is that knowing all ua(p(a0 )) values for all allocations p and all pairs (a↪a0 ) of agents is enough to check the existence of an EEF allocation. By a dynamic programming algorithm based on this observation, we show that EEF-ALLOCATION with monotonic additive preferences encoded in unary can be solved in polynomial time if the number n of agents is a constant. Note that in case of preferences encoded in unary, z and zmax are upper-bounded by the instance size.

Theorem 4. EEF-ALLOCATION with monotonic additive preferences can be solved in O((m· zmax +1)n 2 ·mn 2 ) time.

Proof. We denote the agents by integers 1↪ ▷ ▷ ▷ ↪ n and use the following (n 2 +1)-dimensional binary table where entry

(for 1  k  m and 0  xi↪ j  m · zmax) is 1 if and only if there is an allocation p that (i) assigns each of the first k resources to some agent and (ii) ensures that ui(p( j)) = xi↪ j for 1  i↪ j  n.

After computing the table T our algorithm answers "yes" if there is some entry T(m, x1↪1↪ ▷ ▷ ▷ ↪x1↪n, x2↪1↪ ▷ ▷ ▷ ↪x2↪n, ▷ ▷ ▷ , xn↪1, ▷ ▷ ▷ ↪xn↪n) = 1 such that the following hold: (i) For all i↪ j 2 ¶1↪ ▷ ▷ ▷ ↪n♦ it holds that xi↪i ≥ xi↪ j; and (ii) there is no entry T(m, x01↪1 ↪ ▷ ▷ ▷ ↪x01↪n , x02↪1 ↪ ▷ ▷ ▷ ↪x02↪n , ▷ ▷ ▷ , x0n↪1 , ▷ ▷ ▷ ↪x0n↪n) = 1 where 91  i⇤  n : x0 i⇤ ↪i⇤ > xi⇤ ↪i⇤ and 81  i  n : x0 i↪i ≥ xi↪i; otherwise, the algorithm answers "no". We now show how to compute this table in polynomial time.

In the following, for technical reasons we assume that T(k, x1↪1↪ ▷ ▷ ▷ ↪x1↪n, x2↪1↪ ▷ ▷ ▷ ↪x2↪n, xn↪1↪ ▷ ▷ ▷ ↪xn↪n) = 0 whenever one tries to access an entry out of the table's range (e.g., with k < 1 or xi↪ j < 0). We compute all entries T(k, x1↪1↪ ▷ ▷ ▷ ↪ x1↪n, x2↪1↪ ▷ ▷ ▷ ↪ x2↪n, xn↪1↪ ▷ ▷ ▷ ↪ xn↪n) assuming that all entries T(k -1, x1↪1↪ ▷ ▷ ▷ ↪x1↪n, x2↪1↪ ▷ ▷ ▷ ↪x2↪n, xn↪1↪ ▷ ▷ ▷ ↪xn↪n) are known. The key insight is that for each allocation p 0 of the first k resources, there is an allocation p of the first k - 1 resources such that resource rk can be assigned to some agent i⇤ and the following equations hold for every agent i: (a) ui(p 0 (i⇤ )) = ui(p(i⇤ )) +ui(rk), and (b) ui(p 0 ( j)) = ui(p( j)) for j 6= i⇤ . Formally, we set the entry T(k, x1↪1↪ ▷ ▷ ▷ ↪x1↪n, x2↪1↪ ▷ ▷ ▷ ↪x2↪n, ▷ ▷ ▷ , xn↪1↪ ▷ ▷ ▷ ↪xn↪n) to 1 if and only if there is some i⇤ 2 ¶1↪ ▷ ▷ ▷ ↪ n♦ such that

where, for any 1  i↪ j  n, we define yi↪ j as

For correctness, note that if our algorithm answers "yes", then there clearly is an EEF allocation by the definition of the table T. Now, assume towards a contradiction that the algorithm answers "no", although there is an EEF allocation p. This means that either entry T(m, u1(p(1))↪ ▷ ▷ ▷ ↪u1(p(n)), u2(p(1))↪ ▷ ▷ ▷ ↪u2(p(n)), un(p(1))↪ ▷ ▷ ▷ ↪un(p(n))) = 0 or this entry is 1 but there is an entry T (m, x01↪1 ↪ ▷ ▷ ▷ ↪ x01↪n , x02↪1 ↪ ▷ ▷ ▷ ↪ x02↪n , ▷ ▷ ▷ , x0n↪1 , ▷ ▷ ▷ ↪ x0n↪n) = 1 where 91  i⇤  n : x0 i⇤ ↪i⇤ > ui⇤ (p(i⇤ )) and 81  i0  n : x0 i0 ↪i0 ≥ ui0 (p(i0 )). The former would imply that p does not allocate all m resources, which cannot be true since p is Pareto-efficient and we assume that for each resource r, there is at least one agent a with ua(r) > 0. The latter would imply that p is not Pareto-efficient-a contradiction.

As for the running time, observe that the table is of size m· (m· zmax +1)n 2 , which is a polynomial in the instance size if the number n of agents is a constant and zmax is encoded in unary. To compute a table entry, one has to check at most n previous table entries (involving n subtractions per check).

The algorithm from Theorem 4 can be used not only to decide the problem but also to actually find an EEF allocation. To this end, one basically replaces the binary entries by concrete allocations.

Parameterized by n and z alone, EEF-ALLOCATION is para-NP-hard: Bouveret and Lang [2008] showed NPhardness for EEF-ALLOCATION with two agents and for EEF-ALLOCATION with 0/1 preferences. Theorem 4 gives XP membership for parameter n and unary encoding of the utility values. Since the latter implies that z and zmax are polynomially upper-bounded by the instance size, cases where n and z are both small seem to be easier to solve. We further explore this by considering the combined parameter (n+z) and the parameter n for 0/1 preferences.

Theorem 5. EEF-ALLOCATION is fixed-parameter tractable (i) with respect to the combined parameter (n+z) for identical monotonic additive preferences, and (ii) with respect to n alone for additive 0/1 preferences, where n denotes the number of agents and z is the number of different values that occur in the utility functions.

Proof. We define the fingerprint of some resource r j to be the size-n integer vector f j := (u1(r j)↪u2(r j)↪ ▷ ▷ ▷ ↪un(r j)). We denote the set of fingerprints by F and the number of resources that have fingerprint f by #( f ). Observe that there are at most z n different fingerprints and that, given an EEF allocation p, exchanging any two resources with the same fingerprint between two bundles in p results in another EEF allocation. Moreover, we can characterize EEF allocations by solely specifying how many resources with fingerprint f are allocated to agent ai for each agent ai 2A and each fingerprint f .

Using the fingerprint concept, we develop an integer linear programming formulation as follows. For each agent ai 2 A and each fingerprint f , create one integer variable x f i that denotes the number of resources with fingerprint f allocated to agent ai.

We achieve envy-freeness by adding the constraints

where f [i] denotes the i-th entry in fingerprint f .

To obtain Pareto-efficiency, we add the constraint sets

Constraint set (2) ensures completeness and Constraint set (3) ensures that each resource is allocated to an agent that assigns positive utility to this resource. Hence, due to Observation 1, we obtain Pareto-efficiency.

Finally, fixed-parameter tractability follows by the famous result of Lenstra [1983] (later improved by Kannan; Frank and Tardos [1987; 1987]) that says that an ILP with r variables and ` input bits can be solved in O(r 2▷5r+o(r) `) time.

6 Conclusion

The goal of this work was to contribute to a more fine-grained understanding of the computational complexity landscape of EEF-ALLOCATION for monotonic preferences (dichotomous and additive), which is S P 2 -complete in general. On the positive side, we obtained encouraging fixed-parameter tractability results, indicating practical feasibility of relevant special cases. Indeed, it remains to explore whether the efficiency of the algorithms can be further improved-our focus was on complexity classification rather than engineering best possible running times-and, in the same spirit, to consider even more special but practically relevant cases such as a fixed small number of agents. Indeed, in the long run implementation and experiments with the developed algorithms seems promising. To this end, also studying further natural parameterizations could be helpful. A different theoretical route would be to extend the investigations also to incomplete preferences [Aziz et al., 2014; Bouveret et al., 2010] or approximate envy-freeness [Lipton et al., 2004; Nguyen and Rothe, 2013].

Acknowledgments This work was supported by the Austrian Science Fund (FWF), project Y698, and by the German Research Foundation (DFG), project AFFA (NI 369/15, BR 5207/1).