Open Problem in Voting Theory

Scott Garrabrant

In the previous post, I presented the concept of a maximal lottery-lottery as follows:

We start with a finite set of candidates and a distribution $V \in Δ (C \to [0, 1])$ on utility functions on $C$ . Given lottery-lotteries $A, B \in Δ (Δ (C))$ , we say that $A$ dominates $B$ if $P_{A \sim A, B \sim B, v \sim V} (v (A) > v (B)) \geq P_{A \sim A, B \sim B, v \sim V} (v (B) > v (A))$ . A maximal lottery-lottery is an $M \in Δ (Δ (C))$ such that for all other $L \in Δ (Δ (C))$ , $M$ dominates $L$ .

Conjecture: For any $C$ and $V$ , there always exists a maximal lottery-lottery.

We discussed how we can construct a powerful and elegant new voting system, if only we can guarantee that a maximal lottery-lottery exists. However it is an open problem whether or not they exist. In this post, I will discuss a few different angles of attacking this conjecture.

An Infinite Game

First, consider the following partial result:

Theorem: Let $D$ be any nonempty finite subset of $Δ (C)$ . Then, there exists an $M \in Δ (D)$ such that for all other $L \in Δ (D)$ , $M$ dominates $L$ .

Proof: Consider the following symmetric two-player zero-sum game between Alice and Bob: Alice chooses an $A \in D$ , and Bob chooses a $B \in D$ . Alice gets utility equal to $P_{v \sim V} (v (A) > v (B)) - P_{v \sim V} (v (B) > v (A))$ , and Bob gets the negative of this utility. This game must have a Nash equilibrium, and in this Nash equilibrium, Alice must play a mixed strategy $M \in Δ (D)$ . Since this is a Nash equilibrium in a symmetric zero-sum game, Alice must get at least 0 utility in expectation, no matter what $L \in Δ (D)$ Bob plays. Alice getting at least 0 utility in expectation is exactly saying that $M$ dominates $L$ . $□$

This proof is valid (you can check the details), so why doesn't it generalize to infinite subsets $D$ , and in particular $D = Δ (C)$ ? The problem is that games with infinitely many options need not have Nash equilibria. For example consider the game where Alice and Bob each choose a natural number, and whoever chooses the larger number wins.

Fortunately, often in cases like this, you can get past finiteness assumptions by instead using compactness assumptions, and $Δ (C)$ is compact. Indeed, games with a compact option space and continuous utility functions always have mixed strategy equilibria.

Unfortunately, the game we constructed does not have a continuous utility function! This is easy to see, because if $V$ assigns probability 1 to a single utility function $v$ , if $v (A) > v (B)$ , then Alice wins and gets utility 1, but as we continuously move around $A$ , we can discontinuously jump to the game being a tie, and then to Bob winning.

Fortunately, there are a bunch of papers analyzing situations like this. Discontinuities like this show up a bunch in auctions, which also have an infinite compact option space and discontinuous utilities, resulting from discontinuities in who wins the auction.

Unfortunately, Sam Eisenstat and I spent a while looking through a bunch of papers like this, and failed to find anything that we could apply. Several things looked like they might be able to work, but everything we tried ultimately turned out to be a dead end.

A Limit of Finite Games

The above partial result is actually pretty practically useful on its own. Even if maximal lottery-lotteries do not exist, you can always just take $D = D_{n}$ to be the set of all lotteries that assign each candidate a probability that is a multiple of $\frac{1}{n}$ for some large natural number $n$ . Because of this, practically speaking, we can use the maximal lottery-lotteries voting system today, without ever proving the conjecture!

Further, we can consider what happens as we send $n$ to infinity. If there is an odd number of voters that each have a utility function in general position, we will always get a unique distribution on $M_{n} \in Δ (D_{n})$ that dominates all other distributions on $D_{n}$ , and we can look at what happens to $M_{n}$ as $n$ goes to infinity. Hopefully this converges, but even if it doesn't, we can take any limit point, and ask whether that limit point is a maximal lottery-lottery. My guess is that the sequence does in fact converge, and that the (unique) limit point is a maximal lottery-lottery, but I have not had any luck yet proving either of these.

