Computer Science – Computer Science and Game Theory
Scientific paper
2012-02-29
Computer Science
Computer Science and Game Theory
8 pages
Scientific paper
Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential, and manipulators may know the already cast votes but may not know the future votes. We introduce a framework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that in this setting manipulation can be extremely complex even for election systems with simple winner problems. Yet we also show that for some of the most important election systems such manipulation is simple in certain settings. This suggests that when using sequential voting, one should pay great attention to the details of the setting in choosing one's voting rule. Among the highlights of our classifications are: We show that, depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. And we obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model.
Hemaspaandra Edith
Hemaspaandra Lane A.
Rothe Joerg
No associations
LandOfFree
The Complexity of Online Manipulation of Sequential Elections does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Online Manipulation of Sequential Elections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Online Manipulation of Sequential Elections will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-526427