# maxileximin_envy_allocations_and_connected_goods__764a407d.pdf

Maxileximin Envy Allocations and Connected Goods

Gianluigi Greco, Francesco Scarcello

University of Calabria {gianluigi.greco, francesco.scarcello}@unical.it

Fair allocation of indivisible goods presents intriguing challenges from both a social choice perspective and an algorithmic standpoint. Due to the indivisibility of goods, it is common for one agent to envy the bundle of goods assigned to another agent and, indeed, envy-free solutions do not exist in general. In line with the classical game-theoretic concept of Nucleolus in coalitional games, we propose that a fair allocation should minimize the agents dissatisfaction proﬁle in a lexicographic manner, where the dissatisfaction of an agent is deﬁned as her maximum envy towards other agents. Therefore, we seek allocations that minimize the maximum envy. In cases where multiple solutions have an equal maximum value, we minimize the second-worst value, and so on. Additionally, as is customary in fair division problems, we also consider an efﬁciency requirement: among the allocations with the best agents dissatisfaction proﬁle, we prioritize those that maximize the sum of agents utilities, known as maximum social welfare. Such allocations, referred to as maxileximin allocations, always exist. In this study, we analyze the computational properties of maxileximin allocations in the context of fair allocation problems with constraints. Speciﬁcally, we focus on the Connected Fair Division problem, where goods correspond to the nodes of a graph, and a bundle of goods is allowed if the subgraph formed by those goods is connected. We demonstrate that the problem is F P 2 -complete, even for instances with simple graphical structures such as path and star graphs. However, we identify islands of tractability for instances with more intricate graphs, such as those having bounded treewidth, provided that the number of agents is bounded by a ﬁxed number and utility functions use small values.

Introduction Fair allocation of indivisible goods is a central problem in social choice theory (Amanatidis et al. 2023; Steinhaus 1948; Brams and Taylor 1996), and it has been intensively analysed from the computational and algorithmic viewpoint by the AI community (Bouveret et al. 2016; Lang and Rothe 2016; Walsh 2020; Shams et al. 2022). With multiple agents and indivisible goods, we cannot expect to be able to allocate goods in a way that makes everyone happy, so that in general some agent could envy the bundle of goods assigned to

Copyright c 2024, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

another agent. However, if we can ﬁnd an envy-free (EF) allocation where no agent strictly prefers the bundle assigned of another agent to her own bundle, such an allocation can be clearly perceived as a fair one. Whenever these allocations do not exist, we have to ﬁnd some other fair way for assigning goods. In fact, there are many interesting works in the literature which deﬁne relaxations of envy-freeness (cf. Amanatidis, Birmpas, and Markakis 2018), notions such as envy-freeness up to one good (Lipton et al. 2004) or up to any good (Caragiannis et al. 2016), or the related maximin share allocations (Budish 2011). Other approaches deal explicitly with the (unavoidable) envy, by trying to guarantee to agents the maximum amount of fairness with respect to the scenario at hands. For instance, one can minimize the maximum envy ratio (Caragiannis et al. 2009), the multiplicative degree of envy (Nguyen and Rothe 2014), the number of envious agents (Netzer, Meisels, and Zivan 2016), or the maximum envy (e.g., Cai, Filos-Ratsikas, and Tang 2016), just to name a few. This work pushes ahead on this research and aims at identifying a solution that exists always and is as fair and acceptable as possible for all agents. Fairness properties are well studied in coalitional game theory and fundamental to solution concepts, such as the classical notion of Nucleolus (Schmeidler 1969), which minimizes in a lexicographic way the dissatisfaction of all player coalitions. In our context, the dissatisfaction can be measured as the maximum envy towards other agents. Following this approach, we argue that an important class of allocations, which received less attention in the literature, is the one of the leximin allocations, that is, those minimizing the maximum envy and, among possible solutions with equal maximum value, minimize the second-worst value, and so on. Example 1. Consider a scenario where four indivisible goods (say a, b, c, and d) are available. Figure 1 reports on the left the utilities that three agents can get with these goods. E.g., agent 1 values 3 the good a, and 2 the other goods. Clearly, in any feasible allocation, one agent gets a bundle with two goods, while the others get one good. The ﬁgure also displays two allocations B and B . According to the former, agent 1 and agent 3 have utility 3, while agent 2 gets the bundle {b, c} with a total utility 4. Both agents 1 and 3 would get utility 4 with the bundle assigned to agent 2, hence the difference 4 3 is a measure of their envy. Agent 2

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Figure 1: Allocations B and B in Example 1

