On 12 Mar 2005 at 16:10 PST, Forest Simmons wrote:
> Dear Ted, > > Your TAB method is what I used to call "Approval Seeded Bubble Sort." Hi Forest, thanks for the reference check. It figures that if anybody might have considered it earlier, it would have been you or Jobst ;-). But in my earlier enthusiasm, I mis-spoke in two respects. First: If you sort the candidates first by total approval, then do a careful bubble sort (order of operations *is* important), then this method turns out to be equivalent to Ranked Pairs (total approval), *not* Beatpath (total approval). So you could call it Total Approval Ranked Pairs (TARP), or RP(ta), or Approval Seeded Bubble Sort, but yes, they're all the same thing. Just to be clear what I'm talking about, Sort by approval so that the front of the list has highest approval. Starting at the second point in the list, move that candidate forward (higher) if it defeats higher candidates. Then start at the 3rd point in the list and bubble that candidate upward, etc. In Matlab/octave notation, say you have the pairwise matrix stored in the array A, with A(i,i) containing the total approval of candidate X(i). These octave (and possibly Matlab) operations will give you the winner: I = [1:N] ; % Initialize index array with 1 to N K = for i=1:N; K(i) = A(i,i); endfor % Approval sort keys [T,J] = sort([K' I'], 1) % sort by ascending approval, % also return index array I = flipud(J)(:,1) % Store descending approval % indices into index vector % Bubble sort, with a bias toward higher approval: for j=2:N i = j while ( A(I(i),I(i-1)) > A(I(i-1),I(i)) ) % Swap the indices to bubble the i-th candidate upward k = I(i-1) I(i-1) = I(i) I(i) = k i = i - 1 if ( i == 1 ) break endif endwhile endfor I think this is conceptually easier to grasp than to sort all defeats by the minimum approval of either contestant (total approval defeat strength), but the end result is the same. Any contests that are not considered in the while loop are the same defeats dropped by RP(ta). Unlike traditional ranked pairs, which is already fairly easy to explain, you don't have to rank the defeats, you don't have to discuss "consistency" (cycles), and you don't have to explicitly state that you're dropping defeats. All of those arise automatically from the two sort stages. IMO, this would definitely have a higher voter-appeal factor. TARP also has an intuitive "sports-like" analogy, particularly appropriate during this first week of March Madness (US college basketball playoffs): "Rank candidate 'seeds' in descending order of approval. For a candidate to move up in rank, it has to defeat all higher seeded teams in succession, and only after each of those has itself moved up in rank as much as possible." Jobst, as you said, this may indeed be equivalent to Kevin's approval-completed Condorcet, but I'd like to point out that there's no mention of elimination in this implementation, and the result is a social ordering. Not eliminating candidates too early, to my mind, is one of Condorcet's strongest arguments against plurality or IRV. So whenever possible, you should avoid any formulation that mentions elimination! I'll cover the second problem I found below. > Then after a year of thinking that it was my invention I came across an > article about the Kemeny Order in which the authors called our bubble > sort process "Local Kemenization" and suggested using it as a way of > refining various other orders including the Border order. > > One thing that bothered me was lack of reverse symmetry, so I eventually > came to this version: Is RP(wv) symmetric? I think total approval ranked pairs is symmetric with respect to the approval cutoff. In other words, if "X1>>X2" votes are changed to "X2>>X1" votes. > > Start with the approval order (greatest to least approval <--> top to > bottom). > > While any candidate is beaten by the candidate immediately above her ... > > swap the two adjacent candidates with the greatest "discrepancy" > > EndWhile > > The winner is the candidate that ends up at the top of the list. > > > It's like lining up recruits for drill, and sorting them into order of > height by successive swaps, most urgent first. > > "Discrepancy," like defeat strength can be measured in several ways. > > If you use margins, or some other symmetric measure, then the final order > reverses when all of the ballots are reversed. > > However this reverse symmetry may not be the best goal when trying to > discourage manipulation. I'm not sure that I consider lack of symmetry important. Here's the second problem I realized: > On Sat, 12 Mar 2005, Ted Stern wrote: >> - There is a strong disincentive to bullet vote or truncate (an >> exercise for the reader, but consider the 35:A>B>>C, 25:B, 40:C, in >> which B voters have truncated their true preference 25:B>A>>C). In TARP (aka ASBS), there is some disincentive to truncate preferences. But it is not as strong as I initially thought. For instance, in the example immediately above, B could still win with truncation. But the A block can use the ATLO-like option of placing its cutoff above B to force a C win if B tries to truncate. The B block would do better to appeal to the C voters to gain a rank below their approval cutoff. So strategy-wise, I think TARP / ASBS / RP(ta) is as strong as ATLO or Approval-weighted pairwise, but easier to implement and explain to voters. Jobst, I would even suggest that in many-candidate elections, it is as easy or easier than River. >> >> - There is a strong incentive to be generous with approval cutoff -- you >> want your nearest neighbors, if you will, to be considered earliest in the >> list. Well, not as strong an incentive to be generous with approval cutoff as I thought initially. But maybe it's enough. >> >> - Much less strategic incentive to equal rank due to the approval cutoff. >> Voters can express true preferences above the approval cutoff, AND below, >> without fear of hurting their candidate. >> I think this still stands. As others (Kevin? Gervase? Alex?) have mentioned during the last couple of days, it could be easier to simply have two sets of rankings, some approved and some disapproved. I think any even number of options from 6 to 10 would be adequate, with the approval cutoff in the middle. Perhaps 6 would be a good starting point for a public proposal. Ted -- Ted Stern (change reply address to tedstern at u dot washington dot edu) ---- Election-methods mailing list - see http://electorama.com/em for list info