Diffractor comments on Open Problem in Voting Theory

[Diffractor]

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

$$E_{x,y,a\sim \mu \times \nu \times V}\left[\text{sgn}\right(⟨a,x-y⟩\left)\right]\ge 0$$

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

$$E_{x,y,a\sim \mu \times \nu \times V}[{\text{1}}_{⟨a,x⟩>⟨a,y⟩}-{\text{1}}_{⟨a,y⟩>⟨a,x⟩}]\ge 0$$

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

$$P_{x,y,a\sim \mu \times \nu \times V}[⟨a,x⟩>⟨a,y⟩]-P_{x,y,a\sim \mu \times \nu \times V}[⟨a,y⟩>⟨a,x⟩]\ge 0$$$$P_{x,y,a\sim \mu \times \nu \times V}[⟨a,x⟩>⟨a,y⟩]\ge P_{x,y,a\sim \mu \times \nu \times V}[⟨a,y⟩>⟨a,x⟩]$$

And this then rephrases as

$$P_{x,y,U\sim \mu \times \nu \times V}\left[U\right(x)>U(y\left)\right]\ge P_{x,y,U\sim \mu \times \nu \times V}\left[U\right(y)>U(x\left)\right]$$

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

$$\underset{\mu \in \Delta C}{sup}\underset{\nu \in \Delta C}{inf}f(\mu ,\nu )\ge 0$$

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.

$$\underset{{\nu }^{\prime }:d(\nu ,{\nu }^{\prime })<\delta }{inf}f(\mu ,{\nu }^{\prime })>-ϵ$$

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

$$-ϵ>\underset{\mu \in c.h\left(M\right)}{max}\underset{\nu \in N}{min}f(\mu ,\nu )\ge \underset{\mu \in c.h\left(M\right)}{max}\underset{\nu \in c.h\left(N\right)}{min}f(\mu ,\nu )=\underset{\nu \in c.h\left(N\right)}{min}\underset{\mu \in c.h\left(M\right)}{max}f(\mu ,\nu )\ge \underset{\nu \in c.h\left(N\right)}{min}\underset{\mu \in M}{max}f(\mu ,\nu )>-ϵ$$

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

$$\underset{\mu }{sup}\underset{\nu }{inf}f(\mu ,\nu )\ge 0$$

As desired.