does not envy any bundle of other agents. Consider now B : this is good division for agent 1, who get the bundle {a, b} with a total utility 5. Agent 2 envies that bundle, and her envy is 4 2 = 2 in this case. The envy of agent 3 is instead 4 3 = 1. Therefore it is natural to prefer the allocation B to B . On the other hand, B should be preferred to the allocation B , symmetrical to B, where agent 1 takes d and agent 3 takes a. In this case, we would have two unhappy agents (1 and 3 ) with the worst envy level 2, instead of 1. While focusing on the kinds of setting exempliﬁed above, it must be noticed that unlike the Nucleolus that is deﬁned in a fully transferable utility setting and it is a unique point multiple lexmin allocations can exist over the same scenario. In particular, minimizing the envy does not always lead to maximize the sum of agents utilities, that is, the social welfare. We thus explicitly require that the desirable allocations, called MAXILEXIMIN allocations (short: MLM), besides having the lexicographically smallest envy vector, must have the maximum social welfare, too. Indeed, such efﬁciency requirement is typically needed in desirable outcomes, otherwise there could be solutions without envies just because all agents are unhappy. In fact, fairness is usually combined with efﬁciency, see (Barman, Krishnamurthy, and Vaish 2018; Caragiannis et al. 2016; de Keijzer et al. 2009; Bei et al. 2021). In this paper, we precisely focus on MLM allocations and we consider the setting of fair allocation problems with constraints, which received considerable attention in the last few years (see, e.g., Suksompong 2021). In particular, we deal with the Connected Fair Division (CFD) problem proposed by Bouveret et al. (2017), where goods correspond to the nodes of a graph, and a bundle of goods is allowed if the subgraph induced by its goods is connected. For instance, in Figure 1 the four goods are arranged on a path, so that {a, b} is a feasible bundle, while {a, c} is not. This setting attracted the attention of the community, and there are many works in the literature, studying relaxation of EF allocations such as the maximin share, the parameterized complexity by considering different possible ﬁxed parameters, the price of connectivity, and so on (Suksompong 2017; Lonc and Truszczynski 2018; Bouveret, Cechl arov a, and Lesca 2018; Igarashi and Peters 2019; Bil o et al. 2022; Deligkas et al. 2021; Bei et al. 2022). In fact, an approach to envy minimization similar to ours has recently been deﬁned in (Shams et al. 2021), following the older social-evaluation function based on Gini inequal-

ity indices (Weymark 1981): the work aims at reducing the vector of user dissatisfactions by minimizing the Ordered Weighted Average (OWA) of the envy vector, that is, by using an aggregation function that computes the weighted sum of the envy vector of all agents, non-increasingly ordered. The use of decreasing weight vectors (that sum to one) allows obtaining solutions where the dissatisfaction reduction is preferred more for those who are unhappier. It is shown that allocations minimizing such an OWA can be computed using a mixed-integer linear program. The work of Shams et al. (2021), however, does not consider fair division with constraints; in particular, as far as we know, connectivity constraints have not been studied for OWA allocations. In the following, we refer to MLM-CFD as the problem of computing a maxileximin allocation in the setting of connected fair division. We study MLM-CFD from the computational viewpoint and we provide the following contributions: We show that MLM-CFD is an intractable problem, precisely F P 2 -complete, even on path and star graphs (since an MLM always exists, the decision problem is trivial). These results do not rely on the known NPhardness of deciding whether envy-free allocations on such graphs exist (Bouveret et al. 2017), since F P 2 - hardness is shown to hold even on settings where envyfree allocations are guaranteed to exist, and the problem is just maximizing the social welfare over them (which are clearly the leximin ones). We then consider possible restrictions of the problem, but it turns out that F P 2 -hardness still holds even on smooth scenarios where utility functions use only small values, i.e., values that are polynomially bounded (or, equivalently, given in unary notation). This time, however, more complex network topologies are involved. Finally, we analyze scenarios where the number of agents is bounded by some given constant to identify a tractable class of MLM-CFD instances. We prove that MLM-CFD belongs to the functional version of Log CFL, a complexity class included in polynomial time and whose problems can be solved by leveraging parallelization (Gottlob, Leone, and Scarcello 2002; Chandra, Kozen, and Stockmeyer 1981), if we consider smooth scenarios and the graphs of the goods have small degree of cyclicity, formally, if they have bounded treewidth (Robertson and Seymour 1986). Interestingly, the algorithm can be adapted to work for different fairness notions, in particular for OWA allocations; moreover, smooth functions clearly include binary evaluation functions, which are also studied in the literature (see, e.g., Goldberg, Hollender, and Suksompong 2020). The problem is still intractable, if utility functions use arbitrary large values.

Formal Framework Envy-free allocations. An allocation scenario for MLMCFD is a tuple σ = (N, G, {ui}i N) where N is the set [1; n] of natural numbers encoding the agents, G = (V, E) is a connected non-empty graph whose nodes in V are the available goods and, for each i N, ui is the utility function

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

of agent i. In this paper, we focus on the widely used framework where the value of a bundle of goods for any agent i N is obtained as the sum of the values she assigns to each good: ui is a function that maps each good v V to a natural1 number ui(v), and the value ui(X) of a set X of goods is just given by P g X ui(g), with ui( ) = 0. An allocation for σ is a tuple B = (B1, ..., Bn), whose components associate each agent i N with a bundle Bi V . In the framework we consider, bundles are required to be connected, that is, the goods in each bundle induce a connected subgraph of G. Since goods are indivisible, bundles must be disjoint, that is, Bi Bi = for each pair of distinct agents i and i . An allocation B is envy-free if ui(Bi) ui(Bj), for each pair i, j N. As it is usually done when dealing with envy-freeness, we also require that all goods are assigned to agents, so that allocations are complete: Sn i=1 Bi = G. Example 2. Consider again the example in Figure 1: allocations B and B are complete, and we have B1 = {a}, B2 = {b, c}, B3 = {d}, with u1(B1) = 3, u2(B2) = 4, and u3(B3) = 3. Note that neither allocation is envy-free.

