(I no longer thing this strategy works, see the thread here [LW(p) · GW(p)]; 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 $A$ and $B$, write:

• $f(A,B)=P_{L_A\sim A,L_B\sim B,u\sim V}[E_{a\sim L_A}\left[u\right(a\left)\right]>E_{B\sim L_B}\left[u\right(b\left)\right]]-P_{L_A\sim A,L_B\sim B,u\sim V}[E_{B\sim L_B}\left[u\right(b\left)\right]>E_{a\sim L_A}\left[u\right(a\left)\right]]$

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

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

(ETA: this lemma is false, see comment from Scott below [LW(p) · GW(p)]. I think it's fixed [LW(p) · GW(p)] 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^{\prime }$ won't be. I think this could be greatly simplified.)

Suppose that $f(A,B)=-\epsilon$. 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^{\prime }\subset X_u$ which has at least $1-\frac{\epsilon }{2m}$ of the probability mass. Let $L_u$ be the space of lotteries that have a utility in $X_u^{\prime }$. 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{\epsilon }{2m}=\frac{\epsilon }{2}$ (corresponding to the positive-probability utilities in $X_u$ that aren't in $X_u^{\prime }$).

If $B$ assigns probability $0$ to $L$ then it is trivial to construct $B^{\prime }$ 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 $\epsilon$ (since we can make the continuous part of the change arbitrarily small and the discontinuous part is at most $\frac{\epsilon }{2}$) and so we can find some way of spreading out mass that results in a continuous $B^{\prime }$ with $f(A,B^{\prime })<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)<-\epsilon$ implies that $B$ has $-\Omega \left(\epsilon \sqrt{T}\right)$ 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 $\epsilon$ which $f(A_T,B)<-\epsilon$ 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\left(A\right)$ be the entropy of a lottery-lottery (relative to Lebesgue measure on the simplex) and take $A_T=\arg {max}_A\left(H\right(A)+{\sum }_{t<T}{\alpha }_{t}f(A,A_t\left)\right)$ for a sequence ${\alpha }_t=\Theta \left(\frac{1}{\sqrt{T}}\right)$ (the exact decay rate of ${\alpha }_t$ isn't important as long as it goes to zero but the sum diverges). Note that $A_T\left(L\right)\propto \exp (-{\sum }_{t<T}{\alpha }_{t}f(A,A_t\left)\right)$. and that $f\in [-1,1]$. As a result, the distributions $A_T\left(L\right)$ change very slowly, and we have $f(A_{T+1},X)=f(A_T,X)+O\left({\alpha }_T\right)$ for any lottery-lottery $X$.

Now suppose that  $limf(B,A_t)>\epsilon$. Since ${\sum }_t{\alpha }_t$ diverges, we can find arbitrarily large $T$ such that ${\sum }_{t<T}{\alpha }_{t}f(B,A_t)\ge \Omega \left(\epsilon {\sum }_{t<T}{\alpha }_t\right)=\Omega \left(\epsilon \sqrt{T}\right)$. Then:

• Since $A_T$ was picked as the maximizer: $H\left(B\right)+{\sum }_{t<T}{\alpha }_{t}f(B,A_t)\le H\left(A_T\right)+{\sum }_{t<T}{\alpha }_{t}f(A_T,A_t)$
• Then we can split off the last term from that sum: $H\left(A_T\right)+{\sum }_{t<T-1}{\alpha }_{t}f(A_T,A_t)+{\alpha }_{T-1}f(A_T,A_{T-1})$
• Then we can use the fact that $A_{T-1}$ was itself a maximizer, to replace every $A_T$ except the last with $A_{T-1}$, and obtain: $H\left(B\right)+{\sum }_{t<T}{\alpha }_{t}f(B,A_t)\le H\left(A_{T-1}\right)+{\sum }_{t<T-1}{\alpha }_{t}f(A_{T-1},A_t)+{\alpha }_{T-1}f(A_T,A_{T-1})$
• Continuing in this way, we get $H\left(B\right)+{\sum }_{t<T}{\alpha }_{t}f(B,A_t)\le H\left(A_0\right)+{\sum }_{t<T}{\alpha }_{t}f(A_{t+1},A_t)$
• But now we use the fact that each summand $f(A_{t+1},A_t)=f(A_t,A_t)+O\left({\alpha }_t\right)=O\left({\alpha }_t\right)$, since $f$ is symmetric and $f(A_{t+1},X)\approx f(A_t,X)$.
• Thus $H\left(B\right)+\Omega \left(\epsilon \sqrt{T}\right)\le H\left(B\right)+{\sum }_{t<T}{\alpha }_{t}f(B,A_t)\le H\left(A_0\right)+{\sum }_{t<T}O\left({\alpha }_t^2\right)=H\left(A_0\right)+O\left(\log T\right)$
• Thus $H\left(B\right)<-\Omega \left(\epsilon \sqrt{T}\right)$

(Note that we used the finite number of candidates at this step to get $H\left(A_0\right)=O\left(1\right)$. Effectively we use finite candidates to show that there is only finitely much space, and use the continuity of $B$ to argue that we only need to learn up to finite precision, and therefore this is no worse than a finite learning problem.)

Convergence: we want to argue that there exists a distribution $A_{\infty }$ such that $f(A_T,B)\to f(A_{\infty },B)$ for any continuous $B$. I don't remember my topology very well, but I think we can do this as long as $A_T\left(S\right)$ converges to a limit for every open set $S$. I can just take $A_{\infty }\left(S\right)$ to be that limit, and under compactness I get a probability distribution.

(ETA: I think we can actually use any limit point and don't need convergence, see below [LW(p) · GW(p)]. So I think this is fine but am not sure.)

So we need to rule out the situation where there is some open set $S$ and real numbers $\ell <h$ such that $A_T\left(S\right)<\ell$ and $A_T\left(S\right)>h$ each happen infinitely often. This seems like a really messed up situation that shouldn't happen, but I don't have a clean proof tonight.

Some notes that make me think we should be fine:

• We don't actually need the $A_T$ to converge to a limit, we could define $A_{\infty }=lim\frac{\sum {\alpha }_t{A}_t}{\sum {\alpha }_t}$ if that limit exists. And if we want we can take ${\alpha }_T=\frac{1}{T}$ or ${\alpha }_T=\frac{1}{\log T}$ and the argument above still goes through.
• If $A_{T_1}\left(S\right)<\ell$ but $A_{T_2}\left(S\right)>h$ then the two distributions must be fairly far apart and so the average of the distributions has significantly higher entropy than the average of their entropies. That's a strange situation, since we picked each $A_T$ to maximize entropy (plus the linear function $\sum {\alpha }_{t}f(A,A_t)$).
• By sequential compactness, we can extract a pair of lottery-lotteries $A_{\ell }$ and $A_h$ at a significant distance from one another such that the iterates get arbitrarily close to each of them infinitely often. That seems even more messed up.
• If we really have a problem here, it seems like we can extend the algorithm above to make it converge more nicely by adding traders who push $A\left(S\right)$ back into the interval $[\ell ,h]$ (such that if you go out of the interval infinitely often they make an infinite profit and eventually enforce a hard constraint on $A\left(S\right)$).

I'll probably revisit this tomorrow, but overall non-convergence seems weird up enough that I have a higher probability of something going wrong at some other step in the argument. I think that the main issues with convergence are really the ones in the first lemma that let us focus on continuous $B$.

Epistemic status: rough sketch, there might be holes but I don't see any atm.

I think you need to slightly weaken the definition of an MLL and then you'll have an existence theorem.

Let's start with general discontinuous games. We have a game between two players, with pure strategy spaces $X_1$ and $X_2$ that we assume to be compact Polish spaces and (discontinuous) utility functions $u_{1,2}:X_1\times X_2\to [0,1]$. Then we can take the closure of the graphs of $u_{1,2}$ and get upper hemicontinuous multivalued utility functions. I claim that for such multivalued games, Nash equilibria (in some sense) exist.

Let $X$ be a compact Polish space and $f\subseteq X\times [0,1]$ a multivalued upper hemicontinuos function on it. What does it mean for $x\in X$ to be a "maximum" of $f$? We can define it as follows: for any $y\in X$, the maximal possible value of $f\left(x\right)$ is greater or equal to the lowest possible value of $f\left(y\right)$. It is not hard to see that maxima form a non-empty closed set. This leads to a corresponding notion of "best response" in multivalued games, and a corresponding notion of Nash equilibrium.

Notice that since we only care about the maximal and minimal possible values of $f\left(x\right)$, we might as well require that $f$ takes convex multivalues (i.e. closed intervals), since otherwise we can always take pointwise convex hull. Expected values of intervals can be defined by separately taking the expected value of the upper and lower ends of the interval.

I think that the existence of Nash equilibria follows from the Kakutani theorem in the usual way. The key observation is, for an upper hemicontinuous function, the maximal possible value is a (single-valued) upper semicontinuous function and the lowest possible value is a (single-valued) lower semicontinuous function. This implies that the best-response mapping is upper hemicontinuous.

Applying it to MLL, what I think we get is a notion of "weak" dominance where we only require that $Pr\left[v\right(B)>v(A\left)\right]\le \frac{1}{2}$, and otherwise the definition is the same.

I have a reduction of this problem to a (hopefully) simpler problem. First up, establish the notation used.

[n] refers to the set $\left\{\mathrm{1...}n\right\}$. $n$ is the number of candidates. Use $C$ as an abbreviation for the space $\Delta \left[n\right]$, it's the space of probability distributions over the candidates. View $C$ as embedded in $R^{n-1}$, and set the origin at the center of $C$.

At this point, we can note that we can biject the following: 
1: Functions of type $\left[n\right]\to [0,1]$ 
2: Affine functions of type $C\to [0,1]$ 
3: Functions of the form $\lambda x.⟨a,x⟩+c$, where $x,a\in R^{n-1}$, and and $c\in R$, and everything's suitably set so that these functions are bounded in $[0,1]$ over $C$. (basically, we extend our affine function to the entire space with the Hahn-Banach theorem, and use that every affine function can be written as a linear function plus a constant) We can reexpress our distribution $V$ over utility functions as a distribution over these normal vectors $a$.

Now, we can reexpress the conjecture as follows. Is it the case that there exists a $\mu :\Delta C$ s.t. for all $\nu :\Delta C$, we have 

 Where $\text{sgn}$ is the function that's -1 if the quantity is negative, 0 if 0, and 1 if the quantity is positive. To see the equivalence to the original formulation, we can rewrite things as 

 Where the bold 1 is an indicator function. And split up the expectation and realize that this is a probability, so we get 

 And this then rephrases as 

 Which was the original formulation of the problem.

Abbreviating the function $E_{x,y,a\sim \mu \times \nu \times V}\left[\text{sgn}\right(⟨a,x-y⟩\left)\right]$ as $f(\mu ,\nu )$, then a necessary condition to have a $\mu :\Delta C$ that dominates everything is that 

 If you have this property, then you might not necessarily have an optimal $\mu$ that dominates everything, but there are $\mu$ that get a worst-case expectation arbitrarily close to 0. Namely, even if the worst possible $\nu$ is selected, then the violation of the defining domination inequality happens with arbitrarily small magnitude. There might not be an optimal lottery-lottery, but there are lottery-lotteries arbitrarily close to optimal where this closeness-to-optimality is uniform over every foe. Which seems good enough to me. So I'll be focused on proving this slightly easier statement and glossing over the subtle distinction between that, and the existence of truly optimal lottery-lotteries.

As it turns out, this slightly easier statement (that sup inf is 0 or higher) can be outright proven assuming the following conjecture.

Stably-Good-Response Conjecture: For every $\nu :\Delta C$, and $ϵ>0$, there exists a $\mu :\Delta C$ and a $\delta >0$ s.t. 

Pretty much, for any desired level of suckage and any foe $\nu$, there's a probability distribution $\mu$ you can pick which isn't just a good response (this always exists, just pick $\nu$ itself), but a stably good response, in the sense that there's some nonzero level of perturbation to the foe where $\mu$ remains a good response no matter how the foe is perturbed.

Theorem 1 Assuming the Stably-Good-Response Conjecture, ${sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )\ge 0$.

I'll derive a contradiction from the assumption that $0>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$. Accordingly, assume the strict inequality.

In such a case, there is some $ϵ$ s.t. $0>-ϵ>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$. Let the set $A_{\mu }:=\left\{\nu |f\right(\mu ,\nu )>-ϵ\}$. Now, every $\nu$ lies in the interior of $A_{\mu }$ for some $\mu$, by the Stably-Good-Response Conjecture. Since $\Delta C$ is a compact set, we can isolate a finite subcover and get some finite set $M$ of probability distributions $\mu$ s.t. $\forall \nu \exists \mu \in M:f(\mu ,\nu )>-ϵ$.

Now, let the set $B_{\nu }:=\{\mu \in c.h(M\left)|f\right(\mu ,\nu )<-ϵ\}$. Since $-ϵ>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$, this family of sets manages to cover all of $c.h\left(M\right)$ (convex hull of our finite set.) Further, for any fixed $\nu$, $f(\mu ,\nu )$ is a continuous function $c.h\left(M\right)\to R$ (a bit nonobvious, but true nontheless because there's only finitely many vertices to worry about). Due to continuity, all the sets $B_{\nu }$ will be open. Since we have an open cover of $c.h\left(M\right)$, which is a finite simplex (and thus compact), we can isolate a finite subcover, to get a finite set $N$ of $\nu$ s.t. $\forall \mu \in c.h\left(M\right)\exists \nu \in N:f(\mu ,\nu )<-ϵ$. And now we can go 

 The first strict inequality was from how all $\mu \in c.h\left(M\right)$ had some $\nu \in N$ which made $f(\mu ,\nu )$ get a bad score. The $\ge$ was from expanding the set of options. The $=$ was from how $f$ is a continuous linear function when restricted to $c.h\left(M\right)\times c.h\left(N\right)$, both of which are compact convex sets, so the minimax theorem can be applied. Then the next $\ge$ was from restricting the set of options, and the $>$ was from how every $\nu \in \Delta C$ had some $\mu \in M$ that'd make $f(\mu ,\nu )$ get a good score, by construction of $M$ (and compactness to make the inequality a strict one).

But wait, we just showed $-ϵ>-ϵ$, that's a contradiction. Therefore, our original assumption must have been wrong. Said original assumption was that $0>{sup}_{\mu }{inf}_{\nu }f(\mu ,\nu )$, so negating it, we've proved that 

 As desired.