Computer Science – Artificial Intelligence
Scientific paper
2011-06-27
Computer Science
Artificial Intelligence
7 pages by arxiv pdflatex, 1 figure. The 6-page version has the same content and will be published in Proceedings of the Twent
Scientific paper
We consider manipulation problems when the manipulator only has partial information about the votes of the nonmanipulators. Such partial information is described by an information set, which is the set of profiles of the nonmanipulators that are indistinguishable to the manipulator. Given such an information set, a dominating manipulation is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator's information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.
Conitzer Vincent
Walsh Toby
Xia Lirong
No associations
LandOfFree
Dominating Manipulations in Voting with Partial Information 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 Dominating Manipulations in Voting with Partial Information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dominating Manipulations in Voting with Partial Information will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-638958