Condorcet methods Positional voting Cardinal voting Quota-remainder methods Approval-based committees Fractional social choice Semi-proportional representation By ballot type Pathological response Strategic voting Paradoxes of majority rule Positive results Maximal lotteries are a probabilistic voting rule that use preferential ballots and returns a lottery over candidates that a majority of voters prefer, on average, to any other.
[1] 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[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.
[7][8][9][10] 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] 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
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
if it is more likely that a randomly selected voter will prefer the alternatives sampled from
[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] 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 can be computed in polynomial time via linear programming.
Suppose there are five voters who have the following preferences over three alternatives: The pairwise preferences of the voters can be represented in the following skew-symmetric matrix, where the entry for row
This matrix can be interpreted as a zero-sum game and admits a unique Nash equilibrium (or minimax strategy)
By definition, this is also the unique maximal lottery of the preference profile above.
Many preference profiles admit a Condorcet winner, in which case the unique maximal lottery will assign probability 1 to the Condorcet winner.