[EM] More STV and monotonicity thinking

[Kristofer Munsterhjelm]

A partial sketch for a possibly single-candidate monotone STV method:

Single-candidate monotonicity says that if A is in the elected council 
and then A is raised, then A will remain in the elected council.

Suppose that we have a preset candidate ranking, call it R.

Let an elimination path to a set S of cardinality equal to the number of 
seats to be elected be an ordered list of candidates not in S, so that 
each can be eliminated in order, with none having more than a Droop 
quota of first preferences at any step of the process, so that set S 
remains afterwards.

Since cardinality of S is equal to the number of seats, there exists a 
retention order, i.e. an order of candidates in S so that each candidate 
in order has more than a Droop quota of first preferences, and after 
being eliminated, the next candidate in the retention order has the same 
property for the Droop quota for one seat less.

Now let a set S of candidates be admissible if there exists an 
elimination path to S.

Elect the admissible set S that maximizes the rank of the highest ranked 
candidate in S, and then the rank of the next highest ranked candidate 
in S, and so on, according to the candidate ranking R.

The idea for this method is that suppose that A is a candidate in the 
winning admissible set S_max, and A is then raised. Then R doesn't 
change (by virtue of being fixed beforehand), and A being raised doesn't 
make any candidate in the elimination path drop out of the elimination 
path (because it can't give any of them more first preferences). So it 
can't invalidate the elimination path to S.

So the only thing to consider is whether it enables some better set to 
now have an elimination path to it whereas that was not the case before. 
Call this purported contender set S'. If A is in S', then we're not 
violating single-candidate monotonicity so there's no problem. But if A 
is not in S', then at some point A must have been eliminated, but 
raising A doesn't help eliminate A.


The only problem is that this last part is not complete. I have to 
consider the possibility that B was a blocking candidate who prevented 
an elimination path to S' being possible, but then raising A over B 
lowers B's score to the point that B can be eliminated -- and in any 
case, A is included in the partial elimination path that is completed by 
B being included in it.

The trick of using R is mostly so that I can focus on one problem at a 
time. If the proof can be completed or the method tweaked to obtain 
monotonicity, then R could straightforwardly be replaced with random 
voter hierarchy to get a monotone nondeterministic STV method, and 
perhaps deterministic R are applicable if the associated base method 
passes some property that we don't know about yet. The reason it can't 
just be any method is that it's otherwise possible that raising R 
changes whether B beats C, which could enable some admissible sets to 
increase their "score" (leximax ranking wrt R) relative to the S that 
includes A.

-km