[EM] Monotone resistant set method

[Kristofer Munsterhjelm]

Okay all, here's the method that I mentioned a while ago; I think I have 
convinced myself that it is monotone in winners (i.e. you can't make a 
winner lose by ranking him higher).

Below, I'll define a path relation. Given this path relation, let, for 
any candidate A, in(A) be the number of candidates who have a path to A, 
and out(A) be the number of candidates A has a path to.
Elect the candidates X with in(X) = 0 and maximum out(X).

If you need a winner, not just candidates tied for first, break the tie 
in any monotone way that you'd like.

(Hopefully this should show that it is quite possible to advance the art 
without resorting to underhanded tactics.)

Now to the path definition and its reasoning:

=======================================================================

One problem of the ordinary disqualification relation for the resistant 
set is that raising A, while unable to break any disqualification A~>X, 
*can* break a disqualification between two other candidates, e.g. B~>C.

Thus, we could have a three-candidate election with A~>B, B~>C. With 
something like Resistant,Minmax, it's forced to elects A, even if 
Minmax's actual order is closer to C>A>B. Then raising A could break 
B~>C, inserting C into the resistant set, after which the winner of 
Resistant,Minmax changes from A to C.

One way to deal with this is to create a monotone indirect 
disqualification relation. For this monotone relation, call it X==>Y, 
we'd like to have
	- monotonicity: raising X can't break X==>Y,
	- inclusivity: if A~>X_1~>...~>X_n then A==>X_n
	- antisymmetry: never both X==>Y and Y==>X
	- transitivity: if A==>B and B==>C, then A==>C.

This relation should do:

Let a path A==>B be a list of candidates, starting in A and ending in B, 
and let B be its leaf. Let a suffix set of the path be the set of the k 
latest non-leaf candidates in the path.
Let a subelection (defined by its set of non-eliminated candidates) S's 
longest suffix set be the largest suffix set all of whose candidates are 
in S. For instance, for the path A->B->C->D and the subelection {A, C, 
D}, the longest suffix set is {C}.
Let a subelection have the property that its longest suffix set is 
proper if there exists no longer suffix set with some candidates (but 
not all) included in S. For the example above, the longest suffix set is 
not proper because the suffix set {A, B, C} contains A, which S also 
contains. But if the subelection had been {B, C, D}, then the suffix set 
{B, C} would be its longest and be proper.

Say that there's a path from A of steps X_1, ..., X_n, also written 
A->X_1->...->X_n, if:
	A~>X_1 (ordinary disqualification)
then for any subsequent step along the path, for X_k->X_(k+1) to hold,then
	for any subelection S having a proper longest suffix set Q, as well as 
containing the candidate X_(k+1),
	the sum of the first preferences of every candidate in Q must be 
greater than |Q|/|S| of the total sum of first preferences in that 
subelection.

For instance, if we have, in a three-candidate election, A->B->C, then 
A->B requires:
	fpA > 1/2 of the vote in {A,B}   (A beats B pairwise)
	fpA > 1/3 of the vote in {A,B,C} (A has more than a third of the first 
prefs)
and adding B->C requires:
	fpB > 1/2 in {B,C}		(B beats C pairwise)
	fpB + fpA > 2/3 in {A,B,C}	(C has less than a third of the first prefs)

If these all hold, A has a path to C, A==>C.

Note that the second constraint does not impose anything on {A,C} 
because {A, C} does not have a proper longest suffix set (since both 
suffix sets {B} and {A, B} contain B which is not in that subelection).

For a similar reason, the subelection {A, B, C} is not associated with a 
constraint fpB > 1/2 because even though it contains every candidate in 
the suffix set {B}, that suffix set is not the longest for that 
subelection - {A, B} is, and that's where we get the fpB + fpA > 2/3 
constraint from.

=======================================================================

Some intuitive arguments:
	Every prefix of a viable (i.e. constraints-passing) path is also a 
viable path.
	No path originating from A can be broken by raising A because fpA is in 
all its constraints, so it's not affected by someone raising A over some 
candidate that used to contribute to the l.h.s.
	Raising A can break paths that doesn't originate from A, but doing so 
will only reduce the resulting components' out-values, hence can't harm A.
	Inclusivity holds because the first step is just ordinary 
disqualification. Then inductively if A==>X_k holds and X_k ~> X_(k+1), 
then for some subelection S containing X_k and X_(k+1), where Q is its 
longest proper suffix set for A==>X_k, we already have (sum first prefs 
over candidates in Q) > |Q|/|S| by the assumption A==>X_k. This, along 
with the fpX_k > 1/|S| that's required by X_k ~> X_(k+1), implies that 
(sum over candidates in Q) + fpX_k > (|Q|+1)/|S|.

Beyond this, it's pretty hairy, so independent testing would be 
appreciated. If you want my proof notes, ask and I'll see what I can do. 
They're even hairier and I don't want to clog up the list :-)

-km