TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 31.05.2018


Page Content

to Navigation

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.



Junjie Luo
TEL 512

Back to the research colloquium site.

To top


Quick Access

Schnellnavigation zur Seite über Nummerneingabe