Maximal Lotteries

post by Scott Garrabrant · 2022-10-17T08:54:09.001Z · LW · GW · 11 comments

Contents

  Probabilistic Voting Theory
  Maximal Lotteries
      Doesn't matter. Maximal lotteries always exist!
      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.
      Yep.
      Well, it's Condorcet.
      Yep.....And it satisfies consistency and participation.
      Only for deterministic voting systems!
      They usually don't have to! Remember, maximal lotteries satisfy the Condorcet Criterion. So whenever there is a Condorcet winner, that candidate will just win deterministically, and you won't need to randomize at all!
  Sketches of the Most Important Arguments
    Existence of Maximal Lotteries
    Condorcet
    Consistency
  Maximal Lotteries vs Random Dictatorship
  Fixing U.S. Presidential Elections
None
11 comments

Probabilistic Voting Theory

Recall that in the last post [LW · GW] 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:

  1. The set of candidates is finite.
  2. The function only uses the preorders on candidates implied by the utility functions.
  3. The output distribution assigns probability 1 to a single candidate.
  4. 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  of candidates, lotteries , and an electorate , we say that  dominates  if .

Lets unpack this definition. We are given three distributions , a distribution on voters, and  and , distributions on candidates. We are imagining independently sampling from these three distributions to get , and  respectively. When we do this, one of three things will happen:

  1.  will prefer  to . ()
  2.  will prefer  to . ()
  3.  will be indifferent. ()

We say that  dominates  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  of candidates, and an electorate , a maximal lottery is an  such that for all other  dominates .

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 Criterion. So whenever there is a Condorcet winner, that candidate will just win deterministically, and you won't need to randomize at all!

Sketches of the Most Important Arguments

I will sketch arguments for the existence of maximal lotteries, and the fact that they are Condorcet and consistent. I won't bother proving that they are (usually) unique, satisfy clone invariance and participation, or any unique characterization, as these are harder and also the main thrust of the miracle of maximal lotteries is the fact that they bridge the gap between Condorcet and consistency. For that, I defer here and here.

Existence of Maximal Lotteries

Imagine a two player zero-sum game between Alice and Bob. Alice and Bob each choose a candidate. Alice gets utility equal to the probability that a randomly chosen voter prefers her candidate to Bob's candidate minus the probability that a randomly chosen voter prefers Bob's candidate to hers. Bob, symmetrically, gets the negative of this utility. 

This game has a Nash equilibrium. (Since it is a two player zero sum game, we also get nice properties, like the ability to compute the Nash equilibrium, and the fact that the set of Nash equilibria is convex.) In that Nash equilibrium, Alice and Bob must both used mixed strategies that are Maximal Lotteries.

Condorcet

Imagine there is a Condorcet winner, . Let  be the distribution that assigns probability 1 to , and let  be a maximal lottery. Since  dominates , if  is sampled from , and  is sampled from , the probability that  must be at least the probability that . Since  is a Condorcet winner, for all , the probability that  is greater than . Thus, the probability that  is greater that  times the probability that . Thus, the probability that  is also greater than  times the probability that . Thus, given that , the probability that  and that  are each greater that . This is not possible, so the condition that  must happen with probability . Thus,  assigns probability one to , so the only maximal lottery assigns probability one to .

Consistency

Imagine  is a maximal lottery for electorate  and for electorate . For any other lottery  dominates  for both electorates. Let . Imagine sampling a candidate  from  from , and a voter  from . Imagine that v was sampled by first flipping a coin that comes up heads with probability p, and then sampling from  in the case of heads and  in the case of tails. Conditioned on heads, the probability that  is at least the probability that . Conditioned on tails this is also true. Thus, the unconditioned probability that  is at least the unconditioned probability that , so  dominates  for the electorate . Since  was arbitrary,  is a maximal lottery for electorate .

Maximal Lotteries vs Random Dictatorship

Let us now compare maximal lotteries to random dictatorship. In random dictatorship a voter is sampled at random, and their favorite candidate wins. Random dictatorship is nice because it is strategy proof. Ignoring coalitions, you should always rank you favorite candidate most highly.

I think that maximal lotteries and random dictatorship are actually incomparable. Which one you should use depends on context. Here is a quick test:

Imagine there are only two candidates  and . Imagine that 51% of voters prefer  to . If you think this means  should win with probability 100%, then perhaps you should use maximal lotteries. If you think you should flip a coin and  should win with probability 51%, then perhaps you should use random dictatorship. 

If you think of democracy as replacing the need for war, and voting power is proportional to how many resources you would have in a war, then if the winner of the war would be determined randomly proportionally to resources, then random dictatorship makes more sense, If the side with the most resources would win with certainty, than maximal lotteries makes more sense.

The fact that  does not win with certainty in random dictatorship is what makes random dictatorship not Condorcet. 

