Inhalt des Dokuments
Manipulation and Bribery in Premise-Based Judgment Aggregation with Restricted Formulas
Junjie Luo (TU Berlin)
Judgment aggregation is a framework to aggregate individual
opinions on multiple, logically connected issues into a collective
outcome. As most collective decision frameworks, it is open to
manipulative attacks such as MANIPULATION where judges cast their
judgments strategically or BRIBERY where an external agent influences
the judges. Previous works have shown that most computational problems
corresponding to these manipulative attacks are NP-hard already for
uniform premise-based rules, which form the probably most simple and
natural class of judgment aggregation rules. These hardness results,
however, do often rely on assuming no formula restrictions.
In this paper, we revisit the computational complexity for a large class of MANIPULATION and BRIBERY problems in judgment aggregation. To this end, we restrict all formulas to be clauses in disjunctive form and consider the special cases where all clauses are positive monotone, monotone, Horn-clauses, or have bounded length. For basic variants of MANIPULATION, we show that the restriction to clauses makes several variants, which were in general known to be NP-hard, polynomial-time solvable. We provide a P vs. NP dichotomy for a large class of clause restrictions (generalizing monotone and Horn clauses) by showing a close relationship between variants of MANIPULATION and related variants of SATISFIABILITY. For MANIPULATION with Hamming distance based preferences and several variants of BRIBERY, which were all already known to be NP-hard for monotone clauses, we show that NP-hardness even holds for monotone or Horn clauses of length two. We also identify a few polynomial-time solvable special cases.
Back to the research colloquium site.