[EM] Discounting ties, how can MinMax differ from Ranked Pairs?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[EM] Discounting ties, how can MinMax differ from Ranked Pairs?

robert bristow-johnson

Let's assume Margins, but I think this works for Winning Votes also.

Begin with all candidates marked as "Plausible Winner" (which means they are not yet marked as "beaten") and order all N(N-1) candidate Pairwise Defeats from strongest defeat strength to weakest defeat strength.  Call that ordered list the "Original List".

Now create another ordered list of Pairwise Defeats from the above Original List.

 

MinMax starts with the entire Original List with N(N-1) entries and successively eliminates entries from the bottom up.

Referring to a quote in this Wikipedia article: https://en.wikipedia.org/wiki/Minimax_Condorcet_method#Variants_of_the_pairwise_score , MinMax starts at the bottom and:

     "Disregards the weakest Pairwise Defeat until one candidate is unbeaten."



Similarly Ranked Pairs starts with an empty list and successively includes entries from the Original List from the top down.

Cannot Ranked Pairs be concisely stated as:

     "Include the strongest Pairwise Defeat until only one candidate is unbeaten."   ?

 

Is that not an accurate description of both methods?

Now, a decreasing sequence of numbers (*not* strictly decreasing) of length N(N-1)+1 that represents the number of "unbeaten" candidates (of all Pairwise Defeats above it) having value of N at the top, that can be thought of as having each of the N(N-1) Pairwise Defeats inserted between these numbers of decreasing integer value.

Assuming no ties, the value of this sequence at the bottom must be either 0 or 1.  Also, assuming no ties, this decreasing sequence can only be decremented by 1 or 0.

If the value of this sequence is 1 at the bottom, there is a Condorcet Winner and all Pairwise Defeats are considered.  But regardless of whether MinMax or RP is used, this ordered list is the same decreasing sequence of integer values.  If the value of this sequence of numbers is 0 at the bottom, there is no Condorcet Winner.  But, for all Pairwise Defeats having "1" below them, would not the undefeated candidate be the same candidate?

This might look like:

 

Plausible Winners ----- Pairwise Defeat

N
                             A>D
N-1
                             A>C
N-2
                             B>D
N-2
                             B>A
N-3
                             B>C
N-3
                             C>D
N-3

 

Now if N=4 then the bottom N-3 is 1 and we have a Condorcet Winner.

Now suppose we have a cycle:

Plausible Winners ----- Pairwise Defeat

N
                             A>D
N-1
                             A>B
N-2
                             B>D
N-2
                             C>D
N-2
                             B>C
N-3
                             C>A
N-4

 

Now if N=4 then the bottom N-4 is 0 and we don't have a Condorcet Winner.  But the unbeaten candidate is A whether we include the B>C Pairwise Defeats or not.  Assuming no ties, how can the unbeaten candidate be different?

You guys may have discussed this before when I wasn't paying attention, but it seems to me that if there are no ties and all of the Defeat strengths are unequal values, the ordering of this list must be the same and the number of Plausible Winners must decrease from N at the top to 1 at the bottom if there is a CW (or N to 0 if no CW).  How can MinMax and Ranked Pairs elect a different candidate?

Thank you for any attention and thought put to this.

--

r b-j                         [hidden email]

"Imagination is more important than knowledge."
 

 

 

 


----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Discounting ties, how can MinMax differ from Ranked Pairs? ooops!

robert bristow-johnson

 

I said some things wrong.  First of all, if there are N candidates, the number of Pairwise Defeats is N⋅(N-1)/2, not double that value.

Secondly, I did the scenario with the cycle wrong. I wanted several N-3 values in the decreasing sequence, not just one. But I hope you have the idea.

r b-j



---------------------------- Original Message ----------------------------
Subject: [EM] Discounting ties, how can MinMax differ from Ranked Pairs?
From: "robert bristow-johnson" <[hidden email]>
Date: Tue, June 11, 2019 9:46 pm
To: [hidden email]
--------------------------------------------------------------------------

