Maximal lotteries are a
probabilistic voting rule that use
ranked ballots and returns a
lottery
A lottery (or lotto) is a form of gambling that involves the drawing of numbers at random for a prize. Some governments outlaw lotteries, while others endorse it to the extent of organizing a national or state lottery. It is common to find som ...
over candidates that a majority of voters will prefer, on average, to any other.
[P. C. Fishburn. ''Probabilistic social choice based on simple voting comparisons''. Review of Economic Studies, 51(4):683–692, 1984.] In other words, in a series of repeated head-to-head matchups, voters will (on average) prefer the results of a maximal lottery to the results produced by any other
voting rule.
Maximal lotteries satisfy a wide range of desirable properties: they elect the
Condorcet winner with probability 1 if it exists
and never elect candidates outside the
Smith set.
Moreover, they satisfy
reinforcement
In Behaviorism, behavioral psychology, reinforcement refers to consequences that increase the likelihood of an organism's future behavior, typically in the presence of a particular ''Antecedent (behavioral psychology), antecedent stimulus''. Fo ...
,
[F. Brandl, F. Brandt, and H. G. Seedig]
Consistent probabilistic social choice
Econometrica. 84(5), pages 1839-1880, 2016. participation,
[F. Brandl, F. Brandt, and J. Hofbauer]
Welfare Maximization Entices Participation
Games and Economic Behavior. 14, pages 308-314, 2019. and
independence of clones.
The probabilistic voting rule that returns all maximal lotteries is the only rule satisfying reinforcement, Condorcet-consistency, and independence of clones.
The
social welfare function
In welfare economics and social choice theory, a social welfare function—also called a social ordering, ranking, utility, or choice function—is a function that ranks a set of social states by their desirability. Each person's preferences ...
that top-ranks maximal lotteries has been uniquely characterized using Arrow's
independence of irrelevant alternatives
Independence of irrelevant alternatives (IIA) is an axiom of decision theory which codifies the intuition that a choice between A and B (which are both related) should not depend on the quality of a third, unrelated outcome C. There are several dif ...
and
Pareto efficiency
In welfare economics, a Pareto improvement formalizes the idea of an outcome being "better in every possible way". A change is called a Pareto improvement if it leaves at least one person in society better off without leaving anyone else worse ...
.
[F. Brandl and F. Brandt]
Arrovian Aggregation of Convex Preferences
Econometrica. 88(2), pages 799-844, 2020.
Maximal lotteries do not satisfy the standard notion of strategyproofness, as
Allan Gibbard
Allan Fletcher Gibbard (born 1942) is an American philosopher who is the Richard B. Brandt Distinguished University Professor of Philosophy Emeritus at the University of Michigan, Ann Arbor. Gibbard has made major contributions to contemporary e ...
has shown that only
random dictatorships can satisfy strategyproofness and ex post efficiency. 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.
However, they satisfy relative monotonicity, i.e., the probability of
relative to that of
does not decrease when
is improved over
.
The
support of maximal lotteries, which is known as the ''essential set'' or the ', has been studied in detail.
[B. Dutta and J.-F. Laslier. ''Comparison functions and choice correspondences''. Social Choice and Welfare, 16: 513–532, 1999.][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.]
History
Maximal lotteries were first proposed by the French mathematician and social scientist Germain Kreweras in 1965
[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.] and popularized by
Peter Fishburn.
Since then, they have been rediscovered multiple times by economists,
mathematicians,
[D. C. Fisher and J. Ryan. ''Tournament games and positive tournaments''. Journal of Graph Theory, 19(2):217–236, 1995.] political scientists, philosophers,
[D. S. Felsenthal and M. Machover. ''After two centuries should Condorcet’s voting procedure be implemented?'' Behavioral Science, 37(4):250–274, 1992.] and computer scientists.
[ 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.]
Several natural dynamics that converge to maximal lotteries have been observed in biology, physics, chemistry, and machine learning.
[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.
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
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.
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. By the same argument, the bipartisan set is uniquely-defined by taking the support of the unique maximal lottery that solves a tournament game.
Strategic interpretation
Maximal lotteries are equivalent to mixed
maximin strategies (or
Nash equilibria
In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
) of the symmetric
zero-sum game
Zero-sum game is a Mathematical model, mathematical representation in game theory and economic theory of a situation that involves two competition, competing entities, where the result is an advantage for one side and an equivalent loss for the o ...
given by the pairwise majority margins. As such, they have a natural interpretation in terms of electoral competition between two political parties
[ Laslier, J.-F. ''Interpretation of electoral mixed strategies''. Social Choice and Welfare 17: pages 283–292, 2000.] and can be computed in polynomial time via linear programming.
Example
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
In mathematics, particularly in linear algebra, a skew-symmetric (or antisymmetric or antimetric) matrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition
In terms of the entries of the matrix, if a ...
, 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
Zero-sum game is a Mathematical model, mathematical representation in game theory and economic theory of a situation that involves two competition, competing entities, where the result is an advantage for one side and an equivalent loss for the o ...
and admits a unique
Nash equilibrium
In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
(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
{{Reflist
External links
voting.ml(website for computing maximal lotteries)
Preferential electoral systems
Single-winner electoral systems