Lexicographic Envy Minimization. The envy of agent i for an allocation B is the non-negative value maxj N ui(Bj) ui(Bi). Deﬁne ξ(B) to be the vector containing the agents envies for B arranged in non-increasing order. For a pair of n-dimensional vectors v1, v2, denote by v1 v2 the fact that v1 precedes v2 in the (total) lexicographic order, that is, there exists some q N such that v1[p] = v2[p] for all p < q, and v1[q] < v2[q]. An allocation B is said a leximin allocation if there is no allocation B such that ξ(B ) ξ(B). The set of all leximin allocations is denoted by LEXIMIN(σ). Example 3. For the considered allocations, we have ξ(B) = 1, 1, 0 , ξ(B ) = 2, 1, 0 , and ξ(B ) = 2, 2, 0 . Therefore, ξ(B) ξ(B ) ξ(B ). It can be checked that B is the unique leximin allocation for the scenario.

Reﬁnements based on the Social Welfare. The social welfare of an allocation B is the value SW(B) = Pn i=1 ui(Bi). E.g., in our running example, we have SW(B) = 3+4+3 = 10. A leximin allocation B is SW-maximal, or maxileximin, if SW(B) SW(B ), for every B LEXIMIN(σ). The set of these allocations is denoted by MAXILEXIMIN(σ), in the running example it is the singleton {B}.

Arbitrary Number of Agents We assume a standard encoding for any allocation scenario σ: the utility function ui of each agent i N is encoded by explicitly listing all possible goods v with the associated value ui(v). Therefore, the encoding size ||σ|| is O(|V |2 + |N| |V | Mσ), where Mσ is the maximum size over the values encodings occurring in the utility functions.

Arbitrary Utility Functions Our ﬁrst result is that MLM-CFD is complete for F P 2 , the class of all problems for which a solution can be computed

1For the sake of presentation, to avoid discussing subtle issues related to the fractional form representation of rational numbers, we prefer (w.l.o.g.) to use natural numbers encoded in binary.

Figure 2: Construction in the proof of Theorem 4.

in polynomial time by invoking with unitary cost an NP oracle. Notably, hardness holds even on the restriction of MLMCFD to instances where envy-free allocations are guaranteed to exist (shortly denoted by MLM-CFDef), and even on very simple graph topologies namely star and path graphs.

Theorem 4. MLM-CFDef is F P 2 -hard on star graphs. Proof Sketch. Let G = ( V , E) be a graph where each node x V is weighted with a number wx 0. A set of nodes V V is an independent set if | V ei| 1, for each ei E. The weight of an independent set V V is the value P x V wx. Computing an independent set having maximum possible weight is F P 2 -hard (cf., Krentel 1988). Based on G, we build (in polynomial time) an allocation scenario σ G = (N, G, {ui}i N) as follows. The graph G = (V, E) is a star, having the node R V as its center, and such that V = {R} E V . Note that nodes and edges of G are viewed as goods in the new instance (nodes of G). As an example, Figure 2 reports a graph G over nodes {a, b, c, d} and the graph associated with the corresponding scenario σ G. The set N of agents in σ G is such that:

for each ei = {x, y} E, N contains the agent AG(ei) such that u AG(ei)(x) = u AG(ei)(y) = 2, u AG(ei)(ei) = 3, and u AG(ei)(v) = 0 for each v V \ {x, y, ei}; N contains the agent AG(R) such that: u AG(R)(R) = P x V wx + 1; u AG(R)(x) = wx for each x V ; and u AG(R)(v) = 0 for each v V \ V \ {R}; N contains further dummy agents AG(1), ..., AG(| V | 1) getting utility 0 for any good; no further agent is in N.

Let us point out two important properties of the reduction. Assume that V is an independent set for the graph G and consider an allocation B such that: BAG(ei) = {ei} for each ei E; BAG(R) = {R} V ; and the remaining | V | | V | goods are arbitrarily allocated to agents AG(1), ..., AG(| V | | V |). It is immediate to check that B is envy-free. So, any solution to MLM-CFD is an envy-free allocation maximizing the social welfare. In particular, the social welfare of B is given by SW(B) = P x V wx + 3| E| + u AG(R)(R). On the other hand, let B be an envy-free allocation and note that R BAG(R). Since bundles are connected, for each ei = {x, y} E, agent AG(ei) cannot simultaneously

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Figure 3: Construction in the proof of Theorem 5.

get x and y. Hence, we derive that BAG(ei) = {ei}. Moreover, since AG(ei) does not envy AG(R), it is the case that |BAG(R) ei| 1. That is, BAG(R) V is an independent set for the graph G. And, indeed, the weight of this independent set is given by SW(B) 3| E| u AG(R)(R). Hence, from any solution to MLM-CFD on σ G, we get an independent set for G having maximum weight.

