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

[fsimmons at pcc.edu]

Kristofer,

Thanks for the ideas and leads.  It turns out that the k-covering winner is just the MinMax margins 
winner,

----- Original Message -----
From: Kristofer Munsterhjelm 
Date: Monday, December 13, 2010 12:01 pm
Subject: Re: [EM] A Comparison of the Two Known Monotone, Clone Free Methods for Electing 
Uncovered Alternatives
To: fsimmons at pcc.edu
Cc: election-methods at lists.electorama.com

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