A small addition: Also approval strategy "A" can be thought of as an adjustment of 0-info priors: If w(t) and w2(t) are the winner and 2nd place candidate of the poll at time t, strategy "A" is equivalent to using 0-info strategy with the adjusted priors
p(x,i,t+1) = (1-epsilon-epsilon^2) * delta(x,w(t)) + epsilon * delta(x,w2(t)) + epsilon^2 * p(x,i,t) for a sufficiently small epsilon>0, where delta(x,y)=1 if x=y, and delta(x,y)=0 if not x=y. However, it is probably well known that strategy "A" can lead to cycles, an easy example being the sincere preferences 1 A>>B>C>D 1 B>>C>D>A 1 C>D>A>>B 1 D>A>>B>C where the initial approval cutoffs are indicated by >>. It would be nice to know of any adjustment process which uses more than only the information about who won the last poll but still guarantees convergence. Any ideas? Jobst I wrote: > Dear folks! > > Forest's suggestion to perform an approval poll and use it to determine > a default lottery for use in the actual election made me think about > what happens in approval polls in the first place, especially when there > are repeated polls. > > In the following thoughts, I assume that (i) there is a sequence of > approval polls for some fixed set of voters and candidates, (ii) voters > answer the poll using 0-info approval strategy, and (iii) after each > poll all voters adjust their priors in some way to the poll's result. > The main question is, of course, whether such a process will eventually > converge to some kind of equilibrium. > > Recall that 0-info approval strategy means the following. Each voter i > assigns to each candidate x some cardinal utility u(x,i). For the > poll at time t, each voter i assigns to each candidate x some > prior winning probability p(x,i,t), and then i approves of x if > and only if u(x,i) is larger than the expected utility E(i,t) (= the > sum of p(y,i,t)*u(y,i) over all candidates y). > > The crucial point is how voters adjust their priors over time. I will > study two different natural scenarios here, one of which results in > guaranteed convergence, while the other may lead to cyclic behaviour. > > > I. > Let us first assume that voters only use the information about the > winner and winning approval of the last poll to adjust their priors. In > other words, they ignore all information about the success of the > non-winning candidates relative to each other. This means they > essentially adjust the winner's prior probability and leave the > conditional prior distribution of the rest as is. Formally, this means > that the adjusted priors before (t) and after (t+1) the poll fulfil the > equations > > p(x,i,t+1)/p(y,i,t+1) = p(x,i,t)/p(y,i,t) > > for all candidates x,y which both differ from w(t), the winner at > time t. (In case there is an approval tie t, let us assume that the > tie is broken using the previous poll's data.) > > If this is the case, then no matter what the precise adjustment > technique of the different voters is, the winner can change only a > finite number of times and will eventually become constant! > > To see this, note that the expected utility after the poll is a convex > combination of the expected utility before the poll and the utility of > the winner at time t: > > E(i,t+1) = lambda*E(i,t) + (1-lambda)*u(w(t),i) > > with lambda>0. > This implies that E(i,t+1)<u(w(t),i) if and only if E(i,t)<u(w(t),i). > Therefore, a voter i approves of w(t) at time t+1 if and only if > she approved of w(t) at time t. In other words, the approval score > of the winner w(t) in the next poll at time t+1 is the same as at > time t. Hence whenever the winner changes, the new winner has a larger > approval score than the old one. Obviously, this can happen only a > finite number of times, thus the winner is eventually constant and no > infinite cycles are possible. > > > II. > Let us now assume that all voters instead use the following adjustment > procedure: > > p(x,i,t+1) = (1-alpha)*p(x,i,t) + alpha*a(x,t)/s(t) > > where alpha is some constant, a(x,t) is x's approval score at time > t and s(t) is the total approval score at time t. That is, the > priors are moved a fixed amount towards the relative approval scores of > the last poll. > > Although this seems natural, too, it need not converge but can easily > produce cycles. For example, assume that alpha=2/3 and that there are > 3 voters i,j,k and 3 candidates x,y,z with utilities > > x y z > i 16 7 0 > j 0 16 7 > k 7 0 16 > > and common initial priors > > p(x,1)=11/26, p(y,1)=8/26, p(z,1)=7/26. > > Then for the first poll, the expected utilities are > > E(i,1) = (11*16+8*7)/26 = 232/26 > 7, > E(j,1) = (8*16+7*7)/26 = 177/26 < 7, > E(k,1) = (11*7+7*16)/26 = 189/26 > 7. > > This results in the 0-info strategy approval > > x y z > i + - - > j - + + > k - - + > score 1 1 2 (sum 4) > > That is, z wins the first poll, giving rise to the adjusted priors > > p(x,2) = 1/3*11/26 + 2/3*1/4 = 8/26, > p(y,2) = 1/3*8/26 + 2/3*1/4 = 7/26, > p(z,2) = 1/3*7/26 + 2/3*1/2 = 11/26. > > This is a cyclic permutation of the original priors, hence is is easy to > see that the subsequent winners are y,x,z,y,x,z,y,x, and ever so on > without converging to a constant winner. > > What if we assume a slower adjustment, putting alpha=1/2, for example? > Then the adjusted priors are > > p(x,2) = 1/2*11/26 + 1/2*1/4 = 35/104, > p(y,2) = 1/2*8/26 + 1/2*1/4 = 29/104, > p(z,2) = 1/2*7/26 + 1/2*1/2 = 40/104. > > Then for the second poll, the expected utilities are now all larger than 7: > > E(i,2) = (35*16+29*7)/104 = 7.336... > 7, > E(j,2) = (29*16+40*7)/104 = 7.153... > 7, > E(k,2) = (35*7+40*16)/104 = 8.509... > 7. > > This results in the 0-info strategy approval > > x y z > i + - - > j - + - > k - - + > score 1 1 1 (sum 3) > >>From this point on, the adjusted priors get closer and closer to 1/3 and > the polls only repeat the above result. This suggests the conjecture > that alpha can always be chosen small enough to ensure convergence. > > > Any other ideas how one might adjust one's 0-info priors using poll data? > > > Jobst > > ---- > Election-methods mailing list - see http://electorama.com/em for list info > ---- Election-methods mailing list - see http://electorama.com/em for list info