In the last post we saw how by introducing lotteries, we could resolve one of the major conflicts in voting theory, between Condorcet and consistency (while also satisfying participation and clone independence). Now, we are going to make it better. How? By adding even more lotteries!
As far as I know, unlike the previous posts, the content of this post is a new proposal by me. Everything in this post should be treated as conjecture, rather than proven.
Fix a finite set of candidates, and an electorate .
First, recall the following definition of maximal lotteries. Given lotteries , we say that dominates if . A maximal lottery is an such that for all other , dominates .
Now for maximal lottery-lotteries. Given lottery-lotteries , we say that dominates if . A maximal lottery-lottery is an such that for all other , dominates .
Note that when we say , since is not a candidate, but a distribution of candidates, we mean the expected value of when a is sampled from , and similarly for . Unlike in maximal lotteries, to determine whether , we need the full information of as a utility function (up to affine transformation), not just the preference ordering over candidates.
is a distribution on distributions on candidates, but we need to output a distribution on candidates. Thus, we imagine sampling a distribution at random from , and then sampling a candidate at random from that distribution. The output of the maximal lottery-lotteries voting system is the distribution that assigns each candidate the probability that they would be sampled from the above procedure.
To argue for maximal lottery-lotteries, I introduce a new criterion: lottery independence.
Given an initial set of candidates, , we could imagine fixing any distribution over candidates , and introducing a new lottery candidate, representing . Voters vote for the lottery candidate based on their expected utility from the lottery. Whenever the lottery candidate wins, we sample a candidate according to .
A voting system satisfies lottery independence if introducing lottery candidates does not change the probability that any candidate is elected.
This is not a criterion that voting theorists would normally talk about, because in order to satisfy it, you both have to allow the voting system to be non-deterministic, and you have to collect utility data from the voters.
Lottery independence can be thought of as a strengthening of clone independence. Instead of introducing a clone of a single candidate, we introduce a lottery, which is like a randomized clone which clones a candidate at random after the election is over.
Maximal lottery-lotteries satisfies lottery independence. Indeed, one way to think of maximal lottery-lotteries, is first we close the set of candidates under all possible lotteries, and then we run maximal lotteries on the resulting set of candidates.
Maximal lottery-lotteries also satisfies consistency and participation, since they are just maximal lotteries over a larger set of candidates. (EDIT: this argument doesn't quite work, and I think it is more likely than when I first wrote this that maximal lottery-lotteries fails to be consistent.)
Lottery Condorcet Criterion
Since Condorcet, consistency, and clone independence uniquely specify Maximal lotteries, if maximal lottery-lotteries is different, it must sacrifice one of these properties. It sacrifices the Condorcet criterion.
Note that in most contexts, this is where I would stop reading. My normal first question when I see a new voting system is, "Is it Condorcet?" If the answer is no, my next follow-up questions are "How often does it correctly find the correct (Condorcet) winner?" and "What amazing property is going justify the occasional failure?"
However, I actually think that in this context, we didn't want the Condorcet criterion in the first place. Hear me out. Here is an illustrative example.
There are three voters trying to elect a leader. If any one of them is elected leader, that person gets utility 1, and the other two get utility 0. However, there is also a third anarchy option where they have no leader. Anarchy is bad. Each person gets utility where . Anarchy is the Condorcet winner, and thus maximal lotteries will choose anarchy with probability 1. This is dumb. Everyone would prefer to just randomly pick between the three candidates, which is what maximal lottery-lotteries does.
(It is not maximal lotteries' fault it gets the wrong answer here. Without the full utility data, this situation is indistinguishable from the situation where anarchy gives everyone utility, and is thus the correct answer.)
The problem here is that while anarchy was a Condorcet winner, it was not a lottery Condorcet winner.
A voting system is said to satisfy the lottery Condorcet criterion if whenever a candidate would beat any other distribution over candidates in a one on one election, that candidate should win with probability 1.
The lottery Condorcet criterion is weaker than the traditional Condorcet criterion, since it is harder to be a lottery Condorcet winner. When given full utility information and the ability to randomize, the traditional Condorcet criterion is too strong, and sometimes forces us to choose the wrong candidate.
Maximal lottery-lotteries satisfies the lottery Condorcet criterion, but fails to satisfy the traditional Condorcet Criterion.
Characterizing Maximal Lottery-Lotteries
So we have a strengthening of clone independence to lottery independence, and we have a weakening of Condorcet to lottery Condorcet (which is really more of an improvement), so now we are ready to uniquely characterize maximal lottery-lotteries:
Maximal lottery-lotteries is the unique voting system to satisfy consistency, lottery Condorcet, and lottery independence. (Reminder: everything in this post is only conjecture.)
(EDIT: This characterization might be false, because maximal lottery-lotteries might not be consistent. I suspect we can save it with a weakening of consistency, or by using strengthening of participation instead, but I am guessing it is false as written.)
Existence of Maximal Lottery-Lotteries?
The biggest downside with this proposal is this I have not been able to prove that maximal lottery-lotteries exist. In the next post, I will discuss why this is not trivial, and share some failed attempts and empirical results.