See Martin Harper's treatment of monotonicity in dyadic ballots in his EM posting dated 4 Apr 2001 at the URL:
http://groups.yahoo.com/group/election-methods-list/message/7165 Forest On Tue, 8 Jan 2002, Richard Moore wrote: > 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 > > >
