Complexity of Judgment Aggregation

DOI10.1613/JAIR.3708zbMATH Open1253.68298DBLPjournals/jair/EndrissGP12arXiv1401.5863OpenAlexW2170386081WikidataQ62047305 ScholiaQ62047305MaRDI QIDQ3143579FDOQ3143579

Umberto Grandi, Daniele Porello, Ulle Endriss

Publication date: 3 December 2012

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: We analyse the computational complexity of three problems in judgment aggregation: (1) computing a collective judgment from a profile of individual judgments (the winner determination problem); (2) deciding whether a given agent can influence the outcome of a judgment aggregation procedure in her favour by reporting insincere judgments (the strategic manipulation problem); and (3) deciding whether a given judgment aggregation scenario is guaranteed to result in a logically consistent outcome, independently from what the judgments supplied by the individuals are (the problem of the safety of the agenda). We provide results both for specific aggregation procedures (the quota rules, the premise-based procedure, and a distance-based procedure) and for classes of aggregation procedures characterised in terms of fundamental axioms.

Full work available at URL: https://arxiv.org/abs/1401.5863

zbMATH Keywords

social choicejudgment aggregationquota rulescollective judgementlogical consistence

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Social choice (91B14) Analysis of algorithms and problem complexity (68Q25)

Cited In (24)

• Preservation of semantic properties in collective argumentation: the case of aggregating abstract argumentation frameworks
• Neutrality and relative acceptability in judgment aggregation
• The logic of group decisions: judgment aggregation
• Applications of Logic in Social Choice Theory
• Strategic manipulation in judgment aggregation under higher-level reasoning
• Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation
• Ontology Merging as Social Choice
• Title not available (Why is that?)
• Judgement aggregation in non-classical logics
• Complexity of manipulation and bribery in premise-based judgment aggregation with simple formulas
• Complexity of control in judgment aggregation for uniform premise-based quota rules
• A partial taxonomy of judgment aggregation rules and their properties
• Title not available (Why is that?)
• Structural control in weighted voting games
• Graph aggregation
• Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules
• Strategyproof judgment aggregation under partial information
• Introduction to Judgment Aggregation
• The Complexity Landscape of Outcome Determination in Judgment Aggregation
• Parameterized complexity classes beyond para-NP
• Preservation of Admissibility with Rationality and Feasibility Constraints
• Path-disruption games: bribery and a probabilistic model
• Quota rules for incomplete judgments
• On the Computational Complexity of Non-Dictatorial Aggregation

This page was built for publication: Complexity of Judgment Aggregation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143579)