Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity

1 Introduction

Allocation of goods among agents has been considered from different perspectives in social choice theory and AI. In this paper we focus on fair division of indivisible goods without money transfers. Fair division makes a prominent use of fairness criteria such as equity and envy-freeness, and on this point totally depart from auctions, where only efficiency is relevant (and moreover a specific form of efficiency, since the criterion to be maximized is the total revenue of the auctioneer). Envy-freeness is a key concept in the literature on fair division: an allocation is envy-free if and only if each agent likes her share at least as much as the share of any other agent. Ensuring envy-freeness is considered as crucial; however, envy-freeness alone does not suffice as a criterion for finding satisfactory allocations, therefore it has to be paired with some efficiency criterion, such as Pareto optimality. However, it is known that for any reasonable notion of efficiency, there are profiles for which no efficient and envyfree allocation exists (see [Brams et al., 2000]) 1 .

Whereas social choice theory has developed an important literature on fair division, computational issues have rarely been considered. On the other hand, artificial intelligence has studied these issues extensively, but until now has focused mainly on combinatorial auctions and related problems, investigating issues such as compact representation as well as complexity and algorithms. Complexity issues for negotiation (where agents exchange goods by means of deals) have also been studied (e.g. [Dunne et al., 2005; Chevaleyre et al., 2004]). See also [Bouveret et al., 2005] for a preliminary complexity study of fair division problems.

1 This is even trivial if every good must be assigned to someone: in this case, there are profiles for which not even an envy-free allocation exists.

J´erˆome Lang

IRIT

Universit´e Paul Sabatier - CNRS 31062 Toulouse Cedex, France lang@irit.fr

The above discussion reveals the existence of a gap: compact representation and complexity issues for fair division have received very little attention until now, apart of the recent work [Lipton et al., 2004] which studies approximation schemes for envy-freeness. The need for compact representation arises from the following dilemna, formulated by several social choice theorists: either (a) allow agents to express any possible preference relation on the set of all subsets of items, and end up with an exponentially large representation (such as in [Herreiner and Puppe, 2002]); or (b) severely restrict the set of expressible preferences, typically by assuming additive independence between items, and then design procedures where agents express preferences between single items, thus giving up the possibility of expressing preferential dependencies such as complementarity and substitutability effects among items; this is the path followed by [Brams et al., 2000] and [Demko and Hill, 1998]. Yet, as we advocate in this paper, conciliating conciseness and expressivity is possible, by means of compact representation.

As in most works on fair allocation of indivisible items we focus on the joint search for envy-freeness and efficiency. The impossibility to guarantee the existence of an efficient envy-free allocation implies that determining whether there exists such an allocation is a crucial task, since a positive answer leads to choose such an allocation whereas a negative answer calls for a relaxation of one of the criteria. We consider this problem from the point of view of compact representation and computational complexity. We focus first in the simple case where agents have dichotomous preferences, that is, they simply express a partition between satisfactory and unsatisfactory shares. The interest of such a restriction is that in spite of the expressivity loss it imposes, it will be shown to be no less complex than the general case, while being much simpler to expose. The most natural representation of a dichotomous preference is by a single propositional formula, where variables correspond to goods. Expressing envy-freeness and efficiency within this logical representation reveals unexpected connections to nonmonotonic reasoning. We identify the complexity of the key problem of the existence of an envy-free and Pareto-efficient allocation, which turns out to be Σp2 -complete; we also identify the complexity of several other problems obtained either by imposing some restrictions on the latter or by replacing Pareto-efficiency by other criteria. In Section 5 we extend this result to the case of non-dichotomous, compactly represented preferences.

2 Background

2.1 Fair division problems

Definition 1

A fair division problem is a tuple P = 〈I, X, R〉 where

• I = {1, . . . ,N} is a set of agents;
• X = {x1, . . . , xp} is a set of indivisible goods;
• R = 〈R1, . . . ,RN〉 is a preference profile, where each Ri is a reflexive, transitive and complete relation on 2X .

Ri is the preference relation of agent i. ARiB is alternatively denoted by Ri(A, B) or by A ⪰i B; we note A ≻i B (strict preference) for A ⪰i B and not B ⪰i A and A ∼i B (indifference) for A ⪰i B and B ⪰i A.

