Maximal Lottery-Lotteries
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.
The Proposal
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.
Lottery Independence
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.
- Voting Theory Introduction by (17 Oct 2022 8:48 UTC; 80 points)
- Open Problem in Voting Theory by (17 Oct 2022 20:42 UTC; 74 points)
- Maximal Lotteries by (17 Oct 2022 8:54 UTC; 73 points)
- Constructive Cauchy sequences vs. Dedekind cuts by (14 Mar 2024 23:04 UTC; 47 points)
- EA & LW Forums Weekly Summary (17 − 23 Oct 22′) by (EA Forum; 25 Oct 2022 2:57 UTC; 35 points)
- EA & LW Forums Weekly Summary (17 − 23 Oct 22′) by (25 Oct 2022 2:57 UTC; 10 points)
Lottery-condercet seems like a nicer condition than condercet and this seems like a very compelling argument against condercet. Lottery independence seems like a hard property to reject when randomization is available (and “we didn’t ask the players how they felt about lotteries” is not a very compelling defense). Overall seems like a very interesting perspective, though it would certainly be nicer if maximal lottery-lotteries existed.
In its suggested form Maximal Lottery-Lotteries is still a majoritarian system in the sense that a mere majority of 51% of the voters can make sure that candidate A wins regardless how the other 49% vote. For this, they only need to give A a rating of 1 and all other candidates a rating of 0.
One can also turn the system into a non-majoritarian system in which power is distributed proportionally in the sense that any group of x% of the voters can make sure that candidate A gets at least x% winning probability, similar to what is true of the MaxParC voting system used in vodle
The only modification needed to achieve this is to replace Δ(C) (the set of all lotteries on C) in your formula by the set of those lotteries on C which every single ballot rates at least as good as the benchmark lottery. In this, the benchmark lottery is the lottery of drawing one ballot uniformly at random and electing the highest-rated candidate (as in the “random ballot” or “random dictator” method).
Actually, I think there is a decent chance I am wrong here. It might be merging two electorates that produce the same lottery-lottery over candidates also produces that lottery-lottery, but we can’t say the same thing if we collapse that to lotteries, which is what we would need for consistency.
So far I’m not getting the point of this. Suppose my Lottery-Lottery has one element, the Maximal Lottery (TM). I’m no mathematician, so prove me wrong at-will, but I don’t think there are any other lotteries you can add that do not change the probability that any candidate is elected, that aren’t identical to the Maximal Lottery (TM).
Why would I ever want a Lottery-Lottery that has elements that aren’t the Maximal Lottery (TM)? Surely my voting system is better if I just replace whatever random lotteries are in the Lottery-Lottery with my single Maximal Lottery (TM).
It is not the case that voters on average necessarily prefer the maximal lottery to any other lottery in expected utility. It is only the case that voters on average prefer a candidate sampled at random from the maximal lottery to a candidate sampled at random from any other lottery. Doing the first thing would be impossible, because there can be cycles.
This is how anarchy wins in maximal lotteries in the example in the next section. If you compare anarchy to choosing a leader at random, in expected utility, choosing a leader at random is a Pareto improvement, but if you sample a candidate at random, they will lose to Anarchy by 1 vote.
Answer: The next section gives a situation where a maximal lottery gives a worse result than a certain loterry-lottery.
How to elicit the necessary information in the voting booth? Surely we can’t have a ballot with all possible gambles on it.
We could use score voting (and then process the votes differently, much like the zoo of Borda count alternatives process the same ballot differently). But score voting has strategy problems where you’re incentivized to turn it into approval voting, right? Are there similar strategies in MLL counting?
Not expecting this to be a solved problem, more just reacting in the form of a question.
Utility functions contain all the preferences on all gambles.
If you just maximize average utility as score voting does, yes it is true that the incentives point to always giving utility 0 or 1, which recreates approval voting. I don’t know about MLL.
I’m having trouble with the solution to the dictatorship vs anarchy example. Is a 13 split actually maximal? Is “A dominates B” transitive?
Let’s say ϵ=0.1. Consider an unfair 50/50/0 split in which the first two potential dictators throw the third under the bus. As I understand, this dominates the equal split, since 2 out of the 3 voters prefer this new lottery.
Then say voter #3 counterproposes a 0/60/40 split. This dominates again. But then 50/0/50 dominates that… so domination is non-transitive. And I don’t see a maximal randomized outcome.
Am I missing something here?
New confusion: in the dictator example, it seems like between option A, an even 13 split, and option B, a 50/50/0 split, neither dominates the other. I’m calculating P[v(A)>v(B)]=P[v(A)<v(B)]=29.
EDIT: Probably this is me discovering the difference between maximal lotteries and maximal lottery-lotteries...
Okay, this comment is now making more sense to me: https://www.lesswrong.com/posts/vwrNprXfEzeQ2cy3d/maximal-lottery-lotteries?commentId=Cw7TTF2oTXzvE5e6S
I believe I’m starting to see my mistake; I was thinking there was an argmax step where there’s more like an expectation, due to sampling jointly, at the same time, across the lottery outcomes and voters.
Can someone explain to me how the giry monad factors in? For some A∈Δ(Δ(C)), executing A>>=(λx.δx) to get a Δ(C) would destroy information: what information, and why not destroy it? (Am I being too hasty comparing probability monad to haskell monad?)
When a voter compares two lottery-lotteries, they take expected utilities with respect to the inner Δ, but they sample with respect to the outer Δ, and support whichever sampled thing they prefer.
If we collapse and treat everything like the outer Δ, that just gives us the original maximal lotteries, which e.g. is bad because it chooses anarchy in the above example.
If we collapse and treat everything like the inner Δ, then existence will fail, because there can be non-transitive cycles of majority preferences.
Whoa whoa whoa. This isn’t guaranteed. 0 utility is really bad! Like, if the winner gets to just torture me and my loved ones to death, I don’t want that to happen! I’d prefer anarchy than submitting to that with a 2/3rd probability! Part of the point of the election is that it should mean, ‘this kinda sucks, but I’ll get another chance to have my candidate win next time’. Any voting outcome which is worse than the alternative of ‘must fight an underdog rebellion’ should be expected to turn into an underdog rebellion. Underdog rebellion is worse for the group than anarchy (equal footing, no established leader), but still better than no utility at all. Or did you mean ‘gets 0 utility’ to mean a perfectly neutral state where things are neither positive or negative? That’s a very different and not to-my-mind default meaning.
It seems like an important feature of democracy that winners are in some sense partial, the condition is temporary and intended to have largely reversible effects where possible. This isn’t always the case, like Candidate A committing the country to a war that the other candidates wouldn’t have, but in many cases it is. If the laws passed by one regime are, in practice, found to be intolerable by a large minority, then reversing those laws will become a party ticket in the subsequent campaign.
Here’s another thought. Maybe voting method is less important than campaigning rules by a large margin. Maybe if campaigns were structured in such a way that important information about the relative competence and biases of the proposed candidates were exposed, the voting method would become mostly irrelevant. Forcing all the candidates to undergo public trials of their ability to do legislative decision making in realistic simulations, and then simply summarizing and publicizing their scores seems to me that it could do more to get better candidates elected. If a particular group thought they wanted candidate A, but then saw that actually candidate B’s decisions regularly resulted in much better outcomes for them in the simulations as well as for B’s base (because the world isn’t zero sum, and better decisions can be the tide which floats all boats)… Seems like the shift in favor of B would likely outweigh subtleties of voting methods around edge cases. If I had to pick between candidate-simulation-trials plus a random choice of voting method between <theoretically perfect method> / ranked choice / approval voting, or not have candidate-simulation-trials and be sure to get to use <theoretically perfect voting method>, I’d strongly prefer the option with simulation trials.