Archives

Institute for Logic, Language and Computation


11 October 2016, Computational Social Choice Seminar, Ronald de Haan

Speaker: Ronald de Haan (Vienna & ILLC)
Title: The Complexity of Manipulating the Kemeny Judgment Aggregation Procedure
Date: Tuesday 11 October 2016
Time: 16:00
Location: Room F3.20, Science Park 107, Amsterdam

Abstract

Computational social choice studies methods for group decision making using concepts from theoretical computer science. An important topic in this area is the phenomenon of strategic manipulation, where individuals report an insincere opinion with the aim of getting a better group outcome. We study the problem of manipulation in the setting of judgment aggregation using a computational complexity perspective. In particular, we show that manipulating the Kemeny judgment aggregation procedure is complete for the second level of the Polynomial Hierarchy. This negative complexity result arguably is an obstruction against strategic manipulation of the Kemeny procedure.

Before explaining and discussing the complexity result, we give a gentle introduction to the setting of judgment aggregation and the computational complexity concepts involved. This means that the talk will be accessible for an audience that has no extensive knowledge of judgment aggregation or complexity theory.

For more information, see www.illc.uva.nl/~ulle/seminar or contact Ulle Endriss at .

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X