[EM] A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives

[Kristofer Munsterhjelm]

fsimmons at pcc.edu wrote:
> Kristofer,
> 
> Jobst has also pointed out that, like Copeland, the "Condorcet
> Lottery" is not touched by my example, since it gives equal
> probability to all three candidates in the top cycle.

What is the Condorcet Lottery method? Is it Random Pair, where the 
pairwise winner of two random candidates wins - or is it Rivest's method 
based on the Copeland matrix?

> I want to go in a slightly different direction with this post.
> Covering is a nice relation because it is transitive and cycle free.
> The trouble is that in general there can be two alternatives neither
> of which covers the other,  When that is not the case (i.e. in the
> case where for each X and Y, either X covers Y or else Y covers X) we
> can easily agree to elect the alternative that covers each of the
> others.

That sounds very much like Condorcet. Condorcet is a nice relation 
because it is transitive and cycle free: if there is a chain of 
candidates A, B, C, etc, so that A is the CW and a candidate at position 
x beats all to the right and loses all to the left, obviously this is 
transitive, as the Condorcet loser can't beat the CW.

However, there may not be a CW, and as far as I understand what you're 
saying, there may not necessarily be an unique "covering winner" either.

The Landau set is then the covering "Smith set": members of the Landau 
set cover all those outside it. However, unlike the Smith set, simply 
grafting it onto a base method can lead the result to fail monotonicity.

I also imagine you could construct methods like "Candidate that covers 
everybody else, or the Borda winner if that doesn't exist", but I 
dislike that for the same reason I dislike Black - it hardly feels 
elegant, and there's little chance that the properties we like will 
generalize smoothly. A voting method should have the same general logic 
when there's a winner and there's an almost-winner, I think, or it 
becomes alike decloning ballots to gain independence from clones.

> This leads to the idea of "almost covering."  We can say that X
> almost covers Y iff every alternative that is beaten or almost beaten
> by Y is also beaten or almost beaten by X, too.
> 
> The if "almost" is defined appropriately, for each X and Y, either X
> will almost cover Y or Y will almost cover X.
> 
> If "almost" is defined too loosely, then every alternative will
> almost cover every other alternative, so the relation is not useful.
> On the other hand, if it is defined too strictly, then there may be a
> pair of alternatives for which neither almost covers the other.
> 
> Accordingly, for each whole number k let's say that "X  k-covers  Y "
> iff  for each alternative that Y beats or comes within k votes of
> beating, X also beats or comes within k votes of beating.
> 
> Then let k be the smallest whole number such that for every pair of
> alternatives at least one will k-cover the other.
> 
> This k is somewhere between zero and the total number of voters,
> because if N is the total number of voters, then every alternative
> N-covers every other alternative.
> 
> With k defined as above, we can say that X almost covers Y iff  X
> k-covers Y.
> 
> Note that the almost covering relation is transitive, and that each
> two alternatives are comparable.
> 
> Of course, in general we can expect that there will be alternatives X
> and Y such that each almost covers the other, so electing a candidate
> that almost covers all of the others is not decisive.  Instead we
> have an equivalence class of potential winners each of which almost
> covers every alternative.
> 
> So like Copeland, this basic method needs a tie breaker.  One way is
> to pick at random from the top equivalence class.

So you end up having a set and you need a way to break ties within that 
set. But that's the same problem we had with the Landau set: it often 
provides a set of winners, not a single winner. What do we gain by 
relaxing the covering into k-covering?

The difference seems to be that Landau can end up with a situation where 
the set of those outside is empty, whereas almost-covering can end up 
with a situation where everybody almost-covers everybody else. In both 
cases, that would lead to the respective sets to simply be the set of 
all the candidates.

If we're trying to find a relation that is like covering but behaves 
more nicely (doesn't violate monotonicity by itself as often, etc), then 
perhaps Duggan's "deep covering" would work. I haven't looked at it in 
detail, but he claims that it eliminated discontinuities in a certain 
model. See http://politics.as.nyu.edu/docs/IO/4743/duggan.pdf .

Maybe the maximal-element set based on ISDA (River's 
"almost-independence" criterion) would be useful. That is, find the set 
of candidates that strongly dominate all who are not in it. Since 
Pareto-dominated alternatives are also strongly dominated but not vice 
versa, the strongly dominated relation is stronger than 
Pareto-domination, and so that set would tend to be larger than the 
uncovered set. That does not, by itself, break ties more effectively, 
but the set might be better behaved than the Landau set.

> Another way would be to eliminate all alternatives outside of the top
> equivalence class, calculate a new k for the remaining alternatives,
> and repeat the process (recursively).  It's not clear that this
> procedure would preserve monotonicity.

I doubt that would be monotonic, though I have no proof. It just seems 
like raising a candidate could cause the initial k to change, which 
could cause the latter k to change either up *or* down (since initial k 
going closer to full covering could exclude some candidates that were 
holding k back in later entries).

> Any other ideas?.

Perhaps you could break ties by extending covering itself. Consider a
top set of those who have stronger beatpaths of size at most three to
all others, or a top set of those who have stronger beatpaths of size at 
most four, and so on.

Could a type of iterated beatpath method work here? Start by looking at 
all the candidates who directly beat everybody else. That's the Smith 
set. If it's size one, that's the winner (the CW). Otherwise consider 
the candidates who have beatpaths at most length two the rest. That's 
the uncovered set. If it's one, we're done, otherwise consider all the 
candidates who have beatpaths at most length three to the rest, and so 
on. In other words, find the shortest length beatpath where there exists 
a candidate that has a beatpath of that length to everybody else.

Another idea would be to look at game theory. The uncovered set has 
certain game-theoretical properties (such as being outcomes that occur 
with sophisticated strategy on all sides). However, I'm not very well 
versed in that, so I can't suggest any concrete methods.
Rivest's method tries to do something like that, but (to my knowledge) 
the game-theory backing is weakened when the method is turned 
deterministic. It's not monotone either.