[EM] Possible Multi-Winner Pairwise techniques/algorithms (Part 2)

[Gervase Lam]

Rather than starting from scratch, I thought I would instead quote my own 
e-mail so that I don't have to re-explain myself.  The quotes have also 
been (sort of) moved about slightly.

> From: Gervase Lam
> Subject: Possible Multi-Winner Pairwise techniques/algorithms (Part 1)
> Date: Sunday 29 May 2005 03:02 am

> (1) Where N is the number of winners, find a set of N ballots such that
> the ballots in the set are unlike to each other as possible.  These will
> will be Seed ballots.
>
> To do this, each ballot is converted into a 'ballot' pairwise matrix.
> Remove any duplicate matrices.

Instead of N seed ballots, why not have every ballot being a seed ballot.  
As mentioned above, duplicate rankings are removed.

The method continues as described in my previous post.  However, this time 
there are many more seed ballots to handle.

> (2) From the ballots that have not yet been associated with a seed
> ballot, find the ballot that is the most similar to any one of the seed
> ballots. This will be done in a similar way to how the Seed ballots were
> obtained.
>
> Convert the Seed ballots into pairwise matrices.  Convert the ballots
> into pairwise matrices.
>
> Each ballot pairwise matrix is put "head-to-head" with each Seed ballot
> pairwise matrix.  A score is given to this "head-to-head" by giving 1
> point for each cell/element that is the same in both matrices.  The
> larger the score, more similar a ballot is to a seed ballot.
>
> Associate together the ballot and the seed ballot with the largest
> score. For example, if one of the seed ballots has the ranking A>B>C>D,
> the ballot A>B>C>D would be associated with the seed ballot.

Instead of doing just stopping after associating a ballot with a seed 
ballot, continue associating the ballot with the next closest seed ballot, 
and then the next closest and so on.  However, each time, the weighting of 
the ballot is reduced to 1/2 when associating with the 2nd closest seed 
ballot, to 1/3 when associating with the 3rd closest seed ballot and so on.

(Instead of giving each ballot a weight 1, 1/2, 1/3, etc..., my original 
idea was to give the ballot a weighting equaling the "Kemeny-Young 
closeness" score.  Quoted from Part 1 (1), this score is calculated in the 
following manner...)

> [The seed] ballot pairwise matrix is put 'head-to-head' with [the]
> pairwise matrix [of the ballot].  A score is given to this 'head-to-head'
> by giving 1 point for each cell/element that is the same in both
> matrices.

After associating all of the ballots in this way, determine the pairwise 
winners for each seed ballot using each seed ballot's (weighted) ballots.  
The next step is to determine the N winners.

To do this, the same technique that is described to get the "Kemeny-Young 
closeness" could be used.  However, this won't work for the seed ballots' 
pairwise matrices because the matrices have different weightings.  Also, 
I want to promote pairwise matrices that have strong support (i.e. the 
numbers in the matrix are large, not small).

Let M1 and M2 be two seed ballots matrices being compared.  For each 
pairwise comparison between candidates i and j, calculate a "comparison" 
score:

C(i, j) = M1[i, j] * M2[j, i]

Add up all of the C(i, j) for each pairwise comparison to get S.  S is the 
"head-to-head" score between M1 and M2.

The more dissimilar the ballots M1 and M2 are to each other, the larger S 
is.  However, if either or both of M1 and M2 have little support, then S 
will be small.

> The head-to-heads are then listed in ascending score order.  Let this
> list be called H.

The head-to-heads need to be listed in descending S score order.

> Go down the list H until a head-to-head is reached that has a [matrix]
> which is involved in at least N head-to-heads at or above the
> head-to-head just reached.
>
> Let the [matrix] be called [M1].
> Let the head-to-head just reached be called R.
> Let the head-to-heads involving [matrix M1] at or above R be called h.

As mentioned above, the head-to-head between matrices M1 and M2 is given a 
score S.  If M1 and M2 do have the same pairwise winner, remove the 
head-to-head from h.

I then continued:

> Make a list l of ALL of the [matrices] involved in h.
>
> For each (non-deleted) [matrix] (which shall be called x) in l:
>
> (i) Get the head-to-heads involving x at or above R.
> (ii) List out the ballots that are in the head-to-heads.
> (iii) Delete from l the ballots not in the list made in step (ii).
>
> If the number of ballots in list l falls below N, then continue down the
> list H one head-to-head at time, formulating a list l each time.  When a
> list l is formulated that has N [matrices] in it, the list of ballots l
> is the set of [matrices] that are unlike to each other.

Calculate the pairwise winners of the matrices (which should have 
different winners due to the new 'clause' I added in to disallow M1 and M2 
having the same pairwise winner).  The pairwise winners are the N winners 
required to win the election.

Whereas it is possible for the method in Part 1 to not get enough winners 
in the first attempt, this method is more likely to get N winners in the 
"first attempt".  However, if there aren't N different winners from all of 
the seed ballots' pairwise matrices, this method fails.

Thanks,
Gervase.