Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods

1 Introduction

Specifying a fair division problem of indivisible goods needs the expression of each agent's preferences over all possible combinations (or "bundles") of goods. Such preferences are generally monotonic (an agent never prefers a smaller set of goods to a larger one). In case preferences are numerical, we can resort to a variety of languages for the compact representation of utility or valuation functions, including bidding languages for combinatorial auctions [Nisan, 2006]. Often it is not reasonable to assume that preferences can easily be expressed numerically. When no objective currency is available, it is well-known that agents are often reluctant or even incapable to express their preferences using numbers.

Now, there do exist well-known languages for eliciting and representing ordinal preferences over combinatorial domains, notably CP-nets [Boutilier et al., 2004], tailored to representing preference relations on the domain of each variable conditioned by the values of the variables it depends on, TCPnets [Brafman et al., 2006a], which extend CP-nets by allowing statements of conditional importance between single variables, and conditional preference theories [Wilson, 2004], which further extend TCP-nets. And after all, the set of all bundles has a combinatorial structure, so we might wonder whether these languages would not be good candidates for J´erˆome Lang LAMSADE Universit´e Paris-Dauphine lang@lamsade.dauphine.fr our concern. It turns out that they are not, because they cannot easily express statements such as "everything else being equal, I prefer to have the bundle {a, b} rather than the bundle {a, c, d}" (this will be made more precise later).

In this paper we define a graphical language, called conditional importance networks (CI-nets), for expressing such preferences. This language has strong structural similarities with the (T)CP-net family. More precisely, CI-nets can be seen as being obtained from TCP-nets by a simplification followed by a generalization. First, the variables correspond to the goods (and their domains are binary: each good is in the bundle or it is not). The simplification is that CI-nets do not include any conditional preference statements on the values of the variables: because the preference relation between bundles is monotonic, an agent never prefers not having a good to having it, and expressing a conditional preference on the domains of the variables would be useless (except maybe for distinguishing between strict preference or indifference). The generalization is that importance statements can bear on arbitrary sets of variables, and not only on singletons.

In Section 2 we define CI-nets and give a semantics as well as a proof theory in terms of "worsening flips"; we also discuss the expressivity of the language and the satisfiability problem. In Section 3 we identify the complexity of dominance checking for CI-nets, both in the general case and for some restrictions on the language. Section 4 sketches possible applications of CI-nets to fair division problems.

2 Conditional importance networks

CP-nets [Boutilier et al., 2004] provide a preference representation language based on the notion of conditional independence, allowing to express that the preference on the value of a given variable depends only on a specific set of variables. The main element of CP-nets are conditional preference tables. For binary variables, these tables are of the form {S +, S -} : x ℜ x, with ℜ = ▷ or ℜ = ◁, with S + and S - being sets of variables. This informally translates to: "provided that the variables from S + are set to true and that the variables from S - are set to false, all other things being equal, I prefer having x set to true (false) rather than to false (true)." This is somewhat inadequate for modeling preferences over sets of goods, which are almost always monotonic. In this context, we would rather want to express conditional importance relations between the variables themselves, and not between their truth values. An example of the kind of relations we try to capture is: abc : d▷ef , that is, provided that I have item a but none of items b or c, I would rather have item d than items e and f together, all other things being equal.

2.1 Conditional importance statements

From now on, V is a finite set of binary variables, corresponding to objects to be allocated.

Definition 1 (Conditional importance statement)

A conditional importance statement on V is a quadruple γ = (S +, S -, S1, S2) of pairwise disjoint subsets of V, written as S +, S - : S1 ▷ S2.

The informal reading is: "if I have all the items in S + and none of those in S -, I prefer obtaining all items in S1 to obtaining all those in S2, ceteris paribus." S + and S - are called the positive precondition and the negative precondition of γ, respectively. S1 and S2 are called the compared sets of γ. We will sometimes use x1 . . . xp ¯ y1 . . . ¯ yq : S1 ▷S2 as a shorthand for {x1, . . . , xp}, {y1, . . . , yq} : S1 ▷ S2, and we will typically omit brackets ({a, b} will be denoted as ab).

