[EM] A Comparison of the Two Known Monotone, Clone Free Methods for Electing Uncovered Alternatives
fsimmons at pcc.edu
fsimmons at pcc.edu
Mon Dec 13 15:28:27 PST 2010
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.
>
More information about the Election-Methods
mailing list