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