Maximal lotteries

Maximal lotteries are a probabilistic voting rule that use ranked ballots and returns a lottery over candidates that a majority of voters will 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.^[1] However, they satisfy relative monotonicity, i.e., the probability of ${\displaystyle x}${\displaystyle x} relative to that of ${\displaystyle y}${\displaystyle y} does not decrease when ${\displaystyle x}${\displaystyle x} is improved over ${\displaystyle y}${\displaystyle 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]}

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

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

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

• voting.ml (website for computing maximal lotteries)

• Preferential electoral systems
• Single-winner electoral systems

• Articles with short description
• Short description matches Wikidata