# fair_and_efficient_completion_of_indivisible_goods__756aaf5e.pdf

Fair and Efficient Completion of Indivisible Goods

Vishwa Prakash HV1, Ayumi Igarashi2, Rohit Vaish3

1Chennai Mathematical Institute, India 2University of Tokyo, Japan 3Indian Institute of Technology Delhi, India vishwa@cmi.ac.in, igarashi@mist.i.u-tokyo.ac.jp, rvaish@iitd.ac.in

We formulate the problem of fair and efficient completion of indivisible goods, defined as follows: Given a partial allocation of indivisible goods among agents, does there exist an allocation of the remaining goods (i.e., a completion) that satisfies fairness and economic efficiency guarantees of interest? We study the computational complexity of the completion problem for prominent fairness and efficiency notions such as envy-freeness up to one good (EF1), proportionality up to one good (Prop1), maximin share (MMS), and Pareto optimality (PO), and focus on the class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. We find that while the completion problem is significantly harder than the standard fair division problem (wherein the initial partial allocation is empty), the consideration of restricted preferences facilitates positive algorithmic results for threshold-based fairness notions (Prop1 and MMS). On the other hand, the completion problem remains computationally intractable for envy-based notions such as EF1 and EF1+PO even under restricted preferences.

Introduction The problem of fair and efficient allocation of resources, particularly discrete (or indivisible) resources, is fundamental to economics and computer science. Such problems arise in a multitude of applications such as course allocation at universities (Budish et al. 2017), inheritance division (Goldman and Procaccia 2015), dividing household chores (Igarashi and Yokoyama 2023), and dispute resolution (Brams and Taylor 1996). There is now a well-developed theory on discrete fair division spanning various notions of fairness and algorithmic results (Amanatidis et al. 2023). The existing theory of fair allocation of indivisible resources assumes that all resources are initially unassigned. While this may be a natural assumption, it is not always applicable in practical scenarios where resource allocation is predetermined or specific agents are designated to handle particular tasks. For instance, in a heterosexual couple, certain household tasks like breastfeeding can only be assigned to a specific individual. In course allocation, certain courses may be mandatory for a particular group of students. Similarly, in dispute resolution, legal agreements may specify

Copyright 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

allocating specific assets to each party. In such settings, it is more natural to assume that specific resources have been pre-assigned to particular agents. We refer to such resources as frozen. The goal is to find a fair and efficient completion of the frozen allocation; that is, to allocate the unassigned resources such that the overall allocation is fair and efficient. Frozen resources present an interesting challenge, as illustrated by the following example. Consider a scenario where two agents are each pre-allocated one good, and there is one unallocated precious good. If these agents envy each other under the frozen allocation, then no completion can satisfy envy-freeness up to one good (EF1). An allocation is EF1 if any pairwise envy can be eliminated by removing some good from the envied bundle (Budish 2011). In the absence of frozen goods, an EF1 allocation always exists in the standard setting of fair division (Lipton et al. 2004; Caragiannis et al. 2019). However, as the above example demonstrates, an EF1 completion may not exist with frozen resources. Therefore, studying the existence and computation of fair and efficient completion of indivisible resources is crucial. Another challenge posed by the completion problem is in the formulation of solution concepts. Specifically, let us consider the maximin share (MMS) criterion (Budish 2011), where fairness is defined based on a utility threshold for each agent. This threshold is defined in terms of an n-person cutand-choose game, where the cutter is the last to pick a bundle. When some resources are preassigned, there can be multiple ways of extending this definition. For example, the cutter may only consider the extension of its own frozen bundle, or it may seek to maximize the value of the least-valued bundle overall. These choices lead to different existential and computational results. Thus, adapting existing solution concepts to the completion setting is non-trivial.

Our Contributions. The main conceptual contribution of our work is the formulation of the model of fair and efficient completion of indivisible goods. In our model, the assignment of certain resources is fixed, while the remaining resources can be flexibly assigned. We study the computational complexity of the completion problem for various notions of fairness, including envy-freeness up to one good (EF1), proportionality up to one good (Prop1), and maximin share (MMS), as well as their combinations with economic efficiency (specifically, Pareto optimality). Our results, sum-

The Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25)

Binary Additive Lexicographic General Additive Standard Completion Standard Completion Standard Completion Problem Problem Problem Problem Problem Problem EF1 Poly NP-c (Th. 1) Poly NP-c (Th. 3) Poly NP-c (Th. 6,7) Prop1 Poly Poly (Th. 2) Poly Poly (Th. 4) Poly NP-c (Th. 6,7) MMS Poly Poly (Th. 2) Poly Poly (Th. 5) Σ2 p NP-h (Th. 9) EF1+PO Poly NP-c (Cor. 1) Poly ? Pseudopoly NP-h (Cor. 3) Prop1+PO Poly Poly (Cor. 2) Poly Poly (Th. 4) Poly NP-h (Cor. 3) MMS+PO Poly Poly (Cor. 2) Poly ? ? ?

