One benefit to nonmonotone methods
Since it's pretty quiet at the moment, here's another observation. I've
been testing some methods that pass DMT or DMTC, and I've found out two
things:
-
The "monotonized" contingent vote, where if A is the Plurality winner
and can give some of his first preferences to some other B to displace
the other finalist C and get B into the top two instead, A's score
becomes A>B instead of A>C, is not that much more strategy susceptible
than the ordinary contingent vote (0.91 vs 0.87 for 97 candidates, 10k
elections, 32k tries per election). -
But it's much harder to get the true strategy resistance of
nonmonotone methods, because coalitional strategy is much harder to find
than two-sided "rank who you're compromising for top, the current winner
bottom" strategy.
So even if say, a method X and its monotone variant both have strategy
resistance 0.8, it's often harder to execute strategy against the
nonmonotone one in practice because you can overshoot.
In a monotone method, if your honest vote is A>B>C>D>E, and the current
winner is D, and you're compromising for C, then if A>C>B>D>E works,
then C>A>B>D>E will also work and most likely C>A>B>E>D will also work.
So you can slam your compromise to the top and your burial target (the
current winner) to the bottom, and that's a pretty simple strategy.
But in a nonmonotone method, it's possible that A>C>B>D>E will work but
C>A>B>D>E won't. So even though the honest election is vulnerable to
strategy with both methods, it's harder to find the correct strategy.
Thus if you absolutely need all the strategy resistance you can get,
nonmonotone is probably where it's at. I'll still try to find a good
monotone burial-resistant method, though!
Some stats to show this effect: impartial culture, 97 voters, 5
candidates, 50k elections, 32k coalitional tries per election:
Smith,Contingent vote:
Ties: 0.00612
Burial without compromise: 0.11049
Compromise without burial: 0.24123
Burial and compromise: 0.00278
Two-sided: 0.00254
Other: 0.51588
Total susceptibility: 0.87292
Smith,Contingent vote with donation:
Ties: 0.00904
Burial without compromise: 0.13044
Compromise without burial: 0.23402
Burial and compromise: 0.01158
Two-sided: 0.54180
Other: 4e-05
Total susceptibility: 0.91788
The "Other" category (which contains pushover and pushover-like
strategy) has been almost entirely emptied, and that strategy has become
two-sided instead.
(Two-sided is the fraction of elections where neither burial nor
compromising works, but doing both at the same time works.)
-km
Monotone Banks methods are not easy to come by ... but here is the simplest
UD Monotone Banks method that I know of:
MaxPS Sorted Pairwise
Initialize a list variable L as the list of candidates in order of their
MaxPairwiseSupport.
[Break ties by considering in turn 2nd, 3rd, ... levels of support.]
While no member of L is pairwise undefeated, update L by removing its
bottom member X as well as every candidate defeated by X.
Elect the remaining undefeated candidate highest on the list L.
It seems to me that this procedure yields a very clean, monotone,
clone-free, one pass, precinct summable, Banks efficient, UD, burial
resistant method.
Are we over-looking anything?
fws
On Sun, Jul 30, 2023, 6:21 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Since it's pretty quiet at the moment, here's another observation. I've
been testing some methods that pass DMT or DMTC, and I've found out two
things:
-
The "monotonized" contingent vote, where if A is the Plurality winner
and can give some of his first preferences to some other B to displace
the other finalist C and get B into the top two instead, A's score
becomes A>B instead of A>C, is not that much more strategy susceptible
than the ordinary contingent vote (0.91 vs 0.87 for 97 candidates, 10k
elections, 32k tries per election). -
But it's much harder to get the true strategy resistance of
nonmonotone methods, because coalitional strategy is much harder to find
than two-sided "rank who you're compromising for top, the current winner
bottom" strategy.
So even if say, a method X and its monotone variant both have strategy
resistance 0.8, it's often harder to execute strategy against the
nonmonotone one in practice because you can overshoot.
In a monotone method, if your honest vote is A>B>C>D>E, and the current
winner is D, and you're compromising for C, then if A>C>B>D>E works,
then C>A>B>D>E will also work and most likely C>A>B>E>D will also work.
So you can slam your compromise to the top and your burial target (the
current winner) to the bottom, and that's a pretty simple strategy.
But in a nonmonotone method, it's possible that A>C>B>D>E will work but
C>A>B>D>E won't. So even though the honest election is vulnerable to
strategy with both methods, it's harder to find the correct strategy.
Thus if you absolutely need all the strategy resistance you can get,
nonmonotone is probably where it's at. I'll still try to find a good
monotone burial-resistant method, though!
Some stats to show this effect: impartial culture, 97 voters, 5
candidates, 50k elections, 32k coalitional tries per election:
Smith,Contingent vote:
Ties: 0.00612
Burial without compromise: 0.11049
Compromise without burial: 0.24123
Burial and compromise: 0.00278
Two-sided: 0.00254
Other: 0.51588
Total susceptibility: 0.87292
Smith,Contingent vote with donation:
Ties: 0.00904
Burial without compromise: 0.13044
Compromise without burial: 0.23402
Burial and compromise: 0.01158
Two-sided: 0.54180
Other: 4e-05
Total susceptibility: 0.91788
The "Other" category (which contains pushover and pushover-like
strategy) has been almost entirely emptied, and that strategy has become
two-sided instead.
(Two-sided is the fraction of elections where neither burial nor
compromising works, but doing both at the same time works.)
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
Not monotone?
44 A>B>C
28 C>A>B
28 B>C>A
An A>B>C>A cycle, but C has the least support, so C and, because C beats A pairwise, A as well, are eliminated so B wins. Yay, B!
Hold on, 17 A>B>C voters decide they like B better than A and become B>A>C voters.
27 A>B>C
28 C>A>B
28 B>C>A
17 B>A>C
Now we have the same cycle, but A has the smallest MaxPairwiseSupport, so A and B are eliminated and C wins! The 17 voters made their new favorite lose.
Or I may be misunderstanding something.
Jim Faran
From: Election-Methods election-methods-bounces@lists.electorama.com on behalf of Forest Simmons forest.simmons21@gmail.com
Sent: Sunday, July 30, 2023 8:36 PM
To: Kristofer Munsterhjelm km_elmet@t-online.de
Cc: EM election-methods@lists.electorama.com
Subject: Re: [EM] One benefit to nonmonotone methods
Monotone Banks methods are not easy to come by ... but here is the simplest UD Monotone Banks method that I know of:
MaxPS Sorted Pairwise
Initialize a list variable L as the list of candidates in order of their MaxPairwiseSupport.
[Break ties by considering in turn 2nd, 3rd, ... levels of support.]
While no member of L is pairwise undefeated, update L by removing its bottom member X as well as every candidate defeated by X.
Elect the remaining undefeated candidate highest on the list L.
It seems to me that this procedure yields a very clean, monotone, clone-free, one pass, precinct summable, Banks efficient, UD, burial resistant method.
Are we over-looking anything?
fws
On Sun, Jul 30, 2023, 6:21 AM Kristofer Munsterhjelm <km_elmet@t-online.demailto:km_elmet@t-online.de> wrote:
Since it's pretty quiet at the moment, here's another observation. I've
been testing some methods that pass DMT or DMTC, and I've found out two
things:
-
The "monotonized" contingent vote, where if A is the Plurality winner
and can give some of his first preferences to some other B to displace
the other finalist C and get B into the top two instead, A's score
becomes A>B instead of A>C, is not that much more strategy susceptible
than the ordinary contingent vote (0.91 vs 0.87 for 97 candidates, 10k
elections, 32k tries per election). -
But it's much harder to get the true strategy resistance of
nonmonotone methods, because coalitional strategy is much harder to find
than two-sided "rank who you're compromising for top, the current winner
bottom" strategy.
So even if say, a method X and its monotone variant both have strategy
resistance 0.8, it's often harder to execute strategy against the
nonmonotone one in practice because you can overshoot.
In a monotone method, if your honest vote is A>B>C>D>E, and the current
winner is D, and you're compromising for C, then if A>C>B>D>E works,
then C>A>B>D>E will also work and most likely C>A>B>E>D will also work.
So you can slam your compromise to the top and your burial target (the
current winner) to the bottom, and that's a pretty simple strategy.
But in a nonmonotone method, it's possible that A>C>B>D>E will work but
C>A>B>D>E won't. So even though the honest election is vulnerable to
strategy with both methods, it's harder to find the correct strategy.
Thus if you absolutely need all the strategy resistance you can get,
nonmonotone is probably where it's at. I'll still try to find a good
monotone burial-resistant method, though!
Some stats to show this effect: impartial culture, 97 voters, 5
candidates, 50k elections, 32k coalitional tries per election:
Smith,Contingent vote:
Ties: 0.00612
Burial without compromise: 0.11049
Compromise without burial: 0.24123
Burial and compromise: 0.00278
Two-sided: 0.00254
Other: 0.51588
Total susceptibility: 0.87292
Smith,Contingent vote with donation:
Ties: 0.00904
Burial without compromise: 0.13044
Compromise without burial: 0.23402
Burial and compromise: 0.01158
Two-sided: 0.54180
Other: 4e-05
Total susceptibility: 0.91788
The "Other" category (which contains pushover and pushover-like
strategy) has been almost entirely emptied, and that strategy has become
two-sided instead.
(Two-sided is the fraction of elections where neither burial nor
compromising works, but doing both at the same time works.)
-km
Election-Methods mailing list - see https://electorama.com/em for list info
Very Good!
That should cure my bad habit of treating Implicit Approval and MaxPS as
though they were interchangeable.
I wonder if we replaced MaxPS with MaxPS+MinPS ... would that work?
For three candidates with complete rankings, MaxPS+MinPS should be the same
as TotalPS which should be equivalent to Borda ... which is monotone... at
least in a stand-alone context ... right?
Let's see ... before the seventeen changed their mind, the respective Borda
Counts for A,B,and C were
44-28, 0, and 28-44
Afterwards they become ...
-1, 17, -16
So both before and after, C had the least Borda Count.
So there's a possibility that this sum of max and min PS might work.
Put another way ... average PS is equivalent to Borda ... and when there
are only three candidates average is just half the sum of max and min PS.
Why not just going with Borda?
Because Borda is clone dependent.
fws
On Sun, Jul 30, 2023, 6:17 PM James Faran jjfaran@buffalo.edu wrote:
Not monotone?
44 A>B>C
28 C>A>B
28 B>C>A
An A>B>C>A cycle, but C has the least support, so C and, because C beats A
pairwise, A as well, are eliminated so B wins. Yay, B!
Hold on, 17 A>B>C voters decide they like B better than A and become B>A>C
voters.
27 A>B>C
28 C>A>B
28 B>C>A
17 B>A>C
Now we have the same cycle, but A has the smallest MaxPairwiseSupport, so
A and B are eliminated and C wins! The 17 voters made their new favorite
lose.
Or I may be misunderstanding something.
Jim Faran
From: Election-Methods election-methods-bounces@lists.electorama.com
on behalf of Forest Simmons forest.simmons21@gmail.com
Sent: Sunday, July 30, 2023 8:36 PM
To: Kristofer Munsterhjelm km_elmet@t-online.de
Cc: EM election-methods@lists.electorama.com
Subject: Re: [EM] One benefit to nonmonotone methods
Monotone Banks methods are not easy to come by ... but here is the
simplest UD Monotone Banks method that I know of:
MaxPS Sorted Pairwise
Initialize a list variable L as the list of candidates in order of their
MaxPairwiseSupport.
[Break ties by considering in turn 2nd, 3rd, ... levels of support.]
While no member of L is pairwise undefeated, update L by removing its
bottom member X as well as every candidate defeated by X.
Elect the remaining undefeated candidate highest on the list L.
It seems to me that this procedure yields a very clean, monotone,
clone-free, one pass, precinct summable, Banks efficient, UD, burial
resistant method.
Are we over-looking anything?
fws
On Sun, Jul 30, 2023, 6:21 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
Since it's pretty quiet at the moment, here's another observation. I've
been testing some methods that pass DMT or DMTC, and I've found out two
things:
-
The "monotonized" contingent vote, where if A is the Plurality winner
and can give some of his first preferences to some other B to displace
the other finalist C and get B into the top two instead, A's score
becomes A>B instead of A>C, is not that much more strategy susceptible
than the ordinary contingent vote (0.91 vs 0.87 for 97 candidates, 10k
elections, 32k tries per election). -
But it's much harder to get the true strategy resistance of
nonmonotone methods, because coalitional strategy is much harder to find
than two-sided "rank who you're compromising for top, the current winner
bottom" strategy.
So even if say, a method X and its monotone variant both have strategy
resistance 0.8, it's often harder to execute strategy against the
nonmonotone one in practice because you can overshoot.
In a monotone method, if your honest vote is A>B>C>D>E, and the current
winner is D, and you're compromising for C, then if A>C>B>D>E works,
then C>A>B>D>E will also work and most likely C>A>B>E>D will also work.
So you can slam your compromise to the top and your burial target (the
current winner) to the bottom, and that's a pretty simple strategy.
But in a nonmonotone method, it's possible that A>C>B>D>E will work but
C>A>B>D>E won't. So even though the honest election is vulnerable to
strategy with both methods, it's harder to find the correct strategy.
Thus if you absolutely need all the strategy resistance you can get,
nonmonotone is probably where it's at. I'll still try to find a good
monotone burial-resistant method, though!
Some stats to show this effect: impartial culture, 97 voters, 5
candidates, 50k elections, 32k coalitional tries per election:
Smith,Contingent vote:
Ties: 0.00612
Burial without compromise: 0.11049
Compromise without burial: 0.24123
Burial and compromise: 0.00278
Two-sided: 0.00254
Other: 0.51588
Total susceptibility: 0.87292
Smith,Contingent vote with donation:
Ties: 0.00904
Burial without compromise: 0.13044
Compromise without burial: 0.23402
Burial and compromise: 0.01158
Two-sided: 0.54180
Other: 4e-05
Total susceptibility: 0.91788
The "Other" category (which contains pushover and pushover-like
strategy) has been almost entirely emptied, and that strategy has become
two-sided instead.
(Two-sided is the fraction of elections where neither burial nor
compromising works, but doing both at the same time works.)
-km
Election-Methods mailing list - see https://electorama.com/em for list
info