[EM] Median bifurcation using pairwise matrix
royone at yahoo.com
Mon Aug 13 14:14:13 PDT 2001
For those I annoy by posting too much (not that anyone has complained
yet, bless you all), I apologize. I get excited by some ideas and
share them before they're half-baked. I assure you that this idea is
quite half-baked. Possibly even more.
Anyway, having done at least a little browsing the archives, it seems
bifurcation has not been much explored as an elimination method, and
I think it shows promise. Of course, if you name an election
method "Median Bifurcation", which sounds rather like a digestive
problem, it's going to start out with a handicap, compared to
something with a friendly name like "IRV".
Bifurcation is the process of dividing a group into two sub-groups,
generally to further divide each sub-group until you've got all
groups of one or two, which are processed by some trivial method.
It's used in searching and sorting, and most other recursive computer
Median bifurcation groups candidates by whether a majority of voters
rank them in the upper half of the group they're listed with. It can
be used to completely rank candidates. It is my fondest wish that it
is functionally equivalent to Ranked Pairs, but without the ad hoc
feel of having to keep a sharp lookout for contradictions.
I have found that rather than having to go back to the ballots to re-
establish the rankings after candidates are eliminated, it can all be
done with the pairwise matrix that Borda counts and Ranked Pairs use.
Either matrix can be used (recording all pairwise contests, or only
the winning margins).
First, notice that if you sum all the rows, then sum those totals,
you'll get the same number as if you sum all the columns and sum
*those* numbers. (Let's all say it together: Duh.) The rows indicate
wins for each candidate, the columns indicate losses. If a candidate
has a higher total in his row than in his column, he's in the upper
half. And because the rows and columns total out the same, there's
going to be a lower half -- candidates whose row totals are less than
or equal to their column totals. (Note: "half" refers to median rank
here. With N candidates, as many as N-1 can be in one "half". In a
very special case, all of them could have row_total = column_total,
calling for a special rule.)
Make a table for each new group. Compute row and column totals, and
find the new winners and losers in each table by the same method,
until you've got all "groups" of one.
More information about the Election-Methods