Table 1: Summary of our results for indivisible goods. Each row corresponds to a fairness/efficiency property. Each column corresponds to a preference restriction and whether we are looking at the standard or the completion problem; standard is a special case of completion problem when there are no frozen goods. Each cell shows the computational complexity of the standard or completion problem under specific scenarios. Entries marked with is due to (Caragiannis et al. 2019), is due to (Conitzer, Freeman, and Shah 2017), is due to (Bouveret and Lemaˆıtre 2016), is due to (Aziz, Moulin, and Sandomirskiy 2020), due to (Hosseini et al. 2021), due to (Barman, Krishnamurthy, and Vaish 2018b) and is due to (Barman, Krishnamurthy, and Vaish 2018a)

marized in Table 1, span the well-studied class of additive valuations as well as its subclasses such as binary additive and lexicographic valuations. Some of the technical highlights of our work are:

For binary additive valuations, we show that achieving an EF1 completion is computationally intractable even with the restrictiveness of preferences. This highlights a stark contrast with the standard setting, where an EF1 allocation can be computed efficiently (Lipton et al. 2004; Conitzer, Freeman, and Shah 2017). However, for Prop1 and MMS notions (and their combinations with Pareto optimality), we demonstrate that the completion problem admits efficient algorithms. Moreover, we establish that if the initial allocation (i.e., allocation of frozen goods) is Pareto optimal, the existence of MMS+PO is guaranteed. For lexicographic valuations, we again encounter hardness for EF1. This class of valuations is orthogonal to the class of binary additive valuations; here, each agent s preference over bundles is determined by the most preferred good in the set difference of the bundles. Nevertheless, we show that the completion problem for Prop1, Prop1+PO, and MMS is tractable, highlighting the difference between threshold-based notions and envy-based fairness notions. The other completion problems (MMS+PO and EF1+PO) seem challenging, and we leave them as open problems. For general additive valuations, we show that the completion problem for EF1 and Prop1 (and their combinations with Pareto optimality) is NP-hard. This hardness result holds even for two agents with additive valuations and for three agents with identical additive valuations. We also establish the hardness of deciding the existence of an MMS allocation, a problem whose lower bound on complexity is open in the standard setting. Moreover, we demonstrate that α-MMS may not exist for every α > 0 even when the initial allocation is Pareto optimal.

Notably, our hardness results for general additive and binary additive valuations hold even when the initial allocation is

Pareto optimal.

Related Work. The idea of completion has been studied in computational social choice (Brandt et al. 2016), although under different motivation and technical assumptions than ours. In the voting literature, the notion of possible and necessary winners (Konczak and Lang 2005; Xia and Conitzer 2011) models completion of incomplete preferences (as opposed to allocations). In the fair division literature, the notions of possible and necessary fairness consider agents with ordinal preferences over the goods and examine all realizations of cardinal valuations that are consistent with these preferences (Aziz, Schlotter, and Walsh 2023; Aziz et al. 2023). Our approach of assuming frozen assignments is similar to prior work by Dias et al. (Dias et al. 2003) on fixed and forbidden pairs in the stable matching problem. Studying forbidden assignments in fair division is a relevant direction for future work. We study binary additive and lexicographic valuations, which are subclasses of additive valuations. These subclasses have been extensively studied in the fair division literature and have facilitated several positive existential and algorithmic results for various fairness and efficiency notions (Barman et al. 2022; Barman and Verma 2022; Benabbou et al. 2021; Halpern et al. 2020; Babaioff, Ezra, and Feige 2021; Hosseini et al. 2020, 2021, 2023; Hosseini, Mammadov, and Was 2023). For example, a maximin share (MMS) allocation always exists and can be efficiently computed under binary additive and lexicographic valuations while it might fail to exist for additive valuations (Kurokawa, Procaccia, and Wang 2018). Our work also connects with the literature on fair division with subsidy (Halpern and Shah 2019), which compensates agents with a divisible resource (e.g., money) to eliminate envy. The unallocated indivisible goods in our model play a similar role as subsidy, but our focus is on achieving approximate rather than exact envy-freeness alongside Pareto optimality.

Preliminaries

For any natural number s N, let [s] := {1, 2, . . . , s}.

Problem instance. An instance of the fair completion problem is given by the tuple N, M, V, F where N = [n] denotes a set of n agents, M = [m] denotes a set of m indivisible goods, V = (v1, v2, . . . , vn) denotes a valuation profile, and F = (F1, F2, . . . , Fn) denotes the partial allocation of frozen goods (explained below).

Valuation function. The valuation profile V consists of the valuation functions v1, . . . , vn, where vi : 2M R+ specifies the value that agent i has for any subset of goods; here, R+ is the set of non-negative reals. Each agent values the empty set at 0, i.e., for every i N, vi( ) = 0. We will assume that valuations are additive, which means that the value of any subset of goods is equal to the sum of values of the individual goods in that set. That is, for any i N and S M, vi(S) := P g S vi({g}). For simplicity, we will write vi(g) to denote vi({g}). We will focus on two subclasses of additive valuations: binary additive and lexicographic. Binary additive valuations: We say that agents have binary additive valuations if for every agent i N and every good g M, we have vi(g) {0, 1}. An agent i approves a good g whenever vi(g) = 1. Lexicographic valuations: We say that agents have lexicographic valuations if each agent prefers any bundle containing its favorite good over any bundle that doesn t, subject to that, it prefers any bundle containing its second-favorite good over any bundle that doesn t, and so on. Formally, each agent i is associated with a strict and complete ranking i over the goods in M. Given any two distinct bundles X and Y , agent i prefers X over Y if and only if there exists a good g X \Y such that any good in Y that is more preferable than g is also contained in X, i.e., g X \ Y such that {g Y : g i g} X. Note that the lexicographic preference extension induces a total order over the bundles in 2M. Also, lexicographic preferences can be specified using only an ordinal ranking over the goods (Hosseini et al. 2021).

