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. ---- Election-methods mailing list - see http://electorama.com/em for list info