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.
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.)