[EM] Possible Multi-Winner Pairwise techniques/algorithms (Part 1)
Gervase Lam
gervase.lam at group.force9.co.uk
Sat May 28 19:02:21 PDT 2005
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.
More information about the Election-Methods
mailing list