We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function f of @math alternatives and n voters will be manipulable with probability at least @math , where @math is the minimal statistical distance between f and the family of dictator functions. Our results extend those of FrKaNi:08, which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in BarthOrline:91, ConitzerS03b, ElkindL05, ProcacciaR06 and ConitzerS06) cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of 3 or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.
Corollary and Corollary , which extend the result of @cite_3 to the case of @math or more alternatives, are thus more relevant with respect to the hardness of finding a manipulation. They imply that in the case were votes are cast uniformly at random, a random change of preference for a random voter will yield a beneficial manipulation with non-negligible probability--at most polynomially small in @math and @math by Corollary . Thus in the setup of @cite_17 @cite_16 @cite_1 @cite_2 @cite_4 , with positive probability, a single voter with black-box access to @math can efficiently manipulate. This implies that approach of masking manipulations behind computational hardness cannot hide manipulations completely.
@cite_4 @cite_1 @cite_3 @cite_2 @cite_16 @cite_17
2055053954 1580922218 2070986136 1493942848 2950164662
Explores, for several classes of social choice rules, the distribution of the number of profiles at which a rule can be strategically manipulated. In this paper, we will do comparative social choice, looking for information about how social choice rules compare in their vulnerability to strategic misrepresentation of preferences. This paper addresses the problem of constructing voting protocols that are hard to manipulate. We describe a general technique for obtaining a new protocol by combining two or more base protocols, and study the resulting class of (vote-once) hybrid voting protocols, which also includes most previously known manipulation-resistant protocols. We show that for many choices of underlying base protocols, including some that are easily manipulable, their hybrids are NP-hard to manipulate, and demonstrate that this method can be used to produce manipulation-resistant protocols with unique combinations of useful features. The Gibbard-Satterthwaite theorem states that every non-trivial voting method among at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the Gibbard-Satterthwaite theorem: a random manipulation by a single random voter will succeed with non-negligible probability for every neutral voting method among 3 alternatives that is far from being a dictatorship. Encouraging voters to truthfully reveal their preferences in an election has long been an important issue. Recently, computational complexity has been suggested as a means of precluding strategic behavior. Previous studies have shown that some voting protocols are hard to manipulate, but used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation. Indeed, we demonstrate that NP-hard manipulations may be tractable in the average-case. For this purpose, we augment the existing theory of average-case complexity with some new concepts. In particular, we consider elections distributed with respect to junta distributions, which concentrate on hard instances. We use our techniques to prove that scoring protocols are susceptible to manipulation by coalitions, when the number of candidates is constant. 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 @math NP).