An analytical and experimental comparison of maximal lottery schemes

Randomized voting rules are gaining increasing attention in computational and non-computational social choice. A particularly interesting class of such rules are maximal lottery (ML) schemes, which were proposed by Peter Fishburn in 1984 and have been repeatedly recommended for practical use. However, the subtle differences between different ML schemes are often ignored. Two canonical subsets of ML schemes are C1 -ML schemes (which only depend on unweighted majority comparisons) and C2 -ML schemes (which only depend on weighted majority comparisons). We prove that C2 -ML schemes are the only Pareto efficient-but also among the most manipulable-ML schemes. Furthermore, we evaluate the frequency of manipulable preference profiles and the degree of randomization of ML schemes via extensive computer simulations. In general, ML schemes are rarely manipulable and often do not randomize at all, especially when there are only few alternatives. For up to 21 alternatives, the average support size of ML schemes lies below 4 under reasonable assumptions. The average degree of randomization (in terms of Shannon entropy) of C2 -ML schemes is significantly lower than that of C1 -ML schemes.