election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

DSV: A way to restore monotonicity?

KM
Kristofer Munsterhjelm
Sat, Jul 22, 2023 10:59 AM

I may have found a way to either restore monotonicity or reduce
nonmonotonicity to a method. This is quite good if true, so I'd want
others to check before I run around saying I've done something nobody
has before :-)

"Contingent vote with donation": Suppose we have an A>B>C>A cycle and
that A and C advance to the final. Then A might have preferred to have
fewer first preferences - for some of his voters to have voted BAC
instead of ABC - so that B would've advanced to the final instead, and A
would beat B pairwise and win.

The method I just does this: when it checks a finalist pair A and C, it
sees if there's a way of A to transfer some of his first preferences to
another candidate B so that:
- A remains in the top two
- C is pushed off the top two
- A beats B pairwise more than A beats C.

If so, then A's score is given as the maximum of A>B and A>C, not just
A>C as it would otherwise be. (My scoring scheme is, in the absence of
any first preference donations, that the top two candidates X and Y get
scores X>Y and Y>X respectively, and everybody else gets zero. Ties are
handled by A getting max A>B over any B that could be in a finalist
pairing with A. This is slightly more strategy resistant than just
taking the mean score.)

And that seems to rid the method of its nonmonotonicity! In return the
strategy susceptibility increases quite a lot, but (if true) it's the
most resistant summable method I know of yet - just barely beating fpA -
max fpC, even on 3 candidates.

Note that I don't have an actual monotonicity detector in quadelect yet.
The only thing I'm going by is that pushover strategy would be detected
as "Other" strategy, because it's neither burial nor compromising nor
two-sided. Thus "Other" going to zero or near-zero is a good indication.
It would still have to be verified, though.

And furthermore, I think there's room for more optimization. I don't yet
check if A can be on the losing end of a donation, e.g. {A, B} is a
finalist pair but C could displace B. So in this case, A would get A>B
but should (arguably?) get zero instead, which might help strategy
resistance.

Still!

I also did some experimentation with Quick Runoff. It's not very
strategy resistant, so while I proposed a similar idea to Kevin, I don't
think I'm going to implement it yet.

Something else that's strange is that sometimes X is less strategy
resistant than Smith,X even though X passes the InfMC. Some of the time
it's due to ties, but I'm not sure if that's all there is - yet another
reason others should check things out or try variants.

Stats:

The methods are:
IFFP-like, fpA-sum fpC, fpA-max fpC, IFPP, IRV: as in the previous post
Contingent: Contingent vote
Donation: Contingent vote with donation
QRunoff: Quick Runoff with the same A>B>C>D.. tiebreaker (not strictly
speaking anonymous)
IRV: IRV with the same tiebreaker

Impartial culture, 97 voters, 3 candidates, 75000 elections, 512 Other
attempts per:

(Here every fpA-fpC method is the same so I'm just going to list one of
them. IRV and Contingent differ due to their different tiebreakers.)

                ties    burial  compromise  two-sided   other  total

Smith,fpA-max fpC: 0      0.0665  0.0878      0.0153      0      0.1696
Smith,Donation:    0.0043  0.0616  0.0818      0.0240      0      0.1675
Donation:          0.0117  0      0.1214      0.0407      0      0.1621
Smith,Contingent:  0.0023  0.0346  0.0856      0          0.0175 0.1377
Contingent:        0.0054  0      0.1209      0          0.0213 0.1422
Smith,QRunoff:    0      0.2027  0.0876      1e-05      0.4541 0.7444
Smith,IRV:        0      0.0343  0.0855      3e-05      0.0236 0.1434
Smith,IFPP:        0      0.0687  0.0856      0.0158      0      0.1702

Impartial culture, 97 voters, 4 candidates, 75000 elections, 512 tries:

                ties    burial  compromise  two-sided   other  total

Smith,IFPP-like:  0.0225  0.2576  0.1296      0.5071      0      0.8943
IFPP-like:        0.0996  0      0.8838      0          0      0.8838
Smith,fpA-sum fpC: 0.0097  0.4215  0.0963      0.3758      0      0.8936
Smith,fpA-max fpC: 0.0113  0.1534  0.1474      0.3920      0      0.6923
Smith,Donation:    0.0056  0.1074  0.1647      0.3872      1e-05  0.6593
Smith//Donation:  0.0073  0.1263  0.1449      0.3870      3e-04  0.6586
Donation:          0.0147  0.0452  0.6091      0          4e-05  0.6544
Smith,Contingent:  0.0036  0.0815  0.1700      0.0004      0.2045 0.4565
Contingent:        0.0096  0      0.2614      0          0.2385 0.5000
Smith,QRunoff:    0      0.2677  0.1561      0.0007      0.5105 0.9349
Smith,IRV:        0      0.0555  0.1741      5e-05      0.0497 0.2794
Smith,IFPP:        0      0.0973  0.1653      0.0156      0.0496 0.3277

