[EM] monotonic order of the Landau set

[Forest Simmons]

Why would we want a monotonic ordering of the Landau set (the set of
uncovered candidates)?

I'm thinking that if we can generate the Landau set monotonically, then we
can use our favorite method that chooses monotonically from a
(monotonically generated) list to narrow down the Landau set to a unique
winner.  For example apply DMC to the list by removing candidates from the
bottom of the list until among the remaining candidates their is one that
pairwise beats all of the other remaining candidates.  This would give us a
DMC like method that (in addition to all of the other wonderful properties
of DMC) always elects from Landau.

So here is the method:

(1) As in River lock in the most powerful defeats: for each covered
candidate X , find the highest approval candidate Y that covers X, and lock
in that defeat.

(2) Each uncovered candidate will be a root node of a  tree (or river
basin, if you will) of one component of the graph whose edges are the
locked in defeats (forming a maximal sub tree of the covering relation).

(3) To each such root node assign a score that is the maximum approval of
any of the vertices of the tree of which it is the root. (the max approval
attained among the tributaries to that node including the approval of the
node itself).

Now suppose that (in a subsequent election)  all of the pairwise defeats
among candidates are the same as before except that now root node X
defeats pairwise root node Y, instead of vice-versa.

I contend that X's score will not be lowered, and that Y's score will not
be raised.

The interesting case is when this defeat reversal leads to one or more new
members of Landau.  How could this happen?  If Y was the highest approval
candidate that covered Z, before the reversal, and Z beat X pairwise, then
Y would no longer cover Z after the reversal.  So Z would now be
uncovered.  Now Z is a root node of a tree every tributary of which was
formerly a tributary of Y.  So Z's score can be no higher than Y's previous
score, and if Y is still uncovered, its score could not increase.

If Y ends up covered, then it has dropped out of Landau and so has not
improved relative to  X.

Could X suddenly become covered? If so the candidate V that now covers X
would have to beat both X and Y and all of the candidates that X beat
before the reversal of X and Y.   So V would have covered X before the
reversal, and X never would have been a root node in the first place.  So
after the reversal X is still a root node, and its entourage (system of
tributaries) could grow, which only raise X's score.

In sum, typically X's score stays the same or grows, and Y's score
diminishes, disappears, or gets replaced by one or more scores of new nodes
whose scores are no larger than Y's score prior to the change.

The other thing we have to check for is that moving X up in the approval
list while leaving the other candidates in their same relative order,
cannot decrease X's standing relative to any of the other candidates in the
final order of scores.

This is easier because it doesn't change the pairwise wins, so the Landau
set is the same before and after the change.  Raising X insures that if X
defeat Y was locked in before the change it will also be locked in after
the change, etc.  The new entourage of X will therefore (if anything) be a
superset of the previous entouorage, so X's score will not be diminished,
etc.  Let's not worry about the details for now, but if X passes up Y in
the approval order, X may steal a part of Y's entourage, increasing X's
score at the expense of Y's score, if they change at all.

We could not ask for any stronger form of monotonicity, given the tendency
of members of the Landau set to disappear, bifurcate, or appear seemingly
out of nowhere.

As a side note the MaxUncovered method that Chris Benham has mentioned from
time to time is (in this formulation) to simply elect the root node
candidate with the highest spot in this monotone order, i.e. with the
highest approval tributary candidate.  So as a corollary, that MaxUncovered
method is monotone.

Any worries?

(What, me worry?)

Remark:  The DMC like method mentioned above would be be tantamount to
completing the partial river system with strength of the non-covering
defeats measured by the score of the defeating candidate, i.e. of all the
remaining defeats at any stage after the covering defeats have been locked
in, first lock in the defeat with highest score for the defeating
candidate. Remember the score of an uncovered candidate is the highest
approval of any candidate in its tributary system, which (note bien) is not
necessarily the highest approval among the candidates that are covered by
the candidate, since some of those candidates may end up in another river
basin).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20190331/e63daca0/attachment.html>