We study the phase transition of the coalitional manipulation problem for generalized scoring rules. Previously it has been shown that, under some conditions on the distribution of votes, if the number of manipulators is @math , where @math is the number of voters, then the probability that a random profile is manipulable by the coalition goes to zero as the number of voters goes to infinity, whereas if the number of manipulators is @math , then the probability that a random profile is manipulable goes to one. Here we consider the critical window, where a coalition has size @math , and we show that as @math goes from zero to infinity, the limiting probability that a random profile is manipulable goes from zero to one in a smooth fashion, i.e., there is a smooth phase transition between the two regimes. This result analytically validates recent empirical results, and suggests that deciding the coalitional manipulation problem may be of limited computational hardness in practice.
A recent line of research with an average-case algorithmic flavor also suggests that manipulation is indeed typically easy; see, e.g., the work of Kelly @cite_30 , Conitzer and Sandholm @cite_2 , Procaccia and Rosenschein @cite_25 , and @cite_26 for results on certain restricted classes of SCFs. A different approach, initiated by Friedgut, Kalai, Keller and Nisan @cite_23 @cite_36 , who studied the fraction of ranking profiles that are manipulable, also suggests that manipulation is easy on average; see further Xia and Conitzer @cite_16 , Dobzinski and Procaccia @cite_0 , Isaksson, Kindler and Mossel @cite_14 , and Mossel and R 'acz @cite_33 . We refer to the survey by Faliszewski and Procaccia @cite_12 for a detailed history of the surrounding literature. See also related literature in economics, e.g., @cite_34 @cite_6 @cite_4 .
@cite_30 @cite_26 @cite_14 @cite_33 @cite_4 @cite_36 @cite_34 @cite_6 @cite_0 @cite_23 @cite_2 @cite_16 @cite_25 @cite_12
2055053954 2060522636 2177286302 2144211415 2151939563 2006063189 1975543368 1859798081 2070986136 1566914083 1493942848 2171945484
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. We investigate the problem of coalitional manipulation in elections, which is known to be hard in a variety of voting rules. We put forward efficient algorithms for the problem in Borda, Maximin and Plurality with Runoff, and analyze their windows of error. Specifically, given an instance on which an algorithm fails, we bound the additional power the manipulators need in order to succeed. We finally discuss the implications of our results with respect to the popular approach of employing computational hardness to preclude manipulation. 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 q ≥ 4 alternatives and n voters will be manipulable with probability at least 10−4∈2 n −3 q −30, where ∈ is the minimal statistical distance between f and the family of dictator functions. Our results extend those of [11], which were obtained for the case of 3 alternatives, and imply that the approach of masking manipulations behind computational hardness (as considered in [4,6,9,15,7]) 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. Recently, quantitative versions of the Gibbard-Satterthwaite theorem were proven for k=3 alternatives by Friedgut, Kalai, Keller and Nisan and for neutral functions on k ≥ 4 alternatives by Isaksson, Kindler and Mossel. In the present paper we prove a quantitative version of the Gibbard-Satterthwaite theorem for general social choice functions for any number k ≥ 3 of alternatives. In particular we show that for a social choice function f on k ≥ 3 alternatives and n voters, which is e-far from the family of nonmanipulable functions, a uniformly chosen voter profile is manipulable with probability at least inverse polynomial in n, k, and e-1. Removing the neutrality assumption of previous theorems is important for multiple reasons. For one, it is known that there is a conflict between anonymity and neutrality, and since most common voting rules are anonymous, they cannot always be neutral. Second, virtual elections are used in many applications in artificial intelligence, where there are often restrictions on the outcome of the election, and so neutrality is not a natural assumption in these situations. Ours is a unified proof which in particular covers all previous cases established before. The proof crucially uses reverse hypercontractivity in addition to several ideas from the two previous proofs. Much of the work is devoted to understanding functions of a single voter, and in particular we also prove a quantitative Gibbard-Satterthwaite theorem for one voter. Many analyses of plurality-rule elections predict the complete coordination of strategic voting, and hence support for only two candidates. Here I suggest that stable multi-candidate support will arise in equilibrium. A group of voters must partially coordinate behind one of two challenging candidates in order to dislodge a disliked incumbent. In a departure from existing models, the popular support for each challenger is uncertain. This support must be inferred from the private observation of informative signals, such as the social communication of preferences throughout the electorate, or the imperfect observation of opinion polls. The uniquely stable voting equilibrium entails only limited strategic voting and hence incomplete coordination. This is due to the surprising presence of negative feedback: an increase in the degree of strategic voting by others reduces the incentives for an individual to vote strategically. The incentive to vote strategically is lower in relatively marginal elections, after controlling for the distance from contention of a trailing preferred challenger. A calibration of the model applied to the UK General Election of 1997 is consistent with the impact of strategic voting and the reported accuracy of voters understanding of the electoral situation. It suggests that nearly 50 seats may have been lost by the Conservative party due to strategic voting. The Gibbard-Satterthwaite theorem states that every nondictatorial election rule among at least three 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 a nonnegligible probability for any election rule among three alternatives that is far from being a dictatorship and from having only two alternatives in its range. The recent result of Friedgut, Kalai and Nisan [9] gives a quantitative version of the Gibbard-Satterthwaite Theorem regarding manipulation in elections, but holds only for neutral social choice functions and three alternatives. We complement their theorem by proving a similar result regarding Pareto-Optimal social choice functions when the number of voters is two. We discuss the implications of our results with respect to the agenda of precluding manipulation in elections by means of computational hardness. 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. 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 NP-hard, #P-hard, or even PSPACE-hard. Thus, under these rules, it is unlikely that a computationally efficient algorithm can be constructed that always finds a beneficial manipulation (when it exists). However, this still does not preclude the existence of an efficient algorithm that often finds a successful manipulation (when it exists). There have been attempts to design a rule under which finding a beneficial manipulation is 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. 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. We provide an overview of more than two decades of work, mostly in AI, that studies computational complexity as a barrier against manipulation in elections.