The complexity of online manipulation of sequential elections

作者：

Highlights：

• We model and study the complexity of online manipulation of sequential elections.

• We show that such problems can be complete for each polynomial-hierarchy level.

• We show how ties greatly affect the sequential manipulation complexity of plurality.

• We obtain natural PNP[1]-complete and PNP-complete election problems.

摘要

•We model and study the complexity of online manipulation of sequential elections.•We show that such problems can be complete for each polynomial-hierarchy level.•We show how ties greatly affect the sequential manipulation complexity of plurality.•We obtain natural PNP[1]-complete and PNP-complete election problems.

论文关键词：Computational complexity,Computational social choice,Elections,Manipulation,Online algorithms,Preferences,Sequential voting

论文评审过程：Received 13 February 2013, Revised 16 September 2013, Accepted 1 October 2013, Available online 9 October 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.10.001