An analytical and experimental comparison of maximal lottery schemes

Maximal lottery (ML) schemes constitute an interesting class of randomized voting rules that 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 overlooked. Two canonical subsets of ML schemes are [InlineMediaObject not available: see fulltext.] schemes (which only depend on unweighted majority comparisons) and [InlineMediaObject not available: see fulltext.] schemes (which only depend on weighted majority comparisons). We prove that [InlineMediaObject not available: see fulltext.] schemes are the only homogeneous ML schemes that satisfy SD-efficiency and SD-participation, but are also among the most manipulable ML schemes. While all ML schemes are manipulable and even violate monotonicity, they are never manipulable when a Condorcet winner exists and satisfy a relative notion of monotonicity. We also evaluate the frequency of manipulable preference profiles and the degree of randomization of ML schemes via extensive computer simulations. In summary, ML schemes are rarely manipulable and often do not randomize at all, especially for few alternatives. The average degree of randomization of [InlineMediaObject not available: see fulltext.] schemes is consistently lower than that of [InlineMediaObject not available: see fulltext.] schemes.