Theorem 5. MLM-CFDef is F P 2 -hard on path graphs. Proof Sketch. Let H = ( V , E) be a hypergraph where E = {e1, ..., em} is a set of hyperedges such that, for each ei E, |ei V | = 3. Assume that each hyperedge ei E is equipped with a weight wi 0. A set packing for H is a set E E of hyperedges that are pairwise disjoint, and its weight is the value P ei E wi. Computing a set packing having maximum weight is F P 2 -hard (cf., Krentel 1988). Based on H, we build (in polynomial time) an allocation scenario σ H = (N, G, {ui}i N) as follows. The graph G = (V, E) is a path over V = {xi, yi, zi, ei | ei = {x, y, z} E} {L}. In particular, the subgraph induced over xi, yi, zi is connected, for each ei = {x, y, z} E; and L separates the nodes in {e1, ..., em} from the others the speciﬁc ordering of the nodes in the path is irrelevant as long as these properties are satisﬁed. As an example, Figure 3 reports a hypergraph H over nodes {a, b, c, d} and the graph associated with the corresponding scenario σ H. The set N of agents in σ H is such that:

for each ei E, N contains AG(ei) with u AG(ei)(xi) = u AG(ei)(yi) = u AG(ei)(zi) = 2wi, u AG(ei)(ei) = 5wi; and u AG(ei)(v) = 0 for each v {xi, yi, zi, ei}; for each x V occurring in δ hyperedges, N contains the agents AG(x, 1), ..., AG(x, δ 1). Each AG(x, j) gets utility 0 for any good, but u AG(x,j)(v) = 1 for v {xh | x eh, eh E}; N contains agent AG(L) that gets utility 0 for any good, but u AG(L)(L) = 1; no other agent is in N.

Let us point out two important properties of the reduction. Assume that E is a set packing of maximum weight and note that an allocation B satisfying the following conditions can be built given E : for each ei = {x, y, z} E ,

BAG(ei) {xi, yi, zi}; for each ei = {x, y, z} E , BAG(ei) {ei}; BAG(L) {L}; for each x V occurring in δ > 1 hyperedges, BAG(x,1) . . . BAG(x,δ 1) {xh | x eh, eh E \ E }. It can be checked that these conditions guarantee that B is envy-free. In particular, note that if ei = {x, y, z} is not in E , then no agent can get a bundle with the three goods xi, yi, and zi. By simple algebraic calculations, it can be checked that: SW(B) = 6 P ei E wi + 5 P ei E wi + 1 + 3| E| | V | = P ei E wi + P ei E wi + 1 + 3| E| | V |. On the other hand, assume that B is an envy-free allocation. We immediately derive that BAG(L) {L}, and |(BAG(x,1) . . . BAG(x,δ 1)) {xh | x eh, eh E}| = δ 1 for each x V occurring in δ > 1 hyperedges. Let S be the set of goods not allocated to any of these agents. Assume that B maximizes the social welfare. If S contains the nodes xi, yi, and zi, then BAG(ei) {xi, yi, zi} clearly holds. Otherwise, we have BAG(ei) {ei}. In particular, note that |{xh | x eh, eh E} S| 1 holds for each x V occurring in δ > 1 hyperedges. Therefore, the set {ei | BAG(ei) {xi, yi, zi}} is a set packing. It can be checked that its weight is SW(B) P ei E wi 1 3| E| + | V |. Hence, from any solution to MLM-CFD on σ H, we get a set packing for H having maximum weight.

We now show the F P 2 -completeness. To this end, consider the -BETTER problem that, given as input a scenario, an n-dimensional vector v, and a number w, asks whether there is an allocation B such that ξ(B) v, or ξ(B) = v and SW(B) > w. This problem is clearly in NP, and it can be used as an oracle for computing a maxileximin allocation.

Theorem 6. MLM-CFD is F P 2 -complete.

