[Back]


Talks and Poster Presentations (with Proceedings-Entry):

R. de Haan, U. Endriss:
"Complexity of the Winner Determination Problem in Judgment Aggregation: Kemeny, Slater, Tideman, Young";
Talk: International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), Istanbul, Turkey; 2015-05-04 - 2015-05-08; in: "Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems - AAMAS 2015", G. Weiss, P. Yolum, R. Bordini, E. Elkind (ed.); (2015), ISBN: 978-1-4503-3413-6; 117 - 125.



English abstract:
Judgment aggregation is a collective decision making framework where the opinions of a group of agents is combined into a collective opinion. This can be done using many different judgment aggregation procedures. We study the computational complexity of computing the group opinion for several of the most prominent judgment aggregation procedures. In particular, we show that the complexity of this winner determination problem for analogues of the Kemeny rule, the Slater rule and the Young rule lies at the Θp2-level of the Polynomial Hierarchy (PH). Moreover, we show that the problem has a complexity at the Δp2-level of the PH for the analogue of Tideman's procedure with a fixed tie-breaking rule, and at the Σp2-level of the PH for the analogue of Tideman's procedure without a fixed tie-breaking rule.

Keywords:
winner determination problem, judgment aggregation

Created from the Publication Database of the Vienna University of Technology.