In addition, Ri is said to be monotonous if and only if for all A, B, A ⊆ B ⊆ X implies B ⪰i A. R = 〈R1, . . . , RN〉 is monotonous if and only if Ri is monotonous for every i.

Definition 2

• An allocation for P = 〈I,X,R〉 is a mapping π : I → 2X such that for all i and j ̸= i, π(i) ∩ π(j) = ∅. If for every x ∈ X there exists a i such that x ∈ π(i) then π is a complete allocation.
• Let π, π′ two allocations. π dominates π′ if and only if (a) for all i, π(i) ⪰i π′ (i) and (b) there exists an i such that π(i) ≻i π′ (i). π is (Pareto-) efficient if and only if there is no π′ such that π′ dominates π.
• An allocation π is envy-free if and only if π(i) ⪰i π(j) holds for all i and all j ̸= i.

2.2 Propositional logic

Let V be a finite set of propositional variables. LV is the propositional language generated from V , the usual connectives ¬, ∧ and ∨ and the Boolean constants ⊤ and ⊥ in the usual way 2 . An interpretation M for LV is an element of 2V , i.e., a truth assignment to symbols: for all x ∈ V , x ∈ M (resp. x ̸∈ M) means that M assigns x to true (resp. to false). Mod(ϕ) = {M ∈ 2V | M |= ϕ} is the set of all models of ϕ (the satisfaction relation |= is defined as usual, as well as satisfiability and logical consequence).

A literal is a formula of LV of the form x or of the form¬x, where x ∈ V . A formula ϕ is under negative normal form (or NNF) if and only if any negation symbol in ϕ appears only in literals. Any formula can be turned in polynomial time into an equivalent NNF formula. For instance, a ∧ ¬(b ∧ c) is not under NNF but is equivalent to the NNF formula a∧(¬b∨¬c).

A formula is positive if it contains no occurrence of the negation symbol. For instance, a ∧ (b ∨ ¬c) and a ∨ (¬a ∧ b) are not positive, whereas a ∧ (b ∨ c) and (a ∧ c) ∨ (a ∧ b) are. ⊤ and ⊥ are considered positive as well.

Let ϕ ∈ LV . V ar(ϕ) ⊆ V is the set of propositional variables appearing in ϕ. For instance, V ar((a ∧ c) ∨ (a ∧ b)) = {a, b, c} and V ar(⊤) = ∅.

Lastly, if S = {ϕ1, . . . , ϕn} is a finite set of formulas then ∧ S = ϕ1 ∧ . . . ∧ ϕn is the conjunction of all formulas of S.

2 Note that connectives → and ↔ are not allowed; this is important for the definition of positive formulas (to come).

2.3 Computational complexity

In this paper we will refer to some complexity classes located in the polynomial hierarchy. We assume the reader to be familiar with the classes NP and coNP. BH2(also referred to as DP) is the class of all languages of the form L1 ∩ L2 where L1 is in NP and L2 in coNP. ∆p2 = P NP is the class of all languages recognizable by a deterministic Turing machine working in polynomial time using NP oracles. Likewise, Σp2 = NP NP . Θp2 = ∆p2 [O(logn)] is the subclass of ∆p2 of problems that only need a logarithmic number of oracles. See for instance [Papadimitriou, 1994] for further details.

3 Fair division problems with dichotomous preferences: logical representation

We start by considering in full detail the case where preferences are dichotomous.

Definition 3 Ri is dichotomous if and only if there exists a subset Goodi of 2X such that for all A,B ⊆ X, A ⪰i B if and only if A ∈ Goodi or B ̸∈ Goodi. R = 〈R1, . . . , RN〉 is dichotomous if and only if every Ri is dichotomous.

There is an obvious way of representing dichotomous preferences compactly, namely by a propositional formula ϕi (for each agent i) of the language LX (a propositional symbols for each good) such that Mod(ϕ) = Goodi. Formally:

Definition 4 Let Ri be a dichotomous preference on 2X , with Goodi its associated subset of 2X , and ϕi a propositional formula on the propositional language LX. We say that ϕi represents Ri if and only if Mod(ϕi) = Goodi.

