Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey

1 Introduction

In fair division of indivisible goods, one seeks to allocate the goods (or items, or resources) to the agents so as to satisfy certain fairness conditions. This is an old problem with many important applications in economics, artificial intelligence (AI), and related fields (see, e.g., the recent survey by [Amanatidis et al., 2022] and the book chapters by [Bouveret et al., 2016] and [Lang and Rothe, 2015]). From a computer scientist's point of view, there is a range of fascinating computational problems that need to be solved, and computational techniques that need to be explored. The survey by [Walsh, 2020] provides a comprehensive list of fair allocations problems along with challenging open questions, while the work of [Aziz et al., 2022a] is more focused on approximation algorithms, which produce near-optimal solutions with guaranteed bounds. To complement these works, our paper aims to give a best understanding of the state-of-the-art approaches that can be applied to solve these problems exactly, rather than approximately. The reasons of studying such approaches are two-fold. Firstly, exact fair solutions may be required in certain real-world applications where approximate solutions may not be allowed or may not be good enough. Secondly, the research on faster exponential-time algorithms helps to better understand the reasons for the intrinsic intractability of fair allocation problems, which may also show ways for how to tackle them. Also, even though many of these problems are known to be NP-hard, some of them have been shown to be solved by algorithms running much faster than the brute-force approach, while others do not seem to allow such sophisticated algorithmic techniques. Therefore, research on faster exponential-time algorithms for fair allocation problems will be very useful for practical applications. We survey the state of the art and point to some of these research challenges.

2 Preliminaries

The input I = {A,O, U} of an allocation problem consists of three components: A = {1, 2, . . . , n} = [n] is the set of agents, O = {1, 2, . . . , m} = [m] is the set of items, and U = {u1, u2, . . . , un} is the set of the agents' valuation functions expressing their utilities over the set of items. Formally, we have that ui : 2O → N for i ∈ A. We restrict our attention to the class of monotonic additive valuation functions which have been widely used in the context of resource allocation. A valuation function is monotonic additive if for any subset (or bundle) S ⊆ O, ui(S) = ∑j∈S uij, where uij is agent i's nonnegative integer value for item j. We assume that the value of the empty bundle is zero for every agent and, to avoid triviality, that m ≥ n. An allocation π is a partition of the set of items into n subsets, denoted as π1, . . . , πn, such that ⋃ni=1 πi = O, where πi is the bundle allocated to agent i.

High-multiplicity setting. In this setting, the set A of agents can be partitioned into p types [p] = {1, . . . , p}, and the set O of items can be partitioned into q types [q] = {1, . . . , q}. Agents are said to be of the same type if they agree on the values of all items. That is, for every two agents i, i′ of type k, it holds that uij = ui′ j for every item j. Similarly, we say that two items are of the same type if they have the same value for every agent. Formally, for every two items j, j ′ of type l, it holds that uij = uij ′ for every agent i.

Fairness notions. There are two common ways for interpreting fairness. The first one is to make use of collective utility functions (CUFs) to fairly aggregate individual agents' utilities, which then is maximized. The CUFs that perhaps have been most intensively studied are the min function, which is defined as the lowest utility among agents' utilities [Moulin, 1988], and the product function, which is defined as the product of individual agents' utilities [Nash, 1950] (see, e.g., [Moulin, 1988] for other choices of CUFs).

Definition 1 (max-min fairness). The egalitarian social welfare (ESW) of an allocation π is defined as minni=1ui(πi). We say an allocation of maximum ESW is max-min fair (MMF).

Definition 2 (Nash social welfare). The Nash social welfare (NSW) of an allocation π is defined as ∏ni=1ui(πi). An allocation of maximum NSW is said to be maximal Nash (MNSW).

Another way of defining fairness is to first specify what can be considered to be a fair share of an agent, and then to define an allocation to be fair if every agent can receive her fair share in it. Two common notions of fair shares studied in the literature are maximin share [Budish, 2011] and proportional share originally introduced by [Steinhaus, 1948].

Definition 3 (maximin share). We define the maximin share of an agent i ∈ A as mmsi = maxπ mink∈A{ui(πk)}. An allocation π is said to be maximin share (MMS) if ui(πi) ≥ mmsi for every i ∈ A.

Intuitively, the maximin share criterion means that an agent may choose an allocation first but then has to take the last bundle that is left in the chosen allocation, thus maximizing her worst utility over all allocations. We will focus on this notion and will mention the dual notion of the minimax share [Bouveret and Lemaˆıtre, 2016] only en passant, which is defined by letting agent i, faced with the worst allocation for her, choose her bundle first in it: minπ maxk∈A{ui(πk)}.

