Maximal lotteries

Maximal lotteries are a probabilistic voting method and tournament solution, first proposed by the French mathematician and social scientist Germain Kreweras in 1965, ^[1] and popularized by Peter Fishburn. ^[2] The method uses ranked ballots and returns the probability distribution (or linear combination) of candidates that a majority of voters would prefer to any other.

Maximal lotteries satisfy a wide range of desirable properties, including satisfying all axioms of majority rule in the strongest sense: They elect the Condorcet winner with probability 1 ^[2] and never elect candidates outside the Smith set. ^[2] Moreover, they satisfy reinforcement, ^[3] participation, ^[4] and independence of clones, ^[3] and are weakly group-strategyproof (see below). The social welfare function that top-ranks maximal lotteries is uniquely characterized by Arrow's independence of irrelevant alternatives and Pareto efficiency. ^[5]

However, maximal lotteries do not satisfy the standard notion of strategyproofness, as shown by Gibbard's theorem. Maximal lotteries are also nonmonotonic in probabilities, i.e. it is possible for increasing the rank of a candidate to decrease their probability of winning. ^[6]

Maximal lotteries and variants thereof have been rediscovered multiple times by economists, ^[7] mathematicians, ^{[2] [8]} political scientists, philosophers, ^[9] and computer scientists. ^[10] The support of maximal lotteries, which is known as the essential set ^[11] or the bipartisan set, has been studied in detail. ^{[7] [12]}

Similar ideas appear also in the study of reinforcement learning and evolutionary biology to explain the multiplicity of co-existing species. ^{[13] [14]}

Collective preferences over lotteries

The input to this voting system consists of the agents' ordinal preferences over outcomes (not lotteries over alternatives), but a relation on the set of lotteries can be constructed in the following way: if ${\displaystyle p}$ and ${\displaystyle q}$ are lotteries over alternatives, ${\displaystyle p\succ q}$ if the expected value of the margin of victory of an outcome selected with distribution ${\displaystyle p}$ in a head-to-head vote against an outcome selected with distribution ${\displaystyle q}$ is positive. In other words, ${\displaystyle p\succ q}$ if it is more likely that a randomly selected voter will prefer the alternatives sampled from ${\displaystyle p}$ to the alternative sampled from ${\displaystyle q}$ than vice versa. ^[5] While this relation is not necessarily transitive, it does always contain at least one maximal element.

It is possible that several such maximal lotteries exist, as a result of ties. However, the maximal lottery is unique whenever there an odd number of voters express strict preferences. ^[15] By the same argument, the bipartisan set is uniquely-defined by taking the support of all maximal lotteries that solve a tournament game. ^[6]

Strategic interpretation

Maximal lotteries are equivalent to mixed maximin strategies (or Nash equilibria) of the symmetric zero-sum game given by the pairwise majority margins. As such, they have a natural interpretation in terms of electoral competition between two political parties. ^[16]

Maximal lotteries satisfy several notable strategy-resistance properties, such as eliminating the possibility that a voter can, by misreporting their preferences, obtain a lottery that stochastically dominates another. ^{[17] [18]}

Example

Suppose there are five voters who have the following preferences over three alternatives:

• 2 voters: ${\displaystyle a\succ b\succ c}$
• 2 voters: ${\displaystyle b\succ c\succ a}$
• 1 voter: ${\displaystyle c\succ a\succ b}$

The pairwise preferences of the voters can be represented in the following skew-symmetric matrix, where the entry for row ${\displaystyle x}$ and column ${\displaystyle y}$ denotes the number of voters who prefer ${\displaystyle x}$ to ${\displaystyle y}$ minus the number of voters who prefer ${\displaystyle y}$ to ${\displaystyle x}$.

${\displaystyle {\begin{matrix}{\begin{matrix}&&a\quad &b\quad &c\quad \\\end{matrix}}\\{\begin{matrix}a\\b\\c\\\end{matrix}}{\begin{pmatrix}0&1&-1\\-1&0&3\\1&-3&0\\\end{pmatrix}}\end{matrix}}}$

This matrix can be interpreted as a zero-sum game and admits a unique Nash equilibrium (or minimax strategy) ${\displaystyle p}$ where ${\displaystyle p(a)=3/5}$, ${\displaystyle p(b)=1/5}$, ${\displaystyle p(c)=1/5}$. By definition, this is also the unique maximal lottery of the preference profile above. The example was carefully chosen not to have a Condorcet winner. Many preference profiles admit a Condorcet winner, in which case the unique maximal lottery will assign probability 1 to the Condorcet winner.

References

1. G. Kreweras. Aggregation of preference orderings. In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962), pages 73–79, 1965.
2. P. C. Fishburn. Probabilistic social choice based on simple voting comparisons. Review of Economic Studies, 51(4):683–692, 1984.
3. F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Econometrica. 84(5), pages 1839-1880, 2016.
4. F. Brandl, F. Brandt, and J. Hofbauer. Welfare Maximization Entices Participation. Games and Economic Behavior. 14, pages 308-314, 2019.
5. F. Brandl and F. Brandt. Arrovian Aggregation of Convex Preferences. Econometrica. 88(2), pages 799-844, 2020.
6. Laslier, J.-F. Tournament solutions and majority voting Springer-Verlag, 1997.
7. G. Laffond, J.-F. Laslier, and M. Le Breton. The bipartisan set of a tournament game. Games and Economic Behavior, 5(1):182–201, 1993.
8. D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217–236, 1995.
9. D. S. Felsenthal and M. Machover. After two centuries should Condorcet’s voting procedure be implemented? Behavioral Science, 37(4):250–274, 1992.
10. R. L. Rivest and E. Shen. An optimal single-winner preferential voting system based on game theory. In Proceedings of 3rd International Workshop on Computational Social Choice, pages 399–410, 2010.
11. B. Dutta and J.-F. Laslier. Comparison functions and choice correspondences. Social Choice and Welfare, 16: 513–532, 1999.
12. F. Brandt, M. Brill, H. G. Seedig, and W. Suksompong. On the structure of stable tournament solutions. Economic Theory, 65(2):483–507, 2018.
13. B. Laslier and J.-F. Laslier. Reinforcement learning from comparisons: Three alternatives are enough, two are not Annals of Applied Probability 27(5): 2907–2925, 2017.
14. Jacopo Grilli, György Barabás, Matthew J. Michalska-Smith and Stefano Allesina. Higher-order interactions stabilize dynamics in competitive network models Nature 548: 210-214, 2017.
15. Gilbert Laffond, Jean-François Laslier and Michel Le Breton A theorem on two–player symmetric zero–sum games Journal of Economic Theory 72: 426–431, 1997.
16. Laslier, J.-F. Interpretation of electoral mixed strategies Social Choice and Welfare 17: pages 283–292, 2000.
17. H. Aziz, F. Brandt, and M Brill. On the Tradeoff between Economic Efficiency and Strategyproofness. Games and Economic Behavior. 110, pages 1-18, 2018.
18. Brandl, Florian; Brandt, Felix; Stricker, Christian (2022-01-01). "An analytical and experimental comparison of maximal lottery schemes". Social Choice and Welfare. 58 (1): 5–38. doi:10.1007/s00355-021-01326-x. hdl: 10419/286729 . ISSN   1432-217X.

External links

• voting.ml (website for computing maximal lotteries)
• Pnyx - Practical Preference Aggregation (voting tool that, among other methods, offers maximal lotteries)