[EM] meditations

[fsimmons at pcc.edu]

An alternative X Pareto Dominates alternative Y if Y is not ranked over X on any ballot and X is ranked 
over Y on at least one ballot.

Obviously there can be no Pareto domination cycle.

Furthermore, if ballots are Range style, admitting k distinct ratings, then no Pareto domination beatpath 
can be longer than  k  times the number of ballots, no matter how many alternatives there are.

Now consider the case when k = 2, i.e. approval ballots.  In this case even without Pareto domination 
there can be no beatpath cycle, and the length of a beatpath is also limited by the number of ballots 
irrespective of the number of candidates.

Can we make similar statements for other values of k?

It’s obvious, for example, that when k=3 or when there are only three candidates there can be no beat 
cycle of wv strength greater than two thirds of the number of ballots. 

But I think we can say more than that.  But first we need a definition.

Definition:  Alternative X beats alternative Y by a margin ratio of x to y if the number of ballots on which X 
is ranked above Y divided by the number of ballots on which Y is ranked above X is greater than x/y.

Conjecture 1:  If there are just k levels, then there can be no beat cycle where all the margin ratios are 
greater than  (k-1) to 1.

Conjecture 2:  If there are just k levels, then no matter how many alternatives, there is a bound on the 
length of a beatpath with margin ratios greater than (k-1) to 1, and this bound is (approximately) k times 
the number of ballots.

Note that the Pareto results above correspond to the case of k=infinity, since the margin ratios are 
infinite in a Pareto defeat, and that the approval results correspond to the case of k=2.

[If these conjectures are not true, let’s find the appropriate generalization of the k=2 and k=infinity cases.]

How can we use them?

One way is a generalization of Bucklin:

If there are k alternatives, first eliminate any candidates that are defeated by (k-1) to 1 margins.  If none 
are so defeated, collapse one of the levels as in Bucklin, and then eliminate all of the candidates that are 
defeated by a (k-2) to 1 margin.  Keep going until you get down to two candidates or two levels, and 
eliminate all of the candidates that are defeated by a 1 to 1 margin.  Elect the remaining candidate.

A variation on this uses ballots with ranked preference strengths.  Then instead of collapsing from the 
top down (as in Bucklin) when no candidate is eliminated , we collapse the weakest strength remaining 
preference on each ballot.

A voted ranked preference strength ballot looks like

A>B>>>C>>D>>>>>E>>>>F