Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Maximal Lotteries, published by Scott Garrabrant on October 17, 2022 on LessWrong.
Probabilistic Voting Theory
Recall that in the last post I said that a voting system is a function that takes in a distribution on utility functions on a set of candidates, and produces a distribution on that set of candidates, and that voting theorists tend to make four assumptions:
The set of candidates is finite.
The function only uses the preorders on candidates implied by the utility functions.
The output distribution assigns probability 1 to a single candidate.
The input distribution is the uniform distribution on some finite set.
The fourth assumption doesn't really matter, and isn't really used, so we can just remove it. The third assumption, on the other hand, is important for many of the voting theory conclusions, but we are now going to see what happens if we remove it. We will keep the first two assumptions.
So now, we will be considering lotteries (i.e. distributions) over candidates, since that will be the output of our voting system.
Given a set C of candidates, lotteries A,B∈Δ(C), and an electorate V∈Δ(C[0,1]), we say that A dominates B if Pa∼A,b∼B,v∼V(v(a)>v(b))≥Pa∼A,b∼B,v∼V(v(b)>v(a)).
Lets unpack this definition. We are given three distributions V, a distribution on voters, and A and B, distributions on candidates. We are imagining independently sampling from these three distributions to get v, a, and b respectively. When we do this, one of three things will happen:
v will prefer a to b. (v(a)>v(b))
v will prefer b to a. (v(b)>v(a))
v will be indifferent. (v(a)=v(b))
We say that A dominates B if the first outcome is at least as likely as the second outcome. Note that we don't need to look at the actual utility functions to determine whether A dominates B, we only need to look at the partial ordering of preferences over candidates, so we are not violating assumption 2. Also note that domination need not be transitive.
Maximal Lotteries
Given a set C of candidates, and an electorate V∈Δ(C[0,1]), a maximal lottery is an M∈Δ(C) such that for all other L∈Δ(C), M dominates L.
Sounds great, but surely that is too strong a condition, domination isn't even transitive.
Doesn't matter. Maximal lotteries always exist!
What? Is this some silly Brouwer's fixed point thing, where you can't find them, and they aren't unique?
Nope. Maximal lotteries are basically unique. The only reason they aren't unique is because of ties. For example, if your electorate is the uniform distribution on an odd number of voters that are never indifferent, there will be a unique maximal lottery. And you can find them quickly.
Wow, so this is like a proper voting system then: given an electorate, just output the maximal lottery.
Yep.
Is it any good?
Well, it's Condorcet.
Wow! This is has got to be the most elegant Condorcet voting system I have ever seen! Most of the Condorcet systems I have seen have basically looked like they took the Condorcet criterion, and then wrote an algorithm around it. Is it Clone invariant?
Yep.....And it satisfies consistency and participation.
What? Those are incompatible with Condorcet!
Only for deterministic voting systems!
Wow! I don't really have an intuition for probabilistic voting systems, There must be all sorts of cool stuff you can do once you allow randomness.
No, this is basically it. You could choose a random voter to be dictator, which is nice for being strategy-proof, but that isn't Condorcet. In fact, Maximal Lotteries are uniquely characterized as the only probabilistic voting system that is Condorcet, consistent, and clone invariant. (See this paper by Florian Brandl, Felix Brandt, and Hans Georg Seedig.)
I'm sold. But are people ready to start flipping coins in elections?
They usually don't have to! Remember, maximal lotteries satisfy the Condorcet Criter...