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

[Gervase Lam]

Rather than trying to be a posts about a particular method, these will be 
"stream of consciousness" posts about a few techniques/algorithms that 
could possibly be used in for Multi-Winner Pairwise methods.  There were 
quite a few things that inspired me, including the way MinMax works under 
the hood, voter space and Kemeny-Young.

It could be said that for a multi-winner election, the winners need to be 
as unlike to each other as possible.  This could be done using Voter 
Space.  (Please correct me if I am abusing the definition of Voter Space).

What I am about to describe is analogous to plants in a plot of land.  The 
aim is to start off with the seeds of the plants being as far apart from 
each other as possible.  However, conditions may mean that when the plants 
grow, they grow towards where the sun rises or whatever.

What follows is a description for a method.

(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.  (Though this is not necessary, it does 
make things easier).

Each ballot pairwise matrix is put 'head-to-head' with each other 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 head-to-heads are then listed in ascending score order.  Let this list 
be called H.

Go down the list H until a head-to-head is reached that has a ballot which 
is involved in at least N head-to-heads at or above the head-to-head just 
reached.

Let the ballot be called B.
Let the head-to-head just reached be called R.
Let the head-to-heads involving the ballot B at or above R be called h.

Make a list l of ALL of the ballots involved in h.

For each (non-deleted) ballot (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 (2).

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 ballots in it, the list of ballots l is 
the set of ballots that are unlike to each other.  Therefore, l is the 
list of Seed ballots

(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.

(3) Ignoring the seed ballots that have 1 ballot associated with them, 
repeat (2) until all of the seed ballots have 1 ballot associated with 
them.

(4) Repeat step (3) except ignore seed ballots that have N ballots 
associated with them.  N increases from 2 upwards until all of the ballots 
have been associated with a seed ballot.

(E) For each of the N seed ballots, determine the pairwise winner using 
the ballots associated with the seed ballot.  You now (hopefully) have N 
winners.

One problem with this method is that there may turn out to be less than N 
winners.  One solution I thought of was to repeat the whole process except 
use N+1, N+2, N+3, etc... seed ballots until the required number of 
winners is found.  Very kludgey.

I will (sort of) mention other solutions to this problem and variations of 
the above method in the next post.

Thanks,
Gervase.