Ranked Pairs Feint to Max Gradient Chain Building
A curious observation of Kristofer led Kevin and me into a line of inquiry
that has resulted in the following simple but powerful method:
Initialize a chain with the strongest defeat pair as though you were
starting Ranked Pairs, River, or Beatpath CSSD.
Then suddenly switch to Max Gradient Covering by adding to the chain the
candidate with the strongest defeat against the head of the chain among
those that cover it ... it being the current head of the chain.
Repeat this step until the chain has an uncovered head ... to be elected.
Since this method worked so smoothly as an alternate continuation of the
first Ranked Pairs step, Kevin and I thought perhaps we could use the
finish order of any method as a basis for such a chain: initialize a chain
with the highest finish order candidate and then while any candidate covers
the current head of the chain ... add to the chain the highest such
candidate in the finish order.
We were disappointed to find out that almost all seed methods resulted in
non- monotonic combinations of seed plus chain.
Exceptions had to behave like the finish order of Range/Score ... where
strengthening the score of one candidate would not change the relative
finish order among the other candidates.
So Kevin has called our initial success of seeding with one step of RP ...
'beginner's luck".
But it may turn out that no other luck is needed ... if you marry your high
school sweet heart, and everything works out perfectly ... well, if it
ain't broke ...
The one parameter left free in this RP feint covering chain method is the
gauge of defeat strength.
Recently, while musing on swap cost approval, it occurred to me to gauge RP
defeat strength as winning strong approval times losing strong disapproval
... in particular, in the RCV Universal Domain context, strong approval can
be interpreted as Top of ballot strength, while strong disapproval can be
interpreted as Bottom ballot strength.
For example1:
48 C
28 A>B
24 B
Top(C)Bottom(A)=48(48+24) , the defeat strength for C>A, is clearly the
strongest by this gauge.
And since C is uncovered, the chain is complete.
Example2:
x AB
y BC
z CA
Assuming max(x,y,z)<(x+y+z)/2, there is a beat cycle of ABC.
The respective strengths fo AB, BC, and CA according tour Top*Bottom gauge
are xz, yx, and zy, respectively. The largest of these will be the one with
the smallest missing factor in the product xyz.
So the defeat strength, in this context is proportional to the reciprocal
of the Top strength of the defeated candidate: A,B, or C wins depending on
which of B, C,or A, respectively has the fewest Top votes.
[Again, we used the fact that all candidates are uncovered ... which makes
the initial chain head the winner. This helps explain Krisyofer's original
observation that got this whole thing started. So you can see why I'm
tempted to call this the KKF method!]
What do you think?
-Forest
So far our best defeat strength gauge is the product of winning approval
and losing disapproval.
This still leaves open how to define approval and disapproval in this
context.
Up until now I've been using Equal Top for approval and equal Bottom for
disapproval.
Another possibility is implicit approval and disapproval.
Let's try something more symmetrical between Top and Bottom... a compromise
between those two previous ideas:
For use in defeat strength calculations where approval and disapproval
scores are needed, (for now) we will try ...
For each candidate X let the approval factor a(X) be the number of ballots
on which X is ranked Top (or equalTop) plus half the number of ballots
where X is ranked strictly be tween Top and Bottom ... that is half the
number of ballots on which X is ranked ahead of at least one candidate,
while at least one other candidate is ranked ahead of X.
Also let the disapproval d(X) be given by the difference between the number
of ballots and a(X).
Example:
48 C
28 A>B
24 B
The respective approval scores for A, B and C are 28, 38, and 48.
The corresponding disapprovals are
72, 62, and 52.
The defeat strengths for A>B, B>C, and C>A are ...
2862, 3852, and 48*72, respectively.
The strongest defeat is C>A. And since C is uncovered, no other defeat can
depose C from the head of the chain.
Example2
8 A>B (sincere was A>C)
6 B>C
4 C (sincere was C>A)
The sincere ballots yield C as the only uncovered candidate, hence the
winner.
The truncation in the C faction was a preemptive defense against the burial
of C in the A faction ... let's see if it is protective:
The respective approval/ disapproval pairs are (8, 10), (14, 4), and (10,
8).
The respective defeat strengths are ...
84, 148, and 10*10 ... not quite enough to retain the win for C, but
enough to punish A by electing A's last choice.
I hope you all will experiment with this streamlined method to get a feel
for it.
So far it seems pretty robust to me.
Any bad results?
It's almost simple enough to replace Gross Loser Elimination as the most
viable RCV election method.
What do you think?
Do I need to go over again the simplicity and relevance of "Covering" ...
both in concept and calculation?
-Forest
On Thu, Jan 26, 2023, 12:53 PM Forest Simmons forest.simmons21@gmail.com
wrote:
A curious observation of Kristofer led Kevin and me into a line of inquiry
that has resulted in the following simple but powerful method:
Initialize a chain with the strongest defeat pair as though you were
starting Ranked Pairs, River, or Beatpath CSSD.
Then suddenly switch to Max Gradient Covering by adding to the chain the
candidate with the strongest defeat against the head of the chain among
those that cover it ... it being the current head of the chain.
Repeat this step until the chain has an uncovered head ... to be elected.
Since this method worked so smoothly as an alternate continuation of the
first Ranked Pairs step, Kevin and I thought perhaps we could use the
finish order of any method as a basis for such a chain: initialize a chain
with the highest finish order candidate and then while any candidate covers
the current head of the chain ... add to the chain the highest such
candidate in the finish order.
We were disappointed to find out that almost all seed methods resulted in
non- monotonic combinations of seed plus chain.
Exceptions had to behave like the finish order of Range/Score ... where
strengthening the score of one candidate would not change the relative
finish order among the other candidates.
So Kevin has called our initial success of seeding with one step of RP ...
'beginner's luck".
But it may turn out that no other luck is needed ... if you marry your
high school sweet heart, and everything works out perfectly ... well, if it
ain't broke ...
The one parameter left free in this RP feint covering chain method is the
gauge of defeat strength.
Recently, while musing on swap cost approval, it occurred to me to gauge
RP defeat strength as winning strong approval times losing strong
disapproval ... in particular, in the RCV Universal Domain context, strong
approval can be interpreted as Top of ballot strength, while strong
disapproval can be interpreted as Bottom ballot strength.
For example1:
48 C
28 A>B
24 B
Top(C)Bottom(A)=48(48+24) , the defeat strength for C>A, is clearly the
strongest by this gauge.
And since C is uncovered, the chain is complete.
Example2:
x AB
y BC
z CA
Assuming max(x,y,z)<(x+y+z)/2, there is a beat cycle of ABC.
The respective strengths fo AB, BC, and CA according tour Top*Bottom gauge
are xz, yx, and zy, respectively. The largest of these will be the one with
the smallest missing factor in the product xyz.
So the defeat strength, in this context is proportional to the reciprocal
of the Top strength of the defeated candidate: A,B, or C wins depending on
which of B, C,or A, respectively has the fewest Top votes.
[Again, we used the fact that all candidates are uncovered ... which makes
the initial chain head the winner. This helps explain Krisyofer's original
observation that got this whole thing started. So you can see why I'm
tempted to call this the KKF method!]
What do you think?
-Forest
On 1/26/23 21:53, Forest Simmons wrote:
[Again, we used the fact that all candidates are uncovered ... which
makes the initial chain head the winner. This helps explain Krisyofer's
original observation that got this whole thing started. So you can see
why I'm tempted to call this the KKF method!]
What do you think?
Sounds good! But I'm increasingly feeling that it's hard to understand
the tradeoffs of a method without having a view to their behavior, like
simulations. So if it turns out to be awful in practice, then perhaps
I'll have to retract my statement :-)
On a broader level, I'm wondering if we should pool our simulators
somehow to not duplciate the effort it takes to implement methods. But
my own main simulator is not the prettiest of code, so I would have to
clean that up first. And then I don't get much further than that!
-km
Correction on second example below ...
On Sun, Jan 29, 2023, 10:00 AM Forest Simmons forest.simmons21@gmail.com
wrote:
So far our best defeat strength gauge is the product of winning approval
and losing disapproval.
This still leaves open how to define approval and disapproval in this
context.
Up until now I've been using Equal Top for approval and equal Bottom for
disapproval.
Another possibility is implicit approval and disapproval.
Let's try something more symmetrical between Top and Bottom... a
compromise between those two previous ideas:
For use in defeat strength calculations where approval and disapproval
scores are needed, (for now) we will try ...
For each candidate X let the approval factor a(X) be the number of ballots
on which X is ranked Top (or equalTop) plus half the number of ballots
where X is ranked strictly be tween Top and Bottom ... that is half the
number of ballots on which X is ranked ahead of at least one candidate,
while at least one other candidate is ranked ahead of X.
Also let the disapproval d(X) be given by the difference between the
number of ballots and a(X).
Example:
48 C
28 A>B
24 B
The respective approval scores for A, B and C are 28, 38, and 48.
The corresponding disapprovals are
72, 62, and 52.
The defeat strengths for A>B, B>C, and C>A are ...
2862, 3852, and 48*72, respectively.
The strongest defeat is C>A. And since C is uncovered, no other defeat
can depose C from the head of the chain.
Example2
8 A>B (sincere was A>C)
6 B>C
4 C (sincere was C>A)
The sincere ballots yield C as the only uncovered candidate, hence the
winner.
The truncation in the C faction was a preemptive defense against the
burial of C in the A faction ... let's see if it is protective:
The respective approval/ disapproval pairs are (8, 10), (14, 4), and (10,
8).
B approval should be 8/2+6=10, not 14. So the B disapproval is 8.
C's approval should be 6/2+4=7
The corrected pairs are (8,10),(10,8),& (7,11)
The respective defeat strengths are ...
84, 148, and 10*10
Corrected to 88, 1011, and 7*10 ... so the strongest defeat is B>C with
strength 110 ... which does punish A but does not restore the win to C, the
sincere CW.
... not quite enough to retain the win for C, but enough to punish A by
electing A's last choice.
I hope you all will experiment with this streamlined method to get a feel
for it.
So far it seems pretty robust to me.
Any bad results?
It's almost simple enough to replace Gross Loser Elimination as the most
viable RCV election method.
What do you think?
Do I need to go over again the simplicity and relevance of "Covering" ...
both in concept and calculation?
-Forest
On Thu, Jan 26, 2023, 12:53 PM Forest Simmons forest.simmons21@gmail.com
wrote:
A curious observation of Kristofer led Kevin and me into a line of
inquiry that has resulted in the following simple but powerful method:
Initialize a chain with the strongest defeat pair as though you were
starting Ranked Pairs, River, or Beatpath CSSD.
Then suddenly switch to Max Gradient Covering by adding to the chain the
candidate with the strongest defeat against the head of the chain among
those that cover it ... it being the current head of the chain.
Repeat this step until the chain has an uncovered head ... to be elected.
Since this method worked so smoothly as an alternate continuation of the
first Ranked Pairs step, Kevin and I thought perhaps we could use the
finish order of any method as a basis for such a chain: initialize a chain
with the highest finish order candidate and then while any candidate covers
the current head of the chain ... add to the chain the highest such
candidate in the finish order.
We were disappointed to find out that almost all seed methods resulted in
non- monotonic combinations of seed plus chain.
Exceptions had to behave like the finish order of Range/Score ... where
strengthening the score of one candidate would not change the relative
finish order among the other candidates.
So Kevin has called our initial success of seeding with one step of RP
... 'beginner's luck".
But it may turn out that no other luck is needed ... if you marry your
high school sweet heart, and everything works out perfectly ... well, if it
ain't broke ...
The one parameter left free in this RP feint covering chain method is the
gauge of defeat strength.
Recently, while musing on swap cost approval, it occurred to me to gauge
RP defeat strength as winning strong approval times losing strong
disapproval ... in particular, in the RCV Universal Domain context, strong
approval can be interpreted as Top of ballot strength, while strong
disapproval can be interpreted as Bottom ballot strength.
For example1:
48 C
28 A>B
24 B
Top(C)Bottom(A)=48(48+24) , the defeat strength for C>A, is clearly the
strongest by this gauge.
And since C is uncovered, the chain is complete.
Example2:
x AB
y BC
z CA
Assuming max(x,y,z)<(x+y+z)/2, there is a beat cycle of ABC.
The respective strengths fo AB, BC, and CA according tour Top*Bottom
gauge are xz, yx, and zy, respectively. The largest of these will be the
one with the smallest missing factor in the product xyz.
So the defeat strength, in this context is proportional to the reciprocal
of the Top strength of the defeated candidate: A,B, or C wins depending on
which of B, C,or A, respectively has the fewest Top votes.
[Again, we used the fact that all candidates are uncovered ... which
makes the initial chain head the winner. This helps explain Krisyofer's
original observation that got this whole thing started. So you can see why
I'm tempted to call this the KKF method!]
What do you think?
-Forest
I seem to have lost a draft of a reply ... I won't try to repeat the whole
thing ... just that many numerical experiments are in deed needed ...
specifically to find the best performing defeat strength measures.
Here's one worth exploring ...
max(winning Top, losing Bottom)
Here's an example ...
8 A>B (Sincere is A>C)
6 B>C
4 C (Sincere is C>A)
A>B winning top 8, losing bottom 4
B>C winning top 6, losing bottom 8
C>A winning top 4, losing bottom 10
The max strength is 10 for C>A
This restores the win to the sincere CW.
I like it!
This rule seems to be the best expedient against Dark Horse winners that
some methods elect when the middle range category is the vague,
other/default category ... in this case the outer categories of definite
approval (equal Top) and definite disapproval (equal Bottom) leave the
middle category as the vague "other" default ... a dark horse red flag for
the method inventor.
Our remedy is the defeat strength's prominent usage of the max value of the
two definite categories as a guard against an unknown nobody winning by
default.
-Forest
On Tue, Jan 31, 2023, 4:16 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
On 1/26/23 21:53, Forest Simmons wrote:
[Again, we used the fact that all candidates are uncovered ... which
makes the initial chain head the winner. This helps explain Krisyofer's
original observation that got this whole thing started. So you can see
why I'm tempted to call this the KKF method!]
What do you think?
Sounds good! But I'm increasingly feeling that it's hard to understand
the tradeoffs of a method without having a view to their behavior, like
simulations. So if it turns out to be awful in practice, then perhaps
I'll have to retract my statement :-)
On a broader level, I'm wondering if we should pool our simulators
somehow to not duplciate the effort it takes to implement methods. But
my own main simulator is not the prettiest of code, so I would have to
clean that up first. And then I don't get much further than that!
-km
To prioritize simplicity here's my current thinking:
Gauge pairwise defeat strength with pairwise margins: winning votes minus
losing votes.
To summarize:
Initialize a pairwise defeat chain with the defeat having the greatest
defeat margin.
Until the head of the chain is uncovered, replace it with the candidate
that covers it with the greatest margin of defeat.
Then elect the final head of the chain.
A candidate X is uncovered if it can defeat every challenger Z in two or
fewer steps ... i.e. if an uncovered X is defeated by some challenger Z,
then there is some intermediate candidate Y that is defeated by X but not
defeated by Z.
[or defeats Z but not X]
I doubt that there is any other monotone, clone-independent, Landau
efficient method that is easier to understand or tally.
Landau efficient means that it always elects an uncovered candidate.
In general, every Smith candidate has a beatpath to every other candidate.
Every Landau candidate has a short beatpath to every other candidate. How
short? At most two steps.
So every uncovered candidate is a member of the Smith set ... therefore
when the Smith set has only one member it is the one and only uncovered
candidate.
Any RCV method that elects a covered candidate X should be sued in court by
the supporters of the candidate(s) that cover X.
Part of the court's remedy, besides punitive damages, would have to be a
mandate to adopt a Landau efficient method ... which might be the easiest
route to getting this method adopted.
Once somebody is familiar with this method, why would they propose some
other voting method?
Well, suppose the method turned out to be easy to manipulate ... and that
problem could not be fixed by changing the defeat strength gauge ... then
we would cheerfully tacharlo.
So now, the more people that can test it on their favorite ballot profiles,
the better.
In particular, somebody with a computer should try it on all seven of
Kevin's standard 3-candidate test cases.
Thanks!
-Forest
On Tue, Jan 31, 2023, 6:32 PM Forest Simmons forest.simmons21@gmail.com
wrote:
I seem to have lost a draft of a reply ... I won't try to repeat the whole
thing ... just that many numerical experiments are in deed needed ...
specifically to find the best performing defeat strength measures.
Here's one worth exploring ...
max(winning Top, losing Bottom)
Here's an example ...
8 A>B (Sincere is A>C)
6 B>C
4 C (Sincere is C>A)
A>B winning top 8, losing bottom 4
B>C winning top 6, losing bottom 8
C>A winning top 4, losing bottom 10
The max strength is 10 for C>A
This restores the win to the sincere CW.
I like it!
This rule seems to be the best expedient against Dark Horse winners that
some methods elect when the middle range category is the vague,
other/default category ... in this case the outer categories of definite
approval (equal Top) and definite disapproval (equal Bottom) leave the
middle category as the vague "other" default ... a dark horse red flag for
the method inventor.
Our remedy is the defeat strength's prominent usage of the max value of
the two definite categories as a guard against an unknown nobody winning by
default.
-Forest
On Tue, Jan 31, 2023, 4:16 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
On 1/26/23 21:53, Forest Simmons wrote:
[Again, we used the fact that all candidates are uncovered ... which
makes the initial chain head the winner. This helps explain Krisyofer's
original observation that got this whole thing started. So you can see
why I'm tempted to call this the KKF method!]
What do you think?
Sounds good! But I'm increasingly feeling that it's hard to understand
the tradeoffs of a method without having a view to their behavior, like
simulations. So if it turns out to be awful in practice, then perhaps
I'll have to retract my statement :-)
On a broader level, I'm wondering if we should pool our simulators
somehow to not duplciate the effort it takes to implement methods. But
my own main simulator is not the prettiest of code, so I would have to
clean that up first. And then I don't get much further than that!
-km