RE: Constitutional voting, definition of cummulative prefererence
Raul Miller wrote:
> I would like to know if anyone have a specific problem with the following
> concept of cumulative preference:
>
> An individual ballot prefers option A to option B, if:
>
> (*) Option A is mentioned at some preference, and option B is not
> mentioned at all, or
> (*) Option A is mentioned at a lower cannonical preference number than
> option B. [For example: 1st is a lower cannonical number than
> 5th, so a ballot which rated option A as its 1st preference and
> option B as its 5th preference would prefer option A to option B.]
>
This is a clear definition of 'prefers', which is better than the existing
constitutional wording in that it indicates how truncated ballots should be
handled. Clarifying this is a good idea if the constitution is amended, and
your interpretation is the same as the one that Debian is currently using,
based on my analysis of previous voting results. Treating unranked
candidates the same as if they had been ranked equally in last place is also
the assumption we always make on the Election-Methods list. It is always
desireable to assume this meaning with pairwise methods, otherwise a voter
who truncates will not effectively indicate any preference between his
ranked and unranked choices, and this will have unintended results. For
example, it would be generally unreasonable to assume that if someone votes:
A>B>C
out of five candidates {A,B,C,D,E}
that s/he actually considers E to be as good as A, yet that's how this vote
will be treated if the method doesn't assume the ranked candidates are
preferred to unranked! In other words, interpreting this ballot to mean:
A>B>C>(D=E)
would be sensible; interpreting it as:
A>B>C, (A=D=E), (B=D=E), (C=D=E)
would not. This would have no effect in a method like STV, but for pairwise
methods it is a critical issue. Fortunately, it appears that Debian has
been handling this correctly all along.
One point though -- I recommend that you avoid reference to numerical
rankings in the constitutional wording. So long as ballots are submitted by
e-mail, it may make sense for voters to number the options. In the future,
however, you might use a web interface or some other technique for ordering
candidates in which the options don't even have visible numbers, but are
ordered graphically, with preferred options at the top, and disliked options
at the bottom. If Debian is saddled with restrictive language that requires
preferences to be numbered, the constitution might need to be changed again
to accommodate the different method(s) of expressing a ranking (or
nitpickers might challenge results, etc.). I think it would be better to
just use general terms like 'ranked higher' and 'ranked lower', and leave
the specifics to an ordinary voters' guide, rather than embed these details
in the constitution.
> A set of ballots cumulatively prefers option A to option B if:
>
> * more individual ballots individually prefer option A to option B than
> prefer option B to option A, or
> * There is an option C, where A is cumulatively preferred to option C,
> and option C is cumulatively preferred to option B.
>
I am not exactly sure why you are defining 'cumulatively preferred' to
indicate transitive majority preference between options, so I can't say for
certain whether or not this is a good idea, because I don't know what you
intend to use it for. However:
1) Almost all pairwise methods deal exclusively with whether one option A is
preferred/beats/defeats/dominates another, but this is a simple option-pair
comparison that does not imply any sort of transitivity. To define most
pairwise methods, it is important to precisely define this simple
relationship and label it; Debian's existing term, 'dominates' is as good as
any.
2) The term 'cumulative' implies an additive rather than transitive
relationship, so it would probably be better to say 'transitively preferred'
rather than cumulatively preferred. Another reason to avoid the term
'cumulative' is that it is frequently used in connection with an inferior
multi-winner voting method called 'cumulative voting', in which each voter
gets an equal parcel of votes (usually 3 or so), and allocates these as they
desire among the candidates (3 on one candidate, 1 each on 3 candidates,
etc.) Using this term in connection with pairwise voting may result in
confusion if voters are familiar with the cumulative voting method, and
think this has something to do with Debian's count rules.
3) It is not necessary to define 'cumulatively preferred' unless it is used
as part of a voting method definition, and I'd need to see the whole method
in order to judge the merits of your system. I am aware of only one (truly
excellent) pairwise method which makes use of a similar concept called
'beatpaths', that may interest you. One possible definition of Schulze's
beatpath method is as follows:
*****
Schulze's Method (brief definition):
Candidate A "beats" candidate B if more voters rank A over B than
vice-versa. The strength of that victory is the number of voters who ranked
A over B.
There's a "beat-path" from A to B if either A beats B, or if A beats
something that has a beat-path to B. The strength of a beat-path is
measured by its weakest victory.
Candidate A "defeats" candidate B if A has a stronger beat-path to B than B
has to A.
The winners are those candidates who are undefeated. If there is more than
one winner, exclude all the defeated candidates from the election and
reapply the method until a single winner is found.
*****
Here is an example of how to apply Schulze's method:
Candidates: {A,B,C,D,E}
Ballots:
9: A>B>C>D>E
8: B>A>C>E>D
15: C>E>D>B>A
16: D>E>A>B>C
Pairwise Beats:
"Candidate A "beats" candidate B if more voters rank A over B than
vice-versa. The strength of that victory is the number of voters who ranked
A over B."
(it is a good idea to represent the following information in a square
'pairwise' matrix, where the rows and columns represent the options, and
each cell contains the number of votes for the row option compared to the
column option)
A>B 25:23
{A,B}>C 33:15
C>{D,E} 32:16
{D,E}>{A,B} 31:17
D>E 25:23
Beat-Path Defeats:
"There's a "beat-path" from A to B if either A beats B, or if A beats
something that has a beat-path to B. The strength of a beat-path is
measured by its weakest victory. Candidate A "defeats" candidate B if A has
a stronger beat-path to B than B has to A."
(again, construct a 'beatpath matrix', similar to the pairwise matrix to
hold the strength of each beatpath. To determine beatpath strengths,
construct a network graph with each option represented as a node and each
pairwin as a directed link from the winner to the loser. Find the strongest
path between every pair of candidates, and store it in the beatpath matrix.
If automated, this step is a simple 'shortest-path' problem that can be
solved in O(n^3)).
(A=B 31:31)
A>>C 33:31
A>>D 32:31
A>>E 32:31
B>>C 33:31
B>>D 32:31
B>>E 32:31
C>>D 32:31
C>>E 32:31
(D=E 31:31)
Winners: {A,B}
"The winners are those candidates who are undefeated. If there is more than
one winner, exclude all the defeated candidates from the election and
reapply the method until a single winner is found."
(circle the beatpath win (if any) for each pair of candidates; any column
which contains no circles represents an undefeated candidate that is part of
the winner set (usually just one candidate))
Reapplying Schulze's method, we get:
Candidates: {A,B}
Pairwise Beats: A>B 25:23
Beat-Path Defeats: A>>B 25:23
Winners: {A}
*****
As you can see, Schulze uses the concept of a 'beatpath' as a means of
choosing a winner, by assigning a strength value to all the possible
'cumulative preferences' (your terminology), and then comparing those
numbers pairwise to determine the winner. This method satisfies a whole
raft of useful criteria*, and would be an excellent replacement for Debian's
'Concorde' voting rule (as would Tideman's 'ranked-pairs' method). I can
certainly provide you with more information about the properties of this
method, and explanations of these criteria if you are interested. However,
most methods which use transitive preferences probably contain serious
flaws, so it is better to adopt a method which is tested and known to work
well, than devise a new method which probably has hidden, undesireable
properties.
--
Norm Petry
* Some of the criteria satisfied by the Schulze beatpath method include:
Smith Criterion
Condorcet Winner Criterion
Condorcet Loser Criterion
Clone Independence Criterion
Beatpath GMC (Generalised Majority Criterion)
Reversal Symmetry (prevents 'strange' outcomes)
Modified Independence from Irrelevant Alternatives (MIIAC)
Mike Ossipoff's Strategy Criteria for ranked methods (various)
etc.
There are extensive discussions of these and other criteria in the EM list
archives. You can find a link at
http://www.eskimo.com/~robla/cpr/election-methods.html In particular, refer
to the following message:
Date: Sat, 04 Oct 1997 18:12:49 +0200
To: election-methods-list@eskimo.com
From: Markus Schulze <schulze@sol.physik.tu-berlin.de>
Subject: Re: Condorect sub-cycle rule
in which the beatpath method is first described and justified. Note however
that the Schulze beatpath method is mistakenly referred to there as
'Tideman's method', but Tideman's 'ranked-pairs' rule is a different
procedure which is *also* defined later in the same message -- these two
methods are *not* equivalent (although presumably Markus Schulze thought
they were at the time).
N.
Reply to: