Forest Simmons wrote:
> When we have time, we should summerize some of the blind alleys and
> partial results so as to prevent unnecessary duplication of effort.
> Perhaps some of the list members could then carry it beyond the point
> where we left off.
At one point I did create a brief summary of our correspondence, and
fortunately
did so before the mail folder I kept those messages in got corrupted.
Here is my summary of attempts on a monotonicity definition (the definitions
here are paraphrased from the original wordings, for brevity):
1. Existing definitions have problems --
(1) They either fail to define "favoring" or define it for ranked ballots
only.
(2) They don't account for changes that favor X but that favor Y over X.
(This
can happen with CR ballots.)
2. Forest #1 --
Defines "favoring X over Y" for a single ballot in pairwise terms.
Defines "favoring X" for a ballot swap as meeting two conditions:
no pairwise reversal if X>Y on initial ballot, and
pairwise reversal for some candidate Y where Y>X on initial ballot
Defines "monotone" as "if a swap favors X and no other candidate, then there
is no election in which the swap would disfavor X".
Problems:
(1) Assumes method has provisions for pairwise comparisons on a ballot.
(2) No provision for marginal favoring (e.g., CR and Borda).
(3) "And no other" clause eliminates the test pairs needed to show
non-monotonicity. That is, if the method is not monotone, then we will
be restricting the test to pairs of ballots that do not exhibit the
non-monotonicity, and the method will pass falsely.
3. Richard #1 --
Defines "favoring X" for a swap as converting a loss for X to a win, for
some election.
Defines "monotone" in essentially the same way as Forest #1.
Problems:
(1) "And no other" clause has the same problem as before.
4. Forest #2 --
This was not really a definition, but Forest gave an example of non-monotone
behavior: In one election, a ballot swap converts from X to Y; in another
election, the same swap converts Y to X.
This could serve as the basis for a definition. One possible problem
is that there might exist methods that exhibit non-monotonic behavior for
added ballots but not for swapped ballots. See item 7 below.
5. Richard #2 --
Four-step definition:
"Favoring X over Y" for a single ballot means adding that ballot can convert
the winner from Y to X.
"Losing margin" is then defined in terms of minimum number of ballots
needed to
convert the loss by X to a win.
"Favoring X" means no pairwise reversal results from the change if X is the
initial winner, and losing margin improves for X in some election that X
initially
loses.
"Monotone" is same as in Forest #1.
Problems:
(1) Still has the "and no other" problem. Perhaps, since "favoring" now
includes
margins, this clause isn't needed. But that would only be true if the margin
improvement condition for favoring is modified so that margin improvement
has to be observed for X in some case for every non-X winner. Which means,
we don't need the 2nd and 3rd steps of this definition after all. This
leads to
two possibilities:
6. Richard #3a --
"Favoring X over Y" same as before.
"Monotone" means, for each swap such that favors X over Y for every Y != X,
there is no election for which that swap would convert an X win to a win by
another candidate.
7. Richard #3b --
"Favoring X over Y" same as before.
"Monotone" means, for each swap such that favors X over Y for some Y != X,
there is no election for which that swap would convert an X win to a win
by Y.
This is actually Forest #2 elaborated into a definition.
That was the end of my notes. Subsequently we found that one of the last
two definitions
(I believe it was the last one) had the problem that it was actually
equivalent to
consistency: Forest had proved that, by that definition, monotonicity
implied consistency,
and I had proved that, by the same definition, consistency implied
monotonicity. I don't
think these two criteria were intended to be identical. Consistency is
actually very
easy to write a formal definition for. (M is consistent iff, for all
multisets of ballots
S and T, it is true that if M(S) = X and M(T) = X, then M(S + T) = X.)
All the above monotonicity definitions have the problem that the
definitions of "favoring"
refer to the method being tested. This leads to a hidden circularity in
the definition. I
suggested that we require a definition of "favoring X over Y", for
ballots of the type
used by method M, that is independent of method M. Perhaps this could be
done by using
a separate method (let's call it M') that accepts ballots of the same
type accepted
by M, and that meets the consistency criterion. "Favoring" could then be
defined
according to method M', and we could then say that M is monotone iff:
For any ballot change that favors X in the consistent method M',
if X is the winner in method M before the change, then
X will still be the winner in method M after the change.
or in an alternate version,
For any ballot change that favors X over Y in the consistent method M',
if X is the winner in method M before the change, then
Y will not be the winner in method M after the change.
(The two alternatives are not equivalent, and I'm not sure which one is
better.)
I wrote a formal definition based on one of these alternatives and sent
it to Forest.
Unfortunately, since I lost the message folder, I don't have a copy of
it. Maybe Forest
does. However, I struggled with trying to use that definition to show
monotonicity or
lack thereof for some election methods, and concluded that the
definition was extremely
difficult to work with. That's where I stopped.
-- Richard