Definition 2 (CI-net) A CI-net on V is a set N of conditional importance statements on V.

CI-statements are similar to importance statements in TCPnets [Brafman et al., 2006a], up to a very important difference: CI-nets can compare sets of objects of arbitrary size, while TCP-nets can only express importance statements between single objects, ceteris paribus. On the other hand, CInets do not express preferences between values of variables, as TCP-nets do, since monotonicity makes them redundant.

2.2 Semantics

A (strict) preference relation ≻ is a strict partial order (an irreflexive, asymmetric and transitive binary relation) over 2V . A preference relation ≻ is monotonic if X ⊃ Y entails X ≻ Y for any X, Y ∈ 2V . It is complete if it is a linear order, that is, for any X, Y ∈ 2V with X ̸= Y , either X ≻ Y or Y ≻ X. A preference relation ≻′ refines ≻ just when for all X, Y ∈ 2V , X ≻ Y implies X ≻′ Y .

Definition 3 (Semantics) A preference relation ≻ over 2V

• (i) satisfies a CI-statement S +, S - : S1 ▷ S2 if for every S ′ ⊆ V \ (S + ∪S - ∪S1 ∪S2), we have S ′ ∪S + ∪S1 ≻ S ′ ∪ S + ∪ S2; and it
• (ii) satisfies a CI-net N if ≻ satisfies each CI-statement in N and ≻ is monotonic.

Definition 4 (Satisfiability) A CI-net N is called satisfiable if there exists a preference relation satisfying N.

Definition 5 (Induced preference relation) Let N be a satisfiable CI-net. Then its induced preference relation ≻N is defined as the smallest preference relation satisfying N.

This definition is well-founded, because the intersection of preference relations satisfying N also satisfies N . Figure 1 is an example for a preference relation induced by a CI-net.

While CI-nets, as defined here, are tailored to the representation of strict preferences, one can also consider CI-nets with weak preference (and indifference) statements, that suit the compact representation of weak monotonic preference relations. For the sake of simplicity, we focus on strict preferences, but most of our results easily extend to CI-nets with weak preferences and indifferences: weak CI-statements are of the form A ⊵ B, rather than A ▷ B, and the generated preference relation ⪰ has only to be weakly monotonic.

2.3 Worsening flipping sequences

We can define an alternative (but equivalent) way of interpreting CI-statements in terms of worsening flips, similar to flipping sequences in CP-nets [Boutilier et al., 2004].

Definition 6 (Worsening flip) Let N be a CI-net on the set of variables V, and let V1, V2 ⊆ V. Then V1 ❀ V2 is called a worsening flip wrt. N if one of the following two conditions is satisfied:

• V2 ⊊ V1 (monotonicity flip)
• there is a CI-statement (S +, S - : S1 ▷ S2) ∈ N such that if S = V \ (S + ∪ S - ∪ S1 ∪ S2), then:
• V1 ⊇ S1 ∪ S +, V2 ⊇ S2 ∪ S +;
• V1 ∩S - = V2 ∩ S - = V1 ∩ S2 = V2 ∩ S1 = ∅;
• and S ∩V1 = S ∩V2.

The first condition says: adding items to my bundle makes me better off. The second condition expresses that, all other things being equal (S ∩ V1 = S ∩ V2), having all the goods in S + but none from S -, I prefer having S1 rather than S2.

The notion of worsening flip provides an alternative (operational) semantics (or "proof theory") for CI-nets:

Proposition 1 Let N be a satisfiable CI-net, and A, B ⊆ V two bundles. We have A ≻N B if and only if there exists a sequence of worsening flips from A to B wrt. N .

The proof is omitted for lack of space, but it is similar to the proof of Theorems 7 and 8 in [Boutilier et al., 2004].

We can now formulate a necessary and sufficient condition for satisfiability in terms of worsening flips:

Proposition 2 A CI-net N is satisfiable if and only if it does not possess any cycle of worsening flips.

Proof sketch: Let N be a satisfiable CI-net and ≻ an order satisfying N. By Proposition 1, if N possesses a worsening cycle (X0,X1, . . . ,Xq,X0) then X0 ≻ X0, a contradiction.

