[EM] Monotone method inspiration approach?

Kristofer Munsterhjelm km_elmet at t-online.de
Mon Jan 17 14:38:41 PST 2022


Consider methods as functions that assign some score to candidate, so
that the greatest score wins. I.e. f(A, e) is the score for candidate A
in election e.

Then monotonicity just involves making f(A, e) - f(B, e) nondecreasing
in raising A on some ballot on e.

So I started tinkering with IRV in this form. Method slike Plurality (or
minmax) are easy to make into a function of this form, but IRV's kind of
difficult.

In the three-candidate case, the following rules hold for A:
	If fpA > fpC and fpB > fpC then C is eliminated, so A's score is A>B.
	If fpA > fpB and fpC > fpB then B is eliminated, so A's score is A>C.
	If fpB > fpA and fpC > fpA then A is eliminated and so his score is 0.

And similarly for the other candidates (I've excluded them for brevity).

These if-then clauses may be difficult to put into mathematical
expression form, but I found this (which may seem a bit ugly at first):
	f(A) = g(H(fpA - fpC) * H(fpB-fpC) * A>B,
	         H(fpA - fpB) * H(fpC-fpB) * A>C)

where H is the step function H(x) = 1 if x > 0, 0 otherwise, and g is
some arbitrary function that has the property that g(x * e_k) = x for
any unit vector e_k. For instance, g(x,y) = x+y works, as does g(x,y) =
max(x,y).

Now the nonmonotonicity in IRV is pretty apparent. Raising A might
decrease fpB-fpC and thus cause the H(fpB-fpC) term to go from one to
zero. If A>B is greater than A>C, then this could cause A to lose.

The "obvious" fix, which is like what I did with fpA-fpC, is to
introduce an fpA term into the terms that don't have it, so that
whenever say, fpB-fpC is decreased by raising A to first place, the
increase in fpA compensates for it:

	f(A) = g(H(fpA-fpC) * H(fpA+fpB-fpC) * A>B,
	         H(fpA-fpB) * H(fpA+fpC-fpB) * A>C)

But since first preferences are never negative, fpA+fpB-fpC >= fpA-fpC,
so that's just

	f(A) = g(H(fpA-fpC) * A>B, H(fpA-fpB) * A>C),

which might be reasonable, although I don't know what choices of g
preserve DMTBR.

So perhaps this idea of "write out as an expression then try to add a
term that's increasing in A to terms that may be decreasing in A" can be
used to get inspirations for monotone methods from nonmonotone ones?



Condorcet methods may be more pleasant to work with if f is a function
parameterized on what candidates beat the current candidate and what
candidates the current one beats. E.g. for first preference Copeland let
	f(A, S_beat, S_beaten_by) = sum over all B in S_beaten_by: -fpB
denote the score A attains when beating everybody in S_beat and being
beaten by everybody in S_beaten_by. Then the "naive monotone fix" would be:
	f(A, S_beat, S_beaten_by) = sum over all B in S_beaten_by: fpA-fpB.

Or BPW:
	f(A, {B}, S_beaten_by) = fpB
(only defined when the candidate beats exactly one other) becomes
	f(A, {B}, S_beaten_by) = fpA + fpB.

(Other weightings are possible: fpa + k fpB works as long as 0 < k < 1.)

But I don't know whether any of these preserve strategy resistance.

-km


More information about the Election-Methods mailing list