TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 06.01.2017


Page Content

to Navigation

Efficient Preference Aggregation with Structured Preferences

Dominik Peters (University of Oxford)


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.

Joint work with Edith Elkind and Martin Lackner.


Dominik Peters
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe