Ranking sets of objects : how to deal with impossibility results

Abstract

Modeling preferences over alternatives is a major challenge in many areas of AI, for example in knowledge representation and, especially, in computational social choice. If the number of alternatives is small enough, preferences are most often modeled as a total order. However, in many applications the alternatives are 'combinatorial', i.e., sets of objects. These sets can be, for example, bundles of goods in packing or allocation problems or committees in voting. In these situations, the number of alternatives grows exponentially with the number of objects which makes it unfeasible for agents to specify a full preference relation over all alternatives. A widely used approach to circumvent this problem is to derive a preference order on sets of objects from a preference order on the objects. We call this lifting an order from objects to sets of objects. This process is often guided by axioms postulating properties the lifted order on sets should have. However, well-known impossibility results by Kannai and Peleg and by Barbera and Pattanaik tell us that some desirable axioms - namely dominance together with independence or strict independence - are not jointly satisfiable if all non-empty sets of objects are to be ordered. On the other hand, if not all non-empty sets of objects are to be ordered, the axioms are jointly satisfiable for some families of sets. However, it is not known on which families dominance and (strict) independence can be jointly satisfied and on which they are incompatible. This raises two questions: (1) Is it computationally difficult to decide for a given collection of sets whether dominance and (strict) independence are jointly satisfiable? (2) Is it possible to characterize collections of sets for which dominance and (strict) independence are jointly satisfiable? Observe that the axioms can be compatible to three different degrees. Dominance and (strict) independence can be jointly satisfiable on a family of sets for a specific linear order ≤ on the objects or, alternatively, for every or at least one linear order on the objects. In the first case, we say that the family is ≤-orderable, and in the latter cases we say that the family is strongly resp. weakly orderable. The first question is answered in this thesis by giving a nearly complete picture of the complexity of deciding whether a family is strongly, weakly or ≤-orderable with respect to dominance and independence or dominance and strict independence. In particular, it is shown that it is almost always intractable to decide orderability when the lifted order needs to be total. If the lifted order only needs to be partial, then most problems become tractable with the exception of strong and weak orderability with respect to dominance and strict independence, which remain intractable. For the second question, we focus on families of sets that induce connected subgraphs in graphs. For such families we characterize strong, weak and ≤-orderability with respect to dominance and strict independence, and obtain a tight bound on the class of families that are strongly orderable with respect to dominance and independence.