Jump to content

Maximal lotteries

From Wikipedia, the free encyclopedia
(Redirected from Maximal lottery)

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 relative to that of does not decrease when is improved over .[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

[edit]

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

[edit]

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 and are lotteries over alternatives, if the expected value of the margin of victory of an outcome selected with distribution in a head-to-head vote against an outcome selected with distribution is positive. In other words, if it is more likely that a randomly selected voter will prefer the alternatives sampled from to the alternative sampled from 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

[edit]

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

[edit]

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

  • 2 voters:
  • 2 voters:
  • 1 voter:

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

This matrix can be interpreted as a zero-sum game and admits a unique Nash equilibrium (or minimax strategy) where , , . 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 and in his preference relation, becomes the Condorcet winner and will be selected with probability 1.

References

[edit]
  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.
  2. ^ a b c F. Brandl, F. Brandt, and H. G. Seedig. Consistent probabilistic social choice. Econometrica. 84(5), pages 1839-1880, 2016.
  3. ^ F. Brandl, F. Brandt, and J. Hofbauer. Welfare Maximization Entices Participation. Games and Economic Behavior. 14, pages 308-314, 2019.
  4. ^ a b 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.
  7. ^ B. Dutta and J.-F. Laslier. Comparison functions and choice correspondences. Social Choice and Welfare, 16: 513–532, 1999.
  8. ^ 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.
  9. ^ Laslier, J.-F. Tournament solutions and majority voting Springer-Verlag, 1997.
  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.
  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.
  12. ^ D. C. Fisher and J. Ryan. Tournament games and positive tournaments. Journal of Graph Theory, 19(2):217–236, 1995.
  13. ^ D. S. Felsenthal and M. Machover. After two centuries should Condorcet’s voting procedure be implemented? Behavioral Science, 37(4):250–274, 1992.
  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.
  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.
  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.
  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.
  19. ^ Laslier, J.-F. Interpretation of electoral mixed strategies. Social Choice and Welfare 17: pages 283–292, 2000.
[edit]
  • voting.ml (website for computing maximal lotteries)