Clearly, for any dichotomous preference Ri there is a formula ϕi representing Ri; furthermore, this formula is unique up to logical equivalence.

Example 1 X = {a, b, c} and Goodi = {{a, b}, {b, c}}. Note that Ri is not monotonous. Then ϕi = (a ∧ b ∧ ¬c) ∨ (¬a ∧ b ∧ c) represents Ri.

An easy but yet useful result (whose proof is omitted):

Proposition 1 Let Ri be a dichotomous preference on 2X . The following statements are equivalent:

1. Ri is monotonous;
2. Goodi is upward closed, that is, A ∈ Goodi and B ⊇ A imply B ∈ Goodi.
3. Ri is representable by a positive propositional formula.

From now on, we assume that allocation problems P are represented in propositional form, namely, instead of I, X and R we only specify 〈ϕ1, . . . , ϕN〉. I and X are obviously determined from 〈ϕ1, . . . , ϕN〉.

Let P = 〈ϕ1, . . . , ϕN〉 be an allocation problem with dichotomous preferences; then for each i ≤ N, we rewrite ϕi into ϕ∗i obtained from ϕi by replacing every variable x∗ by the new symbol xi. For instance, if ϕ1 = a ∧ (b ∨ c) and ϕ2 = a ∧ d then ϕ∗1 = a1 ∧ (b1 ∨ c1) and ϕ∗2 = a2 ∧ d2.

For all i ≤ N, let Xi = {xi, x ∈ X} An allocation for a standard allocation problem P corresponds to a model of V = X1∪. . .∪XN satisfying at most one xi for each x ∈ X. In other terms, there is a bijective mapping between the set of possible allocations and the models of the following formula

Let V = {xi | i = 1, . . . ,N, x ∈ X}. Any interpretation M of Mod(ΓP) is such that it is never the case that xi and xj are simultaneously true for i ̸= j, therefore we can map M ∈ Mod(ΓP) to an allocation F(π) = M simply defined by π(i) = {x | M |= xi}. This mapping is obviously bijective, and we denote F -1 (M) the allocation corresponding to an interpretation M of Mod(ΓP ).

If allocation are required to be complete, then ΓP is replaced by ΓCP = ΓP ∧ ∧x∈X (x1 ∨. . .∨xn). The rest in unchanged.

3.1 Envy-freeness

We now show how the search for an envy-free allocation can be mapped to a satisfiability problem. Let ϕ∗j|i be the formula obtained from ϕ∗i by substituting every symbol xi in ϕ∗i by xj: for instance, if ϕ∗1 = a1 ∧ (b1 ∨ c1) then ϕ∗2|1 = a2 ∧ (b2 ∨ c2). (Obviously, ϕ∗i|i = ϕ∗i .)

Proposition 2 Let P = 〈ϕ1, . . . , ϕN〉 be an allocation problem with dichotomous preferences under propositional form, and the formulas ϕ∗j|i and mapping F as defined above. Let

The proof is simple, so we omit it. The search for envy-free allocations can thus be reduced to a satisfiability problem: {F -1 (M) | M |= ΓP ∧ΛP } is the set of envy-free allocations for P Note that, importantly, ΓP ∧ΛP has a polynomial size (precisely, quadratic) in the size of the input data.

Example 2

ϕ1 = a ∨ (b ∧ c); ϕ2 = a; ϕ3 = a ∨ b. ΛP = ((a1 ∨ (b1 ∧ c1)) ∨ (¬(a2 ∨ (b2 ∧ c2)) ∧ ¬(a3 ∨ (b3 ∧ c3))) ∧ (a2 ∨ (¬a1 ∧ ¬a3)) ∧ ((a3 ∨ b3) ∨ (¬(a1 ∨ b1) ∧ ¬(a2 ∨ b2)); Mod(ΓP ∧ ΛP ) = {{c1}, {c1, b3}, {c2, b3}, {c2}, {b3}, {c3}, ∅}. There are therefore 7 envy-free allocations, namely (c, -, -), (c,-, b), (-, c, b), (-, c,-), (-,-, b), (-,-, c) and (-,-,-). Note that none of them is complete.

3.2 Efficient allocations

Definition 5 Let ∆ = {α1, . . . , αm} a set of formulae and β a formula. S ⊆ ∆ is a maximal β-consistent subset of ∆ iff (a) ∧ S ∧β is consistent and (b) there is no S ′ such that S ⊂ S ′ ⊆ ∆ and ∧ S ′ ∧ β is consistent. Let MaxCons(∆, β) be the set of all maximal β-consistent subsets of ∆.

Proposition 3 Let P = 〈ϕ1, . . . , ϕN〉 an allocation problem. Let ΦP = {ϕ∗1, . . . , ϕ∗N }. Then π is efficient for P if and only if {ϕ∗i | F(π) |= ϕ∗i } is a maximal ΓP -consistent subset of ΦP .

This simple result, whose proof is omitted, suggests that efficient allocations can be computed from the logical expression Φ of the problem, namely, by computing the maximal ΓP -consistent subsets of Φ; call them {S1, . . . , Sq}. Then for each Si, let Mi = Mod(∧ Si ∧ ΓP ) and let M = ∪qi=1Mi. Then F -1 (M) is the set of all efficient allocations for Φ3 .

3 Note that there are in general exponentially many maximal ΓP - consistent subsets of Φ (and therefore exponentially many efficient

Example 2 (cont'd) The maximal ΓP -consistent subsets of Φ are S1 = {ϕ∗1 , ϕ∗2 }, S2 = {ϕ∗1 , ϕ∗3 } and S3 = {ϕ∗2 , ϕ∗3 }. ∧ S1 ∧ ΓP has only one model: {b1, c1, a2}. ∧ S2 ∧ ΓP has two models: {a1, b3} and {b1, c1, a3}. ∧ S3 ∧ ΓP has one model: {a2, b3}. Therefore the four efficient allocations for P are (bc, a,-), (a,-, b), (bc,-, a) and (-, a, b). None of them is envy-free.

3.3 Efficient and envy-free allocations

We are now in position of putting things together. Since envy-free allocations corresponds to the models of ΛP and efficient allocations to the models of maximal ΓP -consistent subsets of ΦP , the existence of an efficient and envy-free (EEF) allocation is equivalent to the following condition: there exists a maximal ΓP -consistent subset S of ΦP such that ∧ S ∧ ΓP ∧ ΛP is consistent. In this case, the models of the latter formula are the EEF allocations. Interestingly, this is an instance of a well-known problem in nonmonotonic reasoning:

Definition 6 A supernormal default theory 4 is a pair D = 〈β,∆〉 with ∆ = {α1, . . . , αm}, where α1, . . . , αm and β are propositional formulas. A propositional formula ψ is a skeptical consequence of D, denoted by D |∼∀ ψ, if and only if for all S ∈ MaxCons(∆, β) we have ∧ S ∧ β |= ψ.

Proposition 4 Let P = 〈ϕ1, . . . , ϕN〉 a fair division problem. Let DP = 〈ΓP ,ΦP〉. Then there exists an efficient and envy-free allocation for P if and only if D ̸|∼∀ ¬ΛP .

This somewhat unexpected connection to nonmonotonic reasoning has several implications. First, EEF allocations correspond to the models of ∧ S ∧ ΓP ∧ ΛP for S ∈ MaxCons(ΦP , ΓP ); however, MaxCons(ΦP , ΓP ) may be exponentially large, which argues for avoiding to start computing efficient allocations and then filtering out those that are not envy-free, but rather compute EEF allocations in a single step, using default reasoning algorithms thus, fair division may benefit from computational work in default logic and connex domains such as belief revision and answer set programming. Moreover, alternative criteria for selecting extensions in default reasoning (such as cardinality, weights or priorities) correspond to alternative efficiency criteria in allocation problems.

4 Allocation problems with dichotomous preferences: complexity

It is known that skeptical inference is Πp2 -complete [Gottlob, 1992]; now, after Proposition 4, the problem of the existence of an EEF allocation can be reduced to the complement of a skeptical inference problem, which immediately tells that it is in Σp2 . Less obviously, we now show that it is complete for this class, even if preferences are required to be monotonous.

allocations). This can be tempered by (a) there are many practical cases where the number of maximal consistent subsets is small; (b) it is generally not asked to look for all efficient allocations; if we look for just one, then this can be done by computing one maximal ΓP -consistent subset of Φ.

4 "Supernormal" defaults are also called "normal defaults without prerequisites" (e.g., [Reiter, 1980]).

Let us first note that skeptical inference remains Πp2 - complete under these two restrictions (to which we refer as RSI, for RESTRICTED SKEPTICAL INFERENCE): (a) ψ = ϕ1; (b) n ≥ 2. (Here is the justification: ∆ |∼ ψ if and only if ∆ ∪ {ψ, ψ} |∼ ψ.) Equivalently, RSI is the problem of deciding whether, given ∆ = 〈α1, . . . , αn〉 with n ≥ 2, all maximal consistent subsets of ∆ contain α1.

Proposition 5 The problem EEF EXISTENCE of determining whether there exists an efficient and envy-free allocation for a given problem P with monotonous, dichotomous preferences under logical form is Σp2 -complete.

We show hardness by the following reduction from RSI (the complement problemof RSI) to EEF EXISTENCE. Given any finite set ∆ of propositional formulae, let V∆ = V ar(∆) the set of propositional symbols appearing in ∆, and let P = H(∆) the following instance of EEF EXISTENCE:

(3) for each i = 1, . . . , n, let βi be obtained from αi by the following sequence of operations: (i) put αi into NNF form (let α′i be the result); (b) for every v ∈ V∆, replace, in α′i , each (positive) occurrence of v by vi and each occurrence of ¬v by ¯ vi ; let βi be the formula obtained. Then

• ϕ1 = β1 ∨ x1 ;
• for i = 2, . . . , n, ϕi = βi ∧ xi ;

• ϕn+2 = y.

Lemma 1 An allocation π for P is said to be regular if and only if for all i ̸= n, π(i) ⊆ σ(i), where

• for all i ̸= n, σ(i) = ⋃v∈V∆ {vi , ¯ vi} ⋃{xi };

• σ(n+2) = {y}.

Let now πR defined by πR(i) = π(i) ∩ σi. Then

1. πR is regular;
2. π is efficient if and only if πR is is efficient;
3. if π is envy-free then πR is is envy-free.

Proof: (1) is obvious. For all i, the goods outside σ(i) do not have any influence on the satisfaction of i (since they do not appear in αi), therefore πR(i) ∼i π(i), from which (2) follows. The formulas αi being positive, the preference relations ⪰i are monotonous, therefore π(j) ⪰i πR(j) holds for all i, j. Now, if π is envy-free then for all i, j we have π(i) ⪰i π(j), therefore πR(i) ∼i π(i) ⪰i π(j) ⪰i πR(j) and πR is envy-free, fromwhich (3) follows. ■

Lemma 2 If π is regular then

1. 1 can only envy n+ 1;
2. 2, . . . , n envy noone;
3. n+1 can only envy n+2;
4. n+2 can only envy n+1;

Proof: First, note that for any i, j ̸= i, i envies j if and only if π(i) |= ¬ϕi and π(j) |= ϕi.

1. Let i = 1 and j ∈ {2, . . . , n, n + 2}. Assume 1 envies j. Then π(j) |= ϕ1. π being regular, x1 ̸∈ π(j), therefore π(j) |= β1. Now, since π is regular, π(j) does not contain any vi nor any ¯ vi ; now, β1 can only be made true by variables vi or ¯ vi (which cannot be the case here) unless it is a tautology. Now, if β1 is a tautology, then 1 is satisfied by π and cannot envy j, a contradiction.
2. Let i ∈ {2, . . . , n} and j ̸= i. If i envies j then π(j) |= βi ∧ xi , which is impossible because xi ̸∈ π(j), due to the regularity of π.
3. Let i = n + 1. Assume n + 1 envies 1 then π(1) |= ϕn+1. Since π(1) |= y is impossible (because π is regular), we have π(1) |= ∧v∈V∆ (∧ni=1 vi ) ∨ (∧ni=1 ¯ vi ) ∧ x1 , which implies that either π(1) |= ∧v∈V∆ (∧ni=1 vi ) or π(1) |= (∧ni=1 ¯ vi ). Both are impossible because π is regular and n ≥ 2. The case j ∈ {2, . . . , n} is similar.
4. Let i = n + 2 and j ̸= n. If i envies j then π(j) |= y, which is impossible because π is regular. ■

Lemma 3 Let π be a regular allocation satisfying n + 1 and n + 2. Let M(π) be the interpretation on V∆ obtained from π by: for all v ∈ V∆, M(π) |= v (i.e., v ∈ M(π)) if n + 1 receives ¯ v1 , . . . , ¯ vn, andM(π) |= ¬v otherwise, i.e., if n+1 receives v1 , . . . , vn. Then π is envy-free iff M(π) |= α1.

Proof: Let π be a regular allocation satisfying n + 1 and n + 2. Since π satisfies n + 2, y ∈ π(n + 2). Now, π satisfies n + 1 without giving him y, therefore, for any v, n + 1 receives either all the vi 's or all the ¯ vi 's. This shows that our definition of M(π) is well-founded. Now, since π is regular, it is envy-free if and only if (a) 1 does not envy n+1, (b) n+1 does not envy n+2 and (c) n+2 does not envy n+1. Since n + 1 and n + 2 are satisfied by π, we get that π is envy-free if and only if 1 does not envy n+1, that is, if and only if either π(1) |= ϕ1 or π(n + 1) ̸|= ϕ1. Now, π(n + 1) contains x1 , therefore π(n + 1) |= ϕ1, which entails that π is envy-free if and only if π(1) |= ϕ1. This is equivalent to π(1) |= β1, because 1 does not get x1 (which is assigned to n+1), which in turn is equivalent to M(π) by construction. ■

Lemma 4 For each interpretation M over V∆, let us define πM : I → 2X by:

• πM(1) = {v1 | M |= v} ∪ {¯ v1 | M |= ¬v};
• for each i ∈ 2, . . . , n, πM(i) = {vi | M |= v} ∪ {¯ vi | M |= ¬v} ∪ {xi};
• πM(n + 1) = {x1} ∪ {¯ vi | M |= v, i = 1, . . . , n} ∪ {vi | M |= ¬v, i = 1, . . . , n};
• πM(n+2) = {y}

Then:

1. πM is a well-defined and regular allocation satisfying n + 1 and n + 2;
2. MπM =M (MπM is obtained from πM as in Lemma3).
3. for any i ∈ 1, . . . , n, πM satisfies i iff M |= αi.
4. πM is efficient iff M satisfies a maximal consistent subset of ∆.

Proof:

1. πM does not give the same good to more than one individual, therefore it is an allocation. The rest is straightforward.

1. if M |= v then πM(n + 1) contains {¯ vi | i = 1, . . . , n} and thereforeM(πM) |= v. The case M |= ¬v is similar.
2. let i ∈ 2, . . . , n. Since πM gives xi to i, πM satisfies i if and only if πM(i) |= βi , which is equivalent to M |= αi. If i = 1 then, since πM does not give x1 to 1, πM satisfies 1 if and only if πM(1) |= β1 , which is equivalent to M |= α1.
3. from point 3, {i, πMsatisfiesi} = {i,M |= αi}. Now, since preferences are dichotomous, an allocation π is efficient if and only if the set of individuals it satisfies is maximal with respect to inclusion. Therefore, πM is efficient if and only if M satisfies a maximal consistent subset of ∆. ■

Lemma 5 Let π be a regular and efficient allocation satisfying n+1 and n+2. Then M(π) satisfies a maximal consistent subset of ∆.

Proof: π is regular and satisfies n + 1 and n + 2, therefore π(n + 2) = {y}, x1 ∈ π(n + 1), and M(π) is well-defined. Let π′ obtained from π by

• π′ (1) = {v1 |M(π) |= v} ∪ {¯ v1 |M(π) |= ¬v};
• for each i = 2, . . . , n: π′ (i) = {vi |M(π) |= v} ∪ {¯ vi |M(π) |= ¬v} ∪ {xi };
• π′ (n+1) = {x1}∪{vi |M(π) |= ¬v}∪{¯ vi |M(π) |= v};
• π′ (n+2) = {y}.

π being regular and satisfying n + 1 and n + 2, we have π(n + 1) = π′ (n + 1), π(n + 2) = π′ (n + 2), and then for each i, π(i) ⊆ π′ (i): indeed, let j ∈ {2, . . . , n} (for n + 1 and n + 2 this inclusion is obviously satisfied); then (a) π is regular, therefore π(j) ⊆ σ(j); now, all goods of σ(j) are either in π′ (j) or in π(n + 1) (namely: x1 if j = 1 and all the vj such that M(π) |= ¬v and all the ¯ vj such that M(π) |= v); therefore, π(j) ⊆ π′ (j) ∪ π(n + 1), which, together with π(1) ∩ π(n + 1) = ∅, implies π(j) ⊆ π′ (j). Since preferences are monotonous, all individuals satisfied by π are satisfied by π′ as well; and since π is efficient, π and π′ satisfy the same set of individuals. Now, we remark that π′ = πM(π). By Lemma 4, π′ is efficient iff M(π) satisfies a maximal consistent subset of ∆, fromwhich we conclude. ■

Lemma 6 Any envy-free and efficient allocation for P satifies n + 1 and n + 2.

Proof: Suppose π doesn't satisfy n + 1; then y ̸∈ π(n + 1); now, if y ∈ π(n+2) then n+1 envies n+2; if y ̸∈ π(n+2) then π is not efficient because giving y to n+2 would satisfy n + 2 and thus lead to a better allocation than π.

Now, suppose π does not satisfy n + 1, i.e., y ̸∈ π(n + 2); if y ∈ π(n + 1) then n + 2 envies n + 1; if y ̸∈ π(n + 1) then again, π is not efficient because giving y to n + 2 would satisfy n+2 and thus lead to a better allocation than π. ■

Lemma 7 If there exists an EEF allocation, then there exists a maximal consistent subset of ∆ containing α1.

Proof: Let π be an efficient and envy-free allocation. By Lemma 1, πR is regular, efficient and envy-free. By Lemma 6, πR satisfies n + 1 and n + 2. Then by Lemma 5, M(πR) satisfies a maximal consistent subset of ∆, and by Lemma 3, M(πR) |= α1. Therefore Sat(M(πR),∆) is a maximal consistent subset of ∆ and contains α1. ■

Lemma 8 If there exists a maximal consistent subset of ∆ containing α1 then there exists an EEF allocation.

Proof: Assume that there exists a maximal consistent subset S of ∆ containing α1, and let M be a model of S. By point 4 of Lemma 4, πM is efficient.

By point 1 of Lemma 4, πM is regular; then by Lemma 2, πM is envy-free if and only if (i) 1 does not envy n + 1, (ii) n + 1 does not envy n + 2 and (iii) n + 2 does not envy n+1. By point 1 of Lemma 4, πM satisfies n+1 and n+2, therefore (ii) and (iii) hold. Lastly, by point 5 of Lemma 4, M |= α1 implies that πM satisfies 1, therefore (i) holds as well and πM is envy-free. ■

Proof of Proposition 5: from Lemmas 7 and 8, the existence of a maximal consistent subset of ∆ containing α1 and the existence of an efficient and envy-free allocation for P = H(∆) are equivalent. Clearly, H is computed in polynomial time. Therefore, H is a polynomial reduction from RSI to EEF EXISTENCE, which shows that the latter problem is Σp2 -hard, and therefore Σp2 -complete. ■

As a corollary, this Σp2 -completeness result holds for general (not necessarily monotonous) dichotomous preferences.

As a consequence of this high complexity, it is worth studying restrictions and variants of the latter problem for which complexity may fall down. We start by considering identical dichotomous preference profiles, that is, all agents have the same preference, i.e. the same formula ϕ.

Proposition 6 EEF EXISTENCE with N identical dichotomous, monotonous preferences is NP-complete, for any fixed N ≥ 2.

Due to space limitations the proofs of this result and the following ones are omitted 5 . Note that we have here a hardness result for any fixed number of agents (≥ 2). Things are different with Proposition 5, for which hardness does not hold when N is fixed. Namely, the following holds for N = 2:

Proposition 7 EEF EXISTENCE for two agents with monotonous dichotomous preferences is NP-complete.

Unlike Proposition 5, these results are sensitive to whether preferences are required to be monotonous or not.

Proposition 8 EEF EXISTENCE with N identical dichotomous preferences is coBH2-complete, for any fixed N ≥ 2.

Proposition 9 EEF EXISTENCE for 2 agents with dichotomous preferences is coBH2-complete.

Complexity decreases as well if we weaken Pareto-efficiency by only requiring allocations to be complete:

5 They can be found in the long version of the paper, accessible at http://www.irit.fr/recherches/RPDMP/persos/JeromeLang/papers/eef.pdf.

Proposition 10 The existence of a complete envy-free allocation for agents with monotonous, dichotomous preferences is NP-complete, even for 2 agents with identical preferences. Lastly, replacing Pareto-efficiency by an utilitarianistic notion of efficiency results in a complexity decrease as well:

Proposition 11 The existence of an envy-free allocation satisfying a maximal number of agents with monotonous dichotomous preferences is Θp2 -complete.

5 Non-dichotomous preferences

We now consider the case where preferences are no longer dichotomous. Again, since an explicit description of preferences is exponentially large, the need for a compact description thereof is clear. Many languages exist for succinct representation of preference. However, Proposition 5 extends to any language, provided that (a) it extends propositional logic, i.e., it is able to express compactly any dichotomous preference represented by a propositional formula; (b) comparing two sets of goods can be done in polynomial time. Conditions (a) and (b) are met by many languages for succinct representation of preference 6 . Under assumptions (a) and (b):

Corollary 1 EEF EXISTENCE with monotonous preference under logical form is Σp2 -complete.

For the latter result preferences do not have to be numerical since Pareto efficiency and envy-freeness are purely ordinal notions. Now, if preferences are numerical, which implies the possibility of intercomparing and aggregating preferences of several agents, then, besides Pareto-efficiency, we may consider efficiency based on social welfare functions. We consider here only the two most classical way of aggregating a collection of utility functions 〈u1, . . . , un〉 into a social welfare function sw: utilitarianism (sw = ∑i ui) and egalitarianism (sw = mini ui).

Proposition 12 Given a collection of utility functions on 2R given in compact form:

• the problem of the existence of an envy-free allocation maximizing utilitarian social welfare is ∆p2 -complete, even if N = 2.
• the problem of the existence of an envy-free allocation maximizing egalitarian social welfare is ∆p2 -complete, even if N = 2.

A last case that has not been considered is the case of additive numerical preferences. In the latter case, the utility function of agent i ≤ N is simply expressed by the p numbers ui({xj}), j = 1, . . . , p. While the existence of a complete envy-free allocation is easily shown to be NP-complete (see [Lipton et al., 2004]), things become much harder with EEF EXISTENCE: all we know is that this problem is NP-hard and in Σp2 , but its precise complexity remains an open problem.

6 For the sake of illustration, we pick here one of the most simple ones, similar to those used for combinatorial auctions: agents' preferences are numerical (i.e., utility functions) and are represented by a set of propositional formulas, each of which is associated with a weight denoting its importance; the utility of a set of goods is the sum of the weights of the formulas satisfied. Preferences are monotonous if all formulas are positive and all weights are positive. See for instance [Lang, 2004] for a survey of logical languages for compact preference representation.

6 Concluding remarks

We have identified the exact complexity of the key problem of deciding whether there exists an efficient and envy-free allocation when preferences are represented compactly, in several contexts; we have also considered variations of the problem. We have also drawed connections to a well-studied problem in nonmonotonic reasoning. The next step will consist in designing and experimenting algorithms for the search of an EEF allocation (when it exists) and approximation notions for defining optimal allocations when there is no EEF allocation (see [Lipton et al., 2004] for approximate envy-freeness, although not coupled with efficiency).

Acknowledgements: We thank Michel Lemaˆıtre for stimulating discussions about fair division and compact representation, and Thibault Gajdos for stimulating discussions about envy-freeness and for pointing to us some relevant papers.