Proof Sketch. After Theorem 4 and Theorem 5, we have to focus on the membership in F P 2 only. The problem can be solved with a polynomial number of calls to an NP oracle for -BETTER as follows. Let M be the maximum sum of the values of the goods V over all agents, which is an upper bound for any agent s envy, and let Msw = n M, which is an upper bound for the social welfare. Use binary search over the n elements of the vector of envies to compute the leximin vector of envies, say ξ : call the -BETTER oracle with parameters (σ, v, Msw), where v is the vector of envies M/2, 0, . . . , 0 ; if the answer is yes then replace M/2 by M/4 and try again, otherwise try with 3/4M. Once the value for the ﬁrst position have been found, say e1, repeat the procedure to compute the minimum second worstenvy by calling the oracle with an envy-vector parameter v = e1, M/2, 0, . . . , 0 . At the end of this phase, use again logarithmic search to maximize the social welfare, by ﬁxing the envy-vector parameter to ξ and changing the threshold value for the social welfare at each call of -BETTER (starting with the parameters (σ, ξ , Msw/2) . Finally, by using a classical self-reduction technique, compute an allocation with the desired envy proﬁle and social welfare value by performing further n |V | calls to an NP oracle.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Smooth Utility Functions A class C of allocation scenarios has smooth utility functions if their output values are polynomially bounded, that is, if their maximum value-size Mσ is O(log(|N|+|V |)), for each σ C. Note that one can equivalently consider O(log(|N| |V |)), which is in O(log(|N|+|V |)2) = O(log(|N|+|V |)). It is immediate to check that proofs of Theorem 4 and Theorem 5 provide us with NP-hardness results even when such functions are considered. Indeed, the problems considered in the reductions are well-known to be NP-hard even if nodes/hyperedges have unitary weight. In fact, we can show that MLM-CFD remains complete for F P 2 even on smooth functions. This time, we need to use a different reduction with more involved graph topologies.

Theorem 7. MLM-CFD is F P 2 -hard even on smooth utility functions.

Proof Sketch. Consider the F P 2 -complete LEX-SAT problem (Krentel 1988): given a (w.l.o.g.) satisﬁable Boolean formula Φ = c1 cm in conjunctive normal form over the set {α1, ..., αn} of variables, compute the lexicographically maximum satisfying assignment, with variables being ordered by their indices (that is, α1 is the most signiﬁcant variable). Based on Φ, we build (in polynomial time) an allocation scenario σΦ = (N, G, {ui}i N) as follows. The graph G = (V, E) is deﬁned over the set V = {αp, αp | p {1, ..., n}} {c1, ..., cm} {e, h}. Its edges are such that: for each p {1, ..., n}, E contains the edges {αp, αp}, {αp, e}, and { αp, e}; for each clause cj and variable αp occurring positively (resp., negatively), E contains {cj, αj} (resp., {cj, αj}); E contains the edge {e, h}, and no further edge is in E. As an example, Figure 4 reports the graph associated with the scenario σΦ, for the formula Φ = (α1 α2 α3) (α4). The set N of agents in σΦ is such that:

N contains AG(h) such that u AG(h)(h) = m(n + 1) and u AG(h)(v) = 0, for each v V \ {h}; N contains AG(e) such that u AG(e)(h) = m(n + 1) and u AG(e)(cj) = (n + 1), for each j {1, ..., m}, and u AG(h)(v) = 0, for each v V \ {c1, ..., cm}; N contains AG(1), ..., AG(n) such that u AG(p)( αp) = n p + 1, for each p {1, ..., n}, and u AG(h)(v) = 0, for each v V \ { α1, ..., αp}; no further agent is in N.

We now claim that there is a one-to-one correspondence between leximin allocations for σΦ and lexicographically maximum satisfying assignments for Φ. The key ingredient to prove the claim is that any leximin allocation B is such that BAG(h) {h} and BAG(e) {e, c1, ..., cm}. In particular, by the connectedness condition of BAG(e), it holds that the assignment τB such that τB(αp) = true iff BAG(e) {αp} is satisfying and the construction is possible since Φ is satisﬁable, so that we can always build B in a way that AG(h) and AG(e) do not envy any other agents. Eventually, we have just to observe that the envy of agent AG(p) is n p + 1 if αp BAG(e) holds; otherwise, AG(p)

Figure 4: Construction in the proof of Theorem 7.

does not envy any other agent. That is, the vector of the envies correspond to the variables that evaluate to true in the associated assignment. For the other way round, note that any truth assignment τ immediately identiﬁes an allocation B with τB = τ.

Bounded Number of Agents We now focus on classes of allocation scenarios where the number of agents is bounded by some ﬁxed constant. Observe that, if the underlying graphs are trees, then MLMCFD can be solved in polynomial time by exhaustively enumerating all possible (polynomially many) allocations (cf., Bouveret et al. 2017). It is thus natural to consider classes of graphs that generalize acyclicity, as the quasi-acyclic graphs formalized by the notion of treewidth (Robertson and Seymour 1986). Let G = (V, E) be an undirected graph, with V and E being its (non-empty) sets of vertices and edges, respectively. A tree decomposition of G is a pair T, χ , where T is a tree, and χ is a labeling function assigning to each vertex p in T a set of nodes χ(p) V , such that the following conditions are satisﬁed: (1) for each node x V , there exists p in T such that x χ(p); (2) for each edge {x, y} E, there exists p in T such that {x, y} χ(p); and, (3) for each node x V , the subgraph of T induced by all vertices p such that x χ(p) is connected. The width of T, χ is the number maxp T (|χ(p)| 1). The treewidth of G, denoted by tw(G), is the minimum width over all its decompositions. Treewidth is a generalization of acyclicity: G is acyclic if, and only if, tw(G) = 1.

Arbitrary Utility Functions We ﬁrst point out that, looking for islands of tractability, it is crucial to consider restrictions of utility functions. Indeed, MLM-CFD is NP-hard even for classes with only two agents having the same utility functions and goods graphs having bounded treewidth: we can show that even deciding whether there is an envy-free allocation is NP-hard, in these cases. The proof is routine and uses a reduction from the PARTITION problem (Garey and Johnson 1979).

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Input: σ, E, T, χ Task: decide whether there is an allocation B such that, i, j N, E[i][j] = ui(Bj) Method: let q be root of T CHECKPROFILE(q, , E, , N) Procedure CHECKPROFILE(q, λp, ωp, CT p, rest) Begin Procedure guess a (total) mapping λq : χ(q) 7 N assigning to agents the goods occurring at q let new = AGq \ AGp (the new active agents introduced at q) Stop and Fail if new rest or λq(g) = λp(g), for some good g occurring in both mappings let terminal = AGp \ AGq (the agents that are active at p and disappear at q) for each agent a terminal, Stop and Fail if ωp[i][a] = 0 , for some i N (some value of the bundle assigned to a does not match the proﬁle E), or CT p[a] contains more than one component (the bundle of goods assigned to a is not connected) for each agent a AGq: i N, update the proﬁle value for i w.r.t. the bundle assigned to a: ωq[i][a] = ωp[i][a] P

g (goodsq[a]\goodsp[a]) ui(g)

if a new then guess the components-tree CT q[a] with the connected components of the induced subgraph G[goodsq[a]] else guess an update of the components-tree CT q[a] (to consider new goods and remove disappeared goods) if q is a leaf of T then if rest = new then Stop and Fail (there is some agent without any bundle of goods) for each agent a AGq and each agent i N, Stop and Fail if ωq[i][a] = 0 (the proﬁle value for i w.r.t. the bundle assigned to a does not match E[i][a]), or CT q[a] contains more than one component (the bundle of goods assigned to a is not connected) else (q is not a leaf of T ) guess a partition rest , rest of the agents in rest \ new to be dealt with in the two subtrees guess two matrices ω q and ω q such that, i N, a AGq, ω q[i][a] + ω q [i][a] = ωq[i][a], and i N, j N \ AGq, ω q[i][j] = ω q [i][j] = ωq[i][j] guess a split (CT q[a], CT q [a]) of the components-tree of each a AGq Let ℓand r be the left child and the right child of q in T CHECKPROFILE(ℓ, λq, ω q, CT q, rest ) CHECKPROFILE(r, λq, ω q , CT q , rest ) End Procedure

Figure 5: Deciding the existence of an allocation matching a given value proﬁle

Smooth Utility Functions Finally, we are able to provide our main tractability result, for all those instances where there is a bounded number of agents possibly competing for a large number of goods, whose connections have a small degree of cyclicity, and where utility functions only use small values (that is, values at most polynomially larger than the input size, so that they have a logarithmic encoding). Theorem 8. On classes of smooth allocation scenarios with a bounded number of agents and having bounded treewidth, MLM-CFD belongs to LLog CFL, and thus it is a parallelizable and polynomial time problem.

Proof Sketch. Let σ be a smooth allocation scenario over a graph G = (V, E) with |N| = k agents, and denote its size by σ . We show that the algorithm described in the proof of Theorem 6 can be implemented by a LOGSPACE machine with a Log CFL oracle. First observe that, because we have k agents and logspace utilities, the binary search procedure requires logspace only. It then sufﬁces to show that -BETTER is in Log CFL. To this end, for any allocation B, consider the matrix E such that E[i][j] = ui(Bj) i, j N, which we call the value proﬁle of B. Note that it is immediate to compute, based on E, the envy vector for the agents, call it ξ(E), as well as the social welfare P i N E[i][i]. Then, for an in-

stance (σ, v, s) for -BETTER, where v is a vector of (nonincreasing) envies and s is a threshold for the social welfare, we can enumerate in polynomial time all value proﬁles E such that ξ(E) v, or ξ(E) = v and P i N E[i][i] > s. Indeed, even if there are exponentially many bundle allocations, there are only polynomially-many distinct value proﬁles, whose sizes are logarithmic as we deal with k2 small values. We thus get the tractability for -BETTER by exhibiting the algorithm shown in Figure 5 that, given any value proﬁle E, checks whether there actually exists an allocation whose value proﬁle is equal to E. The algorithm is based on a non-deterministic Boolean function CHECKPROFILE that can be implemented on a logspace Alternating Turing Machine (ATM), with polynomial accepting computation trees, which entails that the problem belongs to Log CFL. The ATM works top-down along a tree decomposition. In particular, because the treewidth is bounded by a ﬁxed constant, we can compute beforehand a minimum-width tree decomposition of the graph G in linear time (Bodlaender 1993) or we can compute it when needed, as the problem belongs to LLog CFL, too. Moreover, we can transform this decomposition into a tree decomposition T, χ of G having the same width and such that T is a full binary tree. High-level description. We use node to refer to any node of the decomposition tree T, while good refers to

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

any node of G. If π : X 7 Y is a partial mapping from X to Y , then we write x π to mean any element x in the active domain of π, that is, such that x X is actually mapped to some π(x) Y . Moreover, denotes the empty mapping (having an empty active domain). We describe the ATM as a high-level recursive procedure performing nondeterministic guess operations. More precisely, when called with a node q as its parameter, the procedure CHECKPROFILE starts guessing an assignment of goods λq : χ(q) 7 N. Denote by AGq the so-called active agents at q, that is, the set of agents {a N | λq(g) = a, for some g χ(q)} to which the goods occurring at q are assigned. Denote by goodsq[a] the goods assigned to such an agent a at q, i.e., the set {g χ(q) | λq(g) = a}. Let t be the treewidth of G, and note that there are at most t + 1 goods in χ(q), and thus at most t+1 active agents at q. These sets and the mapping can be stored with O(log σ ) bits (goods, agents, and nodes are encoded with suitable pointers to the input tape, or indices identifying such elements). The machine also stores a matrix ωq which holds, for each pair i, j N, the value ωq[i][j] that is still missing in the evaluation of agent i of the (partial) bundles assigned to agent j, in order to match the desired entry E[i][j] of the value-proﬁle. At the ﬁrst call of the function at the root of the decomposition tree, this matrix is set to E, and each entry, identiﬁed by a pair i, j N, is then reduced during the computation by considering the values according to ui of the goods assigned to j along the decomposition tree. Before the recursive calls on the children of q in T, the ATM guesses two matrices ω q and ω q that encode the values that, for each entry, should be dealt with in the two subtrees rooted at the children of q. Moreover, it stores the set of agents rest whose bundles have to be assigned in the subtree rooted at q; at the root, rest is set to N. Before performing the recursive calls, the ATM guesses a partition rest and rest of rest \ new holding the agents not yet considered (in the set of new active agents new) that should be dealt with in the subtrees rooted at the children of q. At leaves, all agents must be considered. Connection constraint. The more involved issue is how the ATM can check that the bundle Ba of goods to be assigned to agent a is connected, and that no good is assigned to different agents during the algorithm, possibly at different non-adjacent nodes of the decomposition tree T. This is non-trivial, as we do not have enough memory to store bundles at vertices of T (recall that we can use just logarithmic space and so we can store a constant number of indices of goods, while each bundle may contain an arbitrary number of goods). Note, on the one hand, that the nodes of the decomposition tree T containing goods of Ba induce a connected subtree of T. But, on the other hand, those speciﬁc goods goodsq[a] from Ba that occur at node q of this subtree can be goods that are not directly connected in the graph G. Because of the logarithmic-space constraint, we may have only a partial view of Ba, and we cannot say anything about the connection property of Ba. The main ingredient here is to manage, at any node q of the decomposition-tree, a logarithmic-space partial representation of a spanning tree of the bundle assigned to

each active agent a at q, denoted by CT q[a] and called components-tree. The vertices of CT q[a] encode a partition of the goods goodsq[a] assigned to a at q, and are initially set to be the connected components of the subgraph G[goodsq[a]] induced on G by these goods. Note that there are at most t such vertices, because the treewidth is t and at most t + 1 goods occur at q. The edges (at most t) of any components-tree are guessed non-deterministically by the ATM, and encode paths among the connected components. These paths involve goods, still unknown at this point of the algorithm, that will eventually be found while traversing the decomposition tree. Any edge between two components in CT q[a] encodes a placeholder that we must ﬁnd somewhere down in T an actual connection between some pair of goods occurring in these components. Let ℓand r be the children of q, we require that the actual presence of such a connection is checked either in the subtree rooted at ℓor in the subtree rooted at r. If two components are not to be checked in a subtree, they are combined in one component (the other subtree must eventually deal with them, by checking the existence of the required path). To this end, a suitable split operation produces a pair of components-tree CT q[a] and CT q[a] to be checked recursively. Recursive calls. Eventually, CHECKPROFILE executes a recursive call for each child of q in order to check that the non-deterministic choices performed at q are actually correct. To conclude, just observe that all the information needed at each call of CHECKPROFILE can be encoded in logarithmic space, as required.

Conclusion We have proposed maxileximin allocations as a fair method for allocating indivisible goods and have examined their computational properties, by identifying both hard and easy instances. Our approach guarantees the existence of a solution, which is a critical feature in any application. Moreover, in our notion, efﬁciency is intertwined with fairness. Indeed, it is easy to show examples of envy-free solutions in which almost all agents are dissatisﬁed, while other envy-free solutions offer substantially improved outcomes for all agents. We ﬁrmly believe that, in such situations, choosing the envyfree solution that maximizes agents utilities is a matter of fairness, not just of system efﬁciency. The techniques described in the paper can be used to demonstrate the tractability of different measures of dissatisfaction, such as minimizing the Ordered Weighted Average (OWA) of the envy vector (Shams et al. 2021). Exploring islands of tractability for scenarios with an arbitrary number of agents is a potential area for future research. Additionally, it is worth noting that our approach can be easily extended to incorporate further reﬁnements of leximin allocations. This could involve considering additional measures to optimize in agents dissatisfaction proﬁles (currently focused on envies alone), and potentially incorporating other efﬁciency notions (we have examined social welfare). Speciﬁcally, it would be interesting to study the problem of computing MLM allocations where we additionally consider metrics related to the notion of maximin share (Budish 2011).

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Acknowledgements This work was funded by the following two projects under the Next Generation EU NRRP MUR program: FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, and Tech4You - Technologies for climate change adaptation and quality of life improvement (ECS0000009), call for the creation and strengthening of Innovation Ecosystems , building Territorial R&D Leaders (Directorial Decree n. 2021/3277).

References Amanatidis, G.; Aziz, H.; Birmpas, G.; Filos-Ratsikas, A.; Li, B.; Moulin, H.; Voudouris, A. A.; and Wu, X. 2023. Fair division of indivisible goods: Recent progress and open questions. Artif. Intell., 322: 103965. Amanatidis, G.; Birmpas, G.; and Markakis, V. 2018. Comparing Approximate Relaxations of Envy-Freeness. In Proc. of IJCAI 18, 42 48. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018. Finding Fair and Efﬁcient Allocations. In Proc. of EC 18, 557 574. Bei, X.; Igarashi, A.; Lu, X.; and Suksompong, W. 2022. The Price of Connectivity in Fair Division. SIAM J. Discret. Math., 36(2): 1156 1186. Bei, X.; Lu, X.; Manurangsi, P.; and Suksompong, W. 2021. The Price of Fairness for Indivisible Goods. Theory Comput. Syst., 65(7): 1069 1093. Bil o, V.; Caragiannis, I.; Flammini, M.; Igarashi, A.; Monaco, G.; Peters, D.; Vinci, C.; and Zwicker, W. S. 2022. Almost envy-free allocations with connected bundles. Games Econ. Behav., 131: 197 221. Bodlaender, H. L. 1993. A Linear Time Algorithm for Finding Tree-decompositions of Small Treewidth. In Proc. of STOC 93, 226 234. Bouveret, S.; Cechl arov a, K.; Elkind, E.; Igarashi, A.; and Peters, D. 2017. Fair Division of a Graph. In Proc. of IJCAI 17, 135 141. Bouveret, S.; Cechl arov a, K.; and Lesca, J. 2018. Chore division on a graph. Autonomous Agents and Multi-Agent Systems, 1 24. Bouveret, S.; Chevaleyre, Y.; Maudet, N.; and Moulin, H. 2016. Fair Allocation of Indivisible Goods, 284 310. Cambridge University Press. Brams, S. J.; and Taylor, A. D. 1996. Fair division: From cake-cutting to dispute resolution. Cambridge University Press. Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6): 1061 1103. Cai, Q.; Filos-Ratsikas, A.; and Tang, P. 2016. Facility Location with Minimax Envy. In Proc. of IJCAI 16, 137 -143. Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P.; and Kyropoulou, M. 2009. On Low-Envy Truthful Allocations. In Rossi, F.; and Tsoukias, A., eds., Proc. of ADT 09, 111 119.

Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2016. The Unreasonable Fairness of Maximum Nash Welfare. In Proc. of EC 16, 305 322. Chandra, A. K.; Kozen, D. C.; and Stockmeyer, L. J. 1981. Alternation. J. ACM, 28(1): 114 133. de Keijzer, B.; Bouveret, S.; Klos, T.; and Zhang, Y. 2009. On the Complexity of Efﬁciency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences. In Rossi, F.; and Tsoukias, A., eds., Proc. of ADT 09, 98 110. Deligkas, A.; Eiben, E.; Ganian, R.; Hamm, T.; and Ordyniak, S. 2021. The Parameterized Complexity of Connected Fair Division. In Proc. of IJCAI 21, Virtual Event / Montreal, Canada, 19-27 August 2021, 139 145. ijcai.org. Garey, M. R.; and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co. ISBN 0716710447. Goldberg, P.; Hollender, A.; and Suksompong, W. 2020. Contiguous Cake Cutting: Hardness Results and Approximation Algorithms. J. Artif. Intell. Res., 69: 109 141. Gottlob, G.; Leone, N.; and Scarcello, F. 2002. Computing LOGCFL certiﬁcates. Theor. Comput. Sci., 270(1-2): 761 777. Igarashi, A.; and Peters, D. 2019. Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints. Proceedings of AAAI 19, 33(01): 2045 2052. Krentel, M. W. 1988. The complexity of optimization problems. JCSS, 36(3): 490 509. Lang, J.; and Rothe, J. 2016. Fair Division of Indivisible Goods. In Economics and Computation, 493 550. Springer. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On Approximately Fair Allocations of Indivisible Goods. In Proc. of EC 04, 125 131. Lonc, Z.; and Truszczynski, M. 2018. Maximin Share Allocations on Cycles. In Proc. of IJCAI 18, 410 416. Netzer, A.; Meisels, A.; and Zivan, R. 2016. Distributed Envy Minimization for Resource Allocation. Autonomous Agents and Multi-Agent Systems, 30(2): 364 -402. Nguyen, T. T.; and Rothe, J. 2014. Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Disc. Appl. Mathematics, 179: 54 68. Robertson, N.; and Seymour, P. 1986. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3): 309 322. Schmeidler, D. 1969. The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics, 17: 1163 1170. Shams, P.; Beynier, A.; Bouveret, S.; and Maudet, N. 2021. Minimizing and Balancing Envy Among Agents Using Ordered Weighted Average. In Proc. of ADT 21, Toulouse, France, November 3-5, 2021, volume 13023 of Lecture Notes in Computer Science, 289 303. Springer. Shams, P.; Beynier, A.; Bouveret, S.; and Maudet, N. 2022. Fair in the Eyes of Others. J. Artif. Intell. Res., 75: 913 951.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)

Steinhaus, H. 1948. The problem of fair division. Econometrica, 16: 101 104. Suksompong, W. 2017. Fairly Allocating Contiguous Blocks of Indivisible Items. In Algorithmic Game Theory, 333 344. Suksompong, W. 2021. Constraints in fair division. SIGecom Exch., 19(2): 46 61. Walsh, T. 2020. Fair Division: The Computer Scientist s Perspective. In Proc. of IJCAI 20, 4966 4972. ijcai.org. Weymark, J. A. 1981. Generalized Gini inequality indices. Mathematical Social Sciences, 1(4): 409 430.

The Thirty-Eighth AAAI Conference on Artiﬁcial Intelligence (AAAI-24)