Using Knowledge Compilation in Social Choice

VCLA and AC hosted a talk by Ronald de Haan

ABSTRACT

Various frameworks and settings for collective decision making have been studied in the field of computational social choice. One of these is that of Judgment Aggregation, where individuals vote on logically related issues, with the intent of finding a collective opinion that agrees with the logical constraint on the issues. This is typically formalized using a propositional logic constraint, resulting in intractability for computing the collective outcomes. However, most applications of this framework do not need full propositional logic. In this talk, I will describe how this problem can be avoided by using concepts from the area of knowledge compilation. By expressing the logical constraints using Boolean circuits satisfying one of several properties, one can get polynomial-time guarantees for computing collective opinions. I will describe the setting, discuss some results, and indicate future research directions.

Ronald de Haan, University of Amsterdam