[EM] Some thinking around generalizing STAR

[Kristofer Munsterhjelm]

Here's a thought I had the other day, of a possibly better way to
generalize STAR to deal with clone problems. I haven't got it quite
solved yet, but I thought it might still be of interest.

As usual, the honest continuous rated vote for three candidates is (X:
1, Y: p, Z: 0) if your ranked preference is X>Y>Z and you're indifferent
between getting Y with certainty and a probability p chance of X, (1-p)
probability chance of Z. Having ratings properly defined should help
answer the question "but how much do I rate my second favorite", at
least for honest voters (although it might still be too demanding to
actually *ask* of voters...)

We'll use the same concept as in Schulze STV, that pairwise victories
are between sets, but are only allowed to differ by one candidate, and
then trace beatpaths to each set.

Let the extended pairwise contests be defined by:

{A, B} > {A, C} if, in the three-candidate normalized rated election
involving A, B, and C, C is the loser. (definition 1)

The winning set is the one who has a beatpath to all two-sets. The
candidate who defats the other pairwise in the winning set is the method
winner.

The idea here is: suppose that {X, Y} is the winning set, and let's
clone some losing candidate A into A1 and A2. Then clearly {X, Y} has a
beatpath to every {W, A}. Because A is a rated clone, their rating
difference is epsilon, so the beatpath will hold when we replace A with
either A1 or A2.

The only problems, then, are the beatpaths to or from {A1, A2}. If A is
not the CW, there will exist some B so that {B, A1} > {A1, A2}, in which
case the current winner can just extend his beatpath to {B, A1} to also
scoop up {A1, A2}.

But if A is the CW, then there is no such link, which is where I got
stuck. Would it help to define the relation like one of these instead?

{A, B} > {A, C} if B is the winner in the three-candidate rated election
(definition 2), or

{A, B} > {A, C} if B is the winner or C is the loser (definition 3).

The idea would be that if A is the CW, {A1, A2} > {A1, X} will always be
true (for all these definitions, because one of the As win the Range
election since they're clones). But A can't propagate his beatpath to
the other candidates even though he's the CW, so we might still be able
to save the original winner from losing.

That does mean that we aren't guaranteed that there exists a two-set
that has a beatpath to everybody else. So further modifications would be
needed, and I'm not sure what they would be. Perhaps using lp-norm
normalization for the three-candidate elections would cancel out the
benefits of cloning?



I can at least see which of these reduce to STAR in the three-candidate
case.

First, consider STAR.

Let the Range ordering be A>B>C. In STAR, C is eliminated and then
whoever of {A, B} beats the other pairwise is the winner. So we have to
show that {A, B} is the winner by the method above.

For definition 1:
	{A, B} > {A, C} because C is the loser
	{A, B} > {B, C} likewise
So {A, B} is the winning set and whoever beats the other pairwise wins, OK.

Definition 2:
	{A, B} = {A, C} because neither B nor C is the winner
	{A, B} > {B, C} because A is the winner.
so that doesn't quite work.

Definition 3:
	{A, B} > {A, C} by the tiebreak.
	{A, B} > {B, C} because A is the winner.

So definitions one and three work.

-km