[EM] Friendly Voting: Some Criteria Compliance Proof Sketches

[Kristofer Munsterhjelm]

On 12.10.2022 02:44, Forest Simmons wrote:
> In the quoted text below I gave a slight generalization of Friendly 
> Voting (FV) in a formulation that will be more convenient for the voting 
> method criteria proofs offered in this message (EM List posting).
> 
> "Let L be any proportional lottery on the alternatives.
> 
> Elect argmin S(X), given by
> 
> Sum over Y of d(X,Y)*L(Y),
> 
> Where d(X,Y) is the number of steps in the shortest beatpath from X to Y.
> 
> When L is the random ballot favorite lottery, the above method 
> description becomes an equivalent formulation of Friendly Voting."
> 
> First, FV is Landau efficient:
> Suppose that X is the FV winner and X' covers X. Then if there is a 
> beatpath from X to Y of length d(X, Y), then replacing X with X' in that 
> beatpath will give a beatpath of the same length from X' to Y. If X' 
> directly defeats any later member of that beatpath, then d(X',Y) will be 
> strictly less than d(X,Y). because of the shortcut ... ETC

Does this come with the same caveat as in Friendly Cover that if someone 
has no first preference, then the compliance may be failed? E.g. suppose 
a bunch of nobodies are ranked first (enough so that they're not in 
Smith), then every viable candidate's first preference is zero.

More broadly, I agree that simulations are needed. I would like to 
suggest to someone that they write a library for easy simulations and 
compliance checks of voting methods. Quadelect was going to be such a 
program, but C/C++ has too much boilerplate for quick and dirty tests. 
Perhaps Python?

And maybe I'll write it myself, but I've been occupied with other things 
lately (which also explains my absence from the list) :-)

> Next, Clone Independence:
> As Kristofer pointed out to me, cloning a member Z of the shortest 
> beatpath from X to Y doesn't change the length of the shortest beatpath, 
> because you can just replace Z with any of its clones.
> So it was Kristofer who gave us the courage to use the number of steps 
> in the shortest beatpath, rather than the customary "strength of the 
> weakest link" metric used in the (Markus Schulz) CSSD Beatpath method.

(Also note that going through a clone can't make the beatpath shorter. 
However, you'd have to check that adding a bunch of clones in a cycle 
couldn't make the beatpath from one of the clones to another of the 
clones decisive.)

-km