Stable Manipulation in Voting

Voting has served as a fundamental tool for aggregating preferences of a set of people over a set of alternatives from centuries. A typical voting system consists of a set of alternatives, a set of voters each having a linear order over the set of alternatives as her preference, and a voting rule which selects a set of alternatives as winners depending on the voters' preferences. However, classical results show that every reasonable voting system with at least 3 alternatives can suffer from manipulation [Gib73, Sat75] -- an agent may be able to make her more favored alternative win by misreporting her preference. Bartholdi et al. pioneered the idea of using computational intractability as a barrier to safe guard elections against manipulation [BTT89, BO91]. Indeed, if we have m alternatives and even if the manipulator exactly knows the preferences of all other voters, na ıvely going over all ( m! 1) possible preferences and report the one which results in best outcome for the manipulator is not feasible for any computationally bounded manipulator . Although the idea of Bartholdi et al. was to use computational intractability as a barrier against manipulation, the computational problem of manipulation turns out to be polynomial time solvable for most of the commonly used voting rules such as the scoring rules, maximin, Copeland, etc. with prominent exception being the single transferable (STV) voting rule. Even for voting rules (STV for example) for which the computational barrier exists against manipulation, it seems that the barrier, in reality, may be substantially weak due to existence of heuristics which work well in practice [FP10, FKKN11, MR15, and references there in]. Motivation: The computational problem of manipulation has mostly been studied in what is called the complete information setting -- the manipulator exactly knows the preferences of all other voters.