[EM] Sorting algorithms applied to candidate ranking

[Richard, the VoteFair guy]

On 3/31/2023 9:49 PM, Forest Simmons wrote:
 > The SPE finish order is obtained by bubble sorting the agenda order
 > pairwise.

Using a sorting technique is similar to what I worked out years ago for 
estimating(!) Condorcet-Kemeny results.

The following code includes the function 
"calc_votefair_insertion_sort_popularity_rank" which describes the 
sorting algorithm in the comments.

https://github.com/cpsolver/VoteFair-ranking-cpp/blob/master/votefair_ranking.cpp

This algorithm uses a variation of standard "insertion sorting."

The nice characteristic of this sorting algorithm is that sorting only 
requires pairwise reversals between two adjacent candidates, and the 
sequence scores (which are the inverse of the scores John Kemeny refers 
to) can be compared just by looking at two pairwise vote counts.  In 
other words, none of the other pairwise counts in the pairwise matrix 
are involved when choosing whether to swap those two adjacent candidates.

Clarification:  As Kristofer points out, there are contrived (highly 
cyclic) cases where the results do not match Kemeny results.  Yet the 
top 7 or so candidates can be identified and run through the full Kemeny 
calculations to identify the winner.  It's possible the Kemeny winner 
from the full set of candidates does not get identified as one of the 
top 7 candidates, but in those contrived cases any winner would be 
controversial (in the same way that an algorithm for finding the highest 
mountain would produce controversial results if it were used to find the 
highest sand dune in a desert).

If anyone has questions, just ask.

Richard Fobes
The VoteFair guy



On 3/31/2023 9:49 PM, Forest Simmons wrote:
> I would like to run by you guys an example of a new type of agenda based 
> method that returns a beatpath finish order.
> 
> The input is precisely the same input needed for Sequential Pairwise 
> Elimination ... namely an agenda of alternatives, along with a pairwise 
> win loss tie table.
> 
> The SPE finish order is obtained by bubble sorting the agenda order 
> pairwise.
> 
> To pairwise sort a list of alternatives you repeatedly rectify adjacent 
> pairs that are out of order pairwise ... until there  no longer remain 
> any adjacent pairs out of order ... the same way drill sergeants get the 
> new 'cruits lined up in order of height for their manual of arms and 
> marching drill.
> 
> When rectification priority is given to out of order pairs closer to the 
> unfavorable end of the agenda, we call the pairwise sort a "bubble sort."
> 
> The SPE finish order is the order of the bubble Sorted agenda.
> 
> On the other hand, when rectification priority is given to pairs nearer 
> the favorable end of the agenda, the process is called"sink sorting".
> 
> The head of the sink sort finish order is called the "Definitive 
> Majority Choice" (DMC) alternative.
> 
>   Both the SPE and DMC finish orders are vulnerable to burial and 
> "chicken defection" gambits ... to which the following brand new agenda 
> processing method seems to be highly resistant:
> 
> After sink sorting the agenda, (perversely!) transpose the pair at the 
> favorable end of the resulting list ... before a final bubble sort to 
> arrive at the final finish order.
> 
> In stack based Reverse Polish Notation lingo, we could call the method ...
> "Agenda Sink Swap Bubble."
> 
> This method satisfies Independence from Smith Dominated Alternatives 
> ISDA, because both Sink and Bubble move Smith solidly to the favorable 
> end of the list.
> 
> Example:
> 
> 45 A>B(Sincere A>C)
> 30 B>C
> 25 C>A
> 
> The A faction seems to be counting on an agenda order of (unfavorable to 
> favorable) C B A, which would result in a win for A, which is both the 
> SPE and DMC winner, not to mention Classical Condorcet(winning votes) 
> winner.
> 
> But under Agenda Sink Swap Bubble (ASSB) ...
> the Sink does nothing because no adjacent pair is out of order pairwise.
> 
> The Swap  transposes the pair located at the favorable (right) end of 
> the list ... resulting in the list C A B.
> 
> "Bubble" starts on the left (unfavorable) end ... resulting in A C B.
> 
> So B ends up at the favorable end of the finish order ... a big 
> disappointment to the A faction buriers.
> 
> This method has a sincerity check:
> 
> Take the finish order and apply another short Swap Bubble combo ... 
> resulting in the order ... "challenge" ... B A C ... with C at the head.
> 
> A fresh binary, conclusive vote (with fresh ballots) is taken to decide 
> once and for all between the original finish order and the challenge 
> finish order ... the question is which of these two finish orders do you 
> prefer?
> 
> Because C is the sincere CW and B is the sincere Condorcet Loser ... it 
> is almost certain that a majority of the participating  voters will 
> prefer the challenge order .. which ranks C first and B last.
> 
> Clean & Nifty ... or what?
> 
> Try it out on your favorite scenario involving a burial or chicken 
> defection.
> 
> Thanks!
> 
> -Forest
> 
> 
> 
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info