Proportional share allocations (PROP) can be defined similarly. Such an allocation must allocate to each agent a bundle of value at least 1/n of the whole. The most frequently used concept of fairness is envy-freeness, which has been mainly studied in the context of cake-cutting (i.e., allocation of divisible goods) in the last few decades. An allocation is envy-free if no agent prefers another agent's bundle to their own.

Definition 4 (envy-freeness). An allocation π is said to be envy-free (EF) if ui(πi) ≥ ui(πj) for every i, j ∈ A.

Note that every EF allocation is a PROP allocation, and every PROP allocation is MMS, but the reverse is not true, so EF is the strongest fairness notion among these three.

Table 1: Values of the agents in Example 1

One can see that the maximum value that a worst-off agent can get by an allocation is 9. For example, π = ({g5, g6}, {g1}, {g2, g3, g4}) is an MMF allocation. This allocation has a Nash social welfare of 9 · 9 · 11 = 891. However, π′ = ({g5, g6}, {g1, g2}, {g3, g4}) is a maximal Nash allocation with an NSW of 9 · 18 · 7 = 1134, but it is easy to see that π′ is not an MMF allocation. Also, both π and

π′ are not EF allocations, as a2 envies a3 in π, while a3 envies a2 in π′ . We get an envy-free allocation π′′ by allocating {g4, g5} to a1, {g1} to a2, and {g2, g3, g6} to a3. Unfortunately, π′′ is neither MMF nor maximal Nash. Finally, one can find the maximin share of the agents 1, 2, and 3 as 4, 2, and 6, respectively, and thus all the three allocations π, π′ , and π′′ are MMS. In fact, they are even PROP.

Additional constraints. In addition to the fairness requirement, it is sometimes further required by practical applications that a fair allocation must satisfy a certain type of constraint such as cardinality and connectivity constraints. For example, a cardinality constraint requires every agent to be assigned no more than a given number of items, whilst a connectivty constraint seeks to allocate a connected bundle of items to every agent. We refer to the survey by [Suksompong, 2021] for detailed descriptions of various constraints.

Problem notation. We do not formally define the fair allocation problems that we will consider. We simply use, respectively, MMF, MNSW, MMS, and EF to refer not only to the property but also to the associated problem regarding max-min (fair), maximal Nash, maximin share, and envyfree allocations, and depending on the context it will be clear whether we mean a decision problem (e.g., when we speak about NP-hardness)-given an input, decide if there exists such an allocation-or a functional problem (e.g., when we speak about dynamic programming)-given an input, compute such an allocation.

3 Complexity Results

In this section, we present a survey of computational complexity results for fair allocation problems without constraints, for additive valuations. Note that adding a constraint to a fair allocation problem may or may not lead to a harder problem.

General additive valuations. Most of the fair allocation problems are known to be NP-hard to solve to optimality, even under restricted settings. The first hardness result comes from the simple setting with two agents of the same valuation function [Lipton et al., 2004; Nguyen et al., 2014]. In such a setting, the problems MMF, MNSW, and EF are equally hard: They each have been shown to be NP-hard by a reduction from PARTITION, 1 a standard NP-complete problem.

However, for MMS it is still unknown whether the problem is NP-hard, and this is probably one of the most important open questions in the area of fair allocation. [Kurokawa et al., 2018] have shown the existence of problem instances that do not admit an MMS allocation; their sophisticated counterexample is based on what they call a "Sudoku-like" construction. So far, NP-hardness for MMS could be shown by [Bouveret and Lemaˆıtre, 2016] only in the setting of 2-additive valuations, which is a generalization of additive valuations.

Much work has focused on relaxations of fairness, which has the advantage that allocations satisfying them indeed exist and can be efficiently computed. For instance, one may look for an approximate solution whose value is within a certain distance from that of a max-min fair allocation [Aziz et al., 2022a], or may investigate relaxed notions of EF such as EF1 (envy-freeness up to one item) and EFX (envy-freeness up to any item). Unlike EF allocations, an EF1 allocation always exists and can be found in polynomial time by using either round-robin methods [Caragiannis et al., 2019] or the cycleelimination algorithm [Lipton et al., 2004].

1 Given a sequence of positive integers, we ask whether they can be partitioned into two subsequences such that the sums of the integers in both subsequences are equal.