However, this enables us to get some empirical results! We can just compute some of these finite approximations. Even with three candidates, we have to solve a game with $n^{2}$ different options, and I have not yet optimized it beyond using an off the shelf linear programming solver in Haskell, running for a few minutes, so the highest I got was $n = 45$ . (I am sure we can do much better.)

I took three candidates and three voters, and gave each voter a utility function in general position. Here is a picture of $M_{30}$ . The blank space means that 0 (or near 0) utility is put there. The numbers show the negative of the natural logarithm of the probability that that point is chosen. (Remember, this is a distribution on distributions on a three element set, or equivalently a distribution on the triangle.)

______________________4.4.5.5.5.3.4.4.5.5.5.5.4.5.5.__________
 __________________________7.____________4.6.5.8.5.4.________
  __________________4.5.5.______6.5.__5.__5.9.5.4.4.4.______
   ________________4.5.5.4.______5.____5.__5.__4.4.5.5.____
    ______________5.5.5.5.7.____5.4.5.7.5.108.6.5.4.4.4.5.
     ______________5.________________________5.4.5.____7.
      ____________7.5.4.5.____________6.5.6.__4.__5.6.__
       ______5.4.5.8.__5.8.____6.5.__6.__7.__6.4.6.4.5.
        ____6.7.5.5.5.5.__5.6.8.6.5.7.5.____6.5.5.__4.
         6.6.5.4.5.4.4.5.6.__6.__6.5.__6.____5.6.7.4.
          __5.6.5.________5.__5.6.________5.6.8.5.5.
           4.5.5.__4.6.__5.6.7.5.6.6.____6.4.5.7.4.
            5.4.5.5.5.__5.5.5.7.5.________5.6.4.4.
             6.5.5.5.6.__5.__5.5.6.____7.8.4.7.7.
              5.5.5.5.5.____5.5.5.5.__5.6.7.__4.
               7.4.5.6.__6.5.5.4.6.____4.4.5.5.
                4.__8.5.__5.7.__5.5.5.__6.____
                 5.6.6.6.5.6.5.______________
                  4.________________________
                   ________________________
                    ______________________
                     ____________________
                      __________________
                       ________________
                        ______________
                         ____________
                          __________
                           ________
                            ______
                             ____
                              __

$M_{40}$ for the same candidates and voters looks similar, but with less detail, and some minor changes. This is a lot of data, but since we are going to use it to sample and then sample from the sample, for the purpose of maximal lottery-lotteries, we only really care about the probability each candidate is elected. For the above example, we get (0.262, 0.415, 0.323) for $M_{30}$ and (0.263,0.417,0.320) for $M_{40}$ , which seems like some slight empirical evidence towards converging. Obviously there is a lot of room for a much more careful and larger experimental analysis.

Fractals!?!

