Preference Orders on Families of Sets - When Can Impossibility Results Be Avoided?

1 Introduction

When agents, individually or as a group, make decisions to select one of several options, they refer to their preference orders (or rankings) of the available choices. In a single-agent setting, the agent simply selects an option that she prefers the most. In a group setting, the agents submit their preference orders, or votes, to a voting rule, which determines the option to select.

In many situations, having a preference order on individual objects is not enough for decision making, and the ability to compare sets of alternatives is needed. For instance, when an agent is to select a set of objects subject to some constraints, as in the knapsack problem, that agent must have a preference order on the family of feasible sets. Similarly, in the problem of fair allocation of indivisible goods [Bouveret et al., 2016], knowing how agents rank sets of goods is necessary to ensure that the goods are distributed fairly. Some problems involving strategic behaviors in voting [Barber`a, 1977; Fishburn, 1977; Bossert, 1989; Brandt and Brill, 2011; Brandt et al., 2018] and when determining optimal matchings and assignments [Roth and Sotomayor, 1990] also require the knowledge of agents' preferences on collection of objects. Finally, preferences on sets of outcomes are needed in decision making, when there is uncertainty about the consequences of an action [Larbi et al., 2010].

However, the size of families of subsets of a given set of available objects makes explicit enumerations of preference orders or rankings infeasible. To circumvent this problem, researchers proposed that agents' true preference order on sets be approximated by an order that can be derived from their preference order on individual objects. If such an order is given as a utility function on objects, the utility function (preference) on sets of objects can be derived assuming, say, some form of additivity. This is a common setting, used for instance in the knapsack problem and fair division.

An alternative and more abstract framework, known as the ordinal setting, assumes that preferences on objects in some set X are represented by an order relation on X. The objective is to lift this order to an order on a family of nonempty subsets of X. The problem of lifting an order relation on X to an order on the family of all non-empty subsets of X has been extensively studied. The paper by Barber`a et al. [2004] provides an excellent extensive overview of this research area. The results can roughly be divided into two groups, those concerned with properties of specific ways to lift an order on objects to an order on sets of objects, and those following the "axiomatic" approach, where one postulates desirable properties a lifted order should have and seeks conditions that would guarantee the existence of such a lifting [Barber`a, 1977; Barber`a et al., 1977; Moretti and Tsouki`as, 2012]. The most striking results in this latter group are known as impossibility theorems. They say that some natural desiderata are inherently incompatible and cannot be achieved together [Kannai and Peleg, 1984; Barber`a et al., 2004; Geist and Endriss, 2011].

The impossibility results mentioned above seek liftings to the family of all non-empty subsets of a set. This is a very strong requirement. Often we are only interested in comparing sets frommuch smaller families of sets.

Indeed, if the set of indivisible goods are offices and labs in a new research building and agents are research groups, it is natural to only consider allocations that form topologically contiguous areas. For instance, if the building consists of a single long hall of rooms, legal allocations are only those that split this hall into segments. In such situations, only preferences that research groups may have on contiguous segments of rooms need to be taken into account [Bouveret et al., 2017]. For another example, we might consider a problem of farmland fragmentation, where individual farms consist of many small non-contiguous plots of land as the result of divisions of farms among heirs, and acquiring ownership through marriage [King and Burton, 1982]. Land consolidation was proposed as a method to improve economic performance. The objective of land consolidation is to reallocate the plots so that they form large contiguous land areas. In both cases, the topology of the set of goods can be modeled by a graph and valid sets of goods are those that induce in this graph a connected subgraph.

The question we are concerned here is whether the impossibility results still hold when the goal is to lift an order on a set X (of goods) to specific collections of subsets of X, namely those determined by the condition of connectivity in a given graph on X. More precisely, we seek characterizations of graphs (topologies) when the impossibility results still hold and those, for which lifting to orders satisfying prescribed postulates is possible. To this end, we introduce the key notions of strongly and weakly orderable graphs. A graph is strongly (resp. weakly) orderable wrt a set of axioms if every (resp. at least one) linear order on X can be lifted to an order on the collection of all sets inducing in the graph connected subgraphs. Our contributions are as follows.

1. We show that the disjoint union of orderable graphs yields an orderable graph as well. This enables us to fully describe strong and weak orderability by characterizing the two concepts for connected graphs.
2. We fully characterize orderable connected graphs wrt the axioms of dominance and strict independence. For these two axioms, the class of strongly orderable graphs is that of trees and the class of weakly orderable graphs is that of connected bipartite graphs. This also holds if, in addition, the axiom of (strong) extension is required.
3. We show that weakening strict independence to independence has minimal effect on strong orderability. In combination with strong extension, we show that the only additional connected strongly orderable graph that arises is the complete graph K3. If we do not require extension, we can give a nearly complete picture: all unicyclic graphs become strongly orderable but, with only some exceptions, graphs containing two cycles are not.

An interesting implication of our results is that weakening strict independence to independence results only in a modest extension of the class of strongly orderable graphs. It points to strict independence being perhaps more essential for the concept of strong orderability than its weaker and more commonly studied version.

Although we have focused here on graphs to respresent the sets of elements to be ordered in an implicit and compact way, we believe that our work has impact on further aspects of ongoing research on preferential reasoning in the field of AI. Indeed, implicit preference models are important for representing, eliciting and using preferences in practical applications. As an example, we mention here the work on preferences in Answer-Set Programming (see e.g. [Brewka et al., 2003;

Faber et al., 2013]) where logic programs compactly represent the sets to be ordered and languages as the one by Brewka et al. [2003] allow to express preferences over the individual elements, i.e. the atoms in the program. To this date, it is unclear whether the rankings obtained by such formalisms satisfy desirable properties as the ones discussed above. Our work thus can also be seen as a starting point for more general investigations on (im)possibililty results in formalisms from the areas in AI and KR.

2 Background

All sets we consider in the paper are finite. A binary relation is called an order 1 if it is reflexive, transitive and total. An order is linear if it is also antisymmetric. If ⪯ is an order on a set X, the corresponding strict order ≺ on X is defined by x ≺ y if x ⪯ y and y ̸⪯ x, where x, y are arbitrary elements of X; the corresponding equivalence or indifference relation ∼ is defined by x ∼ y if x ⪯ y and y ⪯ x. If ⪯ is linear then x ∼ y only if x = y.

For a linear order ⪯ on a set A, we write max⪯(A) for the maximal element of A with respect to ⪯. Similarly, we write min⪯(A) for the minimal element of A wrt ⪯. If no ambiguity arises, we drop the reference to the relation from the notation.

Given a set X and a linear order ≤ on X, the order lifting problem consists of deriving from ≤ an order ⪯ on a family X ⊆ P(X) \ {∅} of non-empty subsets of X, guided by axioms formalizing some natural desiderata 2 for such lifted orders. If all axioms in consideration enforce strict preferences we additionally expect the lifted order ⪯ to be a linear order. Otherwise, we expect the lifted order ⪯ to be just an order. In this work, independence is the only axiom not enforcing strict preferences, hence we expect the order to be linear if and only if we do not consider independence. We recall several axioms below. They are natural extensions of the versions of those axioms considered in the case when X = P(X) \ {∅} (cf. [Barber`a et al., 2004]). The extensions consist of adding conditions of the form Y ∈ X not needed in the original formulations (cf. [Maly andWoltran, 2017]).

Axiom 1 (Extension Rule). For all x, y ∈ X, such that {x}, {y} ∈ X :

Axiom 2 (Strong Extension). For all A, B ∈ X :

Axiom 3 (Dominance). For all A ∈ X and all x ∈ X, such that A ∪ {x} ∈ X :

Axiom 4 (Independence). For all A,B ∈ X and for all x ∈ X \ (A ∪ B), such that A ∪ {x}, B ∪ {x} ∈ X :

1 Often also called weak order or total preorder.

2 Observe that this does not mean that every axiom is desirable in every situation. For a more nuanced discussion on the applicability of these axioms see [Barber`a et al., 2004].

Axiom 5 (Strict Independence). For all A, B ∈ X and for all x ∈ X \ (A ∪ B), such that A ∪ {x}, B ∪ {x} ∈ X :

Note that strong extension implies the extension rule. One could also define a dual version of strong extension based on the minima of A and B. Because all problems in this paper are symmetric, we can use either version without loss of generality. These two axioms are strict versions of the well known Hoare and Smyth axioms (see [Brewka et al., 2010]) restricted to linear orders.

Example 1. Take X = {1, 2, 3, 4} with the usual linear order

The axioms impose constraints on any lifted order ⪯ on X. In particular, the extension rule implies {2} ≺ {4}, while strong extension additionally implies {2} ≺ A for all A ∈ X \ {2}. Dominance implies {2} ≺ {2, 4} ≺ {4}, {3, 4} ≺ {4}, {1, 2, 4} ≺ {2, 4} and {1, 4} ≺ {4}, and (strict) independence lifts the preference between {2, 4} and {4} to {1, 2, 4} and {1, 4}. Thus, dominance and independence imply {1, 2, 4} ⪯ {1, 4}, and dominance and strict independence imply {1, 2, 4} ≺ {1, 4}.

The standard version of the order lifting problem asks for the existence of a lifted order on X = P(X) \ {∅} that would satisfy dominance, and independence or strict independence. As it turns out, these requirements can rarely be satisfied together. In their seminal paper, Kannai and Peleg [1984] proved that if |X| ≥ 6 then orders on P(X) \ {∅} satisfying dominance and independence are not possible. Barber`a and Pattanaik [1984] showed a similar impossibility result for |X| ≥ 3, when dominance and strict independence are required.

We show in this paper that the picture for other families of non-empty subsets of X is much more interesting. In particular, we show it to be the case for collections of subsets of X that induce connected subgraphs in some graph on X. Namely, we describe non-trivial classes of graphs defining families of sets that allow for lifted orders satisfying dominance and (strict) independence. In many cases, these lifted orders also satisfy the extension rule or its stronger version. It is important as every reasonable lifted order should satisfy the extension rule. 3

3 Problem Statement

We are interested in families of sets that are defined in terms of connectivity of subgraphs in a graph. We consider undirected graphs only. We write G = (V,E) for a graph with the set of vertices V and the set of edges E. We write an edge between vertices u and v as {u, v} or uv. A subgraph of a graph G is a graph whose every vertex and edge are also a vertex and edge of G. If a subgraph H = (W, F) of G

3 The standard statement of the lifting problem does not explicitly mention the extension rule since for X = P(X) \ {∅} the extension rule is implied by two applications of dominance via {x1} ≺ {x1, x2} ≺ {x2} for x1 < x2.

Figure 2: Graph G′

contains all edges in G connecting vertices in W, H is the subgraph induced by W. A path consists of a non-empty set S of vertices that can be enumerated so that every two consecutive vertices are connected with an edge; its length is given by |S| - 1. A cycle is a sequence of at least three different vertices that can be enumerated so that every two consecutive vertices, as well as the first and the last one, are connected with an edge; the length of a cycle is given by the number of vertices. A graph is connected if every two of its vertices are connected with a path. A forest is a graph with no cycles. A tree is a forest that is connected.

Definition 2. For a graph G we write C(G) for the family of sets of vertices of all connected subgraphs of G. Moreover, IT(G) denotes the family of sets of vertices V ′ such that the subgraphs induced by V ′ in G are trees.

Example 3. For the graph G shown in Figure 1, we get

On the other hand for the graph G′ shown in Figure 2, we have C(G′ ) = P({1, 2, 3, 4}) \ {{1, 3}, {2, 4}} and IT(G′ ) = C(G′ ) \ {1, 2, 3, 4}.

Definition 4. Let X be a set of elements and X ⊆ (P(X) \ {∅}). We say X is strongly DI (S) -orderable, if for every linear order X there is a (linear) order on X satisfying dominance and (strict) independence. We say X is weakly DI (S) -orderable, if for at least one linear order on X there is a (linear) order on X satisfying dominance and (strict) independence. Analogously, we say X is strongly/weakly DI (S)E(S) -orderable if for every/for one linear order on X there is a (linear) order on X satisfying dominance, (strict) independence and (strong) extension. If there is no ambiguity, we say a graph G is strongly/weakly DI (S) - or DI (S)E(S) - orderable if C(G) has the property.

Example 5. Consider the graphs G and G′ form Figures 1 and 2. One can check that G is strongly DI S ES -orderable and G′ is not strongly DI S orderable. If we assume the natural order on the vertices of G′ , dominance and transitivity imply {1} ≺ {1, 2, 3} and {2, 3, 4} ≺ {4}. However, then strict independence implies {1, 4} ≺ {1, 2, 3, 4} ≺ {1, 4}, thus preventing ≺ from being a strict order. This argument obviously does not work on IT(G′ ) because {1, 2, 3, 4} ̸∈ IT(G′ ) and indeed IT(G′ ) is strongly DI S -orderable. Furthermore, if we exchange vertices 2 and 3 in G′ , then there exists an order on C(G′ ) satisfying dominance and strict independence. Hence G′ is weakly DI S -orderable.

It is evident that if a graph G is strongly or weakly orderable with respect to some collection of axioms selected from those discussed above, so are all its connected components. Importantly, the converse holds, too, allowing us to restrict attention to connected graphs only.

Proposition 6. Let G and G′ be graphs with the vertex sets U and V , respectively, such that U ∩ V = ∅. If G and G′ are strongly (weakly) DI (S) (E(S) )-orderable, then G∪G′ is strongly (weakly) DI (S) (E(S) )-orderable.

Proof. (Sketch) Let us define W = U ∪ V . Let us assume that ≤U and ≤V are linear orders on U and V such that some orders ⪯U on C(G) and ⪯V on C(G′ ) satisfy all necessary axioms with respect to ≤U and ≤V . To prove the claim in all its versions, it suffices to show that for every linear order ≤ on W such that ≤U and ≤V are restrictions of ≤ to U and V , respectively, there is an order ⪯ on C(G∪G′ ) satisfying all necessary axioms with respect to ≤. Now let ≤ be such a linear order. In order to define ⪯ we need the following definitions.

Let {u1, . . . , uk} be an enumeration of all elements in U such that {ui} ⪯U {uj} for all i ≤ j. Similarly, let {v1, . . . , vl} be an enumeration of all elements of V such that {vi} ⪯V {vj} for all i ≤ j. Let w ∈ W ∪ {0} for dummy element 0 ̸∈ W. For 1 ≤ i ≤ k - 1 and 1 ≤ j ≤ l - 1, we define

Clearly, the sets Cw, w ∈ {0} ∪ W are pairwise disjoint. Moreover, since C(G∪G′ ) = C(G)∪C(G′ ), it follows that C(G ∪ G′ ) = ⋃w∈{0}∪W Cw.

We define an order ⪯ on C(G ∪ G′ ) by setting A ⪯ B for A, B ∈ C(G ∪ G′ ) precisely when one of the following conditions holds:

• A, B ∈ Cw, for w ̸= 0, and A ⪯U B or A ⪯V B
• A, B ∈ C0, and A ⪯U B or A ⪯V B
• A, B ∈ C0, A ∈ C(G), B ∈ C(G′ )
• A ∈ Cw, B ∈ Cw′ , for w, w′ ∈ {0} ∪W, and w < w′ .

It can be verified that ⪯ is total, reflexive and transitive. Moreover, ⪯ satisfies the same axioms as ⪯U and ⪯V .

The case of strong extension requires a different construction. Let w ∈ U ∪ V . We define

Let us now assume that the orders ⪯U and ⪯V on C(G) and C(G′ ) respectively, satisfy strong extension with respect to ≤U and ≤V , respectively. To define an order ⪯ on C(G∪G′ ), for A, B ∈ C(G ∪ G′ ) we set A ⪯ B precisely when one of the following conditions holds:

• A, B ∈ Cw, w ∈ U and A ⪯U B
• A,B ∈ Cw, w ∈ V and A ⪯V B
• A ∈ Cw, B ∈ Cw′ and w < w′ .

Again, it is easily verified that ⪯ is an order. From the definition, it follows that ⪯ satisfies the strong extension property and it can be checked that it satisfies dominance and (strict) independence.

In the forthcoming two sections we present our main results. Section 4 considers the combination of strict independence with dominance and optionally, extension or strong extension. Then in Section 5 we consider combinations of axioms containing regular independence.

4 Strict Independence

We start our investigations with strong orderability. Our first result concerns the family of all subsets of vertices of a graph that induce a tree.

Proposition 7. For every graph G, IT(G) is strongly DI S ES -orderable.

Proof. (Sketch) Let N = |V | and let ≤ be any linear order on V . Wlog, we assume that V = {1, . . . ,N} and that ≤ is the standard linear order on {1, . . . ,N}. For every A ⊆ V and i ∈ A, we write degA(i) for the degree of i in the subtree of G induced by A. We associate with every set A a vector vA = (a1, . . . , aN) ∈ (N ∪ {∞})N , where ai = ∞ if i ̸∈ A, and ai = degA(i) otherwise.

Let ≤∗ be the reverse of the usual linear order on N∪{∞}, i.e. k ≤∗ l iff l ≤ k and ∞ ≤∗ k for all k. We order IT(G) by defining A ⪯ B precisely when vA ≤lex vB, where ≤lex is the lexicographic order with respect to ≤∗ , with the indices considered from N to 1. That is, A ⪯ B if aN <∗ bN, or aN = bN and aN-1 <∗ bN-1, and so on. Obviously, ≺ is a linear order, and it satisfies strong extension. It can also be checked that it satisfies dominance and strict independence.

This result is optimal in the sense that cycles prevent a graph from being strongly DI S -orderable.

Proposition 9. A graph G is not strongly DI S -orderable, whenever it contains a cycle.

Proof. Let C = v1, . . . , vn be a shortest cycle in G. Then C(G) contains C and all its connected subgraphs. Let ≤ be an order on V such that v1 < · · · < vn. Let us assume that there is an order ⪯ on C(G) that satisfies dominance and strict independence with respect to ≤. Then, by dominance {v1} ≺ {v1, v2} ≺ · · · ≺ {v1, . . . , vn-1} and {v2, . . . , vn} ≺ {v3, . . . , vn} ≺ · · · ≺ {vn}. Therefore, by strict independence {v1, vn} ≺ {v1, . . . , vn} and {v1, . . . , vn} ≺ {v1, vn}, a contradiction!

The following theorem summarizes the previous results and follows from Corollary 8, Proposition 6, Proposition 9 and the fact that any graph that is not strongly DI S -orderable is also not strongly DI S E(S) -orderable.

Theorem 10. The set of strongly DI S -, DI S E- or DI S ES - orderable graphs is exactly given by F, the class of forests.

This result states that every linear order on X can be lifted (wrt dominance, strict independence and strong extension) to every family of sets of vertices inducing a connected subgraph in a forest on X. For instance, no matter what linear order on {1, 2, . . . , n} we consider, it extends to a linear order on the family I = {[i..j] | 1 ≤ i < j ≤ n} that satisfies dominance, strict independence and strong extension. It is so because every set in F induces a connected subgraph in the path in which elements 1, . . . , n are listed in the natural order. The same is true for the family of sets S = {X ⊆ {1, . . . , n} | 1 ∈ X}. Indeed, each set in this family induces a connected subgraph in the "star" tree in which every vertex i ≥ 2 is connected to 1 (and there are no other edges).

We now turn to weak orderability and show in the forthcoming two results that the bipartite graphs form the crucial class for our characterization. We use the fact that a graph is bipartite if and only if it is 2-colorable.

Proposition 11. Every 2-colorable graph is weakly DI S ES - orderable.

Proof. (Sketch) Let us consider a 2-colorable graph G = (V,E). We color G with two colors small and large and call vertices of G small and large accordingly. Let ≤ be any linear order on V such that every small vertex is smaller than every large vertex.

For every A ∈ C(G) we define AL = {x ∈ A | x is large} and AS = {x ∈ A | x is small}. For A,B ∈ C(G), we define A ⪯ B if

• A ⪯ A;
• AL ̸= BL and max(AL△BL) ∈ BL; or
• AL = BL, AS ̸= BS, and min(AS△BS) ∈ AS.

(we write △ for the symmetric difference of sets). It is clear that ⪯ is a linear order. It can be checked that that ⪯ satisfies dominance, strict independence and strong extension.

This result shows, in particular, that if X and Y are disjoint nonempty sets, then the family of sets {Z ⊆ X∪Y | Z∩X ̸= ∅ ̸= Z ∩ Y } is weakly DI S ES -orderable.

Proposition 11 is tight as graphs that are not 2-colorable are not weakly DI S -orderable.

Theorem 12. The set of weakly DI S -, DI S E- or DI S ES - orderable graphs is exactly given by the class of 2-colorable graphs.

Proof. By Proposition 11, it remains to show that graphs that are not 2-colorable are not weakly DI S -orderable, which obviously implies the same for DI S E and DI S ES .

Let V be the vertex set of G. For every linear order ≤ we say a vertex x is large if n < x holds for all neighbors n of x and small if x < n holds. We call x intermediate if x is neither large nor small. We claim that for every order on V there is an intermediate vertex x ∈ V . Indeed, assume otherwise that there is an order ≤ on V without intermediate vertices. Obviously no large vertex can be a neighbor of a large vertex and no small vertex can be the neighbor of a small vertex. Thus, we constructed a 2-coloring of G, a contradiction.

Let ≤ be an order on G with a minimal number of intermediate vertices and let x be an intermediate vertex. We call a neighbor n of x small if n < x holds and large otherwise. We claim that at least one small neighbor of x is connected to at least one large neighbor of x by a path in G-x , the graph induced by V \ {x}. Indeed, let us assume otherwise and let V ′ be the set of all vertices in V reachable in G from x by paths not including any large neighbor of x. Let us define V ′′ = V \V ′ . Clearly, x and all small neighbors of x belong to V ′ and all large neighbors of x belong to V ′′ . For every element u ∈ V , we write ¯u for the dual element of u, i.e. if the rank of u in ≤ is k + 1, then ¯u is the element with rank |V | - k. We construct a linear order ≤′ by flipping u with ¯u, for all u ∈ V ′ in the enumeration of V with respect to ≤. It is clear that ≤′ is a linear order on V . Moreover, x is no longer an intermediate vertex in G and, for all other vertices, whether they are intermediate or not does not change. Thus, ≤′ is a linear order on V ′ with fewer intermediate vertices, a contradiction.

Let then n be a small neighbor of x connected in G-x to a large neighbor of x by a path, say n, x1, . . . , xk, n′ . Let us assume there is a linear order ⪯ on C(G) satisfying dominance and strict independence with respect to ≤. Then, since n < x, we have {n} ≺ {n, x} by dominance. Further, by repeated application of strict independence and transitivity

On the other hand, since x < n′ , we have {x, n′ } ≺ {n′ } and hence

Thus, {n, x1, . . . , xk, n′ } ≺ {n, x1, . . . , xk, n′ }, a contradiction.

5 Regular Independence

We now exchange strict by regular independence and focus on strong DIES -orderability for which we give an exact characterization. The following is easy to see.

Proposition 13. Let X be a set. If |X| ≤ 3, then P(X)\{∅} is strongly DIES -orderable.

The next result shows that we cannot go much beyond 3cycles.

Proposition 14. Let G be a connected graph with four or more vertices that contains at least one cycle. Then G is not strongly DIES -orderable.

Proof. Either G contains a cycle of length at least four or a cycle of length three connected to an additional vertex. In the first case let u, v ∈ V be two non-adjacent vertices contained in the cycle, and let u, v1, . . . , vn, v and u, u1, . . . , um, v be the two paths from u to v. In the second case let u be the additional vertex and let um, vn, v be the vertices in the cycle such that vn is connected to u. Define ≤ as u < u1 < . . . um < v1 < · · · < vn < v. Then there is no order on C(G) satisfying dominance, independence and strong extension with respect to ≤: assume otherwise ⪯ is such an order. Let CY be the set of all vertices in the cycle in the first case and CY = {u, v, um, vn} otherwise. Then, {um} ≺ CY \ {v} by strong extension, and {um, v} ⪯ CY by independence. However, by dominance {v1, . . . , vn, v} ≺ {v} and therefore, by independence, CY \ {u, u1, . . . , um-1} ⪯ {um, v} which contradicts CY ≺ CY \{u, u1, . . . , um-1} as required by dominance.

Therefore, K3 is the only connected graph that is strongly DIES -orderable but not DI S ES -orderable (recall Proposition 9). Also recall that a graph is strongly DI S ES -orderable precisely when it is a forest. The class of DIES -orderable graphs is thus only marginally larger, as is shown by the following result, which is immediate from Propositions 6, 13 and 14.

Theorem 15. The set of strongly DIES -orderable graphs consists precisely of graphs whose each connected component is a tree or a cycle K3.

We now turn to graphs that are strongly DIE- or DIorderable. We omit proofs due to space limits. Our first result shows that by replacing strong extension by extension or dropping extension altogether we get additional strongly orderable graphs.

Proposition 16. Every cycle is strongly DIE-orderable and every unicyclic graph is strongly DI-orderable.

On the other hand, we know that the following two classes of graphs are not strongly DI-orderable.

Proposition 17. A graph G = (V,E) is not strongly DIorderable if one of the following applies:

• there are distinct a, b ∈ V connected by three mutually disjoint paths, such that two of them have length at least two and the sum of their lengths is at least six;
• there is a vertex v ∈ V contained in two cycles C1,C2 of G such that C1 ∩ C2 = {v} and |C1| ≥ 4.

These results allow us to outline the extent of strongly DIorderable graphs. We recall that x is an articulation point in a graph G if the removal of G results in at least two connected components. Graphs without articulation points are two-connected. Propositions 16 and 17 imply that a twoconnected graph that contains a cycle of length at least six and is not a cycle itself is not strongly DI-orderable. Thus, the only two-connected graphs that are strongly DI-orderable are the complete graph K2, all cycles and, possibly, some twoconnected graphs with the length of the longest cycle equal to 4 or 5. For graphs that are not two-connected, we know that unicyclic graphs are strongly DI-orderable. We also know that graphs that contain two cycles sharing one point, with at least one of these cycles having length at least four, are not strongly DI-orderable. This limits connected graphs with articulation points that might be strongly DI-orderable to treelike graphs in which strongly orderable two-connected graphs ("meta-nodes") are connected to each other by paths (in the case of triangle meta-nodes, they may connect via a shared point).

Finally, we provide some preliminary results on weakly DIE-orderable graphs. The result of Kannai and Peleg

[1984] implies that the complete graph KN is not weakly DIE-orderable for N ≥ 6. On the other hand, every proper subgraph of K6 is weakly DIE-orderable.

Proposition 18. Every proper subgraph G of K6 is weakly DIE-orderable.

Observe that this can not be extended to strong extension, because K4 is a proper subgraph of K6 and not weakly DIES -orderable.

6 Discussion

Lifting a preference order on elements of some universe to a preference order on subsets of this universe respecting certain axioms is a fundamental problem, but well-known impossibility results pose severe limits on when such liftings exist. Bossert [1995] observed that these impossibility results may be avoided by considering families of subsets of fixed cardinality. Maly and Woltran [2017] showed that, deciding whether a given linear order on a set of objects X can be lifted to an order on a given collection of subsets of X is NPcomplete. Bouveret et al. [2017] were the first to consider graph topologies and subsets inducing connected subsets. They proposed this model for the problem of fair allocation of indivisible goods. Our work adopts their idea for an implicit representation of classes of families of non-empty subsets (in contrast to the explicit representation used in [Bossert, 1995; Maly and Woltran, 2017]). It turns out that for several interesting families of sets definable in terms of graphs the impossibility results observed for the family of all non-empty subsets of a set can be avoided!

Our main results characterize strongly and weakly DI S ES -orderable graphs. We also obtain a complete characterization of strongly DIES -orderable graphs. For strong DI-orderability we have an almost complete picture. Our results show rich classes of well-motivated families of sets that allow for lifting of linear orders in ways that combine dominance and (strict) independence. They also suggest that independence, despite being much less restrictive than strict independence, does not significantly extend that class of strongly orderable graphs. This suggests that it is strict independence that might be the axiom to focus on.

Even though in many cases our results fully resolve the order lifting problem, they also open several directions for future studies. First, we only touched on weak DI-orderability. We showed that all proper subgraphs of a complete graph K6 are weakly DI-orderable but have as of yet no general results on weakly DI-orderable graphs. Next, using graphs as implicit representations of families of sets is just one of many possibilities. Knowledge representation often uses logic formalisms towards this end. For instance, formulas can be viewed as concise representations of the families of their models. It is therefore important to study lifting of linear orders to orders on families of sets given by those representations. Further, for both graph and logical representations of families of sets it is a key challenge to establish the complexity of deciding the existence of lifted orders, and study algorithms for computing lifted orders in some concise representation. Finally, another direction for future work, is to investigate how our findings apply to the "reverse" problem of social ranking [Moretti and ¨Ozt¨urk, 2017], where an order over individuals needs to be obtained from a given order over sets of individuals.

Acknowledgments

This work was funded by the Austrian Science Fund (FWF) under grant number Y698 and by the NSF under grant number IIS-1618783.