Computationally Efficient Representation Languages for Fairly Dividing Indivisible Goods
Boas Kluiving

Abstract:
We consider the scenario of fairly dividing a set of indivisible items among a group of agents with cardinal preferences. Because agents may have different preferences for every combination of items, intermediate representation languages are required in order to compactly represent the agents’ preferences. To choose the most fair allocation, we consider various solution concepts, such as utilitarian, egalitarian or Nash welfare, and look for the allocation elected by a particular solution concept.

In order to do this efficiently however, we need to be able to calculate such an elected allocation in polynomial time. In this thesis, we study the computational complexity of finding these allocations for various representation languages. Our aim here is to discover representation languages that have polynomial-time algorithms for finding such allocations, while at the same time being as expressive as possible. We also study intractability results for restricted versions of representation languages in order to discover which properties make the problem computationally intractable.

In particular, the languages that we study include the dichotomous language based on propositional formulas, the additive language and languages based on weighted bids. Based on the computational properties of these languages, we present a new representation language, called the disjunctive partition language, which has interesting tractability properties. Finally, we also study the different representation languages from a parameterized complexity perspective.