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

[Kristofer Munsterhjelm]

On 11/26/2016 07:24 AM, Kevin Venzke wrote:
> I'll define a simple "ballot space," meaning a range of scenarios that
> can occur given voter, candidate, and ballot limitations. Then I'll talk
> about the "method space" for that ballot space, meaning the range of
> methods that are possible to define.
> 
> Let there be three factions, each preferring a different one of
> candidates labeled A, B, and C. The "A bloc" is the largest, with B
> being second-largest, and C being smallest. No bloc is a majority, but
> any two blocs would be a majority. Every voter within a bloc votes
> exactly the same (so that we see, total, only three unique ways of
> filling out the ballot). Every ballot is required to be a full, strict
> ranking. Additionally, each bloc will always rank their preferred
> candidate at the top.
> 
> Since each bloc can only fill out the ballot in two ways (e.g. A>B>C or
> A>C>B for the A bloc), this ballot space has only 2^3 = 8 scenarios:
> 1. A>B B>A C>A ballots. A+B mutual majority, A is CW.
> 2. A>B B>A C>B. A+B mutual majority, B is CW.
> 3. A>B B>C C>A. A>B>C>A preference cycle.
> 4. A>B B>C C>B. B+C mutual majority, B is CW.
> 5. A>C B>A C>A. A+C mutual majority, A is CW.
> 6. A>C B>A C>B. A>C>B>A preference cycle.
> 7. A>C B>C C>A. A+C mutual majority, C is CW.
> 8. A>C B>C C>B. B+C mutual majority, C is CW.
> 
> If we put a sequence of eight As, Bs, or Cs in a row to show who wins in
> each scenario, that sequence can define a method for this ballot space.
> I call this a DNA code.
> 
> I have 343-digit codes, covering a larger ballot space, for a few dozen
> election methods. But in this eight-scenario space these reduce to a
> quite small number of codes. For methods that use an approval concept, I
> use the assumption that only the bottom candidate is unapproved. Here
> then is a full list (so far) of the 8-digit codes resulting from methods
> that are at least mostly serious:
> 
> AAAAAAAA: FPP has its own code. Notice how it just elects A no matter
> what any lower preferences are.
> 
> 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.
> 
> ABBBAACC: The Bucklin group. This includes Chris' IBIFA,
> Condorcet//Approval and ICA, MDDA, CdlA, MinMax(AWP), and probably many
> others. Note that, within this ballot space, these are a Condorcet method!
> 
> AAABAAAC: The "descending coalitions" group. It includes DAC, DSC, and a
> couple of my methods (SPST, and both pairwise and Bucklinesque versions
> of "Venzke Bucklin Variant" aka VBV). 
> 
> ABABABAB: IRV group, including my "King of the Hill" (KH) method and
> IRV-without-elimination.
> 
> 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.

> ABABACAC: my QR, aka Chain Runoff.
> 
> ABABACCC: Condorcet//QR.
> 
> ABBBACCC: Forest's TACC method.
> 
> ABCBABCC: BPW (Eivind Stensholt's "Beats Plurality Winner" Condorcet
> method).
> 
> AAABAAAB: VDP (Venzke Disqualified Plurality, aka VFA). 

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.

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.

> That's really it... Other known codes are limited to experiments like
> "IRV where you eliminate the wrong candidate" or "just elect the winner
> of the strongest pairwise contest." (Let me know if you think there's an
> unusual method I've missed, and that can operate on these ballots.)
> 
> 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.

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.

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

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 is 11 methods in a method space containing 3^8 = 6561 methods. Can
> we find any more methods?
> 
> 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.

> ABBBACCC: TACC
> ABCBAACC: Condorcet//"IRV where you eliminate second-lowest tally"
> ABCBABCC: BPW
> ABCBACCC: (???) always elect C in a cycle
> 
> Only two scenarios lack a CW, leaving not a lot of room to experiment.