[EM] Friendly Voting: Some Criteria Compliance Proof Sketches

[Forest Simmons]

On Wed, Oct 12, 2022, 3:35 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

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

Yeah, but if even one Smith member is in the support of lottery L, then no
non-Smith winner has a finite Sum S(X).

That's why all my suggestions for Lare designed to take care of that
problem.

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

Good point!

>
> -km
>

Also apologies for not checking with you before dubbing my version
"Friendly Voting."
I started out just trying to do generalized median voting, and was
surprised when the final simplified version turned out to be "Friendly" ; -)

-Forest

>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20221012/1a54e874/attachment.htm>