Succinctness of Languages for Judgment Aggregation
Endriss, Ulle; Grandi, Umberto; de Haan, Ronald; Lang, Jérôme (2016), Succinctness of Languages for Judgment Aggregation, dans Baral, Chitta; Delgrande, James; Wolter, Frank, KR'16 Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, AAAI Press : Palo Alto (USA), p. 176-186
Type
Communication / ConférenceLien vers un document non conservé dans cette base
http://dl.acm.org/citation.cfm?id=3032049Date
2016Titre du colloque
15th International Conference on Principles of Knowledge Representation and Reasoning (KR'16)Date du colloque
2016-04Ville du colloque
Cape TownPays du colloque
South AfricaTitre de l'ouvrage
KR'16 Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and ReasoningAuteurs de l’ouvrage
Baral, Chitta; Delgrande, James; Wolter, FrankÉditeur
AAAI Press
Ville d’édition
Palo Alto (USA)
Isbn
978-1-57735-755-1
Nombre de pages
642Pages
176-186
Métadonnées
Afficher la notice complèteAuteur(s)
Endriss, UlleInstitute for Logic, Language and Computation [ILLC]
Grandi, Umberto

de Haan, Ronald
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
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.Mots-clés
social choice theory; combinatorial domains; computational complexityPublications associées
Affichage des éléments liés par titre et auteur.
-
Endriss, Ulle; de Haan, Ronald; Lang, Jérôme; Slavkovik, Marija (2020) Article accepté pour publication ou publié
-
Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2009) Communication / Conférence
-
Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme (2006) Communication / Conférence
-
Endriss, Ulle; Kraus, Sarit; Lang, Jérôme; Wooldridge, Michael (2011) Communication / Conférence
-
Wooldridge, Michael; Endriss, Ulle; Kraus, Sarit; Lang, Jérôme (2013) Article accepté pour publication ou publié