This test is not perfect. There are other factors. Often there is a trade off between strategy-proof-ness and Pareto optimality, and while neither is perfect in either criteria, Random Dictatorship is more strategy proof and maximal lotteries are more optimal. (I believe that if you have a bunch of random utility functions, maximal lotteries will lead to higher expected average utility than random dictatorship, but I haven't checked this.) Maximal lotteries is also more robust to a few bad actors, If a minority (or even one person) wants to choose a really bad candidate, random dictatorship will choose that candidate with a small probability. Maximal lotteries will not.

Fixing U.S. Presidential Elections

So now that we have identified the best voting system as maximal lotteries, we just need to use it in practice. 

You might think that given all the math and the randomness and weirdness, it is politically infeasible to implement maximal lotteries. But I think it is actually very feasible. In fact, we are actually pretty close.

One way to compute (and sample from) the maximal lottery is to simulate a two player game. If the game is set up correctly the two players will play Nash equilibria, and will thus choose candidates according to the maximal lottery. In the United States, these two players are the Democrats and the Republicans.

To more accurately compute the maximal lottery, we must:

  1. Eliminate all third-parties. We need a two player game.
  2. The game needs to be zero-sum. Both parties need to care about nothing other than winning. Anyone who votes in primary election should care only about electability. All that matters is that the candidate chosen by their party wins. The views of the candidates are irrelevant except in so far as the change electability. I believe we can achieve this by increasing political polarization and tribal feelings.
  3. The two parties must choose their candidates independently. We already have some of this by having the primaries take place at the same time, but it will help if members of different parties do not talk to each other at all.
  4. The above will only set up the game where the two parties are trying to select the candidate that would win in a one-on-one election. We actually need the two parties to try to select the candidate that would be selected by a randomly chosen voter. To achieve this, we need to decrease voter turnout in the general election. If every voter flips a coin and stays home with probability , then with probability almost one nobody will vote, and the president will be selected from the two candidates by other means, but since it will be from the nominees, it will be according to maximal lotteries. With probability on the order of , one person will vote chosen at random. The probability that more than one person will vote is negligible, so both parties will select the candidate that is most likely to be preferred by one randomly selected voter, and thus select candidates according to maximal lotteries!
  5. As a sanity check that we have done this correctly, we can just look at the policies of the nominees. Any ability to predict correlations between views of candidates and political parties means we have failed (probably by not having enough polarization). Since the game is symmetric, every election cycle the two candidates should be indistinguishable in expectation.

(As a stretch goal, we can approximate the proposal in my next post [LW · GW] by having obnoxiously large numbers of virtually indistinguishable candidates in the primary elections.)

11 comments

Comments sorted by top scores.

comment by Quinn (quinn-dougherty) · 2022-10-17T19:06:43.573Z · LW(p) · GW(p)

Florian Brandl, Felix Brandt, and Hans Georg Seedig

hyperlink 404

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2022-10-17T19:11:06.169Z · LW(p) · GW(p)

Does it work now?

Replies from: quinn-dougherty
comment by Martin Randall (martin-randall) · 2022-10-17T15:36:53.910Z · LW(p) · GW(p)

When choosing between random dictator and maximal lottery, are there good options to compromise between these extremes? Eg, suppose that I want a 75% majority to win 95% of the time.

The first thing that comes to mind is a % chance of each, but that doesn't seem especially elegant.

Replies from: Measure
comment by Measure · 2022-10-17T18:28:59.388Z · LW(p) · GW(p)

Something like squaring the size of each voting bloc before doing a weighted random selection? This gives a 90% chance for a 75% majority to win.

Replies from: Scott Garrabrant, martin-randall
comment by Scott Garrabrant · 2022-10-17T18:53:24.928Z · LW(p) · GW(p)

I don't like this because irrelevant alternatives can split a voting block, and have a large effect.

Replies from: Scott Garrabrant
comment by Scott Garrabrant · 2022-10-17T19:03:01.707Z · LW(p) · GW(p)

Oh, at first I was interpreting voting block as set of people with the same full preference profile. Obviously, since you are modifying RD, it should just be people with the same first choice, so my point doesn't matter.

Unlike RD and ML, your proposal is not clone invarient.

comment by Martin Randall (martin-randall) · 2022-10-18T01:02:14.099Z · LW(p) · GW(p)

For example, randomly sample N voters from the electorate, and run ML taking account only of those voters. Fails Condorcet, like RD, but it gives the behavior I specified. Politically infeasible, of course. And I'm not really sure I buy the argument-from-war for RD.

comment by Algon · 2022-10-17T15:25:05.501Z · LW(p) · GW(p)

I skimmed bits of this, and after reading the last section I'm semi-convinced that Scott is just trolling us. His 5 step plan to "fix US presidential elections" sounds like it would lower the sanity waterline in the US. 

Replies from: martin-randall
comment by Martin Randall (martin-randall) · 2022-10-17T15:38:44.843Z · LW(p) · GW(p)

The last section is of course a joke. It would be much better if we eliminated the bad party. In a one candidate election all voting methods return the same answer.

comment by ChristianKl · 2022-10-17T14:30:53.413Z · LW(p) · GW(p)

The views of the candidates are irrelevant except in so far as the change electability. I believe we can achieve this by increasing political polarization and tribal feelings.

That sounds like a project to make the existing system function even less well than it currently does. The policy debates that happen when choosing presidential candidates have value. 

We already have some of this by having the primaries take place at the same time, but it will help if members of different parties do not talk to each other at all.

That sounds like a recipe to make consensus finding even harder in addition to being unpractical.