Allocation. A partial allocation of the goods in M is an ordered subpartition A = (A1, . . . , An) of M, where, for all distinct i, j N, Ai Aj = and i NAi M. The subset Ai is called the bundle of agent i. An allocation is complete if all goods are allocated, i.e., i NAi = M. For simplicity, we will use the term allocation to refer to a complete allocation and write partial allocation otherwise.

Frozen allocation and completion. A frozen allocation F = (F1, . . . , Fn) is a partial allocation of M that denotes the subset of goods that are pre-assigned to the agents; that is, the goods in Fi are irrevocably allocated to agent i to begin with. We will denote by U := M \ i NFi the set of unallocated goods, i.e., the goods that are not preassigned. A completion C = (C1, C2, . . . , Cn) refers to an allocation of the unallocated goods, i.e., i NCi = U and Ci Cj = for all distinct i, j N. Define an n-tuple A := (A1, . . . , An) such that for every i N, Ai := Fi Ci.

Notice that A is a complete allocation of the goods in M. We will say that allocation A completes the frozen allocation F.

Fairness notions. A partial allocation A = (A1, . . . , An) is said to be envy-free (EF) if for every pair of agents i, j N, we have vi(Ai) vi(Aj) (Gamow and Stern 1958; Foley 1967), and envy-free up to one good (EF1) if for every pair of agents i, j N such that Aj = , there exists some good g Aj such that vi(Ai) vi(Aj \ {g}) (Budish 2011; Lipton et al. 2004). We say that agent i has EF1envy towards agent j if for every good g Aj, we have vi(Ai) < vi(Aj \ {g}). A partial allocation A is proportional (Prop) if for each agent i N, we have vi(Ai) 1

n vi(M) (Steinhaus 1948), and proportional up to one good (Prop1) if for each agent i N, there exists a good g k =i Ak such that vi(Ai {g}) 1

n vi(M) (Conitzer, Freeman, and Shah 2017). A partial allocation A is called maximin fair if every agent receives a bundle of value at least its maximin share (MMS) value. To define the MMS value of agent i, consider any frozen allocation F. The MMS partition of agent i is an allocation, say A, that completes F such that the value of the least-valued bundle in A is maximized (according to agent i). Observe that agent i evaluates all bundles of A under this definition, not just the one that contains Fi. The value of the least-valued bundle under the MMS partition is called the MMS value of agent i. Formally, the MMS value µi of agent i is defined as

µi := max (C1,...,Cn) ΠU min j [n] vi(Fj Cj),

where ΠU denotes the set of all ordered n-partitions of the set of unallocated goods U (the individual bundles in the partition can be empty). An allocation A satisfies the maximin fair share criterion (also denoted by MMS) if each agent s utility under A is at least its MMS value, i.e., for each agent i, vi(Ai) µi. Note that the frozen goods in the bundle Fj for j = i are not actually assigned to agent i; the definition of MMS value µi considers a thought experiment from agent i s perspective wherein it wants to maximize the value of the least-valued bundle by adding only the unallocated goods in U. For any given α 0, we say that partial allocation A is α-maximin fair (α-MMS) if every agent receives a bundle of value at least α times its MMS value, i.e., for each agent i, vi(Ai) α µi.

Pareto optimality. A partial allocation X is said to Pareto dominate another partial allocation Y if for every agent i, vi(Xi) vi(Yi) and for some agent k, vk(Xk) > vk(Yk). A partial allocation is said to be Pareto optimal (PO) if no other partial allocation Pareto dominates it. Note that we allow for the (hypothetical) redistribution of the frozen goods when considering Pareto domination.1

1One could consider a weaker form of Pareto optimality by defining Pareto domination only by allocations that complete the given frozen allocation. For additive valuations, this notion is equivalent to the Pareto optimality with respect to only the unallocated goods. Our algorithmic and hardness results continue to hold for this notion.

We will also be interested in Pareto optimality of only the frozen allocation. A frozen allocation F = (F1, . . . , Fn) is said to be Pareto optimal (with respect to the frozen goods in i NFi) if there is no other allocation of the frozen goods that Pareto dominates F.

p-COMPLETION. Let p denote any fairness property (e.g., EF1, Prop1, MMS) or a combination of fairness and efficiency properties (e.g., EF1+PO). The computational problem p-COMPLETION takes as input an instance N, M, V, F of the completion problem and asks whether there exists a completion C of the frozen allocation F such that the final allocation F C satisfies the property p. The details omitted from the current version can be found in the full version (HV, Igarashi, and Vaish 2024).

Binary Additive Valuations We will start the discussion of our technical results with a restricted subclass of additive valuations called binary additive valuations wherein, for each agent i N and each good g M, we have vi(g) {0, 1}.

Envy-Freeness Up to One Good. In the standard setting of fair division (i.e., without any frozen goods), an EF1 allocation always exists and can be efficiently computed by a simple round-robin algorithm (Caragiannis et al. 2019). However, as discussed in the Introduction, an EF1 allocation could fail to exist when some goods are pre-allocated. Our first main result in this section is that EF1-COMPLETION is computationally intractable even when the agents have binary additive valuations and even when the frozen allocation is Pareto optimal. Note that, for binary additive valuations, an allocation is Pareto optimal if and only if each good is allocated to an agent who approves it.