I believe that maximal lottery-lotteries exist, and are the limit of the above finite approximations, and (when they don't put all probability mass on the distribution that puts all probability mass on a single candidate) usually have some fractal structure. I think the complexity of the above picture is evidence of this, but I also have some mathematical intuition for why this makes sense (which feels hard to put into words):

Being a Nash equilibrium involves equalizing a bunch of constraints. These constraints are combined with the fact that the distribution is supported entirely within the triangle, and so where probability mass would naturally want to be placed outside the triangle, it gets cut off on the boundary. When it is cut off like this, something has to change inside the triangle to fix new constraints that become broken, and this causes the constraints to sort of reflect off the boundary of the triangle, somewhat like ripples. (Some of this intuition is coming from seeing similar things happen when studying nim.) Sorry that I don't have a more articulate description, but the point is, I think we are getting fractals.

Unfortunately, I think this is going to make it harder to show that maximal lottery-lotteries exist, since we will likely not have simple closed forms of what the maximal lottery-lotteries are.

A Generalization of Colonel Blotto

Another way to look at maximal lottery-lotteries is as a generalization of the Colonel Blotto game.

In the the continuous Colonel Blotto game, there are two opposing officers that each have some resources, that they can distribute between some battlefields. We will assume that they each have 1 total unit of resources. Whoever sends the most resources to any given battlefield wins that battlefield. (If they send the same amount, they each win half the battlefield.) Each officer gets utility equal to the number of battlefields that they win. This game and its variants have been analyzed quite a bit over the last century.

Finding maximal lotteries is like solving a variant of the Colonel Blotto game. In the original game, you choose how to distribute resources from the simplex where each battlefield gets non-negative resources, and the total of all the resources is 1, In this variant, you instead have some other convex polytope representing the allowable ways to distribute resources.

To reduce finding maximal lottery-lotteries to a Colonel Blotto game, we consider each voter to be a battlefield. (We will only discuss the case where there is a finite set of equal weight voters here.) Each candidate can be thought of as assigning a utility to each voter, which we can also interpret as sending a number of resources equal to that utility. Thus, the polytope of allowable ways to send resources to battlefields is just the convex hull of these points that come from the candidates. Each point in this convex hull corresponds to (at least) one distribution on candidates, and a solution to this Colonel Blotto game corresponds to a maximal lottery-lottery.

This old RAND paper analyzing Colonel Blotto, seems like some further evidence that we might be looking at fractals.

A Call for Help

I think that proving the existence of maximal lottery-lotteries would actually be a substantial advance for voting theory. (Although it might take some work to get people interested in something that challenges this many of the assumptions of the field.) However, I am not intending to work on this anymore. If you want to take a shot at proving they exist, and have questions, get in touch with me.

Without a proof of existence, I am probably not going to bother writing this up as more than these blogposts, but if anyone manages to prove it, I would be happy to write a paper together. Also if anyone feels very excited about working on this and getting it published in spite of not having a proof, I could maybe be up for collaborating on something like that, especially if someone collects a bunch of experimental evidence and better fractal pictures and is willing to do a lot of the writing.

[-]paulfchristiano2y*170

(I no longer thing this strategy works, see the thread here; sorry for wasting your time Scott!)

Here's an approach which I think could work, though there are definitely some finicky details (including a potentially-fatal question about convergence at the end, which I couldn't deal with---and which I think may not be the weakest link given that the other steps are also a bit shaky).

For lottery-lotteries and $B$ , write:

$f (A, B) = P_{L_{A} \sim A, L_{B} \sim B, u \sim V} [E_{a \sim L_{A}} [u (a)] > E_{B \sim L_{B}} [u (b)]] - P_{L_{A} \sim A, L_{B} \sim B, u \sim V} [E_{B \sim L_{B}} [u (b)] > E_{a \sim L_{A}} [u (a)]]$

We say that B strictly dominates A if $f (A, B) < 0$ .