Conversely, assume N has no worsening cycle. Then take any preference relation ≻ respecting the flips, that is, for every X, Y , (X ≻ Y ⇔ X ❀ Y ). Using again the same kind of technique as in [Boutilier et al., 2004], we can show that ≻ satisfies N, therefore N is satisfiable. ■

2.4 Acyclicity and satisfiability

Definition 4 and Proposition 2 do not offer a practical method for checking satisfiability. We therefore introduce two sufficient conditions for satisfiability of a CI-net. The first condition is very similar to the one introduced in [Brafman et al., 2006a] for TCP-nets, and relies on the notions of dependency graph and S-induced graph.

Formally, given a CI-net N on V, the dependency graph of N ⋆ has V as nodes, and is defined as follows: (x, y) is a directed edge in N ⋆ if and only if there is a CI-statement S +, S - : S1 ▷ S2 in N such that x ∈ S + ∪ S - and y ∈ S1 ∪ S2. Given a set S ⊆ V, the S-induced graph GS(N) is defined as follows: (x, y) is a directed edge in GS(N) if and only if it is a directed edge of N ⋆ or there is a CI-statement S +, S - : S1 ▷ S2 in N such that x ∈ S1, y ∈ S2, S + ⊆ S and S - ∩ S = ∅. As for TCP-nets, a CI-net N will be called conditionally acyclic if GS(N) is acyclic for all S ⊆ ⋃(S+,S-:S1▷S2)∈N (S + ∪ S -).

Proposition 3 Any conditionally acyclic CI-net is satisfiable.

Proof sketch: The proof is similar to the one for TCP-nets [Brafman et al., 2006a]. It is based on two properties: (i) since N is conditionally acyclic, there is at least one root variable a such that ∀(S +, S - : S1 ▷S2) ∈ N, a ̸∈ S + ∪S - and a ̸∈ S2, and (ii) every subnet of a conditionally acyclic CI-net is also conditionally acyclic. The proof proceeds by induction on the number of variables in V: given a root variable a, we project N on V \ {a} to obtain Na and N¯a (for the two possible values of a). An ordering ≻ satisfying N can be obtained by gathering the orderings ≻a and ≻¯a. ■

Verifying conditional acyclicity of a CI-net is coNPcomplete in the general case, for similar reasons as those presented in [Brafman et al., 2006a]. Thus it is worthwhile giving another sufficient condition for satisfiability, which is easier to verify. Given a CI-net N, let the corresponding preference graph G(N) be defined as the graph whose directed edges are the pairs (x, y) such that there is a CI-statement S +, S - : S1 ▷ S2, with x ∈ S1 and y ∈ S2.

Proposition 4 Any CI-net with an acyclic preference graph is satisfiable.

Proof: Let N be a CI-net whose preference graph G(N) is acyclic. Let >O be a linear order on V respecting G(N) (i.e., if (x, y) ∈ G(N) then x >O y). Such an order exists, because G(N) is acyclic. Let ≻O be the lexicographic preference relation wrt. >O. For each (S +, S - : S1 ▷ S2) ∈ N, and each S ′ disjoint from S1, S2, S + and S -, S + ∪ S1 ∪ S ′ ≻O S + ∪ S2 ∪ S ′ because the most important element in (S + ∪S1 ∪S ′ ) \ (S + ∪S2 ∪S ′ ) is in S1, and the most important element in (S + ∪ S2 ∪ S ′ ) \ (S + ∪ S1 ∪ S ′ ) is in S2. Hence, ≻O satisfies every CI-statement in N, and it is monotonic, i.e., N is satisfiable.

■

Since G(N) can be built in polynomial time, this sufficient condition can be checked in (low-order) polynomial time. This condition is at the same time stronger and weaker than conditional acyclicity: it bears on the union of the S-induced graphs, but it does not require dependency acyclicity.

2.5 Expressivity

Let L be a restriction of the language of CI-nets (for a fixed set of objects V). For instance, a particular language may not allow the use of preconditions, or the compared sets referred to in CI-statements may not exceed a certain cardinality. We say that a preference relation ≻ is expressible in L if there exists a CI-net N in L such that (≻N=≻). We first show that the language without any restrictions is fully expressive.

