Title: Ranking Sets of Objects - How to Deal with Impossibility Results
Language: English
Authors: Maly, Jan 
Keywords: Preference Modelling; Computational Social Choice; Ranking Sets of Objects
Advisor: Woltran, Stefan 
Assisting Advisor: Lackner, Martin  
Issue Date: 2020
Number of Pages: 166
Qualification level: Doctoral
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.
URI: https://doi.org/10.34726/hss.2020.83187
http://hdl.handle.net/20.500.12708/15741
DOI: 10.34726/hss.2020.83187
Library ID: AC15760736
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Hochschulschrift | Thesis

Files in this item:

Show full item record

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.