Maximal lotteries

Collective preferences over lotteries

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 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.

Strategic interpretation

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 and can be computed in polynomial time via linear programming.

Example

Suppose there are five voters who have the following preferences over three alternatives:

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

${\displaystyle \begin{array}{c}\begin{array}{ccccc}& & a& b& c\end{array}\\ \begin{array}{c}a\\ b\\ c\end{array}\left(\begin{array}{ccc}0& 1& -1\\ -1& 0& 3\\ 1& -3& 0\end{array}\right)\end{array}}$

This matrix can be interpreted as a zero-sum game and admits a unique Nash equilibrium (or minimax strategy) ${\displaystyle p}$ where ${\displaystyle p(a)=3/5}$, ${\displaystyle p(b)=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}$ and ${\displaystyle c}$ in his preference relation, ${\displaystyle a}$ becomes the Condorcet winner and will be selected with probability 1.