Efficient Preference Aggregation with Structured Preferences

Abstract:

Group decision making is a tricky task: desirable properties (such as Condorcet-consistency or non-manipulability) are incompatible or flat-out impossible to achieve, and many known good decision procedures are NP-hard to evaluate, especially in settings where multiple winning alternatives are desired. However, if agents' preferences are well-structured, both of these problems can be circumvented. For example, if preferences are single-peaked or single-crossing, aggregation problems and hardness results tend to go away. In this talk, we survey such results and see whether they can be extended to more general notions of structured preferences, such as preferences single-peaked on circles and trees, and preferences that are multidimensional. A particular focus lies on the complexity of the problems of recognising whether a given preference profile is structured in one of these ways: to make use of a specialised algorithm, we better have a fast algorithm that checks if it is applicable -- though we will also see some intriguing cases where this initial step can be skipped.

Parts of this talk is joint work with Edith Elkind and Martin Lackner.