Kevin Venzke wrote:
Hi Kristofer,
--- En date de : Jeu 24.6.10, Kristofer Munsterhjelm <[email protected]> a
écrit :
Hi Kristofer,
--- En date de : Mar 22.6.10, Kristofer Munsterhjelm
<[email protected]>
a écrit :
Here are two questions regarding
criterion compliance:
First, does ordinary Copeland (one point for a
win, nothing
for a tie or loss) pass Smith?
I believe so. Suppose that there are x candidates in
the Smith set and
y candidates outside of it. Then everyone in the Smith
set will have
a score of at least y+1, and everyone outside the
Smith set can have a
score of at most y-1.
Does that mean that second order Copeland passes Landau? If
not, I suppose the counterexample would involve a "winner"
that is victorious against a few candidates that beat
many... but I'm not certain.
I don't know. I've never really thought about either of these.
Alright. If I find out, I'll tell you (and the list).
Second, could anyone give me an example of
Copeland failing
mono-add-top?
I can't produce the ballots off the top of my head,
but suppose A is
winning with a score of say 5 while B has a score of
4. Then you add
new ballots of the form A>B>... that cause B to
win two additional contests with no other effect. I would
assume for simplicity that the
Smith set is unchanged (containing A and B in both
elections).
Yes, that works, and it let me find the bug (actually
mis-specification) in my criterion compliance program. The
problem was that it didn't consider situations where there
were ties in either outcome, and Copeland is very well known
for producing lots of ties.
I've fixed that, and now it easily finds Copeland failures
- for instance, this will work:
1: A > C > B
2: B > A > C
1: C > B > A
which gives B = A > C, then we add a ballot ranking A
top:
1: A > B > C
1: A > C > B
2: B > A > C
1: C > B > A
and we get B > A > C, QED.
Incidentally, this means that it is theoretically possible
(at least given that disproof) that a more decisive version
of Copeland can pass mono-add-top. That method would give
the same results as Copeland, except it would resolve ties.
*But* in that case, we know that it must elect B in the
first example (i.e. have ordering B > A > C);
otherwise, the disproof above can still be applied; and if
we could find an example where, say, A = B > C and we can
make both a mono-add-top failure for A and B, then that
would prove that no "more decisive" version of Copeland
could pass, because however it resolves the tie, we can
counter with the appropriate disproof.
That seems to make sense to me...
I've implemented this into my program, and while it hasn't found any
disproofs of exhaustion for Smith and Landau itself with regards to
mono-add-top, it does give some points where we know which candidates
*can't* be the winners.
For instance, for Landau (if my set generator is correct):
3: A > C > B
1: B > A > C
2: C > B > A
must elect A. If it elects B, then
3: A > C > B
1: B > A > C
2: C > B > A
3: B > C > A
forces the election of C (thus failing mono-add-top), and if it elects
C, then
3: A > C > B
1: B > A > C
2: C > B > A
1: C > A > B
forces the election of A, again failing mono-add-top.
I did find a proof of Copeland (1 for win, nothing for tie) failing
mono-add-top outright, though:
1: D > C > A > B
1: C > A > D > B
1: B > C > A > D
1: A > B > D > C
gives A > C > D = B
then, after adding one A > C > D > B ballot, you get a social ordering
of C > A > D > B. The winners are uniquely determined for both ballots,
so no tiebreaker can save Copeland here.
I'll test Smith,minmax(margins) next, which seems to be a
method where it's harder to find a mono-add-top failure. Can
you think of a way of constructing one? IIRC,
Minmax(margins) fails Plurality and so we can't use
Woodall's proof.
I take it there is a Woodall proof that shows the incompatibility of
Mono-add-top, Plurality, and Smith? I don't remember off the top of my
head.
Yes. It goes like this:
11: A > B
7: B
12: C
Methods that pass Plurality must not elect A here, and since the Smith
set is {A,B}, it must elect B. But then:
11: A > B
7: B
2: B > A <-- new ballots
12: C
By mono-add-top, B must still be elected, but now A is the CW.
The question is what criterion could we possibly use to pick a candidate,
which implies Smith, and which doesn't change its mind when you alter
pairwise contests (other than those of the winner) which could very well
alter the membership of the Smith set?
Something like the "margin to change" logic I used in M-Set Webster
seems appropriate here. Consider the problem: what happens is that by
voting some ballot with A top, you flip victories of candidates ranked
lower against candidates ranked higher, so that these candidates do
better than A. The answer must be to not elect A in the first place.
The margin-to-change logic seems then to be to elect the candidate who
is the farthest away from being changed - in other words, the candidate
for which the opposition candidate that could beat him with fewest
votes, would need the most votes to do so. That way, if some opposing
candidates get close enough for it to be possible to execute a
mono-add-top failure, the method will switch to electing some other
candidate before that actually happens.
That, in turn, sounds very much like minmax. Perhaps that is why my
program is having such a hard time at finding a counterexample for
Smith,Minmax(margins). The question remains whether the margins logic is
strong enough. Certainly it is not for Landau,Minmax(margins), where my
program finds a disproof, and properly speaking, I haven't considered
the additional constraints of Smith,* at all.
I have found a mono-add-top failure for Smith,Minmax(margins) as well,
but it is of the weak kind where ties for first are involved, and so an
appropriate tiebreaker might work:
1: B > A > C > G > F > E > H > D
1: B > F > C > E > A > D > G > H
1: D > B > G > A > F > C > E > H
1: D > B > H > G > C > E > A > F
1: D > G > C > E > H > A > B > F
1: F > A > D > C > B > G > H > E
1: F > D > E > B > H > G > C > A
1: G > F > A > H > C > E > D > B
which gives: F = D = C = A > G = B > E > H
then adding 1: C > H > B > E > G > A > F > D gives a social ordering of
B > G = E = A > C > F > D > H, harming C (who was on top of the ballot
we added).
If you want to test it yourself, I'll explain how I get the social
ordering for Smith,X. Consider the "iterated Smith set" ordering that is
constructed by first finding the Smith set, then the Smith set with
defeats by the former set disregarded, then the Smith set with defeats
by the former two sets disregarded, etc. Then, I sort the ordering of
method X by the iterated Smith set: if the iterated Smith set is A = B =
C > D = E = F > G = H = I, the first three candidates will be A, B, and
C in the order that the social ordering for X specifies them; then the
next three will be D, E, and F in the order that the social ordering for
X specifies them, and so on.
I'll try using a tiebreaker for minmax where it considers the next to
maximal defeat to break ties, then the next to next to maximal defeat if
there's still a tie, and so on. It might work - I used a similar leximax
tiebreaker for M-Set Webster.
----
Election-Methods mailing list - see http://electorama.com/em for list info
