OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Succinctness of Languages for Judgment Aggregation

Endriss, Ulle and Grandi, Umberto and De Haan, Ronald and Lang, Jérôme Succinctness of Languages for Judgment Aggregation. (2016) In: 15th International Conference on Principles of Knowledge Representation and Reasoning (KR 2016), co-located with DL 2016 and NMR 2016, 25 April 2016 - 29 April 2016 (Cape Town, South Africa).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


We review several different languages for collective decision making problems, in which agents express their judgments, opinions, or beliefs over elements of a logically structured domain. Several such languages have been proposed in the literature to compactly represent the questions on which the agents are asked to give their views. In particular, the framework of judgment aggregation allows agents to vote directly on complex, logically related formulas, whereas the setting of binary aggregation asks agents to vote on propositional variables, over which dependencies are expressed by means of an integrity constraint. We compare these two languages and some of their variants according to their relative succinctness and according to the computational complexity of aggregating several individual views expressed in such languages into a collective judgment. Our main finding is that the formula-based language of judgment aggregation is more succinct than the constraint-based language of binary aggregation. In many (but not all) practically relevant situations, this increase in succinctness does not entail an increase in complexity of the corresponding problem of computing the outcome of an aggregation rule.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to AAAI. The original PDF is available at: https://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12851
HAL Id:hal-03625799
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > Technische Universität Wien - TU Wien (AUSTRIA)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université Paris-Dauphine (FRANCE)
Other partners > University of Amsterdam - UvA (NETHERLANDS)
Laboratory name:
COST Action IC1205 on Computational Social Choice - FWF Austrian Science Fund (Parameterized Compilation,P26200) - French National Research Agency (Project ANR-14-CE24-0007-01 “CoCoRICo-CoDec”)
Deposited On:20 Feb 2018 16:11

Repository Staff Only: item control page