Monotonicity comments

[Richard Moore]

MIKE OSSIPOFF wrote:

> It seems to me that that gets my definition out of that problem, doesn't it?
> After all,
> just as in a ranking the status of being ranked #5 has nothing to do with
> who the other
> candidates are, or how they're ranked compared to eachother, so A's (4,10)
> or 10/14 says
> something about A's status in the same way.

Your solution to the dyadic ballots problem is on the right track,
I think. However, it probably needs to be a little less simplistic.
Not only the number of ">" marks above and below the candidate, but
the way those marks are grouped, is important. Recall that Forest
mentioned the dyadic ballot maps to a binary tree. The leaves of
the tree can be assigned unique numbers, providing an order to the
possible ways each candidate can be marked. There are more leaves
than candidates, so moving a candidate to a different leaf will
increase or decrease the candidate's rating but not necessarily
change the relative order of the candidates.

> Yes, I see the problem now. It's something that hadn't occurred to me, and
> that
> I'll have to study. Monotonicity is more difficult that it seemed. It seemed
> that it was
> only necessary to make its obvious meaning explicit, but it turns out that
> its meaning
> is far from clear. Might Monotonicity have to be dropped, if no satisfactory
> definition
> is found?

I brought up the self-reference problem, not to discourage work
on the definition of MC, but to stiumlate some "out of the box"
thinking. This criterion is one of the most important ones (IMHO)
and should not be dropped because it's hard to define.

The limited-scope definitions (that apply only to ranked ballots,
or only to CR ballots, etc.) work well within their respective
scopes. The difficulty is in writing one definition that has
universal scope.

The mathematical (non-EM) definition of monotonicity is that
a function is monotonic if it is order-preserving. That is,
if, when x2 > x1, it is always true that f(x2) >= f(x1), then
f is monotonic (specifically, it is monotonically increasing;
it could be monotonically decreasing if f(x2) <= f(x1) for
x2 > x1). This definition is easily understood if there is
just one independent variable. But what if there are multiple
independent variables? How do you decide if (x2, y2) > (x1, y1)?

One approach would be to define x and y (and any other
independent variables) in terms of a single parameter (let's call it t).
This constrains the evaluation of monotonicity to a path
through the domain. Then, since x = x(t) and y = y(t), you could
replace f(x, y) with g(t). We could then make a meaningful
determination of monotonicity subject to those constraints.

The limited-scope definitions already set constraints. For CR ballots,
for example, it is assumed that, when we vote X higher, we are
giving X a higher rating while leaving the other candidates'
ratings untouched or at least not increasing them as much as
we increase X's rating. Having such constraints makes a useful
definition possible. The trick is not to have too much constraint,
or the resulting criterion could fail to detect some types of
monotonicity failure that we care about.

Solving the dyadic ballot problem by mapping the series of
">" symbol groups above and below a candidate to a position on a
binary tree, which position can be assigned a number, is another
way of ordering the domain.

If the path taken by (x(t), y(t)) does not intersect itself anywhere,
then we can also define t in terms of x and y, so the monotonicity
definition for a two-dimensional mathematical function f would
become: "f(x, y) is monotone (w/r/t the function t(x, y)) iff either

(1) t(x2, y2) > t(x1, y1) implies that f(x2, y2) >= f(x1, y1),
or
(2) t(x2, y2) > t(x1, y1) implies that f(x2, y2) <= f(x1, y1)."

We can think of t(x, y) as an ordering function for the domain.
This can be generalized to more than two variables, naturally.

I suggested that the reference method we rely on as the ordering
function should be one that passes the Consistency Criterion.
Consistency and monotonicity are closely related, but consistency
is much easier to define.

Here is the last definition I suggested to Forest (the one that
unfortunately makes proofs difficult):

Method M is monotone iff there exists a method C such that:

(1) C is a consistent method;
and
(2) For every pair (S,S') of multisets of ballots, if M(S') != M(S), then
there exists a multiset T for which at least one of the following is true:

 (a) M(S') != C(S+T) and M(S') = C(S'+T)
 or
 (b) M(S) = C(S+T) and M(S) != C(S'+T)

Putting condition 2a in English, S is the original set of ballots and S'
is the new set of ballots, so M(S) is the original winner (Jones) and
M(S') is the new winner (Smith). If S and S' are such that they elect
two different people (Jones and Smith), then we need to find some set of
ballots (T) such that if the old ballots (S) are combined with T, the
winner under method C will not be Smith, but if the new ballots (S') are
combined with with T then the winner under method C will be Smith. In
other words, according to method C (our reference method), changing
from S to S' favors Smith.

The alternate condition 2b is similar, with the meaning that, according to
method C, changing from S to S' "disfavors" Jones (i.e., could prevent
Jones from being elected when combined with the T ballots).

So under this definition, saying M is monotonic means that there exists
a method C that passes the consistency criterion and such that, if
changing the ballots (from S to S') causes the winner in method M to
change (from Jones to Smith), then according to method C, the change
from S to S' either favors Smith or disfavors Jones.  This is the same
as saying that a change that neither favors Smith nor disfavors Jones
(under method C) should never change the winner from Jones to Smith
(under method M). It might, however, change the winner from Jones to
Johnson (by favoring Johnson), or it might change the winner from
Thompson to Smith (by disfavoring Thompson).

Note that C is not in any way specified; the definition just says that
C must exist. Thus, even if methods M and N use the same type of ballots,
the reference method that is used to determine if M is monotone might not
be identical to the reference method that is used to determine if N is
monotone. But note that, if C is used to evaluate whether changing S to
S' favors Smith for method M, then the same C must be used to evaluate
whether changing R to R' favors Smith for method M.

I'm not satisfied that this definition is correct (it could be too loose, or it
could be too stringent), and as I noted it's not easy to apply, so any new
insights will be welcome.

 -- Richard