Theorem 1. For binary additive valuations, EF1COMPLETION is NP-complete even when the frozen allocation is Pareto optimal.

Intuitively, the construction in Theorem 1 creates enough envy in the frozen allocation such that compensating for it amounts to solving a hard problem. Observe that binary valuations significantly limit the design of the reduced instance, as the agents can only assign a value of 0 or 1 to the goods. Because of this limitation, it is not immediately clear whether reductions similar to those used for general additive valuations (such as from PARTITION problem) can be applied here. Our proof circumvents this challenge by reducing from the EQUITABLE COLORING problem. Formally, given an undirected graph G = (V, E), a proper coloring is an assignment π: V [k] of colors to the vertices of G where no two adjacent vertices have the same color. Such a coloring is called equitable if the number of vertices in any two color classes are the same. Given an undirected graph G and a positive integer k, EQUITABLE COLORING asks whether the graph G has an equitable coloring with a given number k of colors. This problem was used by Hosseini et al. (Hosseini et al. 2019, Section 7.1) to show that, in the standard fair division setting, checking the existence of an envy-free allocation is NP-complete under binary valuations.

Proof of Theorem 1. Checking whether a given completion is EF1 is clearly in NP. We present a reduction from EQUITABLE COLORING to show NP-hardness. Consider an instance (G, k) of EQUITABLE COLORING, where G = (V, E) is an undirected graph and k is a positive integer. Assume, without loss of generality, that there are n = k t vertices for some positive integer t. We construct an instance of our problem as follows. For each edge e = {u, v} E, we create the edge agent e. Additionally, we create color agents c1, c2, . . . , ck and a special agent s. For each vertex v V , we create a vertex good v. Additionally, there are (t + 1) dummy goods d1, . . . , dt+1. Each color agent ci approves all the vertex goods and the t + 1 dummy goods d1, . . . , dt+1. Each edge agent e approves the goods u, v corresponding to the vertices incident to e only. The special agent s approves all the dummy goods d1, . . . , dt+1 only. In a frozen allocation F, the special agent s receives the dummy goods d1, . . . , dt+1 while the other agents receive nothing. Observe that F is Pareto optimal. To show the equivalence of the solutions, let us first suppose that there exists an EF1 allocation A that completes F. We will show that there exists an equitable coloring π: V [k]. Now create an assignment π: V [k] where π(v) is the color class i such that v Aci. Observe that each color agent ci needs to receive at least t vertex goods under the allocation A since otherwise, it would have EF1envy towards the special agent s. Since there are n = k t vertices, all vertex goods are allocated to color agents. Thus, |π 1(i)| = t for each i [k]. Further, no pair of vertices incident to each edge e is allocated to ci; otherwise agent e would have EF1-envy towards ci since e receives none of the goods under A. Thus, π is a proper coloring. We thus conclude that π is an equitable coloring. Conversely, suppose that G admits an equitable coloring π: V [k]. Note that since π is equitable, |π 1(i)| = t for each i [k]. Then construct an allocation A such that agent s receives the dummy goods d1, . . . , dt+1, each color agent ci receives exactly t vertex agents v from π 1(i), and each edge agent e receives nothing. This allocation A completes F. We claim that A is EF1. Indeed, it is easy to see that the special agent does not envy other agents. Each color agent obtains a value of at least t and hence does not have EF1-envy towards the special agent s. Each color agent envies none of the other agents. Now consider any edge agent e. We know that since π is a proper coloring, no pair of vertices incident to e is allocated to the same color agent ci. Thus, from e s perspective, the valuation of every other agent s bundle is at most 1. This implies that A is EF1, as desired.

To obtain the stronger property combination of EF1 and PO, a natural approach is to consider a completion that maximizes Nash welfare (Caragiannis et al. 2019). More precisely, a completion C = (C1, . . . , Cn) is a maximum Nash welfare (MNW) completion if it maximizes the number of agents, say n, receiving a positive utility, and subject to that, the geometric mean of their utilities, i.e.,

argmax C Q i N:vi(Fi Ci)>0 vi(Fi Ci) 1/n . If there is no frozen good, then a maximum Nash welfare allocation is EF1 and PO. For binary additive valuations, a maximum Nash welfare allocation can be computed in polynomial time (Darmann and Schauer 2015; Barman, Krishnamurthy, and Vaish 2018b). By contrast, a completion that maximizes Nash welfare could fail to be EF1 even when an EF1+PO completion exists (HV, Igarashi, and Vaish 2024, Proposition 7). Furthermore, the EF1+POCOMPLETION problem turns out to be NP-complete. This follows from the construction of Theorem 1 where each item is allocated to an agent who approves it.

Corollary 1. EF1+PO-COMPLETION is NP-complete even for agents with binary additive valuations.

Proportionality Up to One Good and Maximin Share. In contrast to EF1, the completion problem can be efficiently solved for Prop1 and MMS notions under binary additive valuations.

Theorem 2. For binary additive valuations, MMSCOMPLETION and Prop1-COMPLETION can be solved in polynomial time.

