Monotone method inspiration approach?
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
On Mon, Jan 17, 2022 at 4:40 PM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
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,
Btw, if you want to make a plot of that, I recommend you replace the
Heavyside function with one that is equal to 0.5 when x is exactly 0.
Otherwise, when fpB == fpC you'll see f(A) suddenly crash to 0 for no
apparent reason and you'll be left scratching your head.
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
.5 + .5*sign(x)
El lun., 17 de ene. de 2022 4:57 p. m., Daniel Carrera dcarrera@gmail.com
escribió:
On Mon, Jan 17, 2022 at 4:40 PM Kristofer Munsterhjelm <
km_elmet@t-online.de> wrote:
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,
Btw, if you want to make a plot of that, I recommend you replace the
Heavyside function with one that is equal to 0.5 when x is exactly 0.
Otherwise, when fpB == fpC you'll see f(A) suddenly crash to 0 for no
apparent reason and you'll be left scratching your head.
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Election-Methods mailing list - see https://electorama.com/em for list
info
We electrical engineering geeks call that the "Unit Step function". And it's the integral of the "Unit Impulse function". Most of the rest of humanity calls the latter the "Dirac delta function".
On 01/17/2022 8:34 PM Forest Simmons forest.simmons21@gmail.com wrote:
.5 + .5*sign(x)
El lun., 17 de ene. de 2022 4:57 p. m., Daniel Carrera dcarrera@gmail.com escribió:
On Mon, Jan 17, 2022 at 4:40 PM Kristofer Munsterhjelm km_elmet@t-online.de wrote:
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,
Btw, if you want to make a plot of that, I recommend you replace the Heavyside function with one that is equal to 0.5 when x is exactly 0. Otherwise, when fpB == fpC you'll see f(A) suddenly crash to 0 for no apparent reason and you'll be left scratching your head.
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
Election-Methods mailing list - see https://electorama.com/em for list info
Election-Methods mailing list - see https://electorama.com/em for list info
--
r b-j . _ . _ . _ . _ rbj@audioimagination.com
"Imagination is more important than knowledge."
.
.
.
On 18.01.2022 01:57, Daniel Carrera wrote:
On Mon, Jan 17, 2022 at 4:40 PM Kristofer Munsterhjelm
<km_elmet@t-online.de mailto:km_elmet@t-online.de> wrote:
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,
Btw, if you want to make a plot of that, I recommend you replace the
Heavyside function with one that is equal to 0.5 when x is exactly 0.
Otherwise, when fpB == fpC you'll see f(A) suddenly crash to 0 for no
apparent reason and you'll be left scratching your head.
That's deliberately left unspecified because when fpB == fpC, that means
that two candidates tie for last, and then IRV's in big trouble. I
think using second preferences to break the tie would then work, but
as this situation is measure zero I didn't want to further complicate my
expression by including it.
In practice, this tie dependence can further amplify IRV's chaotic
behavior. Warren calls it "near-tie nightmares".
-km
On 18.01.2022 10:29, Kristofer Munsterhjelm wrote:
On 18.01.2022 01:57, Daniel Carrera wrote:
On Mon, Jan 17, 2022 at 4:40 PM Kristofer Munsterhjelm
<km_elmet@t-online.de mailto:km_elmet@t-online.de> wrote:
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,
Btw, if you want to make a plot of that, I recommend you replace the
Heavyside function with one that is equal to 0.5 when x is exactly 0.
Otherwise, when fpB == fpC you'll see f(A) suddenly crash to 0 for no
apparent reason and you'll be left scratching your head.
That's deliberately left unspecified because when fpB == fpC, that means
that two candidates tie for last, and then IRV's in big trouble. I
think using second preferences to break the tie would then work, but
as this situation is measure zero I didn't want to further complicate my
expression by including it.
In practice, this tie dependence can further amplify IRV's chaotic
behavior. Warren calls it "near-tie nightmares".
Come to think of it, perhaps that would make for an interesting way to
handle ties in IRV. A first approximation would be this: when there are
no ties, X's score is X's pairwise strength against whatever Y is left
in the final round if X isn't eliminated before the final round,
otherwise 0. And if B and C is tied, then X's score is one half his
score if B got eliminated + one half his score if C got eliminated.
It's not quite the same thing as H being the symmetric (odd) Heaviside
function because the above explanation doesn't handle three-way ties
(fpA-fpC = fpB-fpC = 0). But perhaps it could still be useful for
something. Is there a concise way of recursively describing the full
version?
This is all assuming g() is the plus operator. Different results happen
if g is say, max.
-km
On Tue, Jan 18, 2022 at 3:36 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Is there a concise way of recursively describing the full
version?
I think I have an idea. I'm going to let g() be the plus operator. I will
define a couple of helper functions:
h(A,B) = {1 if fpA > fpB; 0.5 if fpA = fpB; 0 if fpA < fpB}
This is just a repackaged sign function.
k(A,B,C,D,...) = H(fpA - min(fpA, fpB, fpC, ...))
This is a repackaged Heavyside function.
[A > B] = Defined the same way you did.
These provide a lot of notational convenience. Notice that the order of
arguments is significant and k() has a variable number of arguments.
Lastly, I'm going to redefine f(A) so that it too has a variable number of
arguments and the order of arguments is significant.
f(A,B,C,D,...) = score of A in the election {A,B,C,D,...}
Now I can define f() recursively:
f(A,B,C) = k(A,B,C) * ( h(B,C)[A>C] + h(C,B)[A>B] )
f(A,B,C,D) = k(A,B,C,D) * ( f(A,B,C) + f(A,B,D) + f(A,C,D) )
And so on.
So the score of A for the N-candidate election is k(A,B,...), which covers
the option where A is the plurality loser on this round, times the sum of
the scores of A for each of the possible (N-1)-candidate elections that
include A. This can probably be expressed with some combinatorial notation
that I haven't thought of.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University