A joint Politics and Economics series |
Social choice and electoral systems |
---|
![]() |
![]() |
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 relative to that of does not decrease when is improved over . [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 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. [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 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 and admits a unique Nash equilibrium (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.