Computer Science – Computer Science and Game Theory
Scientific paper
2003-07-07
In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003
Computer Science
Computer Science and Game Theory
Scientific paper
Voting is a general method for preference aggregation in multiagent settings, but seminal results have shown that all (nondictatorial) voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally. A number of recent papers study the complexity of manipulating existing protocols. This paper is the first work to take the next step of designing new protocols that are especially hard to manipulate. Rather than designing these new protocols from scratch, we instead show how to tweak existing protocols to make manipulation hard, while leaving much of the original nature of the protocol intact. The tweak studied consists of adding one elimination preround to the election. Surprisingly, this extremely simple and universal tweak makes typical protocols hard to manipulate! The protocols become NP-hard, #P-hard, or PSPACE-hard to manipulate, depending on whether the schedule of the preround is determined before the votes are collected, after the votes are collected, or the scheduling and the vote collecting are interleaved, respectively. We prove general sufficient conditions on the protocols for this tweak to introduce the hardness, and show that the most common voting protocols satisfy those conditions. These are the first results in voting settings where manipulation is in a higher complexity class than NP (presuming PSPACE $\neq$ NP).
Conitzer Vincent
Sandholm Tuomas
No associations
LandOfFree
Universal Voting Protocol Tweaks to Make Manipulation Hard 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 Universal Voting Protocol Tweaks to Make Manipulation Hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Universal Voting Protocol Tweaks to Make Manipulation Hard will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-10294