Proof sketch. The maximin fair share µi for each agent i N can be computed in polynomial time by iteratively assigning each unallocated good approved by agent i to a bundle of minimum value from i s viewpoint. Given a target threshold (µi)i N, we can compute whether there exists an allocation that completes F and gives value µi for each agent i using the maximum flow approach as follows: Create a source node s and a sink node t. For each good j U, introduce a node gj. For each agent i N, create a node ai. For each good node gj, create an arc (s, gj) with capacity 1. For each agent node ai, create an arc (ai, s) with unbounded capacity and a lower quota of µi vi(Fi). For each good-agent pair (gj, ai), if vi(j) = 1, then create an arc (gj, ai) with capacity 1. The maximum flow in this network is always integral and corresponds to a completion C such that (Fi Ci)i N is an MMS allocation. For Prop1, one can similarly compute the desired threshold as 1

nvi(M) vi(Fi) 1 and set this as the lower quota for each (ai, s) arc.

Recall that for binary additive valuations, Pareto optimality is equivalent to assigning each good to an agent who approves it. Thus, to achieve MMS and PO (respectively, Prop1 and PO), it suffices to check whether a given frozen allocation F is Pareto optimal and whether we can obtain an MMS allocation that completes F by assigning goods to agents who approve them. Combining this observation with Theorem 2, we obtain the following corollary.

Corollary 2. For binary additive valuations, MMS+POCOMPLETION and Prop1+PO-COMPLETION can be solved in polynomial time.

Although Theorem 2 provides an efficient algorithm for checking the existence of a Prop1 or an MMS completion, such a completion may not always exist (HV, Igarashi, and Vaish 2024, Proposition 8). Our next result identifies

a sufficient condition for guaranteeing the existence of an MMS+PO completion.

Proposition 1. For binary additive valuations, if the frozen allocation F is PO with respect to the frozen goods, then an MMS and PO allocation that completes F always exists and can be computed in polynomial time.

Lexicographic Valuations

In this section, we consider the class of lexicographic valuations. Recall that lexicographic valuations can be specified using only ordinal ranking over the goods. Furthermore, any allocation that is EF1, Prop1, MMS, or PO with respect to this ordinal ranking also satisfies these properties with respect to any consistent cardinal realization.

Envy-Freeness Up to One Good. We show that the EF1 completion problem is NP-complete even for lexicographic valuations.

Theorem 3. EF1-COMPLETION is NP-complete even for lexicographic valuations.

The detailed proof of Theorem 3 is deferred to the full version (HV, Igarashi, and Vaish 2024) but a brief idea is as follows: The proof uses a reduction from RAINBOW COLORING, which is known to be NP-complete (Garey and Johnson 1979) and asks the following question: Given a hypergraph H = (V, E) and a set of k colors {c1, c2, . . . , ck}, does there exist a coloring of the vertices in V (i.e., an assignment of each vertex to one of k colors) such that all vertices of each hyperedge have different colors? Observe that a necessary and sufficient condition for an allocation to be EF1 under lexicographic preferences is that no agent j has two or more goods that another agent i prefers over the favorite good in i s bundle. The reduction in Theorem 3 enforces this property by creating an agent for each hyperedge and setting up its preferences such that it prefers all vertex goods over the favorite frozen good in its bundle. Further, the construction ensures that all vertex goods are assigned only to the agents representing the k colors. Thus, under any EF1 allocation, no two vertex goods are assigned to the same color agent, ensuring the rainbow property. It is relevant to note that, unlike binary valuations where the value of a bundle depends only on the number of approved goods, the preferences under lexicographic valuations depend on the identity of the goods. This distinction between binary and lexicographic preferences also manifests in the proof techniques: To show the hardness of EF1COMPLETION under binary valuations (Theorem 1), it was more natural to reduce from EQUITABLE COLORING where only the cardinality of the vertices needs to be balanced. By contrast, EF1 for lexicographic preferences requires the more preferred goods to go to separate agents, which is more naturally executed via RAINBOW COLORING.

Proportionality Up to One Good and Maximin Share. Although checking the existence of an EF1 completion is NP-complete, there is an efficient algorithm for checking whether there exists a completion satisfying the weaker fairness notion of Prop1 (Proposition 2).

Proposition 2. Under lexicographic valuations, every allocation satisfies Prop1. Thus, Prop1-COMPLETION can be solved in polynomial time.

The reasoning behind Proposition 2 is that under lexicographic valuations, the favorite good of an agent is more valuable than all the other goods combined. Thus, under any allocation, either an agent receives its favorite good, or, if it doesn t, then it can hypothetically add this good to its bundle. Under lexicographic valuations, an allocation is Pareto optimal if and only if it satisfies sequencibility (Hosseini et al. 2021).2 Therefore, the problem of finding a PO allocation that completes a given frozen allocation reduces to finding a completion such that the final allocation has a corresponding picking sequence of agents. The latter problem can be solved efficiently by constructing a picking sequence for the frozen allocation and extending it for the unallocated goods (HV, Igarashi, and Vaish 2024, Theorem 10). The following is an immediate consequence of this observation and Proposition 2.

Theorem 4. For lexicographic valuations, Prop1+POCOMPLETION can be solved in polynomial time.

