Abstract:
Aggregating the preferences of self-interested agents is a key problem for multiagent systems, and one general method for doing so is to vote over the alternatives (candidates). Unfortunately, the Gibbard-Satterthwaite theorem shows that when there are three or more candidates, all reasonable voting rules are manipulable (in the sense that there exist situations in which a voter would benefit from reporting its preferences insincerely). To circumvent this impossibility result, recent research has investigated whether it is possible to make finding a beneficial manipulation computationally hard. This approach has had some limited success, exhibiting rules under which the problem of finding a beneficial manipulation is {sf NP}-hard, {sf #P}-hard, or even {sf PSPACE}-hard. Thus, under these rules, it is unlikely that a computationally efficient algorithm can be constructed that {em always} finds a beneficial manipulation (when it exists). However, this still does not preclude the existence of an efficient algorithm that {em often} finds a successful manipulation (when it exists). There have been attempts to design a rule under which finding a beneficial manipulation is {em usually} hard, but they have failed. To explain this failure, in this paper, we show that it is in fact impossible to design such a rule, if the rule is also required to satisfy another property: a large fraction of the manipulable instances are both weakly monotone, and allow the manipulators to make either of exactly two candidates win. We argue why one should expect voting rules to have this property, and show experimentally that common voting rules clearly satisfy it. We also discuss approaches for potentially circumventing this impossibility result.