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

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.

Monotonicity:
Suppose the winner X moves up in rank on one or more ballots, while the
other alternatives maintain there ranks relative to each other. It is
obvious that this change cannot increase the value of S(X). But could it
decrease the value of some S(Z) more than it decreases the value of S(X)?

Well, if S(Z) decreases, it has to be because, for some Y, d(Z,Y) has
decreased, i.e. the shortest beatpath from Z to Y just got shorter due to a
shortcut newly created by a defeat of some alternative A that was not
defeated before X got raised in the ranks.
Let's compare the changes:
Before the change the minimal beatpath from X to Y had a length of d(X,Y),
and after the change it had a length of d(X,A) plus d(A,Y). Meanwhile the
length of the shortest beatpath from Z to Y changed from d(Z,X)+d(X,Y) to
d(Z,X)+d(X,A)+d(A,Y).
In both cases the net effect on the Y term in the S sum of the distances is
d(X,A)+d(A,Y)-d(X,Y).
In summary, S(Z) cannot decrease more than S(X) does when X is raised on a
ballot.
[The other factor, L(Y), in the corresponding terms of the sum S does not
depend on X or Z]

So, barring some subtle, but fatal error in my reasoning, it appears that
the method is (1) Clone independent, (2) Landau efficient, and (3)
Monotonic.

If the simulations of Kevin and Kristofer  (and anybody else who wants to
experiment) continue to confirm these claims, we can be increasingly
confident that FV is worth proposing for public elections.

Kristofer and Kevin have done most of the heavy lifting ... I'm just the
lucky guy who got to help out a little with the window dressing!

Thanks!

Forest

---------- Forwarded message ---------
From: Forest Simmons forest.simmons21@gmail.com
Date: Tue, Oct 11, 2022, 10:07 AM
Subject: Re: Friendly Voting
To: Jobst Heitzig heitzig@pik-potsdam.de
Cc: Kristofer Munsterhjelm km_elmet@t-online.de

Jobst,

Your remark connecting Friendly Voting to the benchmark lottery suggested
the following generalization of FV:

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.

If L is the benchmark lottery, we get Friendly Voting.

Kristofer invented the key concept of the important role of "friendliness:"
The fewer beatpath steps from X to Y the friendlier Y is to X.

All I did was make the connection to the generalized median concept. It was
Andy Jennings and Rob LeGrand (and you) who got me thinking about the
median as a way of lowering incentive for insincere strategy.

All My Best,

Forest

On Mon, Oct 10, 2022, 11:36 AM Jobst Heitzig heitzig@pik-potsdam.de wrote:

An example of a lottery L that could be better (in some contexts) than
random ballot favorite: let L(Y) be the percentage of ballots B on which Y
is the highest ranked alternative that has a beatpath to each of the other
alternatives that are ranked on ballot B.

This choice of lottery L would (1)make compromising less of a temptation,
and (2) make winning ties less likely.

Another example: Let L(Y) be the percentage of ballots B on which Y is the
alternative with the worst rank on ballot B that is not pairwise defeated
by any alternative with a better rank on ballot B.

In general, L(Y) should be the percentage of ballots B on which Y would be
an  optimal compromise alternative for the ballot B voter in a Plurality
election.

One more: Bubble sort pairwise the alternatives ranked on ballot B, giving
rectification priority to the out of order pairs closest to the bottom
(worst end) of the ballot. Then let L(Y) be the percentage of the ballots
on which Y ends up on top.

Finally: For each ballot B, while the alternative h currently ranked
highest on B is covered by some alternative y ranked lower on B, swap out t
for the highest such y. Then let L(Y) be the percentage of ballots on which
alternativeY ends up top ranked.

More ideas for lottery L?

-Forest

On Tue, Oct 11, 2022, 5:44 PM Forest Simmons forest.simmons21@gmail.com
wrote:

On 12.10.2022 02:44, Forest Simmons wrote:

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

(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

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

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.

Good point!

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

On 13.10.2022 02:38, Forest Simmons wrote:

My hunch is that since the strength of first preferences (against
burial) comes from that X>W voters can't change who they vote first by
burying, then a burial resistant extension should be based on first
preferences of some subset of the candidates. (If we take the subset to
be just every candidates, we get the usual Friendly Cover/Voting patterns.)

If so, then always using the subset of every possible candidate will
lead to the ISDA/pathological Smith/Landau failure shown above. So when
comparing X to W, we have two possibilities: either a fixed-cardinality
subset (probably containing both X and W) or a variable-cardinality one.

IRV is "essentially" (if you handwave enough) doing the latter, with its
path dependence producing nonmonotonicity and all of the usual flaws.
Since variable-cardinality subsets seem to lead directly to summability
violations, it's kind of a no-go. But perhaps there is a way to do the
former and still retain burial resistance?

There are two problems.

First, suppose we always use subsets of three. Then Condorcet cycle
analogs may occur - e.g. A's fpA-fpC score beats B's in the subset
(A,B,C), B's beats C's in the subset (B, C, D), C's beats D's in the
subset (C, D, A), and D's beats A's in the subset (D, A, B). The usual
fix would be to use something like Ranked Pairs over these orderings,
but I can't see how to prove that burial resistance will be preserved by
this.

Second, if we clone A into A1...An, then we can engineer the cloning to
set the A clones' scores to arbitrary values for fpA-fpC restricted to
the subset (A1,...,An). So using the result for subsets containing only
clones to determine whether A or B should win would fail clone independence.

So, not entirely easy. But perhaps it will give you some ideas for
lotteries along the "restricted subset" path :-)