Proposition 5 CI-nets can express all strict monotonic preference relations on 2V .

Proof sketch: Let ≻ be a strict monotonic order. Consider the CI-net N containing, for every (X, Y ) such that X ≻ Y and X ̸⊃ Y , the CI-statement (X∩Y ), (X ∪ Y ) : X\Y ▷Y \X. It is easy to check that ≻N=≻. ■

This full expressivity is lost when any of the following restrictions to the language is imposed: (a) no positive preconditions; (b) no negative preconditions; (c) the cardinality of compared sets is bounded by a fixed integer K ≤ n - 2.

To see why it is so for restrictions (a) and (b), let V = {x, y, z} and ≻ be a monotonic preference relation containing xy ≻ xz and z ≻ y. ≻ is expressible using the statements x : y▷z, ¯x : z▷y. However, ≻would not be expressible without positive (nor without negative) preconditions: Suppose there exists a satisfiable CI-net N, without negative preconditions, such that ≻=≻N. Because negative preconditions are not allowed, z ≻N y implies that in N we have either (1) z ▷ y, (2) z ▷ x and x ▷ y, or (3) z ▷ xy. In case (1), we have xz ≻N xy, which contradicts xy ≻N xz. In case (2), we have xz ≻N yz ≻N xy, which again contradicts xy ≻N xz. In case (3), we have xz ≻N z ≻N xy, which again contradicts xy ≻N xz. Therefore, there can be no satisfiable CI-net N without negative preconditions such that ≻=≻N (note that an unsatisfiable CI-net would not express ≻ either). A similar line of reasoning shows that the same preference relation ≻ is not expressible without positive preconditions.

To see why it is so for restriction (c), consider V = {x, y, z} and the monotonic preference relation xyz ≻ xz ≻ xy ≻ x ≻ yz ≻ y ≻ z ≻ ∅. ≻ is expressible by the CI-net {x : z ▷ y, ¯x : y ▷ x, x ▷ yz}. If compared subsets in CI-statements were only singletons, there would be no way of expressing x ▷ yz. More generally, if we have n items x1, . . . , xn, then a preference relation satisfying x1 ≻ {x2, . . . , xn} cannot be expressed if the cardinality of the compared subsets is bounded by K ≤ n - 2.

The restriction to singletons is particularly relevant, due to its simplicity. Note that the "conditional importance fragment" of binary TCP-nets falls in this fragment of CI-nets: any conditional importance is translated into a CI-statement on singletons in an obvious way.

Even simpler than the restriction to singletons is the combination of the restriction to comparisons between singletons and the absence of preconditions. In this case, a CI-statement has the form i▷j. ACI-net is called an SCI-net if it is a set of precondition-free, singleton-comparing CI-statements - that is, a set {i1 ▷ j1, . . . , iq ▷ jq}, where ik and jk are elements of V. An SCI-net N is called exhaustive if it has the form iθ(1) ▷ iθ(2) ▷ . . . ▷ iθ(n), where V = {i1, . . . , in}, and θ is a permutation of {1, . . . , n}. Exhaustive SCI-nets have (implicitly) been considered in various places, including [Brams et al., 2004]. An SCI-net N is transitively closed if for every i ▷ j and j ▷ k in N, i ▷ k is in N as well. Observe that the preference relation induced by an SCI-net and its transitive closure N ∗ are equivalent (proof omitted, but easy). Lastly, it is easy to check that an SCI-net is satisfiable if and only if it does not possess a cycle xi1 ▷ xi2 ▷ . . . ▷ xi1 .

Note that CI-nets also capture the monotonic fragment of conditional preferences theories [Wilson, 2004]. Recall that CP-theories allow to express statements of the form "x is preferred to ¯x, given ⃗u whatever the values of the variables in W". Corresponding statements in our language are statements of the form "I prefer the set of objects X to the set Y regardless of whether the objects in Z are in or out" (note that this is much stronger than "ceteris paribus"). Due to monotonicity, such a statement is simply expressed by (X∩Y ), ∅ : (X\Y )▷(Y \X)∪Z. Note that such statements are not expressible in the language of CP-theories when X\Y and Y \ X are not singletons.