>
>
>
> Let's assume Margins, but I think this works for Winning Votes also.
> Begin with all candidates marked as "Plausible Winner" (which means they are not yet marked as "beaten") and order all N⋅(N-1) candidate Pairwise Defeats from strongest defeat strength to weakest defeat strength.  Call that ordered list the "Original List".
> Now create another ordered list of Pairwise Defeats from the above Original List.
>  
> MinMax starts with
> the entire Original List with N⋅(N-1) entries and successively eliminates entries from the bottom up.
> Referring to a quote in this Wikipedia article: https://en.wikipedia.org/wiki/Minimax_Condorcet_method#Variants_of_the_pairwise_score , MinMax starts at the bottom and:
>      "Disregards the weakest Pairwise Defeat until one candidate is unbeaten."
>
>
>
> Similarly Ranked Pairs starts with an empty list and successively includes entries from the Original List from the top down.
> Cannot Ranked Pairs be concisely stated as:
>      "Include the strongest Pairwise Defeat until only one candidate is unbeaten."   ?
>  
> Is that not an accurate description of both
> methods?
> Now, a decreasing sequence of numbers (*not* strictly decreasing) of length N⋅(N-1)+1 that represents the number of "unbeaten" candidates (of all Pairwise Defeats above it) having
> value of N at the top, that can be thought of as having each of the N⋅(N-1) Pairwise Defeats inserted between these numbers of decreasing integer value.
> Assuming no ties, the value of this sequence at the bottom
> must be either 0 or 1.  Also, assuming no ties, this decreasing sequence can only be decremented by 1 or 0.
> If the value of this sequence is 1 at the bottom, there is a Condorcet Winner and all Pairwise Defeats are considered.  But regardless of whether MinMax or RP is used, this
> ordered list is the same decreasing sequence of integer values.  If the value of this sequence of numbers is 0 at the bottom, there is no Condorcet Winner.  But, for all Pairwise Defeats having "1" below them, would not the undefeated candidate be the same
> candidate?
> This might look like:
>  
> Plausible Winners ----- Pairwise Defeat
> N
>                              A>D
> N-1
>                              A>C
> N-2
>                              B>D
> N-2
>                              B>A
> N-3
>                              B>C
> N-3
>                              C>D
> N-3
>  
> Now if N=4 then the bottom N-3 is 1 and we have a Condorcet Winner.
> Now suppose we have a cycle:
> Plausible Winners ----- Pairwise Defeat
> N
>                              A>D
> N-1
>                              A>B
> N-2
>                              B>D
> N-2
>                              C>D
> N-2
>                              B>C
> N-3
>                              C>A
> N-4
>  
> Now if N=4 then the bottom N-4 is 0 and we don't have a Condorcet Winner.  But the unbeaten candidate is A whether we include the B>C Pairwise Defeats or not.  Assuming no ties, how can the unbeaten candidate be different?
> You guys may have discussed
> this before when I wasn't paying attention, but it seems to me that if there are no ties and all of the Defeat strengths are unequal values, the ordering of this list must be the same and the number of Plausible Winners must decrease from N at the top to 1 at the bottom if there is a CW (or N to 0
> if no CW).  How can MinMax and Ranked Pairs elect a different candidate?
> Thank you for any attention and thought put to this.
> --
>
>
> r b-j                         [hidden email]
>
>
>
> "Imagination is more important than knowledge."
>
>  
>  
>  
>  
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info
>

 

 

 


--

r b-j                         [hidden email]

"Imagination is more important than knowledge."
 

 

 

 


----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Discounting ties, how can MinMax differ from Ranked Pairs? ooops!

C.Benham

They can't when there are three candidates.  But plain MinMax doesn't meet Clone-Winner

You can have a trio of clones in a cycle who all narrowly  pairwise beat another single candidate, but
whose strongest defeats (which are only to each other) are stronger than any of that single (Condorcet Loser) candidate's
defeats (to all of them).

But Smith//MinMax doesn't have that problem and will nearly always give the same winner as Ranked Pairs
(and Schulze and River).

A very small consolation prize for MinMax(Margins) is that unlike those methods it meets Mono-add-Top (like IRV).

Chris Benham

On 12/06/2019 2:25 pm, robert bristow-johnson wrote:

 

I said some things wrong.  First of all, if there are N candidates, the number of Pairwise Defeats is N⋅(N-1)/2, not double that value.

Secondly, I did the scenario with the cycle wrong. I wanted several N-3 values in the decreasing sequence, not just one. But I hope you have the idea.

