报告题目：Complexity Border of Strategic Voting Problems
报告时间：2020年1月6日上午11：00
报告地点：校本部计算机楼206会议室
报告简介：Strategic voting problems are central problems in computational social choice. Many strategic voting problems have been proved to be NP-hard in general. However, when they are restricted to the famous single-peaked preferences, many of them become polynomial-time solvable. In this talk, we will discuss several significant concepts of nearly single-peaked domains and present the (parameterized) complexity border of widely studied strategic voting problems between single-peaked preferences and general preferences, with respect to these concepts.
报告人简介：Dr Yongjie Yang received his Ph.D. degree from Saarland University in 11.2015. Currently he is a postdoctoral researcher in the chair of economic theory at Saarland Universily. His research interests include parameterized complexity theory, computational social choice, algorithmic graph theory, and algorithmic game theory. He has published more than 40 papers in IJCAI, AAMAS, JCSS, TCS, etc.
