Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	罗俊杰博士，北京交通大学
Inviter:	陈旭瑾研究员
Title:	Complexity of Manipulation and Bribery in Premise-Based Judgment Aggregation with Simple Formulas
Language:	Chinese
Time & Venue:	2023.07.03 15:00-16:00 南楼N620
Abstract:	WJudgment aggregation is a framework to aggregate individual opinions on multiple, logically connected issues into a collective outcome. These opinions are cast by judges, which can be for example referees, experts, advisors or jurors, depending on the application and context. 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 various Manipulation and Bribery problems in premise-based 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 NP-hardness even holds for positive monotone clauses of length three, but the problem becomes polynomial-time solvable for positive monotone clauses of length two. For Bribery, we show that NP hardness even holds for positive monotone clauses of length two, but it becomes polynomial-time solvable for the same clause set if there is a constant budget. (Joint work with Robert Bredereck.)