The Complexity of Forming an Effective Government
October 29, 2014

The theory of Social Choice investigates procedures to combine the preferences of individuals in order to reach a collective decision. This often leads to intriguing combinatorial and algorithmic problems. I will illustrate this phenomenon by discussing two recent examples. The first deals with the complexity of the problem of deciding whether or not it is possible to form an agenda supported by a majority of the members of a parliament with known individual preferences. The second studies the possibilities to bias the decisions in judgment aggregation over multiple independent issues by bundling several issues together.

Based on joint papers with Bredereck, Chen, Kratsch, Niedermeier and Woeginger, and with Falik, Meir and Tennenholtz.