The Taub Faculty of Computer Science Events and Talks
Ilan Nehama (Hebrew University of Jerusalem)
Sunday, 10.04.2011, 12:30
In this work we analyze judgement aggregation problems in which a group of agents independently votes on a set of complex propositions that has some interdependency constraint between them (e.g., transitivity when describing preferences). We generalize the previous results by studying approximate judgement aggregation. We relax the main two constraints assumed in the current literature, Consistency and Independence and consider mechanisms that only approximately satisfy these constraints, that is, satisfy them up to a small portion of the inputs. The main question we raise is whether the relaxation of these notions significantly alters the class of satisfying aggregation mechanisms. The recent works for preference aggregation of Kalai, Mossel, and Keller fit into this framework. The main result of this paper is that, as in the case of preference aggregation, in the case of a subclass of a natural class of aggregation problems termed `truth-functional agendas', the set of satisfying aggregation mechanisms does not extend non-trivially when relaxing the constraints.
In the talk I plan to describe this framework of judgement aggregation, describe the question of approximate aggregation and show resemblance to current works in the field of local testing. In addition, I will describe few agendas in which we can characterize the approximate aggregation mechanisms.