In the standard fair division setting, Hosseini et al. (Hosseini et al. 2020) obtain a characterization of an MMS allocation for lexicographic valuations. They show that an allocation is MMS if and only if each agent obtains one or more of their top (n 1) goods or all of their bottom (m n + 1) goods. Such an allocation exists and can be computed in polynomial time. By contrast, an MMS completion can fail to exist for lexicographic valuations even when the frozen allocation is Pareto optimal.

Proposition 3. There exists an instance with lexicographic valuations for which an MMS allocation that completes the given frozen allocation F may not exist even when F is Pareto optimal with respect to the frozen goods.

Proof. Consider an instance with four goods f1, f2, g1, g2 and two agents with the following ranking over the goods:

agent 1 : g1 1 g2 1 f1 1 f2 agent 2 : f1 2 f2 2 g1 2 g2

The underlined entries indicate the frozen good assigned to the agent. Note that the frozen allocation F is Pareto optimal with respect to the frozen goods. The MMS partition of agent 1 is (F1 {g2}, F2 {g1}) and hence its maximin fair share is v1(F1 {g2}). On the other hand, the MMS partition of agent 2 is (F1, F2 {g1, g2}) and hence its maximin fair share is v2(F2 {g1, g2}). Thus, to achieve MMS, we need to allocate at least one of g1 and g2 to agent 1, and, simultaneously, both of g1 and g2 to agent 2, which is impossible.

2An allocation is said to be sequencible if there exists a picking sequence that induces it. Formally, an allocation A is sequencible if there exists a string a1, a2, . . . , am , where each ai N denotes the index of an agent, such that starting from a1, if each agent ai picks its favorite remaining item on its turn, then the resulting allocation is A.

Nevertheless, we can design an efficient algorithm to compute the maximin share for each agent for lexicographic valuations. Intuitively, it suffices to identify frozen bundles, say F1, . . . , Fk with vi(F1) . . . vi(Fk), whose values are less than the value of the most valuable unallocated good and allocate each of the top (k 1) unallocated goods to the first k 1 bundles and the remaining goods to the last bundle.

Proposition 4. For lexicographic valuations, the maximin share value can be computed in polynomial time.

The detailed proof of the above proposition is deferred to the full version (HV, Igarashi, and Vaish 2024). Proposition 4 implies that MMS-COMPLETION belongs to NP when agents have lexicographic valuations. Moreover, by exploiting the structure of an MMS partition, we establish the polynomial-time solvability of MMS-COMPLETION. A crucial property here is that to ensure MMS for each agent, it is sufficient to allocate either the empty bundle, a single good, or a segment of their bottom-preferred unallocated goods. This implies that if an MMS allocation exists, there is one with at most one agent of the last type.

Theorem 5. For lexicographic valuations, MMSCOMPLETION can be solved in polynomial time.

General Additive Valuations In this section, we consider the class of general additive valuations.

Envy-Freeness Up to One Good and Proportionality Up to One Good. Our first two results in this section show that deciding the existence of an EF1 completion is computationally intractable even for two agents with additive valuations and for three agents with identical additive valuations. Given the intractability of EF1-COMPLETION, a natural approach in search of tractability results is to weaken the fairness notion from EF1 to Prop1. Unfortunately, using similar proof techniques, it can be shown that the completion problem remains computationally hard even for Prop1.

Theorem 6. EF1-COMPLETION and Prop1-COMPLETION are NP-complete even for two agents with additive valuations.

Theorem 7. EF1-COMPLETION and Prop1-COMPLETION are NP-complete even for three agents with identical additive valuations.

Observe that under identical valuations, every allocation is Pareto optimal. Thus, Theorem 7 also implies that checking the existence of an EF1+PO (and, similarly, Prop1+PO) completion is NP-hard.

Corollary 3. EF1+PO-COMPLETION and Prop1+POCOMPLETION are NP-hard even for three agents with identical additive valuations.

Theorems 6 and 7 do not impose any structural restrictions on a frozen allocation. Our next result (Proposition 5) shows that if the frozen allocation is fair , we can circumvent the intractability of the completion problem. Formally, given a partial allocation A, let us define its envy graph GA

as a directed graph whose vertices are the agents and there is an edge (i, j) if and only if agent i envies agent j under A, i.e., vi(Ai) < vi(Aj) (Lipton et al. 2004). Proposition 5 states that if the frozen allocation is EF1 and its envy graph is acyclic, then an EF1 completion always exists and can be efficiently computed. Proposition 5. Suppose that a frozen allocation F is EF1 and the envy graph with respect to F is acyclic. Then, an EF1 allocation that completes F always exists and can be computed in polynomial time. Note that the two assumptions in Proposition 5 are necessary to guarantee the existence of an EF1 completion and its polynomial-time computability. In fact, if the frozen allocation is EF1 but the envy graph contains a cycle, the completion problem becomes computationally hard. For example, we can construct an instance where the frozen allocation is EF1, but every agent envies another (e.g., each agent receives an item valued at 0, while all other agents receive items valued at a very large amount from their perspective). This setup essentially reduces the problem to deciding whether there exists an envy-free allocation of the unallocated items, which is known to be NP-hard even for binary additive valuations (Bouveret and Lang 2008). Moreover, if the envy graph of the frozen allocation is acyclic, our Theorem 7 already demonstrates that the completion problem remains hard (recall that for identical valuations, any allocation is Pareto-optimal). Building on Proposition 5, we can show that for two agents with identical valuations, there is a polynomial-time algorithm for checking the existence of an EF1 or Prop1 completion. Note that EF1 implies Prop1 but the opposite may not hold. Indeed, an allocation that assigns two goods to agent 1 and nothing to agent 2 is Prop1 but not EF1. Nevertheless, a technique similar to that for EF1 also works for Prop1 and two agents with identical additive valuations. Theorem 8. For two agents with identical additive valuations, EF1-COMPLETION and Prop1-COMPLETION can be solved in polynomial time. As shown in Theorems 6 and 7, the EF1-COMPLETION problem is NP-complete for three agents with identical valuations or two agents with possibly non-identical valuations. Thus, our results present a tight demarcation of the frontier of tractability for the EF1-COMPLETION problem. Further, we note that EF1-COMPLETION problem for a general number of agents is strongly NP-complete; this can be observed by carrying out a reduction from 3-PARTITION. The proof of this result is deferred to the full version (HV, Igarashi, and Vaish 2024).

