Resolving Non-uniqueness in Maximal Lotteries

cfrank

Maximal lotteries are guaranteed to be unique when rankings are strict and there is an odd number of voters. Uniqueness can hold in other cases, and generally non-uniqueness only occurs when the majority margin matrix exhibits "pathological" and non-generic symmetries. It follows that small perturbations of the majority margin matrix almost certainly yields uniqueness.

This post is just a space to discuss how this non-uniqueness should be handled in a fair way when it arises. Here is an example of one idea (not novel):

If the maximal lottery is unique, great.
Otherwise, if we allowed non-strict rankings, induce strict rankings on each ballot's indifferences independently at random. (This raises questions about ballot format and implementation).
If the maximal lottery is still not unique, then the number of counted ballots is even. Produce one additional ballot, such as by randomly sampling one late ballot that was not yet counted (if one exists), by constructing a ballot from those already submitted (randomly sampled or a distributed construction), or by blatant authority (or even just a completely random ranking).

This will guarantee uniqueness of the maximal lottery. However, it may no longer satisfy the formal properties of maximal lotteries---as in, the achieved unique lottery may not actually be maximal for the ex-ante majority margin matrix (unless we use the latecomer ballot).

Alternatively, we can use a rule to select a maximal lottery from the admissible set, such as the maximum entropy maximal lottery, or sampling the maximal lottery from the Jeffrey's prior over maximal lotteries. My personal opinion is that the Jeffrey's prior makes the most sense.

As always, any thoughts are welcome.

Toby Pereira

Just to clarify what's happening here:

A maximal lottery result can be something like:

A: 50%
B: 30%
C : 20%

where these are the probabilities of the candidates A, B and C being elected. So is non-uniqueness simply that sometimes there might be another probability distribution that is also optimal? E.g.

A: 55%
B: 35%
C : 10%

(Or maybe some sort of continuum of optimal results.)

You said that where preferences are strict and the number of voters is odd, there will be a unique solution. Is this simply because an even number of voters can lead to a head-to-head tie between two candidates, or is there something else more complex going on with an even number of voters? It seems intuitive to me that it's just because ties can happen.

In the case of ties, this isn't a problem unique to Maximal Lotteries. You can get ties in any voting method, e.g. FPTP and have to deal with that somehow. With a big election, ties will be rare. Obviously it's less likely with FPTP because it requires a tie at the top, whereas with Maximal Lotteries, there can be a tie between any pair of candidates potentially affecting the result.

It can be argued that in the case of more than one optimal lottery, it doesn't matter which one you choose because they are all optimal for the voters. Some will work out better for some candidates (a higher probability of election), but elections are about what voters want. They're not really about the candidates.

In the same way that a lottery generates the winning candidate, you can simply have a random mechanism to determine which lottery to use. I don't see this as a major problem in the general scheme of things.

cfrank

@toby-pereira your interpretation is correct, and yes with an even number of voters and non-strict rankings, ties can occur and that can induce non-uniqueness. For example there may be two separate, disconnected Condorcet cycles of different sizes in the Smith set for instance.

With ties in other methods, the resolution of ties is typically standard because the set over which the ties occur are discrete—uniformly sample one from among the tied candidates. But for maximal lotteries, when non-uniqueness holds there is a continuum of admissible lotteries as you indicated. The analog of a uniform distribution in this case would be using Jeffrey’s prior, which is why I think that’s the “right” way to go.

But yes it ultimately doesn’t really matter how the maximal lottery used is chosen since they are all maximal, but that’s also kind of the issue, because a choice has to be made.