Recently, there has been a growing interest in work that considers fair allocation problems in a high-multiplicity setting, assuming that the number of agents and/or the number of items is small. While all the four considered fair allocation problems are NP-hard even with identical agents (i.e., the case with one agent type), the complexity status of the case with a fixed number item types is unknown. [Kouteck´y and Zink, 2020] obtain an NP-hardness result for the minmax objective in the context of machine scheduling, and we believe that it can also be extended to MMF. [Nguyen and Rothe, 2020a] prove that MMF, MNSW, and MMS can be solved in polynomial time in m and n, as long as the number of item types is constant, yielding that these problems are in XP (slice-wise polynomial) w.r.t. parameter q, i.e., they are solvable in time O(|x|f(q) ) for some function f. It remains open if a similar result holds for EF. [Aziz et al., 2022b] give a positive answer to this question for the case of q = 2 item types. [Gorantla et al., 2023] show that an EF allocation exists if q is at least a particular finite threshold and there is some agent i whose valuation is unique, i.e., ui cannot be represented as λuj for some λ > 0, for any j ̸= i. They also propose a polynomial-time algorithm for computing EFX allocations when q = 2, but leave the case q ≥ 3 open.

Scoring-based valuations. [Baumeister et al., 2017] and [Darmann and Schauer, 2015] show that MMF and MNSW are NP-hard, even for scoring-based valuation functions such as Borda (using the scoring vector (m,m- 1, . . . , 1)) and lexicographic functions (using the scoring vector (2m, 2m-1 , . . . , 1)). EF is easy to check for lexicographic functions, since every agent needs to get a top-ranked item in an envy-free allocation. This is, however, not true for the Borda function. For MMS, [Bouveret and Lemaˆıtre, 2016] show that there is always a maximin share allocation for instances with scoring-based valuation functions.

d-value functions. Denote by D the domain of the agents' valuation functions, i.e., D = {uij|i ∈ [n], j ∈ [m]}, and let d = |D|. Several complexity results have been obtained under the assumptions made on the size of D, or on the numbers used in D. For D = {0, 1} (i.e., binary valuations), MMF

and MNSW are polynomial-time solvable [Golovin, 2005; Darmann and Schauer, 2015]. Also, finding an MMS allocation (if any exists) is easy, just by following a decentralized protocol where the agent take turns to pick one of their preferred items among the remaining ones [Bouveret and Lemaˆıtre, 2016]. However, it is still open whether checking the existence of EF allocations is NP-hard. [Chan et al., 2016] present an NP-hardness result for MMF when D = {a, b} for a, b > 0. [Akrami et al., 2022] obtain a similar result for MNSW, showing that the problem is solvable in polynomial time when D = {1, a} for any a > 1. MNSW becomes NP-hard when D = {0, 1, a} [Nguyen et al., 2014]. [Amanatidis et al., 2017] show that MMS is in P for D = {0, 1, 2}, but their method does not seem to extend to the case when D = {0, 1, a} with a > 2.

We conclude this section by giving some open problems regarding the complexity of fair allocation problems that would be of much interest for future work.

Open problem 1. · Is EF in XP w.r.t. parameter q?

• Is EF NP-hard for q = O(1)?
• Is EF NP-hard for Borda or binary valuations?

Open problem 2. For general additive valuations:

• What is the complexity of deciding whether MMS allocations exist? 2
• Are MMF, MNSW, and MMS NP-hard for q = O(1)?

4 Dynamic Programming

A naive approach for finding a fair allocation is to search over the space of all possible allocations of m items to n agents. In particular, we need to try every single allocation that could possibly be fair until we find a right one. Since there are nm allocations, the running time of the naive approach is O(nm), which is exponential in the number of items. Obviously, this approach is not practical, as the running time is going up very fast as m increases. Because of this phenomenon, brute-force search is applied only when problemspecific observations can be used to reduce the number of available candidate allocations to a size that is manageable. Perhaps the main advantage of brute-force search is that it can be used to solve fair allocation problems w.r.t. most fairness notions, even with constraints. To achieve algorithms with running time better than O(nm), we need to develop more sophisticated techniques such as the dynamic programming (DP) approach, which will be discussed in this section.

2 For minimax share allocations (introduced by [Bouveret and Lemaˆıtre, 2016]), [Heinen et al., 2018] showed NP-hardness.

4.1 AGeneral DP