Maximin Share. For additive valuations, an MMS allocation can fail to exist (Kurokawa, Procaccia, and Wang 2018), but a (3/4+3/3836)-MMS allocation always exists (Akrami and Garg 2024). By contrast, in the completion problem, it is impossible to guarantee α-MMS for any α (0, 1]. Intuitively, the failure occurs for an instance where each agent i thinks that the first i agents should equally divide the unallocated goods and the remaining agents are already rich enough. This discrepancy in agents valuations prohibits the existence of an α-MMS completion.

Proposition 6. For every α (0, 1], there is an instance for which no α-MMS allocation that completes a given frozen allocation F exists even when the frozen allocation F is Pareto optimal with respect to the frozen goods and each bundle in F contains at most one good.

Proof. For every n N, let Hn := Pn j=1 1 j denote the nth

harmonic number. Consider any α (0, 1], and let n N be such that 1 < α

2 Hn; such n must exist since Hn is strictly monotone increasing. Let 0 < ϵ1 < ϵ2 < . . . < ϵn < 1. Consider an instance of the completion problem with n agents, n frozen goods, and ℓunallocated goods with ℓ n. Construct a frozen allocation F = (F1, . . . , Fn) where for each agent i N, Fi consists of a single frozen good fi such that vi(fj) = ϵj if j i and vi(fj) = ℓ

i if j > i. Here, we have that for i N, ℓ i and each agent i [n] has the same preference ranking over the bundles, i.e., vi(F1) vi(F2) . . . vi(Fn). Further, F is Pareto optimal with respect to the frozen goods since every agent i N strictly prefers good fi over fi 1, fi 2, . . . , f1. Suppose every agent has a value of 1 for every unallocated good. Note that the MMS value µi of agent i N is at least ℓ

i ; this can be achieved by assigning unallocated goods among the first i bundles as equally as possible. Suppose towards a contradiction that there exists an αMMS allocation that completes F. Then, agent i N must be assigned at least α ℓ

i α ℓ 2i unallocated goods. Since there are ℓunallocated goods, it must be that ℓ P i N α ℓ

2i, or, equivalently, 1 α

2 Hn. But this contradicts the assumption that 1 < α

In the standard setting of fair division, the decision problem of determining the existence of an MMS allocation is in Σ2 p (Bouveret and Lemaˆıtre 2016); however, it remains open whether the problem is NP-hard or even harder. A simple reduction from PARTITION shows that the search version of the problem is NP-hard. It is easy to see that MMSCOMPLETION includes the above decision problem as a special case. Our final result shows that MMS-COMPLETION is NP-hard even for two agents with additive valuations. The proof of this result is deferred to the full version (HV, Igarashi, and Vaish 2024).

Theorem 9. MMS-COMPLETION is NP-hard even for two agents with additive valuations.

We initiated the study of fair and efficient completion of indivisible goods and provided several algorithmic and intractability results for this problem under additive valuations as well as its subclasses. Going forward, it would be interesting to study other types of resources such as chores, combination of goods and chores, and combination of divisible and indivisible resources (Bei et al. 2021). Additionally, while our work only considers the case of frozen goods, it would be interesting to also consider forbidden assignments wherein certain items cannot be assigned to certain agents under any completion.

Acknowledgments We thank anonymous reviewers of AAAI 2025 for helpful comments. Ayumi Igarashi acknowledges support from JST FOREST under grant number JPMJFR226O. Rohit Vaish ac knowledges support from DST INSPIRE grant no. DST/INSPIRE/04/2020/000107 and SERB grant no. CRG/2022/002621. Vishwa Prakash HV acknowledges support of TCS Research Scholar Fellowship.

