[EM] Basic Monotony
jweins123 at hotmail.com
Wed Jan 30 01:22:13 PST 2002
The idea of monotony (or, if you like, of monotonicity) of an election
method is quite intuitive. However, getting a workably simple and broadly
applicable precise definition - a goal of many recent postings, some quite
elaborate or convoluted - is another story. The quest for a canonical
definition may well turn out to be infeasible: as a plain fact, there may
be a variety of useful precise concepts of monotone (or monotonic)
methods. However, we may still hope to agree on a simple minimum but
broadly applicable such concept.
The Postscript below offers and discusses such a concept (maybe new, maybe
already known), termed basic monotony. The discussion first describes the
broad scope of methods covered (they include all usual one- and many
multi-winner methods); then it reviews general monotony intuitions and
corresponding precise criteria; and it concludes by treating basic monotony.
Basic monotony is arguably the WEAKEST (i.e., most inclusive) reasonable
monotony concept. All methods commonly rated monotone seem in fact to be
basic monotone, and extant proofs and examples which affirm or refute
monotony in fact affirm or refute basic monotony.
At the same time, as shown below by some very simple concluding examples,
basic monotony is also in a sense the STRONGEST (most restrictive)
reasonable broadly applicable concept. Many basic-monotone methods (e.g.
Borda, and most usual unconstrained CR more complex than Approval) fail the
very simplest reasonable stronger-than-basic monotony criterion.
A later posting will note three sorts of simple example elections (few
voters, few candidates, two precincts) which relate monotony and
consistency. Here is a summary of their import:
* IRV is neither consistent nor basic-monotone.
* The method (termed Bucklins, I am told) which scores each candidate
by median grade, although obviously basic-monotone, is not consistent.
* A consistent method need NOT (?) be basic-monotone!
Thanks for your heed and comments,
Long Beach, CA USA
POSTSCRIPT: BASIC MONOTONY defined and discussed
SIDE QUIBBLE (before we get down to business!). In our EM-list discussions
we dont really mean monotone! Thats because there are two ways a
process (or, mathematically, a function) can be monotone: in the same
direction (increasing: more input yields more output) and in the
opposite direction (decreasing: more input yields less output). The
respective terms are isotone and antitone (or, if you like, isotonic
and antitonic). EM-list monotone really means isotone! For
familiarity, I too will use monotone rather than isotone.
SCOPE OF ELECTION METHODS CONSIDERED. We treat election methods M, for use
in elections for one or more equivalent offices, wherein a marked ballot is
readily coded in a natural commonly agreed-on way as a Cardinal-Ratings-type
ballot. In such a ballot, the voter assigns each candidate one of a fully
ordered set of at least two grades or ratings or ranks. These grades
may be coded as consecutive integer values 0 (lowest), 1, ..., MAXGRADE
Method M prescribes the value MAXGRADE and moreover may impose constraints
on what sorts of grade distributions are allowed on a valid marked ballot.
For instance, strict-ranking methods such as classic Borda or IRV require
that MAXGRADE + 1 = number of candidates, and that each grade be awarded to
exactly one candidate.
Method M also prescribes how to treat a truncated ballot, i.e. one not
fully marked. Depending on M, the ballot is either invalid or else is
equated to a default fully-marked ballot.
To the set of fully marked ballots, method M applies an evaluation
algorithm, and thereby partitions the set of candidates into two sets, - the
winners and the losers. For ties - i.e. winners exceed contested offices -
a randomizing method selects the officeholders from the winners.
The above class of methods includes all usual one-winner and many
multi-winner methods, e.g.: Lone-mark plurality and other Cumulative
methods, Approval and other unconstrained or constrained Cardinal Ratings
methods; Pairwise-Comparisons methods a la Condorcet; and Borda. A readily
treated extension of the class includes methods, like IRV, which may have
several evaluation stages, each possibly with a tie-breaking randomization.
MONOTONY: GENERAL CONCEPT. For brevity lets use the term swap for a
process which revises some marked ballots of an election: that is, each
initial ballot B1 of some set (the swapped set) of marked ballots is
replaced by an altered marked ballot B2, got from B1 by changing certain of
the initially assigned grades.
The various usual defined versions of monotony have a common logical
structure. Namely, each version concerns the effects of certain
well-defined special swaps. For each special swap and each candidate X,
the swap is defined to do one of three things: favor X or disfavor X or
disregard (be neutral on) X.
Whenever a special swap favors X, monotony requires that the status of X not
change from winner to loser. (In a stronger version of monotony - which I
note but will not further discuss or be using - the status of X as winner
must not be diluted, i.e. X cannot be forced into a tie, or into a larger
pool of already-tied winners.)
Whenever a special swap disfavors X, monotony requires that the status of X
not change from loser to winner.
BASIC MONOTONY. Basic monotony uses just a minimal repertoire of special
swaps, called basic swaps. It will be evident that a basic swap
qualifies as a special swap for every reasonable monotony concept . The
following terminology is useful for defining basic swap:
A swap plainly favors candidate X if some ballot is changed to award
candidate X a higher grade, and no ballot is changed to award candidate X a
Similarly, a swap plainly disfavors candidate X if some ballot is changed
to award candidate X a lower grade, and no ballot is changed to award
candidate X a higher grade.
A swap plainly disregards candidate X if on no ballot does the grade for
A swap is basic if it (1) plainly favors at most one candidate, (2)
plainly disfavors at most one candidate, and (3) plainly disregards all
other candidates (i.e. all but the at most two candidates that are plainly
favored or plainly disfavored).
The definition of basic monotony takes as special just the basic swaps, and
no others. For this definition, a basic swap is defined to favor,
disfavor or disregard a candidate X according as the swap plainly favors
or plainly favors or plainly disregards X.
IS BASIC MONOTONY MEANINGFUL? For a meaningful monotony definition, the
family of special swaps must be sufficiently large and varied. This is a
nontrivial condition, as many methods (such as strict ranking methods)
severely constrain the allowed grade distributions and thus also the valid
ballots and the possible swaps.
However, EVERY reasonable election method M allows lots of basic swapping!
Thats because such M must be fair - or permutable or exchangeable -
in respect of marking of the different candidates. More formally, given any
two candidates X and Y, if B1 is an M-valid marked ballot, in which
candidate X gets grade G1 and candidate Y gets grade G2, then an M-valid
marked ballot B2 is got by changing Xs grade to G2 and Ys grade to G1,
while leaving all other candidates grades unchanged.
Note that even a method like Lone-mark plurality - which forbids most swaps
which involve changing just ONE candidates grade - ALWAYS allows a basic
swap involving TWO candidates grades, in accord with the noted
STRONGER-THAN-BASIC MONOTONY? Basic-monotone methods include Lone-mark
plurality and other Cumulative methods, Approval and other unconstrained
Cardinal Ratings methods; and Borda. It turns out, however, that many such
methods with MAXGRADE>1 - and almost all usual ones with MAXGRADE>3 - FAIL
to be monotone in the simplest stronger-than-basic sense!
Suppose we have a simplest imaginable NON-basic swap. The swap changes just
one marked ballot - ballot B1 is changed to ballot B2 - and moreover there
are two candidates (rather than just at most one) X and Y whose grades are
both made higher, or are both made lower. Almost every usual method M with
MAXGRADE > 3 admits such an example which violates monotony.
For instance, let method M be usual unconstrained Five-Slot CR. That is,
MAXGRADE=4, and in any election the winners are those candidates with
maximum score, where the score of each candidate Z is the sum over all
ballots of Zs grade on each ballot.
Suppose that all ballots initially give victory to Y over X by 1 point (and
lesser scores to all other candidates), and that ballot B1 grades X=0 and
Y=3. To get an M-valid ballot B2 from B1, change the X and Y grades to X=3
and Y=4, and leave alone other grades. This swap, which plainly favors Y
(as well as also X), in fact changes Y from winner to loser.
A swap of this simple kind need not exist if method M has certain
constraints on the grade distribution, in particular if M is a
strict-ranking method. However, even given strict ranking or other
constraints, so long as method M scores by summation and has a valid
three-or-more-candidate ballot B1 something like the following, we get a
counterexample. Namely, we now suppose that on ballot B1 we not only have
graded candidates X=0 and Y=3 but also Z=4. Then get B2 from B1 by
changing grades to X=3 and Y=4 (as above) and also Z=0. B2 must be an
M-valid ballot, again owing to fairness (or 'permutability' or
'exchangeability' of grades) - this time among the three candidates. Again,
a 1-point initial victory of Y over X is changed to defeat.
END OF POSTSCRIPT: BASIC MONOTONY
MSN Photos is the easiest way to share and print your photos:
More information about the Election-Methods