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

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.