On 7/6/23 03:35, Forest Simmons wrote:

Let's consider the three-candidate ABCA cycle case.

If I'm not mistaken, at least when all ballots are fully specified,
RBAFP(Y) is linearly related to just Y's Antiplurality score, because
the probability is Y's antiplurality count or score, divided by the
number of voters.

So in this simple cycle, we associate with A the strength of the number
of last preference votes for the candidate who beats A pairwise. So in
my terminology: lpC. Since minimum wins, and my "linear" methods elect
the candidate with a maximum, A's score is thus -lpC.

I just created a burial example finder that uses linear programming; I
was going to write a post about using a sort of alternating method
(first find DMTCBR burial example, then find method that doesn't fail
it, then find a burial example that it fails, etc) as a poor man's
quantifier elimination, but I haven't got around to do it. Still, it's
useful for finding a particular example.

What we want is:
- A has >1/3 first preferences and is the honest Condorcet winner,
hence the dominant mutual third candidate.
- Then some BAC voters change their vote into BCA
- As a result there's an ABCA cycle and B wins, i.e.
- lpA is less than lpC (B has a better score than A),
and - lpB is less than lpC (B has a better score than C).

This produces the following example:
2: A>B>C
1: B>C>A (honest is B>A>C)
2: C>A>B

It's an A>B>C>A cycle: A has 2 first preferences out of 5, hence >1/3
first preferences. The probabilities of a ballot having a last
preference for
A is 1/5
B is 2/5
C is 3/5
A's penalty (to be minimized) is C's probability, i.e. 3/5. B's penalty
is A's last place probability, i.e. 1/5; and C's penalty is B's: 2/5.

So the social ordering is B>C>A. Hence the burial paid off. It pushed A
from first to last place.

However, the example election has an unusual configuration: the burial
fails for every method implemented by LeGrand's rbvote (my mirror is at
https://munsterhjelm.no/km/rbvote/calc.html). Thus it might well have
been hard to spot the flaw.

In case it might be of interest, I've added the AMPL/GMPL linear program
below :-) I've added integer constraints so that the ballot weights are
all integer, which strictly speaking makes this an integer program, but
it would work even without those constraints.

var ABC >= 0 integer;
var ACB >= 0 integer;
var BAC >= 0 integer;
var BCA >= 0 integer;
var CAB >= 0 integer;
var CBA >= 0 integer;
var V >= 0 integer;
var lpA >= 0 integer;
var lpB >= 0 integer;
var lpC >= 0 integer;

minimize voters: V;

s.t. def_V: V = ABC + ACB + BAC + BCA + CAB + CBA;
s.t. fpA_exceeds_third: 3 * (ABC + ACB) >= 1 + ABC + ACB + BAC + BCA +
CAB + CBA;
s.t. AbeatsB: ABC + ACB + CAB >= BAC + BCA + CBA + 1;
s.t. BbeatsC: BAC + BCA + ABC >= CAB + CBA + ACB + 1;
s.t. CbeatsAafter: CAB + CBA + BCA >= ABC + ACB + BAC + 1;
s.t. AbeatsCbefore: ABC + ACB + BAC + 1 >= BCA + CAB + CBA;

s.t. def_lpA: lpA = BCA + CBA;
s.t. def_lpB: lpB = ACB + CAB;
s.t. def_lpC: lpC = BAC + ABC;

s.t. lpA_less_than_lpC: lpC >= lpA + 1;
s.t. lpB_less_than_lpC: lpB >= lpA + 1;

solve;

It can easily be adapted to find burial examples for other methods. For
instance, here are constraints for Smith,Antiplurality and Smith,Bucklin:

s.t. lpB_less_than_lpC: lpC >= lpB + 1;
s.t. lpB_less_than_lpA: lpA >= lpB + 1;

which gives
2: A>B>C
1: B>C>A
1: C>A>B
1: C>B>A

(Funnily, with three candidates and complete ballots, Bucklin seems to
be just Majority,Antiplurality: either someone has a majority, or the
candidate with the greatest first pref + second pref count wins; but
first + second + last prefs = number of voters, so that's the same as
the candidate with the fewest last place votes winning!)

