Indices of manipulabilty

Nitzan-Kelly Index (NK-index)

The Nitzan-Kelly index (NK-index) was introduced in (Nitzan, 1985) and ( Kelly, 1993). It shows the degree of manipulability of a social choice rule. NK-index stands for the share of manipulable profiles: \[NK=\frac{number\ of\ manipulable\ profiles}{total\ number\ of\ profiles}\]

Freedom of Manipulation (\(I_1\))

A class of the Freedom of manipulation indices (\(I_1\)) was introduced in (Aleskerov, Kurbanov, 1999). These indices show the shares of all possible manipulation attempts which lead to making the outcome of the social choice better, equal or worse, respectively. For each profile all possible manipulation attempts, i.e., all possible ways of misrepresenting preferences, are generated.

Assuming that there are p possible attempts to manipulate, we can classify them as

1. Successful attempts \(p^+\): the result after such an attempt is better for the manipulating voter or coalition
2. Unsuccessful attempts which lead to the same choice \(p^0\): the result after such an attempt is the same as without this manipulation attempt
3. Unsuccessful attempts which worsen the choice \(p^-\): the result after such an attempt is worse than without this manipulation attempt
4. Unsuccessful attempts which lead to an incomparable result \(p^?\): it is impossible for the manipulating agent or coalition to determine what result is better, with or without such a misrepresentation of preferences. \(p^?=0\) for the cases with full extended preferences (strong manipulation), i.e., when all possible voting results may be compared.

By definition we have \({p=p}^++p^0+p^-+p^?\)

Then, we define \(I_1\) indices as the share of attempts which make the outcome better, same or worse, i.e., \[I_1^+=\frac{p^+}{p};\ I_1^0=\frac{p^0}{p};\ I_1^-=\frac{p^-}{p};\ I_1^?=\frac{p^?}{p}\] It can be noticed that \[I_1^++I_1^0+I_1^-+I_1^?=1\]

Efficiency of Manipulation (\(I_2\) and \(I_3\))

Efficiency of manipulation indices (\(I_2\) and \(I_3\)) were introduced in (Aleskerov, Kurbanov, 1999). They stand for average and maximum gains for an agent or a coalition as a result of manipulation.

Index \(I_2\) measures average gain of manipulability. For all successful manipulation attempts (\(p^+\)) we calculate the benefit of manipulation (\(g_i\)) in terms of the number of places in agent’s extended preferences. For example, if we use Leximin rule of constructing extended preferences, i.e., EP is: \(\left\{a\right\}\succ\left\{a,b\right\}\succ{b}\succ{a,c}\succ{a,b,c}\succ\left\{b,c\right\}\succ\left\{c\right\}\), and if before manipulation the choice is \({c}\), and after manipulation it becomes \({a,\ c}\), then \(g_i=3\) (the new choice is 3 places better). Thus, \(I_2\) is equal to the average gain in all successful manipulation attempts. \[I_2=\frac{\sum g_i}{p^+}\] Since an extended preference is a linear order over all possible \(2^m-1\) choices (non-empty subsets of the set of alternatives), thus, \(I_2\) may vary from 1 (a successful manipulation attempt gives only a 1-place better choice) to \(2^m-2\) (a successful manipulation attempt drastically changes the outcome from the worst alternative to the best).

Index \(I_3\) measures maximum gain of manipulability. For a given profile we calculate the largest gain (\({maxgain}_i\)) which can be obtained by any agent or any coalition in this profile. \(I_3\) will be equal to average of maximum gains for every profile \[I_3=\frac{\sum{maxgain}_i}{total\ number\ of\ profiles}\] Index \(I_3\) also varies from 1 to \(2^m-2\).

Average Loss (\(I_4\))

Average Loss index (\(I_4\)) stands for the average loss in unsuccessful manipulation attempt.

For all unsuccessful manipulation attempts (\(p^-\)) which lead to worsening the social choice for the manipulating agent or coalition, we calculate the benefit of manipulation (\(g_i\)) in terms of the number of places in agent’s extended preferences. For the case of worsening the social choice \(g_i\) < 0. Then, we calculate the average loss. Thus, the index will be equal to \[I_4=\frac{-\sum g_i}{p^-}\]

Expected Outcome

Expected Outcome Index (EO) stands for the math expectation of the change of the result if a manipulation attempt is made.

Let us assume that there are p possible manipulation attempts, i.e., all possible ways of misrepresenting preferences by an agent or by a coalition. Then, each manipulation attempt leads to a new social choice, and there is a certain change \(g_i\) in the result. We measure this change g_i as the number of places in the agent’s extended preferences between the new social choice and the initial (with sincere preferences) social choice. If the social choice after a manipulation attempt becomes better than it was without manipulation, \(g_i\)>0. If it becomes worse, \(g_i\)<0. If it remains the same or becomes incomparable, \(g_i=0\).

Expected Outcome (EO) index stands for the math expectation of the change in the social choice in all manipulation attempts, i.e., \[EO=\frac{\sum g_i}{p}\]

In most cases EO<0, meaning that preference’s misrepresentation more often leads to worsening the social choice for the manipulating agent or coalition.

EO-index may be also calculated using indices \(I_1\), \(I_2\) and \(I_4\): \[EO=I_1^+\ast I_2-I_1^-\ast I_4\]

Decisiveness and Resoluteness

These indices were described in (Aleskerov et. al., 2009).

Decisiveness (D) shows how often a social choice rule returns a single-valued choice. \[D=\frac{number\ of\ profiles\ with\ single\ winner}{total\ number\ of\ profiles}\] D-index varies from 0 to 1, higher values of D-index stand for a procedure which more often returns a single winner, while lower values of D-index mean that a procedure often returns multi-valued choice with ties between two or more alternatives.

Resoluteness (R) stands for the average number of alternatives which constitute social choice. Let \(c_1\) be the number of profiles where the social choice consists of 1 alternative (single winner), \(c_2\) – the number of profiles where the social choice is a tie between 2 alternatives, … \(c_m\) – the number of profiles where the social choice is a tie between m alternatives. In this case, R-index will be equal to \[R=\ \frac{c_1\ast1+c_2\ast2+\ldots+\ c_m\ast m}{total\ number\ of\ profiles}\] R-index varies from 1 to m. R=1 means that the social choice rule always returns a single winner. R=m means that the result of the social choice rule is always a tie between all alternatives making it practically useless.

References

1. Nitzan S. The vulnerability of point-voting schemes to preference variation and strategic manipulation // Public Choice. 1985. Vol. 47. P. 349–370.
2. Kelly J. Almost all social choice rules are highly manipulable, but few aren't // Social Choice and Welfare. 1993. Vol. 10. Р. 161–175.
3. Aleskerov F., Kurbanov E. Degree of manipulability of social choice procedures // Alkan А. et al. (eds.) Current Trends in Economics. Studies in Economic Theory. Berlin Heidelberg, N.Y.: Springer, 1999. Vol.8. P.13-27.
4. Aleskerov, Fuad & Karabekyan, Daniel & Sanver, M. Remzi & Yakuba, Vyacheslav. (2009). Evaluating the Degree of Manipulability of Certain Aggregation Procedures under Multiple Choices. Journal of the New Economic Association. 37-61.

---