[Zurück]

R. de Haan, U. Endriss, S. Szeider:
"Parameterized Complexity Results for Agenda Safety in Judgment Aggregation";
Vortrag: International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Istanbul, Turkey; 04.05.2015 - 08.05.2015; in: "Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems - AAMAS 2015", G. Weiss, P. Yolum, R. Bordini, E. Elkind (Hrg.); (2015), ISBN: 978-1-4503-3413-6; S. 127 - 136.

Many problems arising in computational social choice are of high computational complexity, and some are located at higher levels of the Polynomial Hierarchy. We argue that a parameterized complexity analysis provides valuable insight into the factors contributing to the complexity of these problems, and can lead to practically useful algorithms. As a case study, we consider the problem of agenda safety for the majority rule in judgment aggregation, consider several natural parameters for this problem, and determine the parameterized complexity for each of these. Our analysis is aimed at obtaining fixed-parameter tractable (fpt) algorithms that use a small number of calls to a SAT solver. We identify several positive results, including several results where the problem can be fpt-reduced to a single SAT instance. In addition, we identify several negative results. We hope that this work may help initiate a structured parameterized complexity investigation of problems arising in the field of computational social choice that are located at higher levels of the Polynomial Hierarchy.