3 Computational complexity

Next, we analyze the complexity of reasoning about preferences expressed as CI-nets. We will be interested in two problems: checking whether a given CI-net is satisfiable, and checking whether one bundle dominates another according to a given CI-net. The DOMINANCE problem is defined as: Given a CI-net N on V and bundles X, Y ∈ 2V , is it the case that X ≻N Y ? Note that, formally, (semantic) dominance has only been defined for satisfiable CI-nets (Definition 5).

Proposition 6 DOMINANCE in satisfiable CI-nets is PSPACE-complete, even under any of these restrictions:

1. every CI-statement bears on singletons and has no negative preconditions;
2. every CI-statement bears on singletons and has no positive preconditions;
3. every CI-statement is precondition-free.

Proof sketch: Membership is easy to establish. For hardness, we need a reduction for each of the three cases.

For case (1), consider the following reduction from DOMINANCE IN SATISFIABLE BINARY CP-NETS, known to be PSPACE-complete [Goldsmith et al., 2008]. With every satisfiable CP-net M = 〈X, G, T 〉, where X is a set of binary variables, G a graph on X, and T a set of conditional preference tables wrt. G, we associate the following CI-net N:

• V = {x, x′ | x ∈ X};
• for each z ∈ X and each ⃗t : z ≻ ¯ z (resp. ⃗t : ¯ z ≻ z) in T (where ⃗t denotes a vector of Boolean values), we add a

statement f(⃗t),∅ : z ▷ z′ (resp. f(⃗t),∅ : z′ ▷ z), where f(⃗t) = {x | ⃗t contains x} ∪ {x′ | ⃗t contains ¯x}.

Let ⃗x, ⃗y ∈ 2X . We claim that ⃗x ≻M ⃗y if and only if f (⃗x) ≻N f(⃗y). First, assume ⃗x ≻M ⃗y. Then there exists a worsening sequence from ⃗x to ⃗y. Replacing ¯x by x′ everywhere in it, we obtain a worsening sequence in N; hence f(⃗x) ≻N f(⃗y).

Conversely, assume f(⃗x) ≻N f(⃗y). Then there exists a worsening sequence from f(⃗x) to f(⃗y) in ≻N . Such a worsening sequence is composed of applications of CI-statements in N and monotonicity flips. Now, f(⃗x) and f(⃗y) both have n = |X| objects, and every CI-statement in N preserves the number of objects. Therefore, as soon as one monotonicity flip is applied, the obtained set of objects contains n - 1 objects, and there is no way of obtaining n objects again later in the sequence. This implies that the worsening sequence is composed only of applications of CI-statements in N. Now, replacing every z′ by ¯ z, we obtain a worsening flipping sequence from ⃗x to ⃗y in N. Finally, note that N contains a worsening cycle if and only ifMdoes; therefore, the satisfiability of M implies the satisfiability of N .

For case (2), the reduction is the same as above, except that f(⃗t),∅ : z ▷ z′ is replaced by ∅, g(⃗t) : z ▷ z′ , with g(⃗t) = {x′ | ⃗t contains x} ∪ {x | ⃗t contains ¯x}.

For case (3), we use a reduction from case (1). Any CI-net over singletons with only positive preconditions M on V is mapped to the following CI-net N:

• the set of objects for N is V ∪ {v′ | v ∈ V};
• N contains the n statements v′ ▷v, for every v ∈ V, plus, for every X : a ▷ b on M, the statement X ∪ {a} ▷ X′ ∪ {b}, where X′ = {x′ | x ∈ X}.

For instance, if M = {a : b ▷ c, bc : d ▷ a}, then N = {ab ▷ a′ c, bcd ▷ b′ c′a, a′ ▷ a, b′ ▷ b, c′ ▷ c, d′ ▷ d}. We claim that for any A, B ⊆ V, A ≻M B if and only if A ≻N B.

Assume A ≻M B. Then there exists a worsening sequence from A to B. Consider any flip Zi ❀ Zi+1 in the sequence. If it is a monotonicity flip, leave it unchanged. If it is an application of some CI-statement X : y ▷z, then we can write Zi = X ∪ {y} ∪ Ti and Zi+1 = X ∪ {z} ∪ Ti. Then replace this flip by X∪{y}∪Ti ❀ X′ ∪{y}∪Ti, followed by the |X| flips {x′ ▷ x | x ∈ X} in any order. It is easily checked that a flipping sequence in M from A to B is thus transformed into a flipping sequence in N from A to B. Hence, A ≻N B.

Conversely, assume A ≻N B. We only sketch the proof. There exists a flipping sequence Z1 = A ❀ Z2 ❀ . . . ❀ Zq = B sanctioned by N. This sequence can be mapped to an equivalent sequence where every flip Zk ❀ Zk+1 resulting from the application of a CI-statement X ∪{a}▷X′ ∪{b} is followed directly by |X| - 1 flips of kind v ▷ v′ , and such that Zk and Zk+|X| do not contain any object from V ′ . This new sequence can be mapped directly into a worsening flipping sequence from A to B in M.

It is important to note that the reductions used give rise to satisfiable CI-nets. Hence, the dominance problem remains PSPACE-complete for satisfiable CI-nets. ■

The complexity of DOMINANCE falls down to P for the case of precondition-free singletons (SCI-nets):

Let N be an SCI-net. As remarked in Section 2.5, ≻N=≻N ∗ . Therefore, we can assume wlog. that N is transitively closed, and acyclic (if it were cyclic it would not be consistent). Note that N defines a partial order on V. For any X, Y ⊆ V, we define the bipartite graph GN,X,Y = (V1, V2,E), where V1 = X \ Y , V2 = Y \ X and (i, j) ∈ E if and only if N contains i ▷ j.

Lemma 1 If |X| = |Y | then X ≻N Y if and only if there exists a perfect matching in GN,X,Y .

Proof: If there exists a perfect matching π in GN,X,Y , then we can construct the flipping sequence starting from X and consisting in applying, in any order, the statements i ▷ π(i) for every i ∈ X \ Y (it is easy to see that all these flips will be applicable). Therefore, X ≻N Y .

Conversely, assume X ≻N Y . Then there is a flipping sequence X = Z0 ❀ Z1 ❀ Z2 . . . ❀ Zq = Y from X to Y sanctioned by N. We now show, by induction on the length t of the flipping sequence, that if there is a flipping sequence from X to Y sanctioned by N, then there exists a perfect matching πt in GN,X,Y . This is true if t = 1: because there is a T such that X = T ∪{a}, Y = T ∪{b}, the CI-statement applied being a ▷ b; thus X \ Y = {a}, Y \ X = {b}, and the matching is defined by π1(a) = b. Now, assume the property is true for any flipping sequence of length t. Consider a sequence X ❀ . . . ❀ Zt ❀ Zt+1. By the induction hypothesis, there exists a perfect matching πt between X \ Zt and Zt \ X, such that for every i ∈ X, i ▷ πt(i). Let a ▷ b be the CI-statement of N applied between Zt and Zt+1. We know that a ∈ Zt \ Zt+1 and b ∈ Zt+1 \ Zt. We are now going to build πt+1 from πt and a ▷ b. There are four possible cases (we only detail the first two ones due to lack of space):

1. a ∈ X and b ̸∈ X. Since a ∈ X ∩ Zt, a was not involved in πt, nor b (because b ̸∈ X). Just add a ↦→ b to πt, we get a perfect matching in GN,X,Zt+1 .
2. a ∈ X and b ∈ X. Then b ∈ X \ Zt, therefore, by applying the induction hypothesis, there exists a c ∈ Zt \ X such that πt(b) = c (therefore, b▷c is in N). Note that c ̸= a, because a ∈ X. Then, c ∈ Zt and c is left intact by the application of a ▷ b from Zt to Zt+1, therefore c ∈ Zt+1, that is, c ∈ Zt+1 \ X. Moreover, N contains a ▷ b and b ▷ c, therefore it contains a ▷ c by transitivity. Replacing b ↦→ c in πt by a ↦→ c, we get a perfect matching πt+1 in GN,X,Zt+1 .
3. a ̸∈ X and b ∈ X. One can check that replacing d ↦→ a and b ↦→ c in πt by d ↦→ c (with πt(b) = c and πt(d) = a) gives a perfect matching in GN,X,Zt+1 .

