[EM] Monotonic Burial Resistant Method

[Kristofer Munsterhjelm]

On 7/6/23 03:35, Forest Simmons wrote:
> For each candidate Y, let RBAFP(Y) be Y's  Random Ballot Anti-Favorite 
> Probability ... the probability that on a randomly drawn ballot, 
> candidate Y would be the candidate designated as "anti-favorite" (worst 
> position) on the ballot.
> 
> For each candidate X, let S(X) be the sum over all Y that defeat X, of 
> RBAFP(Y).
> 
> Elect argmin(S(X))

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