r b-j



---------------------------- Original Message ----------------------------
Subject: [EM] Discounting ties, how can MinMax differ from Ranked Pairs?
From: "robert bristow-johnson" [hidden email]
Date: Tue, June 11, 2019 9:46 pm
To: [hidden email]
--------------------------------------------------------------------------

>
>
>
> Let's assume Margins, but I think this works for Winning Votes also.
> Begin with all candidates marked as "Plausible Winner" (which means they are not yet marked as "beaten") and order all N⋅(N-1) candidate Pairwise Defeats from strongest defeat strength to weakest defeat strength.  Call that ordered list the "Original List".
> Now create another ordered list of Pairwise Defeats from the above Original List.
>  
> MinMax starts with
> the entire Original List with N⋅(N-1) entries and successively eliminates entries from the bottom up.
> Referring to a quote in this Wikipedia article: https://en.wikipedia.org/wiki/Minimax_Condorcet_method#Variants_of_the_pairwise_score , MinMax starts at the bottom and:
>      "Disregards the weakest Pairwise Defeat until one candidate is unbeaten."
>
>
>
> Similarly Ranked Pairs starts with an empty list and successively includes entries from the Original List from the top down.
> Cannot Ranked Pairs be concisely stated as:
>      "Include the strongest Pairwise Defeat until only one candidate is unbeaten."   ?
>  
> Is that not an accurate description of both
> methods?
> Now, a decreasing sequence of numbers (*not* strictly decreasing) of length N⋅(N-1)+1 that represents the number of "unbeaten" candidates (of all Pairwise Defeats above it) having
> value of N at the top, that can be thought of as having each of the N⋅(N-1) Pairwise Defeats inserted between these numbers of decreasing integer value.
> Assuming no ties, the value of this sequence at the bottom
> must be either 0 or 1.  Also, assuming no ties, this decreasing sequence can only be decremented by 1 or 0.
> If the value of this sequence is 1 at the bottom, there is a Condorcet Winner and all Pairwise Defeats are considered.  But regardless of whether MinMax or RP is used, this
> ordered list is the same decreasing sequence of integer values.  If the value of this sequence of numbers is 0 at the bottom, there is no Condorcet Winner.  But, for all Pairwise Defeats having "1" below them, would not the undefeated candidate be the same
> candidate?
> This might look like:
>  
> Plausible Winners ----- Pairwise Defeat
> N
>                              A>D
> N-1
>                              A>C
> N-2
>                              B>D
> N-2
>                              B>A
> N-3
>                              B>C
> N-3
>                              C>D
> N-3
>  
> Now if N=4 then the bottom N-3 is 1 and we have a Condorcet Winner.
> Now suppose we have a cycle:
> Plausible Winners ----- Pairwise Defeat
> N
>                              A>D
> N-1
>                              A>B
> N-2
>                              B>D
> N-2
>                              C>D
> N-2
>                              B>C
> N-3
>                              C>A
> N-4
>  
> Now if N=4 then the bottom N-4 is 0 and we don't have a Condorcet Winner.  But the unbeaten candidate is A whether we include the B>C Pairwise Defeats or not.  Assuming no ties, how can the unbeaten candidate be different?
> You guys may have discussed
> this before when I wasn't paying attention, but it seems to me that if there are no ties and all of the Defeat strengths are unequal values, the ordering of this list must be the same and the number of Plausible Winners must decrease from N at the top to 1 at the bottom if there is a CW (or N to 0
> if no CW).  How can MinMax and Ranked Pairs elect a different candidate?
> Thank you for any attention and thought put to this.
> --
>
>
> r b-j                         [hidden email]
>
>
>
> "Imagination is more important than knowledge."
>
>  
>  
>  
>  
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info
>

 

 

 


--

r b-j                         [hidden email]

"Imagination is more important than knowledge."
 

 

 

 


----
Election-Methods mailing list - see https://electorama.com/em for list info

Virus-free. www.avg.com

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Discounting ties, how can MinMax differ from Ranked Pairs? ooops!

robert bristow-johnson



