[EM] Two questions

[Kristofer Munsterhjelm]

Kevin Venzke wrote:
> Hi Kristofer,
> 
> --- En date de : Jeu 24.6.10, Kristofer Munsterhjelm <km-elmet at broadpark.no> a écrit :
>>> Hi Kristofer,
>>>
>>> --- En date de : Mar 22.6.10, Kristofer Munsterhjelm
>> <km-elmet at broadpark.no>
>> 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.