(4) a ̸∈ X and b ̸∈ X. Replace d ↦→ a in πt by d ↦→ b (with πt(d) = a) to get a perfect matching in GN,X,Zt+1 . ■

Proof of Proposition 7: When |X| = |Y |, the claim is a direct consequence of Lemma 1, because a matching can be found in polynomial time. If |X| > |Y |, just add |X| - |Y | dummy items z1, . . . , z|X|-|Y | to Y , and for every x ∈ X and every i, add x ▷ zi to N. Then X ≻N Y if and only if X ≻N Y ∪ {z1, . . . , z|X|-|Y |}, and again the problem is in P. Lastly, if |Y | > |X|, we cannot have X ≻N Y , because for any worsening flip Z ❀ Z ′ either |Z| = |Z ′ | (CI flip), or

■

SCI-nets are a fragment of TCP-nets, so Proposition 7 can also be seen as a tractability result for a fragment of TCPnets, which, to the best of our knowledge, does not follow from any of the known complexity results for TCP-nets.

An open question is the complexity of DOMINANCE for precondition-free CI-nets where the cardinality of the compared sets is bounded by a constant.

Lastly, we discuss the complexity of SATISFIABILITY, the problem of deciding whether a given CI-net is satisfiable.

Proposition 8 SATISFIABILITY for CI-nets is PSPACEcomplete.

Proof: Membership is as usual. Hardness comes from the following reduction from DOMINANCE: given a satisfiable CI-net N and two bundles A, B, we have A ≻N B if and only if N ∪{A∩B, ∅ : B\A▷A\B} is not satisfiable. ■

Since the CI-net resulting from the reduction has no negative preconditions, SATISFIABILITY remains PSPACE-complete even for CI-nets free of negative preconditions. However, the result does not obviously carry over to precondition-free CI-nets, nor to CI-nets where the compared sets are singletons. Finally, SATISFIABILITY for SCI-nets is in P, because an SCI-net is satisfiable if and only if it is acyclic.

Note that while the PSPACE-hardness results may seem rather negative, this is inherent to the problem: as soon as we want to design a language for specifying preferences between sets of objects of arbitrary size, to be understood ceteris paribus, we have to face this high complexity. This can be compared to the inherent complexity of propositional STRIPS planning: as soon as we want the language to be as expressive as STRIPS, we have to face PSPACE-hardness. On the positive side, as PSPACE-hardness is caused by the existence of exponentially long flipping sequences, it may be reasonable enough, in many practical cases, to look for short flipping sequences, at the risk of not finding any when there exists one (compare this to the SATPLAN approach to STRIPS planning). We conjecture that the simpler the CI-statements (where simplicity can be measured, for instance, by the cumulative size of preconditions and compared subsets), the shorter the flipping sequences (we leave this for further research).

4 CI-nets and fair division

A possible field of application for CI-nets is fair division. We now briefly want to outline how they may be used. Let us first recall the basics of fair division of indivisible goods (see e.g., [Brams et al., 2004]). Given a set of goods V, a set of agents A = {1, . . . ,N}, each of whom has a preference structure on 2V , we have to find an allocation π : A → 2V , such that π(i) ∩ π(j) = ∅ for every i ̸= j, satisfying some fairness or efficiency criteria. Two classical criteria are envy-freeness (an allocation is envy-free if every agent (weakly) prefers his own share to the share of any other agent) and Pareto-efficiency (there is no other allocation making some agent better and no other agent worse off). These two criteria are purely ordinal. It is a well-known fact that for some fair division problems there exists no allocation that is both envy-free and efficient.