---------------------------- Original Message ----------------------------
Subject: Re: [EM] Discounting ties, how can MinMax differ from Ranked Pairs? ooops!
From: "C.Benham" <[hidden email]>
Date: Tue, June 11, 2019 10:37 pm
To: [hidden email]
"[hidden email]" <[hidden email]>
Cc: "John M" <[hidden email]>
--------------------------------------------------------------------------

> They can't when there are three candidates.

You mean 3 candidates in the Smith set, right?  There might be 4 or more candidates, but if the cycle only involves three (like Rock-Paper-Scissors), I think that MinMax, RP, and Schulze all elect the same candidate, no?

So here's another issue:

While I think that ties of votes will be rare (but i was once at a Dem caucus for mayor in Burlington in 2012 where the caucus was tied with ca. 830 voters), i wonder if Margins might be tied more often.

If we're doing RP or MinMax using Margins, how might we order it if the Margins are tied between two pairwise races?  I can kinda conceive how it would make a difference in a weird case.  Which is better?  A higher Winning Votes or a lower Losing Votes?  With a fixed Margin, a lower Losing Votes (which makes the total votes lower) means that the Margin corresponds to a higher percent margin.  Maybe that's better than Winning Votes.  What do you guys think?


--

r b-j                         [hidden email]

"Imagination is more important than knowledge."
 

 

 

 


----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Discounting ties, how can MinMax differ from Ranked Pairs? ooops!

John
In reply to this post by C.Benham


On Wed, Jun 12, 2019 at 1:37 AM C.Benham <[hidden email]> wrote:

They can't when there are three candidates.  But plain MinMax doesn't meet Clone-Winner

You can have a trio of clones in a cycle who all narrowly  pairwise beat another single candidate, but
whose strongest defeats (which are only to each other) are stronger than any of that single (Condorcet Loser) candidate's
defeats (to all of them).

But Smith//MinMax doesn't have that problem and will nearly always give the same winner as Ranked Pairs
(and Schulze and River).

A very small consolation prize for MinMax(Margins) is that unlike those methods it meets Mono-add-Top (like IRV).

How does all of this compare to Tideman's Alternative?

1.  Identify Condorcet winner;
2.  If no Condorcet winner, identify Top Cycle;
3.  Eliminate all candidates not in Top Cycle;
4.  Eliminate remaining candidate with fewest votes;
5.  Go to 1.

I tend to use the Schwartz Set for the Condorcet Winner, and the Smith Set for the Top Cycle.  I've found the Schwartz Set is nearly always one candidate. 

I know TA is independent of smith-dominated alternatives, but I haven't determined if it's LIIA or reversal-symmetry (apparently Schulze isn't LIIA and ranked pairs is, but I don't see how).  I doubt it satisfies later-no-harm and later-no-help, but the run-off step at 4 might allow it to.

Chris Benham

On 12/06/2019 2:25 pm, robert bristow-johnson wrote:

 

I said some things wrong.  First of all, if there are N candidates, the number of Pairwise Defeats is N⋅(N-1)/2, not double that value.

Secondly, I did the scenario with the cycle wrong. I wanted several N-3 values in the decreasing sequence, not just one. But I hope you have the idea.

r b-j



---------------------------- Original Message ----------------------------
Subject: [EM] Discounting ties, how can MinMax differ from Ranked Pairs?
From: "robert bristow-johnson" [hidden email]
Date: Tue, June 11, 2019 9:46 pm
To: [hidden email]
--------------------------------------------------------------------------