Lemma: if $B$ strictly dominates $A$ , then there is a continuous $B^{'}$ that also strictly dominates $A$ , i.e. such that $B^{'}$ has a density with respect to Lebesgue measure and $f (A, B^{'}) < 0$ .

(ETA: this lemma is false, see comment from Scott below. I think it's fixed but am not sure.)

Proof: (I'll assume for convenience that there is a finite set of $m$ voters although I think this is easy to relax. We could assume that $B$ is a point mass if we wanted though obviously $B^{'}$ won't be. I think this could be greatly simplified.)

Suppose that $f (A, B) = - ε$ . For each utility function $u$ in the support of the electorate $V$ we'll define $X_{u}$ as the space of values for utility function $u$ that occur with positive probability under $A$ . Note that $X_{u}$ is countable and hence that there is a finite set $X_{u}^{'} \subset X_{u}$ which has at least $1 - \frac{ε}{2 m}$ of the probability mass. Let $L_{u}$ be the space of lotteries that have a utility in $X_{u}^{'}$ . Let $L$ be the union of $L_{u}$ over all the utility functions $u$ .

The idea is that $L$ is just a finite union of hyperplanes, and so it divides the space of lotteries into a finite set of open regions. Within each of these regions, continuously shifting $B$ 's probability between nearby lotteries results in continuous changes in $f (A, B)$ , plus a discontinuous term whose magnitude is at most $m \frac{ε}{2 m} = \frac{ε}{2}$ (corresponding to the positive-probability utilities in $X_{u}$ that aren't in $X_{u}^{'}$ ).

If $B$ assigns probability $0$ to $L$ then it is trivial to construct $B^{'}$ by spreading out $B$ continuously within each of these regions: there is guaranteed to be some spreading that changes $f (A, B)$ by strictly less than $ε$ (since we can make the continuous part of the change arbitrarily small and the discontinuous part is at most $\frac{ε}{2}$ ) and so we can find some way of spreading out mass that results in a continuous $B^{'}$ with $f (A, B^{'}) < 0$ .

If $B$ assigns positive probability to $L$ we need one more step. The idea is that for each point in $L$ we can find a "safe" direction to shift the probability from $B$ so that it's no longer in $L$ : if we pick a random direction each voter prefers to move one way or the other, and so one direction must have majority approval (note that the argument would break at this point if $f (A, B)$ depended on the probability that $B$ was at least as good as $A$ , rather than being defined symmetrically). Once we've picked such a direction for every point on $L$ , we can associate all of the probability from $L$ into one of the adjacent open regions and proceed as before. (ETA: this step fails if you are on the edge of the simplex.)

(This lemma might be enough to prove the result when combined with standard fixed point theorems. I'll finish by using standard tools from CS but that may just be because it's what I'm familiar with. I also can't easily do the convergence analysis at the end so that might not work and/or be much simpler from a mathematical perspective.)

Proving the theorem given the lemma: We'll describe a sequence of distributions $A_{T} \to A_{\infty}$ such that $f (A_{T}, B) < - ε$ implies that $B$ has $- Ω (ε \sqrt{T})$ entropy.

We'd like the sequence to be convergent $A_{T} \to A_{\infty}$ in the sense that for any continuous $B$ , $f (A_{T}, B) \to f (A_{\infty}, B)$ . If this were the case then we'd infer that we can't have $f (A_{\infty}, B) < 0$ for a continuous $B$ , since that would give us an absolute $ε$ which $f (A_{T}, B) < - ε$ for all sufficiently large $T$ , implying that $B$ has $- \infty$ entropy. By the main lemma, we'd conclude that no $B$ (continuous or otherwise) can strictly dominate $A_{\infty}$ . For now I'll present the algorithm to generate $A_{T}$ , in the next section I'll discuss convergence.

Our construction is follow-the-regularized leader with a standard analysis for playing 2-player games. It doesn't converge to a Nash equilibrium but I think it will still be good enough for us.

Let $H (A)$ be the entropy of a lottery-lottery (relative to Lebesgue measure on the simplex) and take $A_{T} = arg {max}_{A} (H (A) + \sum_{t < T} α_{t} f (A, A_{t}))$ for a sequence $α_{t} = Θ (\frac{1}{\sqrt{T}})$ (the exact decay rate of $α_{t}$ isn't important as long as it goes to zero but the sum diverges). Note that $A_{T} (L) \propto exp (- \sum_{t < T} α_{t} f (A, A_{t}))$ . and that $f \in [- 1, 1]$ . As a result, the distributions $A_{T} (L)$ change very slowly, and we have $f (A_{T + 1}, X) = f (A_{T}, X) + O (α_{T})$ for any lottery-lottery $X$ .

Now suppose that $lim f (B, A_{t}) > ε$ . Since $\sum_{t} α_{t}$ diverges, we can find arbitrarily large $T$ such that $\sum_{t < T} α_{t} f (B, A_{t}) \geq Ω (ε \sum_{t < T} α_{t}) = Ω (ε \sqrt{T})$ . Then:

Since $A_{T}$ was picked as the maximizer: $H (B) + \sum_{t < T} α_{t} f (B, A_{t}) \leq H (A_{T}) + \sum_{t < T} α_{t} f (A_{T}, A_{t})$
Then we can split off the last term from that sum: $H (A_{T}) + \sum_{t < T - 1} α_{t} f (A_{T}, A_{t}) + α_{T - 1} f (A$

LESSWRONG
LW

75