[EM] monotonic order of the Landau set

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

[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).

Election-Methods mailing list - see https://electorama.com/em for list info