[EM] "unavoidable change" not enough?

[Richard Moore]

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