References Akrami, H.; and Garg, J. 2024. Breaking the 3/4 Barrier for Approximate Maximin Share. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, 74 91. SIAM. 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. Artificial Intelligence, 103965. Aziz, H.; Li, B.; Xing, S.; and Zhou, Y. 2023. Possible Fairness for Allocating Indivisible Resources. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, 197 205. Aziz, H.; Moulin, H.; and Sandomirskiy, F. 2020. A Polynomial-Time Algorithm for Computing a Pareto Optimal and Almost Proportional Allocation. Operations Research Letters, 48(5): 573 578. Aziz, H.; Schlotter, I.; and Walsh, T. 2023. Computational Complexity of Necessary Envy-Freeness. Mathematical Social Sciences. Babaioff, M.; Ezra, T.; and Feige, U. 2021. Fair and Truthful Mechanisms for Dichotomous Valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, 5119 5126. Barman, S.; Krishna, A.; Narahari, Y.; and Sadhukan, S. 2022. Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations. In Proceedings of the 31st International Joint Conference on Artificial Intelligence, 60 66. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018a. Finding Fair and Efficient Allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, 557 574. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018b. Greedy Algorithms for Maximizing Nash Social Welfare. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems, 7 13. Barman, S.; and Verma, P. 2022. Truthful and Fair Mechanisms for Matroid-Rank Valuations. In Proceedings of the 36th AAAI Conference on Artificial Intelligence, volume 36, 4801 4808. Bei, X.; Li, Z.; Liu, J.; Liu, S.; and Lu, X. 2021. Fair Division of Mixed Divisible and Indivisible Goods. Artificial Intelligence, 293: 103436. Benabbou, N.; Igarashi, A.; Chakraborty, M.; and Zick, Y. 2021. Finding Fair and Efficient Allocations for Matroid Rank Valuations. ACM Transactions on Economics and Computation, 9(4): 1 41.

Bouveret, S.; and Lang, J. 2008. Efficiency and Envyfreeness in Fair Division of Indivisible Goods: Logical Representation and Complexity. Journal of Artificaial Intelligence Research, 32: 525 564. Bouveret, S.; and Lemaˆıtre, M. 2016. Characterizing Conflicts in Fair Division of Indivisible Goods using a Scale of Criteria. Autonomous Agents and Multi-Agent Systems, 30(2): 259 290. Brams, S. J.; and Taylor, A. D. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press. Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D. 2016. Handbook of Computational Social Choice. Cambridge University Press. Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6): 1061 1103. Budish, E.; Cachon, G. P.; Kessler, J. B.; and Othman, A. 2017. Course match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Operations Research, 65(2): 314 336. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation, 7(3): 1 32. Conitzer, V.; Freeman, R.; and Shah, N. 2017. Fair Public Decision Making. In Proceedings of the 2017 ACM Conference on Economics and Computation, 629 646. Darmann, A.; and Schauer, J. 2015. Maximizing Nash Product Social Welfare in Allocating Indivisible Goods. European Journal of Operational Research, 247(2): 548 559. Dias, V. M.; Da Fonseca, G. D.; De Figueiredo, C. M.; and Szwarcfiter, J. L. 2003. The Stable Marriage Problem with Restricted Pairs. Theoretical Computer Science, 306(1-3): 391 405. Foley, D. 1967. Resource Allocation and the Public Sector. Yale Economic Essays, 45 98. Gamow, G.; and Stern, M. 1958. Puzzle-Math. Viking Press. Garey, M. R.; and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. Goldman, J.; and Procaccia, A. D. 2015. Spliddit: Unleashing Fair Division Algorithms. ACM SIGecom Exchanges, 13(2): 41 46. Halpern, D.; Procaccia, A. D.; Psomas, A.; and Shah, N. 2020. Fair Division with Binary Valuations: One Rule to Rule Them All. In Proceedings of the 16th International Conference on Web and Internet Economics, 370 383. Halpern, D.; and Shah, N. 2019. Fair Division with Subsidy. In Proceedings of the 12th International Symposium on Algorithmic Game Theory, 374 389. Springer. Hosseini, H.; Mammadov, A.; and Was, T. 2023. Fairly Allocating Goods and (Terrible) Chores. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, 2738 2746.

Hosseini, H.; Sikdar, S.; Vaish, R.; Wang, H.; and Xia, L. 2020. Fair Division through Information Withholding. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, volume 34, 2014 2021. Hosseini, H.; Sikdar, S.; Vaish, R.; Wang, J.; and Xia, L. 2019. Fair Division through Information Withholding. ar Xiv preprint ar Xiv:1907.02583. Hosseini, H.; Sikdar, S.; Vaish, R.; and Xia, L. 2021. Fair and Efficient Allocations under Lexicographic Preferences. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, 5472 5480. Hosseini, H.; Sikdar, S.; Vaish, R.; and Xia, L. 2023. Fairly Dividing Mixtures of Goods and Chores under Lexicographic Preferences. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems, 152 160. HV, V. P.; Igarashi, A.; and Vaish, R. 2024. Fair and Efficient Completion of Indivisible Goods. ar Xiv preprint ar Xiv:2406.09468. Igarashi, A.; and Yokoyama, T. 2023. Kajibuntan: A House Chore Division App. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 16449 16451. Konczak, K.; and Lang, J. 2005. Voting Procedures with Incomplete Preferences. In Proceedings of the IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, volume 20. Citeseer. Kurokawa, D.; Procaccia, A. D.; and Wang, J. 2018. Fair Enough: Guaranteeing Approximate Maximin Shares. Journal of the ACM, 65(2): 1 27. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On Approximately Fair Allocations of Indivisible Goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, 125 131. Steinhaus, H. 1948. The Problem of Fair Division. Econometrica, 16(1): 101 104. Xia, L.; and Conitzer, V. 2011. Determining Possible and Necessary Winners Given Partial Orders. Journal of Artificial Intelligence Research, 41: 25 67.