>
>
>
> Let's assume Margins, but I think this works for Winning Votes also.
> Begin with all candidates marked as "Plausible Winner" (which means they are not yet marked as "beaten") and order all N⋅(N-1) candidate Pairwise Defeats from strongest defeat strength to weakest defeat strength.  Call that ordered list the "Original List".
> Now create another ordered list of Pairwise Defeats from the above Original List.
>  
> MinMax starts with
> the entire Original List with N⋅(N-1) entries and successively eliminates entries from the bottom up.
> Referring to a quote in this Wikipedia article: https://en.wikipedia.org/wiki/Minimax_Condorcet_method#Variants_of_the_pairwise_score , MinMax starts at the bottom and:
>      "Disregards the weakest Pairwise Defeat until one candidate is unbeaten."
>
>
>
> Similarly Ranked Pairs starts with an empty list and successively includes entries from the Original List from the top down.
> Cannot Ranked Pairs be concisely stated as:
>      "Include the strongest Pairwise Defeat until only one candidate is unbeaten."   ?
>  
> Is that not an accurate description of both
> methods?
> Now, a decreasing sequence of numbers (*not* strictly decreasing) of length N⋅(N-1)+1 that represents the number of "unbeaten" candidates (of all Pairwise Defeats above it) having
> value of N at the top, that can be thought of as having each of the N⋅(N-1) Pairwise Defeats inserted between these numbers of decreasing integer value.
> Assuming no ties, the value of this sequence at the bottom
> must be either 0 or 1.  Also, assuming no ties, this decreasing sequence can only be decremented by 1 or 0.
> If the value of this sequence is 1 at the bottom, there is a Condorcet Winner and all Pairwise Defeats are considered.  But regardless of whether MinMax or RP is used, this
> ordered list is the same decreasing sequence of integer values.  If the value of this sequence of numbers is 0 at the bottom, there is no Condorcet Winner.  But, for all Pairwise Defeats having "1" below them, would not the undefeated candidate be the same
> candidate?
> This might look like:
>  
> Plausible Winners ----- Pairwise Defeat
> N
>                              A>D
> N-1
>                              A>C
> N-2
>                              B>D
> N-2
>                              B>A
> N-3
>                              B>C
> N-3
>                              C>D
> N-3
>  
> Now if N=4 then the bottom N-3 is 1 and we have a Condorcet Winner.
> Now suppose we have a cycle:
> Plausible Winners ----- Pairwise Defeat
> N
>                              A>D
> N-1
>                              A>B
> N-2
>                              B>D
> N-2
>                              C>D
> N-2
>                              B>C
> N-3
>                              C>A
> N-4
>  
> Now if N=4 then the bottom N-4 is 0 and we don't have a Condorcet Winner.  But the unbeaten candidate is A whether we include the B>C Pairwise Defeats or not.  Assuming no ties, how can the unbeaten candidate be different?
> You guys may have discussed
> this before when I wasn't paying attention, but it seems to me that if there are no ties and all of the Defeat strengths are unequal values, the ordering of this list must be the same and the number of Plausible Winners must decrease from N at the top to 1 at the bottom if there is a CW (or N to 0
> if no CW).  How can MinMax and Ranked Pairs elect a different candidate?
> Thank you for any attention and thought put to this.
> --
>
>
> r b-j                         [hidden email]
>
>
>
> "Imagination is more important than knowledge."
>
>  
>  
>  
>  
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info
>

 

 

 


--

r b-j                         [hidden email]

"Imagination is more important than knowledge."
 

 

 

 


----
Election-Methods mailing list - see https://electorama.com/em for list info

Virus-free. www.avg.com

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Discounting ties, how can MinMax differ from Ranked Pairs? ooops!

Kristofer Munsterhjelm-3
In reply to this post by robert bristow-johnson
On 12/06/2019 09.27, robert bristow-johnson wrote:

> While I think that ties of votes will be rare (but i was once at a Dem
> caucus for mayor in Burlington in 2012 where the caucus was tied with
> ca. 830 voters), i wonder if Margins might be tied more often.
>
> If we're doing RP or MinMax using Margins, how might we order it if the
> Margins are tied between two pairwise races?  I can kinda conceive how
> it would make a difference in a weird case.  Which is better?  A higher
> Winning Votes or a lower Losing Votes?  With a fixed Margin, a lower
> Losing Votes (which makes the total votes lower) means that the Margin
> corresponds to a higher percent margin.  Maybe that's better than
> Winning Votes.  What do you guys think?

For breaking ties in Minmax, I like what I've called "Ext-Minmax". In
ordinary Minmax, the winner has the best worst defeat against him (i.e.
it's the A so that the greatest value of X>A is the least, for some X).
In Ext-Minmax, just break ties by the next-to-greatest defeat. If there
are still any ties, break by third greatest defeat, and so on.

I wonder if there's anything that's to Schulze what Ext-Minmax is to
Minmax, but I haven't yet found any equally intuitive extensions. (That
said, I haven't been looking hard either.)
----
Election-Methods mailing list - see https://electorama.com/em for list info