epistemic/ontological status: almost certainly all of the following -
a careful research-grade writeup of a genuinely kinda shiny open(?) question in theoretical psephology that will likely never see actual serious non-cooked-up use;
dedicated to a very dear cat;
utterly dependent, for the entirety of the most interesting parts, on definitions I have come up with and results I have personally proven partially using them, which I have done with a professional mathematician's care; some friends and strangers have also checked them over;
my attempt to prove that something that can reasonably be called a maximal lottery-lottery exists;
my attempt to scavenge what others have left behindand craft a couple of missing pieces, and then to lay out a blueprint for how it could begin to work;
not a 30-minute read
the first half of something incomplete
Maximal Lottery-Lotteries: Far More Than It Ever Occurred To You To Want To Know
This post is mostly a distillation/concentrated treatment of the Maximal Lottery-Lotteries Sequence, though I define an important property and prove an important existence result at the end. It's the first of two posts in a sequence, the second of which is linked here.
The Maximal Lottery-Lotteries sequence details why anyone should care about sortitive/lottery-using electoral systems even without any particular hope of getting to implement it.[1] It also ends in early November of 2022 with the author and a handful of other technical alignment notables all honorably giving up on the shiny math problem with varying degrees of explicitness. This post is meant as a follow-on to the sequence, and its sequel is, too. I also end up drawing heavily on the Geometric Rationality sequence for its central tools.
As per my usual policy, if I've managed to misunderstand anything or write anything up unclearly or incorrectly, or you have any questions about what I've written, please comment below or at https://www.admonymous.co/lorxus and I'll fix it/reply to it when I can.
If you're reading this post for the first time, you might want to keep the notation reference on hand. If you're relatively inexperienced with reading text which treats dense mathematical notation on par with English prose, slow down and make sure you understand what each mathematical expression really means or what object or type of object it refers to before continuing. "Is it a nonce-object instantiated just for the proof, or does the notation suggest anything more about its type or identity?" If you can answer that kind of question without much effort, it'll make understanding any mathematically-dense text much easier. Mathematical notation is extremely compact and precise; if I tried to write all the below purely in prose, it'd be three times as long and a tenth as clear - but all compression comes with compute costs, and math notation is no exception.[2]
Let C be a set of candidates, VC≅Hom(C,[0,1]) the voterspace for C, which is also the set of all utility functions on C (or candidate preferences), and V∈ΔVC an electorate (or voterbase), which is a partition of unity tagged by candidate preferences which we may think of as the "voter share" with each candidate preference.[3] Then a voting systemf:ΔVC→ΔC is a function taking a distribution over voterspace on C to a distribution over C.[4] We write fC(V) for the outcome of voting system f with choice of candidates taken from C and polling electorate V; we'll often suppress the subscript when the candidate set is clear.
This is classically subject to the following four constraints:[5]
Candidate finiteness: |C|<∞, that is, the set of candidates is finite (else we've got lost and ended up somewhere in social choice theory).
Ordinality: f is invariant under precomposition by preorder-respecting functions applied to utility functions - it only uses the preorders on candidates implied by the utility functions (else we need cardinal information, as per score voting, or we allow some preference collapse, as per approval voting).
Determinism: fC(V) always assigns measure 1 to some ci∈C, no matter what C or V are (else we have a sortitive or otherwise nonclassical voting system).
Regularity: the input distribution to f is always the uniform distribution on some finite set (which is a regularity condition to avoid ghost candidates, unequal votes, and other weird possibilities we don't care about).
We can generally ignore regularity, and (spoilers) we'll soon be relaxing determinism, too. At the end, we even get rid of ordinality.
Now for a few desirable properties voting systems can have. We'll phrase them in our language of functions and voting outcomes, which lends itself so much better to generalizing electoral outcomes from deterministic outcomes to lotteries:
Condorcet: Whenever some candidate beats every other candidate in a head-to-head matchup, that candidate should win overall.
Equivalently: assume that for some c∈C, it is the case that ∀d∈C,Pv∼V(v(c)>v(d))>12 whenever d≠c. Then a Condorcetf satisfies fC(V)(c)=1.[6]
Equivalently: assume that we can separate C as C=S⊔D such that ∀c∈S,d∈D,Pv∼V(v(c)>v(d))>12. Then a Smithf satisfies fC(V)(S)=1, that is, fC(V)∈ΔS.
Consistency: Two distinct voterbases each giving the same result as each other should mean that after joining the voterbases, the joined voterbase should still give the same result as before.
Equivalently: assume that fC(V)=fC(W)=D∈ΔC. Then for all choices of intermediacy parameter p∈[0,1], a consistentf satisfies fC(p⋅V+(1−p)⋅W)=D.
Participation: It should never be the case that a voter can predictably do themself better by not voting. This is notably a limiting case of consistency, as one subpopulation becomes increasingly small and certain.
Equivalently, let W∈ΔVC be an electorate, v∈VC a voter, p∈[0,1] an intermediacy parameter. Then a participatoryf satisfies v(fC(p⋅v+(1−p)⋅W))≥v(fC(W)), where we interpret p⋅v+(1−p)⋅W as the p-parametrized mix of W and the element V∈ΔVC that happens to put measure 1 on v, or equivalently as something for which sampling from it means first choosing between v with probability p and otherwise a draw from W with probability 1−p, and where for a lottery D∈ΔC, we interpret v(D)=Ed∼Dv(d).
Dupe-resistance:[7] If there's two or more candidates in the dupe set D={d1,d2,⋯,dn} where for all voters v∈V and candidate c∈C∖D, there is a d∈D such that v is indifferent between d and each of the di, and v always has the same ordinal preference between c,di for every di, then the outcome of the election should be identical, for every candidate outside the dupe-set D, to if the election were rerun with a single candidate d replacing all of D.
Equivalently, let C=ˆC⊔{d}⊔D, and suppose that ∀c∈ˆC,di∈D, v∈V∈ΔVC, we have v(c)>v(di)↔v(c)>v(d) and v(c)<v(di)↔v(c)<v(d). Then a dupe-resistantf satisfies fC(V)(c)=fC∖D(V)(c) for all c∈ˆC, that is, c still wins exactly as much as if there were just no d-dupes.
Famously, Arrow's impossibility theorem says that for a classical voting system (i.e., one that deterministically spits out a single candidate at the end, among other requirements), you can't have all of these. You can't even have the Condorcet criterion, dupe-resistance, and consistency at the same time - isomorphic to Arrow's usual sorrowful guarantee. You can't even have both participation and the Condorcet criterion at the same time! A pall of soot falls over the Sun, and democracy dies to thunderous applause.
Also, I've cheated a little here, because that's technically not the standard definition of the Smith criterion. That's because the real standard definition is actually just wrong for our purposes - it always talks about such a voting system always picking its unique winner from the Smith set. We recall that voting theorists usually assume determinism of outcomes, which we have long since made up our minds to discard - if we were to put that assumption back, we recover the classical definition of the Smith criterion.
But look - phrasing it this way means that the Smith criterion generalizes itself when we pass from deterministic elections to lotteries, and it even gets much more powerful and flexible when we do! We should think of the Smith condition as being "the Condorcet condition, but one which fails more gracefully and has a reasonable plan in case there's no Condorcet winner". For deterministic elections, that additional strength doesn't count for much more than some annoying noise in the outcomes. However, this weakness - that if we force the Smith set to do all the final choosing for us, we then have to blame it for sometimes producing unsatisfying outcomes - is one we already have the tools to trivially resolve. We simply leave it to a lottery, and the Smith criterion's issues fall away. Sortitive voting systems are the Smith criterion's true home.[8]
The Smith criterion's precondition is strictly weaker than that of the Condorcet criterion (because if there's a Condorcet winner, then the Smith set is a singleton containing just that candidate) and its backup guarantees are strictly stronger than that of the Condorcet criterion (some admittedly weaker control over the outcome of the election, as opposed to nothing at all) so overall the Smith criterion is a more empowering property than the Condorcet criterion is. That said, it's not by all that much - for example, in a worst-case scenario where the voterbases's collective preferences over candidates is maximally-nontransitive, the Smith set is just the entire candidate set.
We start by relaxing determinism and ceasing to bother tracking regularity from among the assumptions in the previous section; the immediate consequence of this is that fC(V) is in general a lottery D∈ΔC rather than an individual candidate (or in reality a measure-1 chance of drawing some specific candidate) as might have been tacitly assumed in the previous section.
Probabilistic outcomes also require actually formulating a definition of what it means for one candidate to beat another. Let A,B∈ΔC be candidate-lotteries, V∈ΔVC an electorate, and for the sake of notation take draws a∼A,b∼B,v∼V. Then A dominatesB (and we write A⪰B) if Pa,b,v(v(a)>v(b))≥Pa,b,v(v(b)>v(a)). In slightly more prose, we take independent draws a,b,v from A,B,V, and then compare v(a),v(b)∈[0,1], and if it's more often or more likely the case that (after we've drawn all our samples) v prefers a to b, then A dominates B. Importantly, dominance is not a necessarily transitive relation, but it still only requires ordinal preference rankings and so our assumption of ordinality is safe for now.
A maximal lottery is some lottery M∈ΔC such that for all candidate-lotteries L∈ΔC,M⪰L.
Theorem: (Maximal lotteries exist): Let C be a set of candidates, V∈VC an electorate. Then there exists at least one candidate-lottery M∈ΔC such that for all choices of candidate-lottery L∈ΔC,
epistemic/ontological status: almost certainly all of the following -
Maximal Lottery-Lotteries: Far More Than It Ever Occurred To You To Want To Know
This post is mostly a distillation/concentrated treatment of the Maximal Lottery-Lotteries Sequence, though I define an important property and prove an important existence result at the end. It's the first of two posts in a sequence, the second of which is linked here.
The Maximal Lottery-Lotteries sequence details why anyone should care about sortitive/lottery-using electoral systems even without any particular hope of getting to implement it.[1] It also ends in early November of 2022 with the author and a handful of other technical alignment notables all honorably giving up on the shiny math problem with varying degrees of explicitness. This post is meant as a follow-on to the sequence, and its sequel is, too. I also end up drawing heavily on the Geometric Rationality sequence for its central tools.
As per my usual policy, if I've managed to misunderstand anything or write anything up unclearly or incorrectly, or you have any questions about what I've written, please comment below or at https://www.admonymous.co/lorxus and I'll fix it/reply to it when I can.
If you're reading this post for the first time, you might want to keep the notation reference on hand. If you're relatively inexperienced with reading text which treats dense mathematical notation on par with English prose, slow down and make sure you understand what each mathematical expression really means or what object or type of object it refers to before continuing. "Is it a nonce-object instantiated just for the proof, or does the notation suggest anything more about its type or identity?" If you can answer that kind of question without much effort, it'll make understanding any mathematically-dense text much easier. Mathematical notation is extremely compact and precise; if I tried to write all the below purely in prose, it'd be three times as long and a tenth as clear - but all compression comes with compute costs, and math notation is no exception.[2]
Generalized Voting Theory
Let C be a set of candidates, VC≅Hom(C,[0,1]) the voterspace for C, which is also the set of all utility functions on C (or candidate preferences), and V∈ΔVC an electorate (or voterbase), which is a partition of unity tagged by candidate preferences which we may think of as the "voter share" with each candidate preference.[3] Then a voting system f:ΔVC→ΔC is a function taking a distribution over voterspace on C to a distribution over C.[4] We write fC(V) for the outcome of voting system f with choice of candidates taken from C and polling electorate V; we'll often suppress the subscript when the candidate set is clear.
This is classically subject to the following four constraints:[5]
We can generally ignore regularity, and (spoilers) we'll soon be relaxing determinism, too. At the end, we even get rid of ordinality.
Now for a few desirable properties voting systems can have. We'll phrase them in our language of functions and voting outcomes, which lends itself so much better to generalizing electoral outcomes from deterministic outcomes to lotteries:
Equivalently: assume that for some c∈C, it is the case that ∀d∈C,Pv∼V(v(c)>v(d))>12 whenever d≠c. Then a Condorcet f satisfies fC(V)(c)=1.[6]
Equivalently: assume that we can separate C as C=S⊔D such that ∀c∈S,d∈D,Pv∼V(v(c)>v(d))>12. Then a Smith f satisfies fC(V)(S)=1, that is, fC(V)∈ΔS.
Equivalently: assume that fC(V)=fC(W)=D∈ΔC. Then for all choices of intermediacy parameter p∈[0,1], a consistent f satisfies fC(p⋅V+(1−p)⋅W)=D.
Equivalently, let W∈ΔVC be an electorate, v∈VC a voter, p∈[0,1] an intermediacy parameter. Then a participatory f satisfies v(fC(p⋅v+(1−p)⋅W))≥v(fC(W)), where we interpret p⋅v+(1−p)⋅W as the p-parametrized mix of W and the element V∈ΔVC that happens to put measure 1 on v, or equivalently as something for which sampling from it means first choosing between v with probability p and otherwise a draw from W with probability 1−p, and where for a lottery D∈ΔC, we interpret v(D)=Ed∼Dv(d).
Equivalently, let C=ˆC⊔{d}⊔D, and suppose that ∀c∈ˆC,di∈D,
v∈V∈ΔVC, we have v(c)>v(di)↔v(c)>v(d) and v(c)<v(di)↔v(c)<v(d). Then a dupe-resistant f satisfies fC(V)(c)=fC∖D(V)(c) for all c∈ˆC, that is, c still wins exactly as much as if there were just no d-dupes.
Famously, Arrow's impossibility theorem says that for a classical voting system (i.e., one that deterministically spits out a single candidate at the end, among other requirements), you can't have all of these. You can't even have the Condorcet criterion, dupe-resistance, and consistency at the same time - isomorphic to Arrow's usual sorrowful guarantee. You can't even have both participation and the Condorcet criterion at the same time! A pall of soot falls over the Sun, and democracy dies to thunderous applause.
Also, I've cheated a little here, because that's technically not the standard definition of the Smith criterion. That's because the real standard definition is actually just wrong for our purposes - it always talks about such a voting system always picking its unique winner from the Smith set. We recall that voting theorists usually assume determinism of outcomes, which we have long since made up our minds to discard - if we were to put that assumption back, we recover the classical definition of the Smith criterion.
But look - phrasing it this way means that the Smith criterion generalizes itself when we pass from deterministic elections to lotteries, and it even gets much more powerful and flexible when we do! We should think of the Smith condition as being "the Condorcet condition, but one which fails more gracefully and has a reasonable plan in case there's no Condorcet winner". For deterministic elections, that additional strength doesn't count for much more than some annoying noise in the outcomes. However, this weakness - that if we force the Smith set to do all the final choosing for us, we then have to blame it for sometimes producing unsatisfying outcomes - is one we already have the tools to trivially resolve. We simply leave it to a lottery, and the Smith criterion's issues fall away. Sortitive voting systems are the Smith criterion's true home.[8]
The Smith criterion's precondition is strictly weaker than that of the Condorcet criterion (because if there's a Condorcet winner, then the Smith set is a singleton containing just that candidate) and its backup guarantees are strictly stronger than that of the Condorcet criterion (some admittedly weaker control over the outcome of the election, as opposed to nothing at all) so overall the Smith criterion is a more empowering property than the Condorcet criterion is. That said, it's not by all that much - for example, in a worst-case scenario where the voterbases's collective preferences over candidates is maximally-nontransitive, the Smith set is just the entire candidate set.
Lottery Outcomes
We start by relaxing determinism and ceasing to bother tracking regularity from among the assumptions in the previous section; the immediate consequence of this is that fC(V) is in general a lottery D∈ΔC rather than an individual candidate (or in reality a measure-1 chance of drawing some specific candidate) as might have been tacitly assumed in the previous section.
Probabilistic outcomes also require actually formulating a definition of what it means for one candidate to beat another. Let A,B∈ΔC be candidate-lotteries, V∈ΔVC an electorate, and for the sake of notation take draws a∼A,b∼B,v∼V. Then A dominates B (and we write A⪰B) if Pa,b,v(v(a)>v(b))≥Pa,b,v(v(b)>v(a)). In slightly more prose, we take independent draws a,b,v from A,B,V, and then compare v(a),v(b)∈[0,1], and if it's more often or more likely the case that (after we've drawn all our samples) v prefers a to b, then A dominates B. Importantly, dominance is not a necessarily transitive relation, but it still only requires ordinal preference rankings and so our assumption of ordinality is safe for now.
A maximal lottery is some lottery M∈ΔC such that for all candidate-lotteries L∈ΔC,M⪰L.