Maximal lotteries

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.