An Analytical and Experimental Comparison of Maximal Lottery Schemes

F. Brandl, F. Brandt, C. Stricker
IJCAI 2018
Abstract
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.

Remarks: Has a journal version: Florian Brandl, Felix Brandt, Christian Stricker: An analytical and experimental comparison of maximal lottery schemes. Soc. Choice Welf. 58(1): 5-38 (2022)

Experiments:

Election type Culture Candidates Voters Instances Parameters
Ordinal Impartial Anonymous Culture {3, 5, 11, 21} {3, 5, 11, 21, 51, 151, 501} 100000 None
Ordinal Impartial Anonymous Culture {3, 4, 5, 6} [3-29] 2000 None