(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).
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.
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 Xu as the space of values for utility function u that occur with positive probability under A. Note that Xu is countable and hence that there is a finite set X′u⊂Xu which has at least 1−ε2m of the probability mass. Let Lu be the space of lotteries that have a utility in X′u. Let L be the union of Lu 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ε2m=ε2 (corresponding to the positive-probability utilities in Xu 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 ε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 AT→A∞ such that f(AT,B)<−ε implies that B has −Ω(ε√T) entropy.
We’d like the sequence to be convergent AT→A∞ in the sense that for any continuous B, f(AT,B)→f(A∞,B). If this were the case then we’d infer that we can’t have f(A∞,B)<0 for a continuous B, since that would give us an absolute ε which f(AT,B)<−ε for all sufficiently large T, implying that B has −∞ entropy. By the main lemma, we’d conclude that no B (continuous or otherwise) can strictly dominate A∞. For now I’ll present the algorithm to generate AT, 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 AT=argmaxA(H(A)+∑t<Tαtf(A,At)) for a sequence αt=Θ(1√T) (the exact decay rate of αt isn’t important as long as it goes to zero but the sum diverges). Note that AT(L)∝exp(−∑t<Tαtf(A,At)). and that f∈[−1,1]. As a result, the distributions AT(L) change very slowly, and we have f(AT+1,X)=f(AT,X)+O(αT) for any lottery-lottery X.
Now suppose that limf(B,At)>ε. Since ∑tαt diverges, we can find arbitrarily large T such that ∑t<Tαtf(B,At)≥Ω(ε∑t<Tαt)=Ω(ε√T). Then:
Since AT was picked as the maximizer: H(B)+∑t<Tαtf(B,At)≤H(AT)+∑t<Tαtf(AT,At)
Then we can split off the last term from that sum: H(AT)+∑t<T−1αtf(AT,At)+αT−1f(AT,AT−1)
Then we can use the fact that AT−1 was itself a maximizer, to replace every AT except the last with AT−1, and obtain: H(B)+∑t<Tαtf(B,At)≤H(AT−1)+∑t<T−1αtf(AT−1,At)+αT−1f(AT,AT−1)
Continuing in this way, we get H(B)+∑t<Tαtf(B,At)≤H(A0)+∑t<Tαtf(At+1,At)
But now we use the fact that each summand f(At+1,At)=f(At,At)+O(αt)=O(αt), since f is symmetric and f(At+1,X)≈f(At,X).
(Note that we used the finite number of candidates at this step to get H(A0)=O(1). 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∞ such that f(AT,B)→f(A∞,B) for any continuous B. I don’t remember my topology very well, but I think we can do this as long as AT(S) converges to a limit for every open set S. I can just take A∞(S) 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. 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 ℓ<h such that AT(S)<ℓ and AT(S)>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 AT to converge to a limit, we could define A∞=lim∑αtAt∑αt if that limit exists. And if we want we can take αT=1T or αT=1logT and the argument above still goes through.
If AT1(S)<ℓ but AT2(S)>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 AT to maximize entropy (plus the linear function ∑αtf(A,At)).
By sequential compactness, we can extract a pair of lottery-lotteries Aℓ and Ah 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(S) back into the interval [ℓ,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(S)).
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.
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.
Haven’t ready through everything yet, but I am skeptical here with respect to points on the boundary of the simplex.
I agree that’s a bug in the proof (and the lemma obviously can’t be true as written given that e.g. if 90% of voters are single-issue voters who hate candidate X, then no continuous lottery-lottery can dominate a lottery that puts 0 probability on X).
I haven’t thought about how serious this is. It feels like we could hope to fix things by considering a game where you pick (i) which candidates to give probability 0, which is a discrete choice from a set of size 2n−1and hence relatively unproblematic, (ii) what distribution to play within the corresponding simplex, where we can make a similar continuity argument to handle the infinitely many options.
I don’t know if that plays nicely, I’ll probably think about it tomorrow.
At face value it looks like it will be OK: we just define the same algorithm, but now we define a probability distribution over 2n simplices and define conditional entropy as the sum of the discrete entropy of the outer choice + the continuous entropy over the chosen simplex. (But there are a bunch of subtleties.)
ETA: you can’t just take the topology generated by the open sets of every face and then run my argument in exactly the same way, because that isn’t compact and so we don’t get a limit point A∞. But we can define our algorithm over the disjoint union of all the faces which is compact (note that a given lottery-lottery is no longer uniquely represented but that’s not a problem). The lemma still shows that if any B strictly dominates A∞ then there must be a continuous B (in the disjoint union) that dominates A∞. And we can still find arbitrarily large T for which f(B,∑t<TαtAt)>ε, which leads to a contradiction just as before. So overall I think that this fix works.
Ok, here are some questions to help me understand/poke holes in this proof. (Don’t think too hard on these questions. If the answers are not obvious to you, then I am asking the wrong questions.
Does the argument (or a simple refactorization of the argument you also believe) decompose through “If B strictly dominates A∞, then there is a B′ that also strictly dominates A∞ such that the probability of any voter being indifferent between something sampled from B′ and something sampled from A∞ is 0 (or negligable).”
If Yes to 1, do you believe the above lemma is also true for an arbitrary A?
If Yes to 1, do you believe the above lemma is true if we replace “strictly dominates” with “f(B,A)>x” for some fixed x>0.
If No to 1, is there some minor modification that will give me a similar looking lemma the argument does decompose through?
#1: It doesn’t. The previous version implied that there was a B′ for which the probability of ties was arbitrarily low, but the new version can have lots of voters who are indifferent. If B puts its mass in the interior of a face F, then we redistribute probability mass within the interior of F, but some voters assign the same utility to everything in F.
#4: The current lemma is:
If B strictly dominates A, then there is a face F of the simplex and a B’ which is continuous over F such that B’ strictly dominates A.
I think this is OK (though still lots of room for subtleties). Spelling this aspect out in more detail:
Fix some arbitrary A which is strictly dominated by B.
We claim that there exists a face F and a continuous B’ over F such that B’ also dominates A.
Sample some lottery from B to obtain a concrete lottery b that strictly dominates A.
If b is a vertex we are done. Otherwise, let F be the face such that b lies in the interior of F.
For each voter, their level sets are either hyperplanes in F or else they are all of F.
We can ignore the voters who are indifferent within all of F, because any B’ supported in F will be the same as b from those voters’ perspectives.
Now define Xu,X′u,Lu,L as before, but restricting to the voters who have preferences within F.
We obtain a continuous distribution B’ for which f(B′,A)≈f(b,A) if we ignore the voters who were indifferent. But f(B′,A)=f(b,A) for the voters who are indifferent, so we have f(B′,A)≈f(b,A) overall.
(Of course this just goes through the existence of an open set of lotteries all of which strictly dominate A, we can just take B’ uniform over that set.)
This lemma is what we need, because we will run follow the leader over the space of pairs (F, A) where F is a face and A is a distribution over that face. So we conclude that the limit is not dominated by any pair (F, B’) where F is a face and B’ is a continuous distribution.
Actually we could take A∞ to be any limit point of A<T=∑t<TαtAt∑t<Tαt (in the sense that f(A∞,B) is a limit point of f(A<T,B) for any continuous B) and then get the same conclusion. I think compactness guarantees the existence of such a limit point (e.g. choose some countable basis for the topology and then restrict the sequence so that one open set after another has a limit), and so the convergence worries are resolved.
Hm, I’m now pretty skeptical about the limit step. In particular, if A<T(S) converges to a limit for every open set S, we can’t take A∞(S) to be the limit of those probabilities (since it doesn’t satisfy countable additivity even though the simplex is compact). In general the space of probability distributions is not compact in the relevant topology, and so I think we can’t possibly have f(AT,B)→f(A∞,B) based only on the fact that f(⋅,B) is the expectation of a bounded function.
This seems like it’s plausibly the same topological problem that would break fixed-point theorems, and so I think it’s the most likely candidate for where the whole thing breaks and why this strategy doesn’t make any progress.
There are various ways to try to route around the problem, but it feels like it may just be the same thing you’ve been working on, so it seems probably easier to start with looking for an examples where this breaks my algorithm and then confirming that it’s the same problem the other approaches run into.
To really break the strategy, what we’d want is a sequence AT and a lottery B such that f(AT,B)→0 but there is no way to take the limit A∞ (e.g. in earth mover distance) for which f(A∞,B)=0. If we found that then I could still try to argue that such sequences are never produced by the algorithm, but it would at least show I need a different proof strategy and likely indicate that the strategy didn’t make progress.
ETA here is easy counterexample:
There are three candidates, X, Y, Z. There is a voter who only likes X and a voter who only likes Y.
B puts 1⁄2 of its probability mass on Z, and the other half spread uniformly over X/Y lotteries.
AT puts its probability mass on lotteries between X and Y where X is almost certain to win (converging to certainty as T→∞).
In the limit, AT always wins the X voters, and it wins Y voters half of the time (whenever B picks Z) and so it has a 3⁄4 win probability.
It’s clear that AT→A∞ which puts all of its mass on X. So it always wins the X voters, and ties on the Y voters half of the time (when B samples Z), so it has a 5⁄8 win probability.
If we add a Z voter with half weight or something, then we’ll have f(AT,B)→0 but f(A∞,B)<0.
Still would take work to turn it into a counterexample for the original algorithm. Would be curious to do that and see if I actually believe that game ought to have an equilibrium (or to understand why it can’t be done).
And here’s a significantly worse counterexample, showing that there need not be any B′ near B such that limf(A<T,B′)<f(A∞,B):
There are three candidates X, Y, Z and there are three voters: one only likes X, one has u(X) = 2 and u(Y) = 3, one has u(X) = 2 and u(Z) = 3.
B puts all of its mass on X.
A<T puts 1⁄3 of its mass on X, 1⁄3 of its mass on a lottery between Y and Z with the probability of Y approaching 2⁄3 from above as T→∞, and 1⁄3 on a lottery between Y and Z with the probability of Y approaching 1⁄3 from below.
Under these conditions:
A∞ puts 1⁄3 of its mass on X, 1⁄3 on (2/3 Y, 1⁄3 Z), and 1⁄3 on (1/3 Y, 2⁄3 Z).
We can compute that A∞ never beats B, and loses 4⁄9 of the time.
On the other hand, every A<T beats B2⁄9 of the time (and still loses 4⁄9 of the time).
If B′ puts any mass on gambles where X doesn’t get 100% of the probability, it loses the X-loving voter.
As a result, any B′ near B must lose against A<T at least 2⁄9 of the time, and can win at most 5⁄9 of the time.
So there’s no way for it to match f(A∞,B)=−4/9.
In light of that example I think the basic proof strategy is probably no good. It may be tough to construct a concrete example where the algorithm fails, but if it works it would have to be due to some property other than the fact that no continuous B can beat infinitely many A<T, which is all I really wanted to do.
(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 A and B, write:
f(A,B)=PLA∼A,LB∼B,u∼V[Ea∼LA[u(a)]>EB∼LB[u(b)]]−PLA∼A,LB∼B,u∼V[EB∼LB[u(b)]>Ea∼LA[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 Xu as the space of values for utility function u that occur with positive probability under A. Note that Xu is countable and hence that there is a finite set X′u⊂Xu which has at least 1−ε2m of the probability mass. Let Lu be the space of lotteries that have a utility in X′u. Let L be the union of Lu 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ε2m=ε2 (corresponding to the positive-probability utilities in Xu 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 ε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 AT→A∞ such that f(AT,B)<−ε implies that B has −Ω(ε√T) entropy.
We’d like the sequence to be convergent AT→A∞ in the sense that for any continuous B, f(AT,B)→f(A∞,B). If this were the case then we’d infer that we can’t have f(A∞,B)<0 for a continuous B, since that would give us an absolute ε which f(AT,B)<−ε for all sufficiently large T, implying that B has −∞ entropy. By the main lemma, we’d conclude that no B (continuous or otherwise) can strictly dominate A∞. For now I’ll present the algorithm to generate AT, 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 AT=argmaxA(H(A)+∑t<Tαtf(A,At)) for a sequence αt=Θ(1√T) (the exact decay rate of αt isn’t important as long as it goes to zero but the sum diverges). Note that AT(L)∝exp(−∑t<Tαtf(A,At)). and that f∈[−1,1]. As a result, the distributions AT(L) change very slowly, and we have f(AT+1,X)=f(AT,X)+O(αT) for any lottery-lottery X.
Now suppose that limf(B,At)>ε. Since ∑tαt diverges, we can find arbitrarily large T such that ∑t<Tαtf(B,At)≥Ω(ε∑t<Tαt)=Ω(ε√T). Then:
Since AT was picked as the maximizer: H(B)+∑t<Tαtf(B,At)≤H(AT)+∑t<Tαtf(AT,At)
Then we can split off the last term from that sum: H(AT)+∑t<T−1αtf(AT,At)+αT−1f(AT,AT−1)
Then we can use the fact that AT−1 was itself a maximizer, to replace every AT except the last with AT−1, and obtain: H(B)+∑t<Tαtf(B,At)≤H(AT−1)+∑t<T−1αtf(AT−1,At)+αT−1f(AT,AT−1)
Continuing in this way, we get H(B)+∑t<Tαtf(B,At)≤H(A0)+∑t<Tαtf(At+1,At)
But now we use the fact that each summand f(At+1,At)=f(At,At)+O(αt)=O(αt), since f is symmetric and f(At+1,X)≈f(At,X).
Thus H(B)+Ω(ε√T)≤H(B)+∑t<Tαtf(B,At)≤H(A0)+∑t<TO(α2t)=H(A0)+O(logT)
Thus H(B)<−Ω(ε√T)
(Note that we used the finite number of candidates at this step to get H(A0)=O(1). 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∞ such that f(AT,B)→f(A∞,B) for any continuous B. I don’t remember my topology very well, but I think we can do this as long as AT(S) converges to a limit for every open set S. I can just take A∞(S) 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. 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 ℓ<h such that AT(S)<ℓ and AT(S)>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 AT to converge to a limit, we could define A∞=lim∑αtAt∑αt if that limit exists. And if we want we can take αT=1T or αT=1logT and the argument above still goes through.
If AT1(S)<ℓ but AT2(S)>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 AT to maximize entropy (plus the linear function ∑αtf(A,At)).
By sequential compactness, we can extract a pair of lottery-lotteries Aℓ and Ah 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(S) back into the interval [ℓ,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(S)).
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.
Haven’t ready through everything yet, but I am skeptical here with respect to points on the boundary of the simplex.
I agree that’s a bug in the proof (and the lemma obviously can’t be true as written given that e.g. if 90% of voters are single-issue voters who hate candidate X, then no continuous lottery-lottery can dominate a lottery that puts 0 probability on X).
I haven’t thought about how serious this is. It feels like we could hope to fix things by considering a game where you pick (i) which candidates to give probability 0, which is a discrete choice from a set of size 2n−1and hence relatively unproblematic, (ii) what distribution to play within the corresponding simplex, where we can make a similar continuity argument to handle the infinitely many options.
I don’t know if that plays nicely, I’ll probably think about it tomorrow.
At face value it looks like it will be OK: we just define the same algorithm, but now we define a probability distribution over 2n simplices and define conditional entropy as the sum of the discrete entropy of the outer choice + the continuous entropy over the chosen simplex. (But there are a bunch of subtleties.)
ETA: you can’t just take the topology generated by the open sets of every face and then run my argument in exactly the same way, because that isn’t compact and so we don’t get a limit point A∞. But we can define our algorithm over the disjoint union of all the faces which is compact (note that a given lottery-lottery is no longer uniquely represented but that’s not a problem). The lemma still shows that if any B strictly dominates A∞ then there must be a continuous B (in the disjoint union) that dominates A∞. And we can still find arbitrarily large T for which f(B,∑t<TαtAt)>ε, which leads to a contradiction just as before. So overall I think that this fix works.
Ok, here are some questions to help me understand/poke holes in this proof. (Don’t think too hard on these questions. If the answers are not obvious to you, then I am asking the wrong questions.
Does the argument (or a simple refactorization of the argument you also believe) decompose through “If B strictly dominates A∞, then there is a B′ that also strictly dominates A∞ such that the probability of any voter being indifferent between something sampled from B′ and something sampled from A∞ is 0 (or negligable).”
If Yes to 1, do you believe the above lemma is also true for an arbitrary A?
If Yes to 1, do you believe the above lemma is true if we replace “strictly dominates” with “f(B,A)>x” for some fixed x>0.
If No to 1, is there some minor modification that will give me a similar looking lemma the argument does decompose through?
#1: It doesn’t. The previous version implied that there was a B′ for which the probability of ties was arbitrarily low, but the new version can have lots of voters who are indifferent. If B puts its mass in the interior of a face F, then we redistribute probability mass within the interior of F, but some voters assign the same utility to everything in F.
#4: The current lemma is:
I still haven’t understood all of your argument, but have you missed the fact that some faces are entirely contained in L?
(Your arguments look similar to stuff we did when trying to apply this paper.)
I think this is OK (though still lots of room for subtleties). Spelling this aspect out in more detail:
Fix some arbitrary A which is strictly dominated by B.
We claim that there exists a face F and a continuous B’ over F such that B’ also dominates A.
Sample some lottery from B to obtain a concrete lottery b that strictly dominates A.
If b is a vertex we are done. Otherwise, let F be the face such that b lies in the interior of F.
For each voter, their level sets are either hyperplanes in F or else they are all of F.
We can ignore the voters who are indifferent within all of F, because any B’ supported in F will be the same as b from those voters’ perspectives.
Now define Xu,X′u,Lu,L as before, but restricting to the voters who have preferences within F.
We obtain a continuous distribution B’ for which f(B′,A)≈f(b,A) if we ignore the voters who were indifferent. But f(B′,A)=f(b,A) for the voters who are indifferent, so we have f(B′,A)≈f(b,A) overall.
(Of course this just goes through the existence of an open set of lotteries all of which strictly dominate A, we can just take B’ uniform over that set.)
This lemma is what we need, because we will run follow the leader over the space of pairs (F, A) where F is a face and A is a distribution over that face. So we conclude that the limit is not dominated by any pair (F, B’) where F is a face and B’ is a continuous distribution.
Ok, I believe this version of the Lemma, and am moving on to trying to get the rest of the argument.
Actually we could take A∞ to be any limit point of A<T=∑t<TαtAt∑t<Tαt (in the sense that f(A∞,B) is a limit point of f(A<T,B) for any continuous B) and then get the same conclusion. I think compactness guarantees the existence of such a limit point (e.g. choose some countable basis for the topology and then restrict the sequence so that one open set after another has a limit), and so the convergence worries are resolved.
Hm, I’m now pretty skeptical about the limit step. In particular, if A<T(S) converges to a limit for every open set S, we can’t take A∞(S) to be the limit of those probabilities (since it doesn’t satisfy countable additivity even though the simplex is compact). In general the space of probability distributions is not compact in the relevant topology, and so I think we can’t possibly have f(AT,B)→f(A∞,B) based only on the fact that f(⋅,B) is the expectation of a bounded function.
This seems like it’s plausibly the same topological problem that would break fixed-point theorems, and so I think it’s the most likely candidate for where the whole thing breaks and why this strategy doesn’t make any progress.
There are various ways to try to route around the problem, but it feels like it may just be the same thing you’ve been working on, so it seems probably easier to start with looking for an examples where this breaks my algorithm and then confirming that it’s the same problem the other approaches run into.
To really break the strategy, what we’d want is a sequence AT and a lottery B such that f(AT,B)→0 but there is no way to take the limit A∞ (e.g. in earth mover distance) for which f(A∞,B)=0. If we found that then I could still try to argue that such sequences are never produced by the algorithm, but it would at least show I need a different proof strategy and likely indicate that the strategy didn’t make progress.
ETA here is easy counterexample:
There are three candidates, X, Y, Z. There is a voter who only likes X and a voter who only likes Y.
B puts 1⁄2 of its probability mass on Z, and the other half spread uniformly over X/Y lotteries.
AT puts its probability mass on lotteries between X and Y where X is almost certain to win (converging to certainty as T→∞).
In the limit, AT always wins the X voters, and it wins Y voters half of the time (whenever B picks Z) and so it has a 3⁄4 win probability.
It’s clear that AT→A∞ which puts all of its mass on X. So it always wins the X voters, and ties on the Y voters half of the time (when B samples Z), so it has a 5⁄8 win probability.
If we add a Z voter with half weight or something, then we’ll have f(AT,B)→0 but f(A∞,B)<0.
Still would take work to turn it into a counterexample for the original algorithm. Would be curious to do that and see if I actually believe that game ought to have an equilibrium (or to understand why it can’t be done).
And here’s a significantly worse counterexample, showing that there need not be any B′ near B such that limf(A<T,B′)<f(A∞,B):
There are three candidates X, Y, Z and there are three voters: one only likes X, one has u(X) = 2 and u(Y) = 3, one has u(X) = 2 and u(Z) = 3.
B puts all of its mass on X.
A<T puts 1⁄3 of its mass on X, 1⁄3 of its mass on a lottery between Y and Z with the probability of Y approaching 2⁄3 from above as T→∞, and 1⁄3 on a lottery between Y and Z with the probability of Y approaching 1⁄3 from below.
Under these conditions:
A∞ puts 1⁄3 of its mass on X, 1⁄3 on (2/3 Y, 1⁄3 Z), and 1⁄3 on (1/3 Y, 2⁄3 Z).
We can compute that A∞ never beats B, and loses 4⁄9 of the time.
On the other hand, every A<T beats B 2⁄9 of the time (and still loses 4⁄9 of the time).
If B′ puts any mass on gambles where X doesn’t get 100% of the probability, it loses the X-loving voter.
As a result, any B′ near B must lose against A<T at least 2⁄9 of the time, and can win at most 5⁄9 of the time.
So there’s no way for it to match f(A∞,B)=−4/9.
In light of that example I think the basic proof strategy is probably no good. It may be tough to construct a concrete example where the algorithm fails, but if it works it would have to be due to some property other than the fact that no continuous B can beat infinitely many A<T, which is all I really wanted to do.
(I’ll retract the original proposal.)