Breadth of loss due to manipulation (Q2447147)

This paper investigates the maximal number of people who are harmed when a social choice rule is manipulated by one person. Let \(g\) be a social choice rule. A manipulation by individual \(i\) from profile \(u\) to \(u^*\) causes a \textbf{loss} for \(k\) individuals if there are \(k\) individuals \(j\), \(j \neq i\), with \(g(u)\) ranked higher than \(g(u^*)\) in the individual preference ranking \(u(j)\) of \(j\). The \textbf{breadth of loss}, \(Br(g)\), of \(g\) is the maximum value of \(k\) such that some manipulation of \(g\) causes a loss for \(k\) individuals. The authors establish lower bounds of \(Br(g)\) for choice rules \(g\) satisfying certain properties and compute \(Br(g)\) for some specific rules. Let \(m\) be the number of alternatives and \(n\) the number of individuals. Given \(m \geq 3\), \(n \geq 3\), then for every \(k\) with \(1 \leq k \leq n - 1\) there exists a neutral social choice rule \(g\) with \(Br(g) = k\) and there exists an anonymous social choice rule \(g\) with \(Br(g) = k\). For \(g\) the Borda rule with alphabetic tie-break, \(Br(g) \geq n - [n/m]\). If \(n \geq 3\) is odd and rule \(g\) satisfies both the Pareto and Condorcet conditions, then \(Br(g) \geq (n - 1)/2\). And if \(n \geq 4\) is even and \(g\) satisfies both the Pareto and strong Condorcet conditions, then \(Br(g) \geq n/2\). Let \(g(u)\) be the Condorcet winner if there exists one and \(g(u)\) is the alphabetically earliest Borda winner, otherwise. Then for odd \(n\) and for \(m\) large relative to \(n\), \(Br(g) = n - 1\). Maximal numbers are also calculated for other scoring rules, for which the selection depends only on which individuals have which alternatives ranked at the top, for rules that satisfy the Pareto criterion, but not the Condorcet criterion, and for rules that satisfy the Condorcet criterion, but not the Pareto criterion.