Universiteit van Amsterdam

Archives

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

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.

Please note that this newsitem has been archived, and may contain outdated information or links.