[Horowitz and Sahni, 1976] were among the first to study the DP approach for solving machine scheduling problems. This approach can be modified to work well with fair allocation problems [Nguyen et al., 2014; Bliem et al., 2016; Aziz et al., 2019; Garg et al., 2022]. Basically, DP can be seen as an alternative way of doing brute-force search. Instead of generating all possible bundle vectors (π1, . . . , πn), we generate all possible valuation vectors (a1, . . . , an), where ai encodes agent i's value for bundle πi. Based on this encoding, let Vj be the set of all possible value vectors which present allocations of the first j items among agents, for j ∈ [m]. Formally, the set Vj+1 can be generated as follows: For each vector a in Vj, we create n vectors a + uij+1 · ei, for each i, and then put them into Vj and remove the duplicates. Here, the ei's are vectors in the standard basis of Rn . It is easy to see that the size of Vj+1 is at most n|Vj|, and thus |Vm| ≤ nm. On the other hand, for every j, the number of vectors in Vj cannot be greater than Kn , where K = maxni=1 {ui(O)} = O(m · umax) with umax = max{uij| i ∈ [n], j ∈ [m]}, since every vector contains integer coordinates not exceeding K. This implies that |Vj| = O(Kn ) for every j ∈ [m]. Therefore, the overall complexity of the DP algorithm is O(max{m(m · umax)n , nm}). Its correctness is easy to verify, since all possible valuation vectors are enumerated, and the allocations that are discarded at each step cannot lead to an optimal allocation.

One can see that the DP approach above can be used to solve MMF, MNSW, and MMS. Unfortunately, it does not work directly for EF, since every valuation vector only contains the value of each agent. This obstacle can be overcome by using an n2 -dimension vector to encode an allocation. In particular, we define a valuation vector a = (a11, . . . , a1n, . . . , an1, . . . , ann) in which aii denotes the value of agent i, and aij for j ̸= i denotes the value of agent i for agent j's bundle. Hence, an EF allocation corresponds to a vector a ∈ Vm with aii ≥ aij for every i, j ∈ [n].

Remark 1. It is worth noting that the dynamic programming approach above may also be viewed as a branch-andbound method in which Vj represents the nodes at level j of the branch-and-bound tree. The elimination rule eliminates those nodes that are dominated by other nodes in the tree and thus corresponds to the bounding operation performed in a branch-and-bound algorithm.

4.2 Another DP

In this section, we present a DP algorithm that has an exponential running time of O(nm · 3m). This algorithm is suggested by [Jansen et al., 2016] in the context of machine scheduling problems. We first present the DP algorithm for MMF and then show how to modify it to work for MMS and MNSW, as well as for other constrained allocation problems.

Optimal Substructure. For each subset S ⊆ O and each agent k ∈ [n], we define a subproblem, denoted as (S, k), in which we want to find an optimal value F [S, k] when allocating the items in S to the first k agents: 1, . . . , k.

Recurrence equation. Obviously, if we know S′ ⊆ S that is allocated to agent k in an optimal allocation, then the recursive subproblem to solve is to compute F[S \ S′ , k - 1]. Therefore, the values F[S, k] satisfy the recurrence equation

We can compute all values F[S, k] with a dynamic program in 3m · n iterations, where each iteration requires time O(m) to compute the value of the current item set S. Thus our algorithm has a total running time of O(nm · 3m). The objective value of an maximal schedule can then be read from F [O, n]. Note that the running time of the DP is almost optimal, since achieving an exact O(|I| · 2o(m) ) algorithm is impossible, unless the Exponential Time Hypothesis fails.

The DP can be modified to work with MMS and MNSW. Indeed, for MNSW, one just needs to replace the min operator in the recurrence equation by the product operator. A similar approach also applies to PROP but not to EF.

4.3 ADP for Few ItemTypes

Another DP algorithm, recently studied independently by [Kouteck´y and Zink, 2020] and by [Nguyen and Rothe, 2020a; Nguyen and Rothe, 2023] (remotely related, see also [Nguyen and Rothe, 2020b; Nguyen and Rothe, 2021]), yields a running time that is exponential in the number of item types. Indeed, the DP algorithm runs in time O(nm2q ) and returns (if there exists any) an allocation in which the value of every agent i is at least βi, for given thresholds β1, . . . , βn. The idea is to show that such an allocation will correspond to a longest path of a suitable weighted directed acyclic graph (DAG) constructed from a given instance I as described below.

