The Complexity Landscape of Outcome Determination in Judgment Aggregation
Endriss, Ulle; de Haan, Ronald; Lang, Jérôme; Slavkovik, Marija (2020), The Complexity Landscape of Outcome Determination in Judgment Aggregation, Journal of Artificial Intelligence Research, 69, p. 687–731. 10.1613/jair.1.11970
TypeArticle accepté pour publication ou publié
Journal nameJournal of Artificial Intelligence Research
MetadataShow full item record
de Haan, Ronald
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)We provide a comprehensive analysis of the computational complexity of the outcome determination problem for the most important aggregation rules proposed in the literature on logic-based judgment aggregation. Judgment aggregation is a powerful and flexible framework for studying problems of collective decision making that has attracted interest in a range of disciplines, including Legal Theory, Philosophy, Economics, Political Science, and Artificial Intelligence. The problem of computing the outcome for a given list of individual judgments to be aggregated into a single collective judgment is the most fundamental algorithmic challenge arising in this context. Our analysis applies to several different variants of the basic framework of judgment aggregation that have been discussed in the literature, as well as to a new framework that encompasses all existing such frameworks in terms of expressive power and representational succinctness.
Subjects / Keywordscomputational complexity
Showing items related by title and author.
Lang, Jérôme; Pigozzi, Gabriella; Slavkovik, Marija; van der Torre, Leendert; Vesic, Srdjan (2017) Article accepté pour publication ou publié