[EM] Differentiation for monotonicity, linear Condorcet methods

[Kristofer Munsterhjelm]

(Finally!)

The cycle behavior of fpA-fpC, but also a surprisingly large number of 
other Condorcet methods, can in the three-candidate universal domain no 
tie case be phrased the following way:

Without loss of generality, suppose that the cycle is A>B>C>A and that 
we're trying to determine the rank of candidate A.

Let w = [w_ABC, ..., w_CBA] be a weight vector depending on the method. 
Then let x_A = [ABC, ..., CBA] be a value vector that indicates the 
number of people who voted a particular way. The _A means "from the 
perspective of A".

For instance, x_A = [1, 1, 0, 0, 2, 3] is
1: A>B>C
1: A>C>B
2: C>A>B
3: C>B>A

Then the method's score of candidate A is w dot x_A. By relabeling the 
candidates and following the cycle,
	x_A = [ABC, ACB, BAC, BCA, CAB, CBA]
	x_B = [BCA, BAC, CBA, CAB, ABC, ACB]
	x_C = [CAB, CBA, ACB, ABC, BCA, BAC]

so that B's score is w dot x_B, and C's score is w dot x_C. Call these 
scores f(A), f(B), and f(C).

Some weight vectors are:
	fpA-fpC: [1, 1, 0, 0, -1 -1], i.e. fpA - fpC
	Smith,Plurality: [1, 1, 0, 0, 0, 0], i.e. fpA
	Minmax, Schulze, etc: [1, 1, 1, 0, 0, 0], i.e. A>C
	max A>B: [1, 1, 0, 0, 1, 0], i.e. A>B
	Forest's recent method: [-1, 0, -1, 0, 0, 0], i.e. -lpC

To pass a particular relative criterion for a method of this type, we 
need two things:
	1. That the method pass at the boundary between "A is a CW" and 
"A>B>C>A cycle"
	2. That moving further into the "A>B>C>A cycle" region in a way that 
shouldn't make A lose, doesn't make A lose.

For instance, for DMTCBR, #1 means that under no election where A would 
be a DMT candidate, except that due to one (or an epsilon amount of a) 
BAC ballot being replaced with a BCA one, we now have an ABCA cycle, 
should A lose. The epsilon puts it right at the boundary. #2 means that 
replacing more BAC ballots with BCA should not change the situation from 
one where A's score is greater than B and C's, to one where B's score is 
greater than A and C's.

Monotonicity is particularly well-behaved: you can't raise A and get 
from a CW region to a cycle. So we don't need to care about #1 because 
if the method passes Condorcet, the election has to be in a cycle for 
raising A to harm A.

Which leaves #2, which is where I pull the differential approach.

Monotonicity means that A shouldn't go from winning to losing by raising 
A (or, I think equivalently, that A shouldn't go from losing to winning 
by being lowered?). This is a bit tricky to deal with, so I'll use the 
following stronger version:

It shouldn't be possible for A to go from being ranked ahead of X in the 
social outcome to being ranked below X, simply by some voters raising A 
on their ballots.

This is stronger because it concerns the social outcome, not just 
winning vs losing. But it's easier to quantify, as what it means is that 
moving an epsilon of voting weight from a ballot ranking A kth to one 
ranking A (k-1th) shouldn't narrow the gap f(A) - f(B) nor the gap f(A) 
- f(C).

Let g(A) = f(A) - f(B), h(A) = f(A) - f(C). Then (strong) monotonicity 
implies
	dg/dABC - dg/dBAC >= 0
	dg/dBAC - dg/dBCA >= 0
	dg/dACB - dg/dCAB >= 0
	dg/dCAB - dg/dCBA >= 0

and equivalently for dh.

Since everything is linear, it's just all a bunch of linear 
inequalities. The hard part is getting the fiddly bits right, but I'll 
try. Hopefully there are no missteps.

	dg/dABC - dg/dBAC >= 0

(w_ABC - w_CAB) - (w_BAC - w_ACB) >= 0

	dg/dBAC - dg/dBCA >= 0

(w_BAC - w_ACB) - (w_BCA - w_ABC) >= 0

	dg/dACB - dg/dCAB >= 0

(w_ACB - w_CBA) - (w_CAB - w_BCA) >= 0

	dg/dCAB - dg/dCBA >= 0

(w_CAB - w_BCA) - (w_CBA - w_BAC) >= 0

and similarly for dh:

(w_ABC - w_BCA) - (w_BAC - w_CBA) >= 0
(w_BAC - w_CBA) - (w_BCA - w_CAB) >= 0
(w_ACB - w_BAC) - (w_CAB - w_ABC) >= 0
(w_CAB - w_ABC) - (w_CBA - w_ACB) >= 0

Now let's try the -lpc method: w_ABC = w_BAC = -1, everything else 0.

(-1 - 0) - (-1 - 0) >= 0		OK
(-1 - 0) - (0 - -1) >= 0		not OK	(dg/dBAC - dg/dBCA)
(0 - 0) - (0 - 0) >= 0			OK		
(0 - 0) - (0 - -1) >= 0			not OK	(dg/dCAB - dg/dCBA)
(-1 - 0) - (-1 - 0) >= 0		OK
(-1 - 0) - (0 - 0) >= 0			not OK	(dh/dBAC - dh/dBCA)
(0 - -1) - (0 - -1) >= 0		OK
(0 - -1) - (0 - 0) >= 0			OK

This suggests:
	- raising A from BCA to BAC can make B gain score at the expense of A,
	- raising A from CAB to CBA can make B gain score, and
	- raising A from BAC to BCA can make C gain score at the expense of A.

Let's check.

if f(A) = -lpC, then since C is the candidate beating A pairwise,
    f(B) = -lpA and
    f(C) = -lpB.

f(A) - f(B) = lpA - lpC,
f(A) - f(C) = lpB - lpC.

If we raise A from BCA to BAC, that increases lpC by one and decreases 
lpA by one. So f(A) - f(B) decreases, which benefits B. In addition, 
f(A) - f(C) decreases because it too has a -lpC term. So C is also 
helped, though not as much as B.

If we raise A from CBA to CAB, that increases lpB by one and decreases 
lpA by one. So f(A) - f(C) decreases, which benefits C.

So that checks out.

Compare to fpA-fpC:
w = [1, 1, 0, 0, -1 -1]

(1 - -1) - (0 - 1) >= 0
(0 - 1) - (0 - 1) >= 0
(1 - -1) - (-1 - 0) >= 0
(-1 - 0) - (-1 - 0) >= 0
(1 - 0) - (0 - -1) >= 0
(0 - -1) - (0 - -1) >= 0
(1 - 0) - (-1 - 1) >= 0
(-1 - 1) - (-1 - 1) >= 0

for which all the inequalities are satisfied.

Also, the following modification to Forest's method, derived by linear 
programming:

f(A) = -lpC - 2 lpA
w = [-1, 0, -1, -2, 0, -2]

should be monotone, as:

(-1 - 0) - (-1 - 0) = 0
(-1 - 0) - (-2 - -1) = 0
(0 - -2) - (0 - -2) = 0
(0 - -2) - (-2 - -1) = 3
(-1 - -2) - (-1 - -2) = 0
(-1 - -2) - (-2 - 0) = 3
(0 - -1) - (0 - -1) = 0
(0 - -1) - (-2 - 0) = 3

but I don't see why you would bother with it, as it's likely not burial 
resistant.

That should be it!

-km