Vertices. Recall that q is the number of item types. Let s = (s1, . . . , sq) denote a vector with integer coordinates such that sj ≤ mj for every j ∈ [q], where mj is the number of items of type j. Also, let ξ = (m1, . . . ,mq) and 0 = (0, . . . , 0). There are two vertices v0,ξ and vn,0, and a vertex vi,s for each pair (i, s), i ∈ [n - 1]. Vertices are grouped into n + 1 disjoint sets B0,B1, . . . ,Bn, where the first and the last vertex sets, contain only one vertex v0,ξ and vn,0, respectively, and Bi = {vi,s| s ∈ [m1] × · · · × [mq]}, for i ∈ [n - 1]. Intuitively, a vertex vi,s ∈ Bi represents a state giving partial information about an allocation of items to agents: It indicates that agents 1, . . . , i have been allocated items (but we do not know which items are assigned to which agents), and s represents 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.

Edges and weights. There are only edges between vertices of two consecutive vertex sets Bi-1 and Bi, which are defined as follows. For each i ∈ [n], there is a direct edge from a vertex vi-1,s ∈ Bi-1 to a vertex vi,s′ ∈ Bi if and only if sj-s′j ≥ 0 holds for all j ∈ [q], and ∑qj=1 uij ·(sj-s′j ) ≥ βi. In this case, the weight of the edge (vi-1,s, vi,s′ ) is defined as w(vi-1,s, vi,s′) = ∑qj=1 uij · (sj - s′j ). Intuitively, by this edge we mean that agent i is allocated a bundle of items encoded by the vector s - s′ = (s1 - s′1 , . . . , sq - s′q ), where sj - s′j is the number of items of type j allocated to agent i.

Moreover, the weight w(vi-1,s, vi,s′ ) is exactly the value that agent i achieves by this allocation.

A longest path of the DAG. One can see that a (simple) path of the constructed 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., a path of maximum total weight) in the DAG which can be done via dynamic programming. In fact, finding a longest path in a DAG G can be reduced to finding a shortest path in -G, obtained by changing every weight to its negation. If the path is of positive weight, it corresponds to an allocation satisfying that every agent i gets a value of at least βi; otherwise, there is no such allocation. Note that the number of vertices is O(nmq ), and for each vertex we have at most mq outgoing edges. Therefore, the overall running time of DP is O(nm2q ).

To solve MMF, we apply the dynamic program above with βi = T, for i ∈ [n], where T is the optimal egalitarian social welfare, which can be found via binary seach. The case of maximin share can be treated similarly by setting agent i's maximin share to βi. For MNSW, we need to redefine the weighted fucntion as w(vi-1,s, vi,s′ ) = log(∑qj=1 uij · (sj - s′j )), since maximizing ∏i ui(πi) is equivalent to maximizing ∑i log(ui(πi)). Unfortunately, the DP cannot be applied to EF, and it remains open if we can solve the problem in polynomial time in n and m whenever q is fixed.

Remark 2. We would like to emphasize that all three DPs presented above are applicable to the setting with cardinality constraints or the setting with a mixture of items (goods and chores). Also, it is not hard to see that, while the DPs in Section 4.2 and Section 4.3 can be used to handle both connectivity constraints and the nonadditivity of the agent valuations, the DP in Section 4.1 cannot. Finally, it is worth mentioning that studying DP algorithms is important as this is one of the most efficient techniques for designing fast approximation schemes for many fair allocation problems.

5 Integer Programming Approaches

An alternative idea for solving a fair allocation problem is to model it as a mixed integer program (MIP), which then can be either solved by standard solvers (e.g., CPLEX or Gurobi) or be formulated in structured forms (N-fold IPs or IPs of fixed dimension) from which efficient algorithm can be derived.

5.1 General MIPModels

Max-min fairness. Naturally, finding a max-min fair allocation amounts to finding a maximum value of T (via binary search) for which the following system is feasible w.r.t. T :

where the binary variable xij specifies if item j is assigned to agent i. In what follows, we assume w.l.o.g. that the optimal T is given when solving MMF, and by solving MMF we mean finding optimal values of variables xij w.r.t. T .

Envy-freeness. To achieve an IP formulation for EF, we replace the constraint (1) by the set of constraints

which guarantee the envy-freeness among agents.

MaximumNash social welfare. In the natural MIP model of MNSW, we have an objective function of maximizing ∏ni=1 {∑mj=1uijxij }, subject to the constraint (2). Because of the nonlinearity of the objective function, we will not be able to use CPLEX for solving it directly. To address this issue, one can employ the technique introduced by [B.-Tal and Nemirovski, 2001] to propose an equivalent model, called Second-Order Cone Program (SOCP), which indeed can be handled by CPLEX. To do so, they introduce new variables zi = ∑mj=1uijxij and write

