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: fsimm...@pcc.edu Cc: election-methods@lists.electorama.com > fsimm...@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. > ---- Election-Methods mailing list - see http://electorama.com/em for list info