On Wed, 2 Mar 2005, Jobst Heitzig wrote:
Dear Forest!
When I understand you right, you propose to just strike out all strongly covered candidates and then use Random Ballot on the rest, right?
But then there must be some error in your proof of monotonicity, I fear -- look at the following example:
Situation 1: Situation 2: | | Ballots: 2 A>B>>C>D ditto 2 B>C>>D>A ditto 2 C>D>>A>B ditto 2 D>A>>B>C ditto 1 B>D>>A>C D>B>>A>C --- --- Defeats: A>B>C>D>A>C ditto and B>D and D>B
Approval: A B C D ditto 4 5 4 5
Covering relation: B>C A>B
Strong covering relation: B>C none
Random Ballot results (probabilities times 9): A B C D A B C D 2 3 2 2 2 2 2 3 (monotonic)
R.B.MacSmith results (probabilities times 9): A B C D A B C D 2 5 0 2 2 2 2 3 (monotonic)
Your proposal results (probabilities times 9): A B C D A B C D 2 3 0 4 2 2 2 3 (not monotonic: raising D decreases its probability!)
At least raising D relative to B preserved D's positive probability and increased the ratio of their probabilities from 4/3 to 3/2, as in the Condorcet Lottery kind of monotonicity. Maybe something can be salvaged here.
That's a pity since I like your proposal. But I have seen so many rules seem to be monotonic at first glance and then turn out not to be monotonic that I'm always quite suspicious. I hope my own proof that R.B.MacSmith is monotonic really holds...
I wonder about the "Needle Point" method. Is it monotonic?
Remember that a needle is a maximal chain such that no member is beaten by any preceding member either approvalwise or pairwise, but every member beats every predecessor either approvalwise or pairwise or both.
A needle point is the sharp end of a maximal needle.
At least the needle point method survives the above example:
Both before and after D is moved up, the only needle points are A, B, and C.
Note that AC, BC, and DA are needles both before and after the change, while BD is a needle before and DB is a needle after. Candidate C is not the point of any maximal needle in either case. So "random ballot needle point" yields the respective winning probabilities 2, 3, 0, and 4 per nine in both cases.
If we iterate needle, eventually we end up with B alone in the first case and D alone in the second case.
In general it may not be a good idea to iterate needle, but in this example it seems to amplify the effect of changing B>D to D>B.
Unfortunately needle doesn't punish the B faction defection in the example
49 C 24 B>>A 27 A>B>>C
If the B supporters truncate A, then the needle points go from A and B (before the truncation) to C and B (after), which is a reward to the truncators.
But if the A supporters take the precaution of raising the approval cutoff, then A and C become the only needle point candidates whether or not B truncates.
If we iterate in the case of B truncating, then the winner becomes C.
If we iterate in the case of C not truncating (but A raising the bar) then the needle point candidates remain A and C.
"Random ballot among not strongly covered" seems to do better at discouraging insincere ballots. Do we have to sacrifice monotonicity to some degree for that advantage?
Forest
---- Election-methods mailing list - see http://electorama.com/em for list info
