Algorithmics and Computational Complexity

Computational Social Choice: Multiple Preference Profiles and Multiple Solutions (COMSOC-MPMS)

Synopsis

The area of computational social choice (COMSOC) is concerned with the analysis of collective decision problems from an algorithmicperspective. So far, the main focus in this area lied on analyzing problems where a single preference relation for each agent is given and a single solution reflecting all agents’ preferences needs to be found. However, this modeling is not rich enough to capture the changing and ambivalent nature of real-world problems. To be able to model such aspects, in this project, we relax the classical paradigm which assumes that we are given only a single preference profile for which a single solution needs to be found. Instead, we allow for multiple preference profiles in the input and/or for multiple separate solutions in the output. We identify various conceptually fundamentally different settings that naturally arise in this context, which we plan to systematically study in this project. Our ultimate goal is to create a toolbox of concepts, axiomatic properties, and algorithms that can be used to model complex real-world problems involving aspects like time and multimodality.

Funded by

Deutsche Forschungsgemeinschaft (Project COMSOC-MPMS, NI 369/22)

Time

Since November 2021

Head: formerly Rolf Niedermeier, since 2022:

Organization name Algorithmics and Computational Complexity
Office TEL 5-1
Room TEL 509A
office hoursTuesdays 17:30 - 18:30

People