Complexity of Manipulation in Premise-Based Judgment Aggregation with Simple Formulas

Judgment aggregation is a framework to aggregate individual opinions on multiple, logically connected issues into a collective outcome. It is open to manipulative attacks such as Manipulation where judges cast their judgments strategically. Previous works have shown that most computational problems corresponding to these manipulative attacks are NP-hard. This desired computational barrier, however, often relies on formulas that are either of unbounded size or of complex structure. We revisit the computational complexity for a large class of Manipulation problems in judgment aggregation, now focusing on simple and realistic formulas. We restrict all formulas to be clauses that are (positive) monotone, Horn-clauses, or have bounded length. For basic variants of Manipulation, we show that these restrictions make several variants, which were in general known to be NP-hard, polynomial-time solvable. Moreover, 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 variants of Satisfiability. For Hamming distance based Manipulation, we show that NPhardness even holds for positive monotone clauses of length three, but the problem becomes polynomial-time solvable for positive monotone clauses of length two.