[EM] Method space of 3-bloc, strictly-ranked scenarios

Sat Nov 26 15:00:16 PST 2016

Hi Kristofer,
De : Kristofer Munsterhjelm <km_elmet at t-online.de>À : Kevin Venzke <stepjak at yahoo.fr>; EM list <election-methods at electorama.com> Envoyé le : Samedi 26 novembre 2016 7h25Objet : Re: [EM] Method space of 3-bloc, strictly-ranked scenarios
>> ABABAACC: The MinMax group. This includes most MinMax methods (including>> also Schulze, MAM, etc.), DMC, Approval-Elimination Runoff, MAMPO, some>> scenarios of Kristofer's "linear" Condorcet method, a couple of obscure>> Woodall methods (MinGS and 3MaxGS), Condorcet//FPP, and probably a lot>> of other methods.>>> ABABABCC: Condorcet//IRV group, including Raynaud, Condorcet//KH, and>> most scenarios of Kristofer's "linear" method. Off the top of my head it>> should also include the "Woodall" and "Benham" methods.>>So the linear methods are somewhat more Minimax-y C//IRVs. That sort of>makes sense, in particular when even Condorcet/FPP is considered>Minmaxy. Moving closer to minmax makes the methods more monotone, but>they're still similar to C//IRV in being strategy resistant Condorcet>methods.
Sounds right although, within this framework, I can't even show that IRV is not monotone. I wonder if there could be a different cause of undesirablebehavior. Of the properties I have (and which make sense in the 8-scenario case), C//IRV lacks two properties compared to the MinMax group: it violatesa sort of mono-remove-bottom, and a property I can't quite generalize into words which says that the last choice of the largest faction shouldn't beelected.
(Incidentally the MinMax and C//IRV groups are the only Condorcet ones that satisfy a sort of participation property, in that a faction's lastchoice should not be elected if the withdrawal of that faction would electtheir compromise choice.)
>>> ABCBABCC: BPW (Eivind Stensholt's "Beats Plurality Winner" Condorcet>> method).>>Stensholt also has another method (which he has called SV):>>Let F(X) be the fraction of voters who gave X a first preference vote>(e.g. F(A) = 0.5 is half the voters put A first).>Let a = 1/2 - F(A), b = 1/2 - F(B), g = 1/2 - F(C).>If there's no cycle, the CW wins, otherwise WLOG suppose it's an ABCA>cycle. Then A's penalty is b/g, B's is g/a, and C's is a/b. Minimum>penalty wins.>>I guess this would produce the same results as BPW, but you could check.>>In my post about linear methods, I also mentioned this nonlinear method:>>Again WLOG let the cycle be ABCA. Then the scores are>>A's score: A>B * min(C>A, A>B)/fpC>B's score: B>C * min(A>B, B>C)/fpA>C's score: C>A * min(B>C, C>A)/fpB>>and greatest score wins. fpX is the number of first preferences for X.>>I kind of suspect the min() part is related to beatpaths. Isn't min(C>A,>A>B) the strength of the beatpath from C to B, i.e. from who beat A to>who A beats? Of course, the optimizer has no idea what concept it's finding.
Ok. I didn't know about Stensholt's other method, and I should check it out. And I did bring up our old emails to review the nonlinear method. The troubleis that methods that are sensitive to the "absolute" size differences betweenthe factions, tend to produce more than one DNA code. That's what was goingon when you see that I put the linear method under two groups: It has two codes. Most methods (even with 343 digits) only have one. But e.g. MinMax(margins) has seven, and FPP(ER-Fractional) has twelve...
>>You could also try BTR-IRV, which is IRV-like but sometimes not. It>consists of, in every round, beat whoever pairwise loses to the other of>the last two candidates sorted by Plurality count. It would be more like>the "always eliminate the second to last finisher" than plain IRV is.
I forgot about BTR-IRV. I'll definitely add that one (it's unusual, and easyto code). At a glance I believe that one falls under the MinMax group, though.
I should say once we add in other ballot types the plot changes quite a bit.E.g. on the plot I just posted, DAC/DSC are a single point. But when we add inbullet votes they tend to be on opposite ends of one axis.
> >> Here is an attempt at plotting the Hamming distances of these codes, so>> that more similar methods are plotted closer together:>>[snip]>>I was thinking about something similar the other day. You could do this:>>Let each method's feature vector be something like:>--first letter--,    --second--, --third--    ...>[is it A?, is B? is C?  A?, B?, C?  A?, B?, C?    ]>>1 if true, 0 if false. So, for instance, a method that starts in ABC>would have a feature vector starting in>>[1, 0, 0,  0, 1, 0,  0, 0, 1, ....]>>If you take the Euclidean distance between two different methods'>feature vectors, you should get twice the Hamming distance. (If method X>and Y agree on the first letter, that contributes 0 to the distance, but>if they disagree, that contributes 1 to the distance)>>Now make a matrix of all the methods' feature vectors, run SVD on it,>and pick the two first singular vectors (corresponding to the greatest>singular values). Multiply them by their respective singular values, let>the resulting vectors give the x and y coordinates, and plot.
Uh oh. I had to google SVD.
>>This can in theory be done on any dimension feature vector, so you could>collapse the 343-digit codes to two dimensions that way as well, or even>consider each particular election that way (e.g. if you test on 100k>elections, the vector would be 300k long). You could model methods that>fit partly in the camp as well, if you'd like, e.g.
I can say part of the motivation for the 343 is to not have to do simulations, and be able to exhaustively investigate a method. (Or atleast its representation within the framework...)
>>[0.5, 0.5, 0, ...]>>is a method that, in the first scenario set, elects A half the time, B>the other half, and never elects C.>>Another possibility as far as plotting goes is to use a synthetic>coordinate algorithm to determine points on a plane that give distances>most like the distances you have already calculated. Such distances>could be sums of Kendall-tau distances between the different methods'>social orderings. I did that once, and you commented that the plot>didn't seem to make much sense beyond the rough scale: all Condorcet>methods gathered together in the middle, and then Plurality was off to>one side and Random Ballot off to another, I think.
Hmm, I think I remember that.
The way the plotting works now is that it finds the Hamming distances(using however many digits of DNA) and then plots methods one-by-one in2D space, trying to reduce the sum of squares of difference between theHamming distance and the apparent Euclidean distance. The whole thing isdone a number of times and with the methods in randomized order, keepingthe best result.
>>If you have an n*n method-method distance matrix (where d[a][b] gives>some distance between methods, e.g. by the Kendall tau distance), you>could also use a hierarchical clustering algorithm to get something>analogous to a cladogram or phylogenetic tree - a dendrogram. I think I>did that once, too, and though I didn't post my results, it seemed to>make more sense than the synthetic coordinate diagram. You might end up>with something like...>>              +---Carey>      +--IRV--+>      |       +----Plurality>      |>all----+>      |>      |            +---Borda>      +--Sinkhorn--+>                   +---Schulze>
That's a neat idea. I'll need to read up on how this algorithm can workthough. Sometimes a strange method gets plotted out in space and I don'tknow how arbitrary its placement is wrt the methods it appears to be closestto. A tree would probably be helpful there.
>>> In all of those 6561, only nine of them are Condorcet methods. I can>> describe all of them:>> >> ABABAACC: MinMax>> ABABABCC: C//IRV>> ABABACCC: C//QR>> ABBBAACC: Bucklin>> ABBBABCC: (???) always elect B in a cycle>Wouldn't that one fail neutrality? Suppose the cycle is ABCA. You could>always relabel the candidates by following the cycle.
Not neutrality, because the candidates are labeled by faction size. The problem is that the A faction may wish they had received fewer votes sothat their candidate could be the one labeled "B."
I actually made an unexpected amount of progress today evaluating theproperties of all 6561 methods. I think probably only a handful more areworth mentioning...
Kevin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20161126/5bf85e90/attachment-0001.htm>