Maybe the easiest way is to just come up with something that passes
DMTCBR and is based on the fixed subset pattern, and see if its burial
resistance is robust. A possible clue here is that fpA-fpC restricted to
every (assume cardinality three) subset containing A will have A
outscore B and C even after burial. But then again, that's also true of
pairwise victories...

Or it might be possible to do something along the lines of: if A ties B,
then A's tiebreaker is based on the relation of A's max-scoring friend
wrt B's -- because in the case that A covers B, then B can't possibly
win. As long as the "relation of A's max-scoring friend wrt B's" also
takes into consideration the tiebreakers of these max-scoring friends.

That's no trouble at all :-)

I definitely won't complain if Friendly turns out to be a really good
method!

-km

Suppose de granted each candidate one free bullet ballot .... that would
keep non-Smith candidates from being in the tied-for-win set ... but it
creates a non-scaling problem.

However, if we grant each candidate a gratuitous bullet ballot with
positive weight epsilon, and shrink epsilon until further shrinkage stops
changing the winner, then the method becomes scale invariant.

-Forest

On Sat, Oct 15, 2022, 2:18 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

On 10/16/22 03:08, Forest Simmons wrote:

Yeah, I thought about that. Basically you can add an epsilon to every
candidate's first preference count and then let epsilon go to zero. This
is equivalent to counting sum over friends A: fpA - sum over defeaters
C: fpC as a two-vector whose first element is just the sum and the
second is the number of friends minus the number of defeaters, and then
using leximax.

The problem is that this fails clone independence. Suppose A and B are
tied even given the tiebreaker above, and let C be some friend of A
who's not a friend of B. Clone C, then A wins.

-km

OK, here's what I would like to call Friendly Approval, a decisive approval
score method based on friendly ideas:-)

For each ballot B, let f(B) be B's favored first place choice.

For each candidate X  let A(X) be the number of ballots B that rank X, for
which X has a short beatpath to f(B).
This A(X) is X's base level approval. If argmax A(X) has only one member,
that member is to be elected.

Otherwise, break the tie with E(X), defined as the number of ballots B that
rank X for which X has a beatpath to f(B) of at most one step.

If there are still tied candidates, break the tie with C(X) defined as the
number of ballots B for which X is ranked on B and covers (or weakly
covers) f(B).

If there are still tied candidates, break the tie with F(X) defined as the
number of ballots for which X=f(B).

In other words elect argmax S(X), where S(X) is the sum given by

A(X)/epsilon^3+E(X)/epsilon^2
+C(X)/epsilon+F(X)

For a weaker approval method, add to S(X) the term G(X)/epsilon^4, where
G(X) is the number of ballots B on which X is ranked for which X has a
finite beatpath to f(B).

-Forest

On Sun, Oct 16, 2022, 2:26 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

This "friendly approval" turns out to be pretty blah.

But here's a new method that has fpA-SumfpC as a first order approximation:

It is of the form elect argmax L(X), where L is a lottery on the candidates
defined by the following experiment:

Draw a random ballot A.

Let f(A) be the candidate most favored on ballot A.

Continue drawing ballots, and let C be the first ballot drawn such that
f(C) defeats f(A), provided there is such a ballot.

Continue drawing ballots, and let D1be the first ballot for which f(D1)
defeats both f(A) and f(C), if there is such a ballot.
...
Continue until you reach the last ballot DMax in this sequence ... the one
such that f(DMax) defeats all of the previous favorites in the sequence,
but is maximal in that regard ... no ballot has a favorite that defeats
both f(DMax) and all of the previous favorites in the sequence.

This last ballot favorite DMax is the lottery winner, which is the result
of a random experiment.

To get a deterministic method based on this experiment, we define L(X) as
the probability that X will be the lottery winner DMax. This probability is
not a random variable, but is completely determined by the voted ballots.

So our election method (elect argmaxL(X))  is deterministic.

If I am not mistaken, the first few terms in the calculation of L(A) are
fp(A) -fp(C1)-fp(C2) - ... -fp(Cn), where the Ck are the candidates that
defeat A.

The higher degree terms are beyond the scope of my tired brain.

But the thought experiment gives some probabilistic meaning to the original
fpA-SumfpC formula.

It might suggest how to alter the experiment to get a method with better
properties ... say when we get into the D's, start looking at lower
candidates, not just f(D) for defeaters of the previous D's.

-Forest

On Mon, Oct 17, 2022, 8:23 PM Forest Simmons forest.simmons21@gmail.com
wrote: