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. 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, participation, 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 that top-ranks maximal lotteries has been uniquely characterized using Arrow's independence of irrelevant alternatives and Pareto efficiency.

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. 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 ${\displaystyle x}$ relative to that of ${\displaystyle y}$ does not decrease when ${\displaystyle x}$ is improved over ${\displaystyle y}$.

The support of maximal lotteries, which is known as the essential set or the bipartisan set, has been studied in detail.

Maximal lotteries were first proposed by the French mathematician and social scientist Germain Kreweras in 1965 and popularized by Peter Fishburn. Since then, they have been rediscovered multiple times by economists, mathematicians, political scientists, philosophers, and computer scientists.

Several natural dynamics that converge to maximal lotteries have been observed in biology, physics, chemistry, and machine learning.

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