Maximal lotteries

Maximal lotteries refers to a probabilistic voting rule. The method uses preferential ballots and returns a probability distribution (or linear combination) of candidates that a majority of voters would weakly prefer to any other.^[1]

Maximal lotteries satisfy a wide range of desirable properties: they elect the Condorcet winner with probability 1 if it exists^[1] and never elect candidates outside the Smith set.^[1] Moreover, they satisfy reinforcement,^[2] participation,^[3] and independence of clones.^[2] The probabilistic voting rule that returns all maximal lotteries is the only rule satisfying reinforcement, Condorcet-consistency, and independence of clones.^[2] The social welfare function that top-ranks maximal lotteries has been uniquely characterized using Arrow's independence of irrelevant alternatives and Pareto efficiency.^[4]

Maximal lotteries do not satisfy the standard notion of strategyproofness, as Allan Gibbard has shown that only random dictatorships can satisfy strategyproofness and ex post efficiency.^[5] Maximal lotteries are also nonmonotonic in probabilities, i.e. it is possible that the probability of an alternative decreases when a voter ranks this alternative up.^[1] However, they satisfy relative monotonicity, i.e., the probability of $x$ relative to that of $y$ does not decrease when $x$ is improved over $y$ .^[6]

The support of maximal lotteries, which is known as the essential set or the bipartisan set, has been studied in detail.^[7]^[8]^[9]^[10]

History

Maximal lotteries were first proposed by the French mathematician and social scientist Germain Kreweras in 1965^[11] and popularized by Peter Fishburn.^[1] Since then, they have been rediscovered multiple times by economists,^[8] mathematicians,^[1]^[12] political scientists, philosophers,^[13] and computer scientists.^[14]

Several natural dynamics that converge to maximal lotteries have been observed in biology, physics, chemistry, and machine learning.^[15]^[16]^[17]

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 $p$ and $q$ are lotteries over alternatives, $p\succ q$ if the expected value of the margin of victory of an outcome selected with distribution $p$ in a head-to-head vote against an outcome selected with distribution $q$ is positive. In other words, $p\succ q$ if it is more likely that a randomly selected voter will prefer the alternatives sampled from $p$ to the alternative sampled from $q$ than vice versa.^[4] While this relation is not necessarily transitive, it does always admit 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 the number of voters is odd.^[18] By the same argument, the bipartisan set is uniquely-defined by taking the support of the unique maximal lottery that solves a tournament game.^[8]

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^[19] and be computer in polynomial-time via [linear programming].

Example

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

2 voters: $a\succ b\succ c$
2 voters: $b\succ c\succ a$
1 voter: $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 $x$ and column $y$ denotes the number of voters who prefer $x$ to $y$ minus the number of voters who prefer $y$ to $x$ .

${\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) $p$ where $p(a)=3/5$ , $p(b)=1/5$ , $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. If the last voter in the example above swaps alternatives $a$ and $c$ in his preference relation, $a$ becomes the Condorcet winner and will be selected with probability 1.

References

^ ^a ^b ^c ^d ^e ^f P. C. Fishburn. Probabilistic social choice based on simple voting comparisons. Review of Economic Studies, 51(4):683–692, 1984.
^ ^a ^b ^c F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Econometrica. 84(5), pages 1839-1880, 2016.
^ F. Brandl, F. Brandt, and J. Hofbauer. Welfare Maximization Entices Participation. Games and Economic Behavior. 14, pages 308-314, 2019.
^ ^a ^b F. Brandl and F. Brandt. Arrovian Aggregation of Convex Preferences. Econometrica. 88(2), pages 799-844, 2020.
^ Gibbard, Allan (1977). "Manipulation of Schemes that Mix Voting with Chance". Econometrica. 45 (3): 665–681. doi:10.2307/1911681. hdl:10419/220534. ISSN 0012-9682. JSTOR 1911681.
^ 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.
^ B. Dutta and J.-F. Laslier. Comparison functions and choice correspondences. Social Choice and Welfare, 16: 513–532, 1999.
^ ^a ^b ^c 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.
^ Laslier, J.-F. Tournament solutions and majority voting Springer-Verlag, 1997.
^ F. Brandt, M. Brill, H. G. Seedig, and W. Suksompong. On the structure of stable tournament solutions. Economic Theory, 65(2):483–507, 2018.
^ 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.
^ D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217–236, 1995.
^ D. S. Felsenthal and M. Machover. After two centuries should Condorcet’s voting procedure be implemented? Behavioral Science, 37(4):250–274, 1992.
^ 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.
^ 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.
^ 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.
^ F. Brandl and F. Brandt. A Natural Adaptive Process for Collective Decision-Making. Theoretical Economics 19(2): 667–703, 2024.
^ 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.
^ Laslier, J.-F. Interpretation of electoral mixed strategies. Social Choice and Welfare 17: pages 283–292, 2000.

External links

voting.ml (website for computing maximal lotteries)

[Fish84a-1] ^ ^a ^b ^c ^d ^e ^f P. C. Fishburn. Probabilistic social choice based on simple voting comparisons. Review of Economic Studies, 51(4):683–692, 1984.

[Bran13a-2] F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Econometrica. 84(5), pages 1839-1880, 2016.

[Bran15a-3] F. Brandl, F. Brandt, and J. Hofbauer. Welfare Maximization Entices Participation. Games and Economic Behavior. 14, pages 308-314, 2019.

[BrBr19a-4] F. Brandl and F. Brandt. Arrovian Aggregation of Convex Preferences. Econometrica. 88(2), pages 799-844, 2020.

[5] Gibbard, Allan (1977). "Manipulation of Schemes that Mix Voting with Chance". Econometrica. 45 (3): 665–681. doi:10.2307/1911681. hdl:10419/220534. ISSN 0012-9682. JSTOR 1911681.

[6] 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.

[DL99-7] B. Dutta and J.-F. Laslier. Comparison functions and choice correspondences. Social Choice and Welfare, 16: 513–532, 1999.

[LLL93b-8] 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.

[Laslier97-9] Laslier, J.-F. Tournament solutions and majority voting Springer-Verlag, 1997.

[BBHS18-10] F. Brandt, M. Brill, H. G. Seedig, and W. Suksompong. On the structure of stable tournament solutions. Economic Theory, 65(2):483–507, 2018.

[Krew65a-11] 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.

[FiRy95a-12] D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217–236, 1995.

[FeMa92a-13] D. S. Felsenthal and M. Machover. After two centuries should Condorcet’s voting procedure be implemented? Behavioral Science, 37(4):250–274, 1992.

[RiSh10a-14] 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.

[LL17-15] 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.

[Grillil17-16] 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.

[BrBr21a-17] F. Brandl and F. Brandt. A Natural Adaptive Process for Collective Decision-Making. Theoretical Economics 19(2): 667–703, 2024.

[18] 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.

[Laslier2000-19] Laslier, J.-F. Interpretation of electoral mixed strategies. Social Choice and Welfare 17: pages 283–292, 2000.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]