-km

I may have found a way to either restore monotonicity or reduce nonmonotonicity to a method. This is quite good if true, so I'd want others to check before I run around saying I've done something nobody has before :-) "Contingent vote with donation": Suppose we have an A>B>C>A cycle and that A and C advance to the final. Then A might have preferred to have fewer first preferences - for some of his voters to have voted BAC instead of ABC - so that B would've advanced to the final instead, and A would beat B pairwise and win. The method I just does this: when it checks a finalist pair A and C, it sees if there's a way of A to transfer some of his first preferences to another candidate B so that: - A remains in the top two - C is pushed off the top two - A beats B pairwise more than A beats C. If so, then A's score is given as the maximum of A>B and A>C, not just A>C as it would otherwise be. (My scoring scheme is, in the absence of any first preference donations, that the top two candidates X and Y get scores X>Y and Y>X respectively, and everybody else gets zero. Ties are handled by A getting max A>B over any B that could be in a finalist pairing with A. This is slightly more strategy resistant than just taking the mean score.) And that seems to rid the method of its nonmonotonicity! In return the strategy susceptibility increases quite a lot, but (if true) it's the most resistant summable method I know of yet - just barely beating fpA - max fpC, even on 3 candidates. Note that I don't have an actual monotonicity detector in quadelect yet. The only thing I'm going by is that pushover strategy would be detected as "Other" strategy, because it's neither burial nor compromising nor two-sided. Thus "Other" going to zero or near-zero is a good indication. It would still have to be verified, though. And furthermore, I think there's room for more optimization. I don't yet check if A can be on the losing end of a donation, e.g. {A, B} is a finalist pair but C could displace B. So in this case, A would get A>B but should (arguably?) get zero instead, which might help strategy resistance. Still! I also did some experimentation with Quick Runoff. It's not very strategy resistant, so while I proposed a similar idea to Kevin, I don't think I'm going to implement it yet. Something else that's strange is that sometimes X is less strategy resistant than Smith,X even though X passes the InfMC. Some of the time it's due to ties, but I'm not sure if that's all there is - yet another reason others should check things out or try variants. Stats: The methods are: IFFP-like, fpA-sum fpC, fpA-max fpC, IFPP, IRV: as in the previous post Contingent: Contingent vote Donation: Contingent vote with donation QRunoff: Quick Runoff with the same A>B>C>D.. tiebreaker (not strictly speaking anonymous) IRV: IRV with the same tiebreaker Impartial culture, 97 voters, 3 candidates, 75000 elections, 512 Other attempts per: (Here every fpA-fpC method is the same so I'm just going to list one of them. IRV and Contingent differ due to their different tiebreakers.) ties burial compromise two-sided other total Smith,fpA-max fpC: 0 0.0665 0.0878 0.0153 0 0.1696 Smith,Donation: 0.0043 0.0616 0.0818 0.0240 0 0.1675 Donation: 0.0117 0 0.1214 0.0407 0 0.1621 Smith,Contingent: 0.0023 0.0346 0.0856 0 0.0175 0.1377 Contingent: 0.0054 0 0.1209 0 0.0213 0.1422 Smith,QRunoff: 0 0.2027 0.0876 1e-05 0.4541 0.7444 Smith,IRV: 0 0.0343 0.0855 3e-05 0.0236 0.1434 Smith,IFPP: 0 0.0687 0.0856 0.0158 0 0.1702 Impartial culture, 97 voters, 4 candidates, 75000 elections, 512 tries: ties burial compromise two-sided other total Smith,IFPP-like: 0.0225 0.2576 0.1296 0.5071 0 0.8943 IFPP-like: 0.0996 0 0.8838 0 0 0.8838 Smith,fpA-sum fpC: 0.0097 0.4215 0.0963 0.3758 0 0.8936 Smith,fpA-max fpC: 0.0113 0.1534 0.1474 0.3920 0 0.6923 Smith,Donation: 0.0056 0.1074 0.1647 0.3872 1e-05 0.6593 Smith//Donation: 0.0073 0.1263 0.1449 0.3870 3e-04 0.6586 Donation: 0.0147 0.0452 0.6091 0 4e-05 0.6544 Smith,Contingent: 0.0036 0.0815 0.1700 0.0004 0.2045 0.4565 Contingent: 0.0096 0 0.2614 0 0.2385 0.5000 Smith,QRunoff: 0 0.2677 0.1561 0.0007 0.5105 0.9349 Smith,IRV: 0 0.0555 0.1741 5e-05 0.0497 0.2794 Smith,IFPP: 0 0.0973 0.1653 0.0156 0.0496 0.3277 -km