[EM] Basic Monotony

[Joe Weinstein]

BASIC MONOTONY

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 “Bucklin’s”, 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,

Joe Weinstein
Long Beach, CA USA

------------------------------------------------------------------------------------------------------------------
POSTSCRIPT:   BASIC MONOTONY defined and discussed

SIDE QUIBBLE  (before we get down to business!).  In our EM-list discussions 
we don’t really mean ‘monotone’!  That’s 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 
(highest).

	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 let’s 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 
lower grade.

	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 
X change.

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!  
That’s 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 X’s grade to G2 and Y’s 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 candidate’s grade - ALWAYS allows a basic 
swap involving TWO candidates’ grades, in accord with the noted 
fairness/permutability/exchangeability condition.

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 Z’s 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: 
http://photos.msn.com/support/worldwide.aspx