Maximal lotteries

Maximal lotteries refers to a probabilistic voting system first considered by Germain Kreweras^[1] in 1965. The method uses preferential ballots and returns so-called maximal lotteries, i.e., probability distributions over the alternatives that are weakly preferred to any other probability distribution. Maximal lotteries satisfy the Condorcet criterion,^[2] the Smith criterion,^[2] reversal symmetry, polynomial runtime, and probabilistic versions of reinforcement,^[3] participation,^[4] and independence of clones.^[3]

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 can be computed using linear programming. In 2015, maximal lotteries were axiomatically characterized by showing that only maximal lotteries satisfy probabilisitic versions of population-consistency (a weakening of reinforcement), agenda-consistency, and composition-consistency (a strengthening of independence of clones).^[3] It was also shown that maximal lotteries satisfy a strong notion of Pareto efficiency and a weak notion of strategyproofness.^[5] In contrast to random dictatorship, maximal lotteries do not satisfy the standard notion of strategyproofness. Also, maximal lotteries are not monotonic in probabilities, i.e., it is possible that the probability of an alternative decreases when this alternative is ranked up. However, the probability of the alternative will remain positive.

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

Preferences over lotteries

The input to this solution concept consists of the agents' ordinal preferences over outcomes (not lotteries over outcomes), but a relation on the set of lotteries is constructed in the following way: if $p$ and $q$ are different lotteries over outcomes, $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. While this relation is not necessarily transitive, it does always contain at least one maximal element.

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 table or 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. Most realistic preference profiles admit a Condorcet winner, in which case the unique maximal lottery will assign probability 1 to the Condorcet winner.

References

^ 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.
^ ^a ^b ^c 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. Working paper. 2015.
^ H. Aziz, F. Brandt, and M Brill. On the Tradeoff between Economic Efficiency and Strategyproofness in Randomized Social Choice. In Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 455–462. 2013.
^ ^a ^b 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.
^ 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.

External links

Pnyx - Practical Preference Aggregation (voting website that, among other methods, offers maximal lotteries)

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

[Fish84a-2] P. C. Fishburn. Probabilistic social choice based on simple voting comparisons. Review of Economic Studies, 51(4):683–692, 1984.

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

[Bran15a-4] F. Brandl, F. Brandt, and J. Hofbauer. Welfare Maximization Entices Participation. Working paper. 2015.

[ABB13a-5] H. Aziz, F. Brandt, and M Brill. On the Tradeoff between Economic Efficiency and Strategyproofness in Randomized Social Choice. In Proceedings of the 12th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 455–462. 2013.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]