Let k = ⌈log2 n⌉. The constraint (4) can be represented as

where η, {ylj }, j = 1, . . . , 2k , l = 0, . . . , k-1, are additional variables. The above formulation is mixed integer SOCP since any constraint of the form {u, v,w ≥ 0 | u ≤ √vw} is equivalent to {u, v, w ≥ 0 | 4u2 + (v - w)2 ≤ (v + w)2 }.

Based on the MIP (or SOCP) models constructed for the fair allocation problems above, one can directly use the standard solvers to find optimal solutions. Among others, CPLEX and Gurobi are the most frequently used ones. The idea behind CPLEX is to make use of kind of branch-and-bound or branch-and-cut methods combined with a dynamic search, while the main essential parts of Gurobi are cutting planes algorithms, heuristics, and search techniques. [Lesca and Perny, 2010] have empirically examined the effectiveness of CPLEX in solving MMF. However, so far there has not been any similar study for MMS, MNSW, or EF.

5.2 Integer Linear Programs of Fixed Dimension

In this section, we present various ways for modeling fair allocation problems in IP forms, which might result in polynomial-time algorithms or fixed-parameter tractable (FPT) algorithms when some input parameters are small. A parameterized problem A is FPT if there is an algorithm solving any instance I of A with parameter k in time f(k) · poly(|I|) for some computable function f, where |I| denotes the size of the instance. Such an algorithm is called an FPT algorithm. [Mnich and Wiese, 2015] utilize mathematical programming techniques in fixed dimension to obtain an FPT algorithm for the minimum makespan on unrelated machines. Their method is naturally extended to the fair allocation problems as well. Let β1, . . . , βn be given nonnegative integers. We consider the problem of computing an allocation in which each agent i receives a bundle of value at least βi, which is equivalent to find a nonnegative integer solution of the following integer linear program ILP(β1, . . . , βn):

where the integer variable xij denotes the number of items of type j assigned to agent i. Hence, the total number of integer variables is nq, yielding an O((nq)O(nq) log(¯ β ¯mumax)) algorithm [Kannan, 1987], which is FPT in n + q, where ¯ β = maxi βi and ¯m = maxj mj = O(m).

Theorem 1. MMF, MMS, EF, and MNSW are FPT with parameters n + q or n + d.

Proof. To solve MMF, one can solve ILP(T, . . . , T), where T = O(mqumax) is the maximal egalitarian social welfare. For MMS, we first compute the maximin share mmsi of each agent i by solving ILP(T, . . . , T) for the case of idential agents, and then again solve ILP(mms1, . . . , mmsn). For EF, one needs to replace the constraint (7) by (3), noting that the number of variables is not affected by this change, whilst the number of constraints increases additively by at most O(n2 ). Finally, for MNSW, since the objective function is nonlinear but quasi-concave, we can obtain an FPT algorithm by utilizing the result that maximizing a quasi-concave function over linear constraints in fixed dimension can be efficiently solved [Heinz, 2005]. Note that q = (d + 1)n , thus all the results above yield FPT algorithms with parameter n + d.

One may argue that the assumption that the number n of agents is small is quite strong. We can relax this assumption by considering the high-multiplicity setting where it is allowed to have many agents but only a few agent types. In such a seting, one can have an ILP model that admits an algorithm that is exponential in the number of agent types and the number of item types, but polynomial in the input size. Our method takes advantage of recent findings about structures of the integer cone proposed by [Goemans and Rothvoß, 2014] and [Jansen and Klein, 2020].

Theorem 2. MMF and MMS can be solved in polynomial time when the number of agent types and the number of item types are fixed.

In what follows, we give a proof for MMF only, as MMS can be treated similarly. As before, let T be the maximal egalitarian social welfare of the given problem instance.

Structure of integer cone. Given a polytope P = {x ∈ Rq | Ax ≥ b}, where A ∈ Zr×q and b ∈ Zr+, let ∆ be the largest coefficient in A and b, and set M = rq qO(q) (log∆)q . [Goemans and Rothvoß, 2014] show that one can compute in time M O(1) a subset X ⊆ P ∩ Zq of size at most M such that: For any vector a ∈ int.cone(P ∩ Zq ), there exists a vector λ ∈ ZP∩Zq + such that a can be decomposed as a = ∑x∈P∩Zq λx ·x, where λx ∈ {0, 1} for all x ∈ (P∩Zq )\X, |supp(λ) ∩ X| ≤ 22q , and |supp(λ) \ X| ≤ 22q .

