Show simple item record

Succinctness of Languages for Judgment Aggregation

hal.structure.identifierInstitute for Logic, Language and Computation [ILLC]
dc.contributor.authorEndriss, Ulle
hal.structure.identifier
dc.contributor.authorGrandi, Umberto
HAL ID: 735707
ORCID: 0000-0002-1908-5142
hal.structure.identifier
dc.contributor.authorde Haan, Ronald
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLang, Jérôme
dc.date.accessioned2017-04-04T12:57:19Z
dc.date.available2017-04-04T12:57:19Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16483
dc.language.isoenen
dc.subjectsocial choice theory
dc.subjectcombinatorial domains
dc.subjectcomputational complexity
dc.titleSuccinctness of Languages for Judgment Aggregationen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.
dc.identifier.citationpages176-186en
dc.relation.ispartoftitleKR'16 Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoningen
dc.relation.ispartofeditorBaral, Chitta
dc.relation.ispartofeditorDelgrande, James
dc.relation.ispartofeditorWolter, Frank
dc.relation.ispartofpublnameAAAI Pressen
dc.relation.ispartofpublcityPalo Alto (USA)en
dc.relation.ispartofdate2016
dc.relation.ispartofpages642en
dc.identifier.urlsitehttp://dl.acm.org/citation.cfm?id=3032049
dc.relation.ispartofisbn978-1-57735-755-1en
dc.relation.conftitle15th International Conference on Principles of Knowledge Representation and Reasoning (KR'16)en
dc.relation.confdate2016-04
dc.relation.confcityCape Townen
dc.relation.confcountrySouth Africaen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-04-04T12:18:53Z
hal.identifierhal-01501681*
hal.version1*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record