-km

On Thu, Jul 6, 2023, 1:43 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

Since these events are mutually exclusive, the probabilities should not
surpass 100 percent.

A's penalty (to be minimized) is C's probability, i.e. 3/5. B's penalty

On 7/6/23 19:33, Forest Simmons wrote:

You're right. I had originally written an example with more voters and I
forgot to update the numerators. The right numbers are:

A: 1/5
B: 2/5
C: 2/5

which can be seen by counting last preference votes.

So the penalties should be:

A: (C's probability): 2/5
B: (A's probability): 1/5
C: (B's probability): 2/5

B>A=C

Does that seem right?

-km

On Thu, Jul 6, 2023, 10:46 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:

Yes.

Let's compare with the MMPO analysis:

: 2 A>B
1 B>C
2 C>A

A>B 4 to 1, B>C 3 to 2, C>A 3 to 2

MPO's are 3, 4, and 3, respectively for A, B,and C.

So A and C are tied for MinMPO. The tie is broken in favor of A, because
its second highest MPO is only 1.

B has the fewest losing votes against this MMPO candidate, so the sincere
final is between A and C ... which is won by the sincere CW, namely A.

The new method is based on the idea of finding the candidate X that needs
the least supplematation to form a pair that covers the candidate set.

If X is A, then Y=C is not yet covered because C beats A. The cost of
supplementing with C is C's antifavorite count, which is 2.

If X=B, we need a candidate (like A) that beats B to complete our covering.
The cost of adding A is only 1, its antifavorite count.

This is clearly the least costly ... so X=B is the candidate most cheaply
built up to a covering.  Therefore B (the burier in this example) is the
method winner.

The burier is rewarded (frown!)

Now suppose that sincere had been

2 A>C
1 B>C
2 C>A

Then  the MMPO method would have detected & restored C as the sincere CW in
the A vs C sincere final ... while our new method would fave still elected
B ... punishing the burier A by electing its sincere antifavorite.

The equality in the B>A=C cycle confounds things a little with two equally
weak links B>C and C>A.

How about the monotonicity and Landau Efficiency of the new method?

BTW in the formula for S(X) the sum of over all Y defeating X of RBAFP(Y)
could be replaced by
Max over all Y beating X of  BottomCount(Y).

This makes it easier to explain and compute ... no need of
lottery/probability concepts, etc.

-fws

On 7/6/23 22:30, Forest Simmons wrote:

Unless it's due to a bug in my linear program, there seems to be
something about the structure that makes it impossible to get B elected
after burial both by this new method and by (pre-tiebreaker) minmax. I
suspect that it's a matter of too few degrees of freedom and that thus
it'd be possible to produce such an election with four candidates.

It's possible to make the ordering strict, though, e.g.

4: A>B>C
1: B>C>A (honest: B>A>C)
3: C>A>B
1: C>B>A

which should give a result of B>C>A.

I'm working on a post showing how to use differentiation to determine
monotonicity, with this method as an example. But the short answer is:
no, it's not monotone. (I don't think so, at least.)

Suppose C and A have an equal number of last preferences, so that A and
B are tied. Then raising A on a B>C>A ballot can increase C's last
preferences, helping B and making him the argmin candidate:

1: A>B>C
1: B>A>C
2: B>C>A
3: C>A>B

Penalties:
A = lpC = 2
B = lpA = 2
C = lpB = 3

so A=B>C.

Now raise A on a B>C>A ballot:

1: A>B>C
2: B>A>C
1: B>C>A
3: C>A>B

Penalties:
A = lpC = 3
B = lpA = 1
C = lpB = 3

B > A = C.

You can probably add strategic epsilons to the ballot counts to break
the outcome ties; I haven't done so here.

It's kind of the reverse of the IRV problem where raising someone
decreases someone else's first preference count, so presumably there's
an analog of fpA-fpC that restores monotonicity. But then you could just
use fpA-fpC itself!

-km