[email protected] 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