An ILP of fixed dimension. In the high-multiplicity setting, it is useful to encode the entire set O of items by a vector ξ = (m1, . . . ,mq). Thus every subset S ⊆ O can be represented by a vector a = (a1, . . . , aq) ∈ Zq+ with aj ≤ mj representing the number of items of type j contained in S. We call such a vector a configuration. Suppose that we know that ξ (t) = (ξ (t) 1 , . . . , ξ (t) q ) is a configuration that is allocated to the group of agents of type t ∈ [p] in a proportional allocation, for every t ∈ [p]. Then ξ (t) belongs to the polytope Pt = {x ∈ Rq | ∑qj=1 ut,jxt,j ≥ T, 0 ≤ xt,j ≤ mj}, where ut,j is the value of agents of type t for item j. By the result above, one can compute a set Xt ⊆ Pt ∩ Zq of size at most (q logumax)O(q) such that ξ (t) can be represented using at most 22q configurations fromXt and at most 22q configurations from Xt = (Pt ∩ Zq ) \ Xt. Moreover, these configurations from Xt are only used once. Therefore, by enumeration, one can guess in time (logumax)2O(q) the correct subset of configurations from Xt that are used in the representation of ξ (t) . Let us denote these configurations as ξ (t,ℓ) = (ξ (t,ℓ) 1 , . . . , ξ (t,ℓ) q ), for ℓ ∈ [2O(q) ]. In addition, one can guess in time 2O(q2 ) the correct number zt ≤ 2O(q) of configurations fromXt that are used in the presentation. Denote them as ζ (t,ℓ) = (ζ (t,ℓ) 1 , . . . , ζ (t,ℓ) q ), for ℓ ∈ [zt]. Also, let yt,ℓ be the number of agents of type t that are assigned the configurations ξ (t,ℓ) . Based on this guessing, one can establish an integer program whose number of integer variables is at most 2O(q2 ) , which can be solved (using, e.g., Kannan's algorithm [Kannan, 1987]) in time 22O(q2 ) (log umax)O(1) :

This ILP can be solved in O(logTq(q-1)2q +1 (m·n·umax)) time. This result can be slightly improved using a recent result by [Jansen and Klein, 2020] regarding the structure of the integer cone, for which the set X is chosen as the vertex set in the integer hull of the polytope P. Unfortunately, this method is not directly applicable to EF and MNSW, as it is not clear how to define the polytope Pt in these cases.

Open problem 3. Can EF and MNSW with few agent types and few item types be solved in polynomial time?

5.3 N-Fold ILPs

N-fold integer programs can be seen as an important class of block-structured IPs for which fast algorithms can be developed. It turns out that many fair allocation problems in the high-multiplicity setting can be succinctly formulated in terms of N-fold IPs, and thus algorithms running in time polynomial in the size of the succinct encoding can be designed, which may be significantly smaller than the size of the natural IP models presented in Section 5.1.

Consider the following N-fold ILP:

with A1, . . . , An ∈ Zr×t and B1, . . . , Bn ∈ Zs×t , and 0 denotes the (s × t)-matrix containing only zero entries. [Hemmecke et al., 2013] were the first to prove that there is an FPT algorithm solving problem (12) with Ai = A and Bi = B for every i ∈ [n]. In fact, the running time of the algorithm is O(a3t(rs+st)n3L), where L is the size of the input and a is the maximum absolute value among the coefficients in A, B, ℓ, and u. [Knop and Kouteck´y, 2018] model the minimum makespan on unrelated machines of the form (12) and utilize the result of [Hemmecke et al., 2013] to give a (uO(q2 ) max · n3 ) algorithm. Note that q = (umax+1)p , and thus we also have a (upmax )O(u2p max ) · n3 algorithm, which is FPT with parameters umax and p. Since then, several improved algorithms have been proposed for solving the problem (12), and the currently best one is due to [Cslovjecsek et al., 2021].

Theorem 3. There is an algorithm that solves the problem (12) in time 2O(rs2 ) (rs∆)O(r2 s+s2 ) (nt)1+o(1) , where ∆ is the largest absolute value of an entry in Q.

Consider the model ILP(β1, . . . , βn) with constraints (6) and (7). By adding slack variables, one can rewrite the constraints (7) as ∑qj=1uijxij - yi = βi, for nonnegative variables yi. Indeed, by a suitable order of the constraints (6) and (7), the constraint matrix Q of ILP(β1, . . . , βn) has the form (13), with Bi = (ui1, ui2, . . . , uiq,-1)T and Ai = A = [Iq 0], where Iq is the identity matrix of size q, and 0 is the zero column. Therefore, the matrix Q has size (n + q) × n(q + 1). Hence, by Theorem 3, ILP(β1, . . . , βn) can be solved in time 2O(q) · (qumax)O(q2 ) · n1+o(1) .

Theorem 4. MMF, MMS, and MNSW can be solved in time 2O(q) · (qumax)O(q2 ) · n1+o(1) .

As before, using the above algorithm together with a suitable choice of the vector (β1, . . . , βn), one can solve MMF, MMS, and MNSW. However, a similar N-fold IP for EF is still not known yet. [Bredereck et al., 2019] give an FPT algorithm with parameters umax and n for the problem.

Open problem 4. Is EF in FPT with parameter q +umax?

6 Other Approaches

Beyond the DP and IP approaches, several other specific approaches have been successfully developed and applied to fair allocation problems under restricted settings.

Greedy approach. Under certain circumstances, solutions to fair allocation problems can be found just by doing some greedy strategy. For binary valuations, [Barman et al., 2018b] have shown that a maximal Nash allocation can be found by using some kind of greedy technique. Starting from any suboptimal allocation, the greedy algorithm runs for at most O(m(n+1) log(nm)) iterations, and at each iteration, it identifies a pair of agents such that a chain of swaps between them yields the largest improvement in NSW. [Benabbou et al., 2021] show that an EF1 allocation that is also Pareto optimal (PO) can be computed by a simple greedy algorithm: Starting with an allocation that is optimal w.r.t. utilitarian social welfare, it iteratively diminishes envy by transferring an item from the envied bundle to the envious agent.

Another greedy algorithm, called Round-Robin, can be used to find EF1 allocations [Caragiannis et al., 2019]. The idea is to first fix a permutation σ of the agents, and then to cycle through the agents according to σ. In each round, allocate to an agent her most preferred item among those remaining. [Conitzer et al., 2017] prove that the Round-Robin algorithm can also find proportional-up-to-one-item (PROP1) allocations. In a similar fashion, the cycle elimination proposed by [Lipton et al., 2004] works in rounds, and in each round, one of the remaining goods is assigned to an agent that is not envied by any other agent. Such an agent always exists and is found via resolving cyclic envy relations in a so-called envy graph of an allocation.

Graph-matching-based approach. In the special case where the number of agents is equal to the number of items, both MMF and MNSW can be efficiently solved via a graphmatching approach. We construct a weighted bipartite graph G = (A×O, E), where the two disjoint vertex sets, A and O, correspond, respectively, to the set of agents and the set of items. In the case of MMF, there is an edge between an agent vertex in A and an item vertex in O, and its weight is set to 1 if the item has value at least T for the agent, and is set to 0 otherwise, where T is the maximal egalitarian social welfare. Now, a max-min fair allocation w.r.t. T is corresponding to a maximum-weight perfect matching of graph G, which can be found in polynomial time. For MNSW, one needs to define the weight of an edge connecting an agent i with an item j as loguij if uij > 0, and -∞otherwise.

Network-flow-based approach. [Golovin, 2005] shows that MMF is solvable in polynomial time for binary valuations, using MAX-FLOW computations in a network. [Darmann and Schauer, 2015] give a similar result for MNSW by transforming it to a MIN-COST FLOW problem. Interestingly, this method has been shown to be able to produce even a leximin allocation [Aziz and Rey, 2020].

Local search. [Akrami et al., 2022] give a local-searchbased algorithm for computing a maximal Nash allocation for two-value instances, where the values for items are in the domain {a, b} and a divides b. [Barman et al., 2018a] use local search (a sequence of item swaps and price rises) to compute an integral competitive equilibrium that is price envy-free up to one good. [Conitzer et al., 2019] prove that a locally Nash-maximal allocation that satisfies group fairness up to one good can be computed in pseudo-polynomial time.

Fisher-market-based approach. This algorithm, due to Barman et al. [2018], uses local search and price-rise subroutines in a Fisher market associated with the fair division instance, and returns an EF1 and PO allocation. The worstcase running time of this algorithm is pseudo-polynomial.