A serious problem is that it is not reasonable to expect agents to specify their preferences explicitly over all sets of goods. This was already pointed out in [Brams et al., 2004; Brams and King, 2005], who suggested to use a preference relation over singletons, the semantics of which corresponds exactly to our exhaustive SCI-nets. The problem was discussed further, and analyzed computationally, in [Bouveret and Lang, 2008], but there mostly for the case of dichotomous preferences. CI-nets can be seen as a way of coping with this issue: they provide a fully expressive, yet compact way for agents to express their monotonic preferences.

Due to space limitations, we only illustrate how CI-nets can be used to express and solve fair division problems by means of an example. For every agent i, her (not necessarily complete) preference relation ≻i on 2V is described succinctly by a CI-net Ni. Following [Brams et al., 2004], though with a slight shift in terminology, we say that an allocation π is:

• EF-necessary if π is envy-free under every possible refinement of every agent's ≻i to a complete relation;
• EF-possible if π is envy-free under some refinement of every agent's ≻i to a complete relation;

Pareto-necessity and -possibility are defined accordingly.

Example Let V = {a, b, c}. Suppose there are two agents with CI-nets N1 = {b : c▷a, b : a▷c} and N2 = {c▷a, a▷b}. Allocations are denoted by pairs 〈π(1), π(2)〉.

• 〈a, bc〉 is not EF-possible, because bc ≻1 a. Neither are 〈c, ab〉, 〈ac, b〉, and 〈bc, a〉. Furthermore, 〈abc,∅〉 and 〈∅, abc〉 are not EF-possible due to monotonicity.
• 〈ab, c〉 is EF-possible but not EF-necessary: agent 1 prefers ab to c, and for agent 2, ab and c are incomparable. The same is true for 〈b, ac〉. Furthermore, it can be checked that 〈ab, c〉 is also Pareto-necessary.

If we allow incomplete allocations, then 〈a, c〉 is EFnecessary (but not Pareto-possible, since it is incomplete). Note that no allocation is both definitely envy-free and efficient (i.e., EF-necessary and Pareto-necessary).

Another (related) application of CI-nets is constrained optimization. Assume we have an agent whose monotonic preferences are represented by a CI-net over V, and that some constraints restrict the set of feasible subsets (for instance, the user may only receive a fixed number of objects, or more generally, each object may have a volume and there may be a maximum volume allowed). Then searching for a preferred feasible subset is a nontrivial task worth studying.

5 Conclusion

This paper contributes to filling a gap in preference representation in combinatorial domains: we have introduced a language, CI-nets, for the compact representation of monotonic preference relations over sets of goods, which is crucial in many applications. Compactness stems from the ceteris paribus interpretation of preference statements; a single CIstatement may express up to an exponential number of comparisons. While there were languages for expressing numerical preferences before (e.g., bidding languages), there was no such language for ordinal preferences.

We have already commented on the related work on CPnets, TCP-nets, and CP-theories. [Brafman et al., 2006b] give a very different language for expressing preferences over sets of objects; they have a two-tier language where preferences are expressed on properties that the set of objects enjoy, while we express preferences directly at the object level. Also, they are not concerned with monotonicity. These two lines of work are complementary to each other: we could use a two-tier systems and use CI-nets for expressing monotonic preferences over sets of properties. Finally, Yaman and desJardins [2007] identify a tractable subclass of CP-nets, which is characterized by what the authors call monotonic variables - not to be confused with the monotonicity property of preference relations themselves, which is what we are interested in.

We have shown that CI-nets can represent all monotonic strict orders, and that any of the natural restrictions on the language considered reduces expressivity. A study of which restriction can model which class of preferences is an important issue for future work, even if many families of cardinal preferences do not have natural ordinal counterparts.

Reasoning about preferences expressed as CI-nets can be hard, which is typical in compact preference representation. As our results show, as soon as we compare sets of arbitrary size with a ceteris paribus interpretation, dominance is hard.

Finally, we have sketched the application of CI-nets in the context of fair division. As our discussion indicates, there are a plethora of opportunities for fruitful research in this area.

Acknowledgements We would like to thank the anonymous referees for their comments. S. Bouveret and J. Lang have been partly supported by the project ANR-05-BLAN-0384.