Re: [EM] Best Deterministic Ranked Preference Method?

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Kevin Venzke
Forest wanted the below posted to EM.

But Forest, the original is not BPW. BPW only cares about the first preference winner and is only for three candidates. I called your method "BTT" in my post.

I'll take a look at your new idea.

Kevin


Le mercredi 23 décembre 2020 à 10:02:27 UTC−6, Forest Simmons <[hidden email]> a écrit :
>
>Season's Greetings!

Kristofer & Kevin pointed out the non-monotonicity and identified the original version as Stensholts BPW, 
and Kevin compared it wth some related methods with various relative advantages  ... great work!

I generalized in a different direction than Kevin, and got lucky ... the mono-raise problem fixed!

Elect the alternative that (for the greatest number of ballots B) is not pairwise beaten by any of the 
alternatives that are approved on ballot B.

This version is closest to BPW when "approved" means  "ranked equal top."

It works equally well wth implicit or explicit approval.

This method always elects from Landau, i.e. the winner is always uncovered.

This property can be traded in for the FBC by simply swapping out the phrase "not pairwise beaten" for 
the phrase "not majority defeated." (a trick I learned from Kevin many years ago)

If the voters are not allowed explicit approval cutoffs, then they should be allowed equal top, or truncation 
at the very least, in order to accommodate a default cutoff. For the FBC compliant version equal top must 
be allowed.

As we have seen from past experience, the explicit approval cutoff facilitates different responses to burial 
and chicken offensives.

We can review that in another message.

Best Wishes to All!

Forest

P.S. Kristofer, please forward this to the EM list; when I do it, I always get some spam back for some 
mysterious reason.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Forest Simmons
This Stenholts fix needs a name.... until Kevin gives it a label in his methods space diagram, I'll just refer to it as "Hog Belly Honey" in honor of the late immortal R. A. Lafferty ... one of his characters gave that name to his fateful invention "on account of it's so sweet!"

This method makes use of approval cutoffs, whether explicit, implicit, or default. I would like to add another choice to the default category ... a version of Joe Weinstein's approval strategy:

On each ranked ballot B approve alternative X iff the total random ballot probability of the alternatives ranked strictly above X on ballot B is less than 50 percent.

So together HBH & Weinstein say ...

... for each ballot B work down the ranks to the lowest level L such that the random ballot probabilities of higher ranked alternatives sum to no more than fifty percent. 

Each alternative that is not pairwise beaten by any alternative ranked above level L on ballot B gets a point from B.

Declare as winner the alternative with the greatest accumulation of points from the various ballots.

It is important to note that this Weinstein approval add-on is monotone when used as a stand alone DSV approval method for elections based on rankings of the alternatives. Consequently, unless I am grossly mistaken, the combined method HBH\\Weinstein must satisfy mono-raise, a true miracle anong DSV-like methods!

On Wednesday, December 23, 2020, Kevin Venzke <[hidden email]> wrote:
Forest wanted the below posted to EM.
rankins
But Forest, the original is not BPW. BPW only cares about the first preference winner and is only for three candidates. I called your method "BTT" in my post.

I'll take a look at your new idea.

Kevin


Le mercredi 23 décembre 2020 à 10:02:27 UTC−6, Forest Simmons <[hidden email]> a écrit :
>
>Season's Greetings!

Kristofer & Kevin pointed out the non-monotonicity and identified the original version as Stensholts BPW, 
and Kevin compared it wth some related methods with various relative advantages  ... great work!

I generalized in a different direction than Kevin, and got lucky ... the mono-raise problem fixed!

Elect the alternative that (for the greatest number of ballots B) is not pairwise beaten by any of the 
alternatives that are approved on ballot B.

This version is closest to BPW when "approved" means  "ranked equal top."

It works equally well wth implicit or explicit approval.

This method always elects from Landau, i.e. the winner is always uncovered.

This property can be traded in for the FBC by simply swapping out the phrase "not pairwise beaten" for 
the phrase "not majority defeated." (a trick I learned from Kevin many years ago)

If the voters are not allowed explicit approval cutoffs, then they should be allowed equal top, or truncation 
at the very least, in order to accommodate a default cutoff. For the FBC compliant version equal top must 
be allowed.

As we have seen from past experience, the explicit approval cutoff facilitates different responses to burial 
and chicken offensives.

We can review that in another message.

Best Wishes to All!

Forest

P.S. Kristofer, please forward this to the EM list; when I do it, I always get some spam back for some 
mysterious reason.

----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Kevin Venzke
In reply to this post by Kevin Venzke
Hi Forest,

Here are some thoughts. Recall your original non-monotone method is being called BTT.

Your approval method, I call BTA. I think this method is monotone only if you use an explicit approval cutoff. With implicit approval, raising a candidate (from the bottom) can change two candidates' approval and create a problem.

BTA is quite similar to MinMax(WV) and MinMax(AWP).

I thought it was odd that if one votes A>B (approving both) and B pairwise defeats A, then A can't get credit for this vote. So I took the liberty of devising another method called BTP (P=preferred). In BTP, instead of checking for losses to all the approved candidates, you check for losses to the candidates strictly preferred to the candidate you're scoring. This revised method turns out to be incredibly similar to MinMax(WV). It's not so obvious to me yet why it should be, but for now I'm amazed.

(Comparing BTP to other WV methods, Schulze/River/RP/MinMax are closer to each other than to BTP. Since BTP seems to satisfy Schwartz and mono-raise I wonder if it must have a clone problem or other weird flaw. By some metrics BTP seems to be less good.)

Your idea to make BTA satisfy FBC unfortunately doesn't seem to quite work. I call that version BTAM (M=majority). It's an indecisive method: Consider a scenario with no majorities at all, with perfect scores awarded to everyone. If you break ties with approval, it is very similar to MDDA. A problem for FBC is that your top-ranked candidates may stand in each other's way of getting credit for the vote. Example:

0.384: B>A>C
0.299: C>B>A
0.176: C=A>B  -----> change to C>A=B
0.138: A>C>B
0.002: B>C>A

There's an A>C>B>A majority cycle. Initially B wins. Then A is lowered on some ballots. This has no effect but to allow C to claim those ballots to their score. Now C wins.

That's it for now.

Kevin


>Le mercredi 23 décembre 2020 à 10:13:09 UTC−6, Kevin Venzke <[hidden email]> a écrit :
>
>
>Forest wanted the below posted to EM.
>
>But Forest, the original is not BPW. BPW only cares about the first preference winner and is only for 
>three candidates. I called your method "BTT" in my post.
>
>I'll take a look at your new idea.
>
>Kevin
>
>
>Le mercredi 23 décembre 2020 à 10:02:27 UTC−6, Forest Simmons <[hidden email]> a écrit :
>>
>>Season's Greetings!
>
>Kristofer & Kevin pointed out the non-monotonicity and identified the original version as Stensholts BPW, 
>and Kevin compared it wth some related methods with various relative advantages  ... great work!
>
>I generalized in a different direction than Kevin, and got lucky ... the mono-raise problem fixed!
>
>Elect the alternative that (for the greatest number of ballots B) is not pairwise beaten by any of the 
>alternatives that are approved on ballot B.
>
>This version is closest to BPW when "approved" means  "ranked equal top."
>
>It works equally well wth implicit or explicit approval.
>
>This method always elects from Landau, i.e. the winner is always uncovered.
>
>This property can be traded in for the FBC by simply swapping out the phrase "not pairwise beaten" for 
>the phrase "not majority defeated." (a trick I learned from Kevin many years ago)
>
>If the voters are not allowed explicit approval cutoffs, then they should be allowed equal top, or truncation 
>at the very least, in order to accommodate a default cutoff. For the FBC compliant version equal top must 
>be allowed.
>
>As we have seen from past experience, the explicit approval cutoff facilitates different responses to burial 
>and chicken offensives.
>
>We can review that in another message.
>
>Best Wishes to All!
>
>Forest
>
>P.S. Kristofer, please forward this to the EM list; when I do it, I always get some spam back for some 
>mysterious reason.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Kevin Venzke
Hi Forest, two replies in one:

>On Wednesday, December 23, 2020, Kevin Venzke <[hidden email]> wrote:
>>
>> I thought it was odd that if one votes A>B (approving both) and B pairwise defeats A, then A can't get credit for this 
>>vote. So I took the liberty of devising another method called BTP (P=preferred). In BTP, instead of checking for losses 
>>to all the approved candidates, you check for losses to the candidates strictly preferred to the candidate you're 
>>scoring. This revised method turns out to be incredibly similar to MinMax(WV). It's not so obvious to me yet why it 
>>should be, but for now I'm amazed.
>>
>We're getting close with BTP!
>
>My tweak: x gets a point from every ballot B on which it is both ranked AND it pairwise beats every alternative 
>ranked strictly above it on that ballot B.
>
>More generally, ... a point from every ballot on which it is both approved and it beats every alternative ranked above it.
>
>(No alternative gets a point from any ballot on which it is not approved, i.e. not ranked in the case of implicit approval)
>
>How about that?

I call this BTPA. (But I used beat-or-tie, not strictly beat.) It is quite different from BTP or BTA, and appears extremely similar to Condorcet//DSC, especially with 3 candidates. For my taste this is not very good. It's also pretty close to fpA-fpC though, with 3 candidates.

Basically with BTPA your score as a candidate is capped by your implicit approval, and you can be deprived of it by weaker candidates who beat you pairwise. In contrast it seems to be important to BTP's properties that candidates can score off of ballots that didn't vote for them, which only voted for candidates that were beaten by them.

Also, it seems to me to be an advantage of BTP over BTA or BTPA that you don't need any implicit approval concept.

---

Regarding HBH and Weinstein, I'm having a lot of trouble getting this to work reasonably. For one thing, I can't find a way to interpret single-round Weinstein DSV Approval so that it is monotone. Also, if approval can extend into the bottom rank, it violates Plurality a lot. I can disallow that, but this creates a lot more monotonicity issues.

(One could suggest that the approval cutoff be placed prior to the rank that exceeds 50% of the random ballot odds, but this doesn't seem workable because it means a majority favorite can't receive his votes.)

Here's a Weinstein mono-raise example for your consideration.

0.311: D>C>A>B approves DCA
0.270: A>B>C>D approves AB
0.186: C>B>D>A approves CBD
0.143: B>D>A=C approves BD
0.087: B>D>A=C approves BD

D wins. Now change the 0.143 bloc to vote D>B at the top instead of B>D. I find that this causes the .311 bloc to stop approving A (since D carries more weight now), and the .270 bloc to start approving C (since B carries less weight). So now C wins.

Kevin
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Kristofer Munsterhjelm-3
On 24/12/2020 22.19, Kevin Venzke wrote:

> Regarding HBH and Weinstein, I'm having a lot of trouble getting this
> to work reasonably. For one thing, I can't find a way to interpret
> single-round Weinstein DSV Approval so that it is monotone. Also, if
> approval can extend into the bottom rank, it violates Plurality a
> lot. I can disallow that, but this creates a lot more monotonicity
> issues.

DSV tends to be nonmonotone in general: in a way, IRV is Plurality DSV.
Brams made a simlar point about a ministerial apportionment method: the
greedy approach could make someone wish they'd been asked to pick a
position *later*. He solved the problem with a negotiation mechanic: if
party X wanted to switch a minister seat with party Y and both agreed,
then it would be done. So some kind of either fix to get out of a local
optimum, or lookahead to avoid getting into that optimum to begin with,
seems to be needed.

About fpA-fpC, one way to get an idea of what a four-candidate fpA-fpC
method may be like could be to investigate elections where clone
independence demands that some candidate wins (e.g. you can get to the
election by cloning A, and B wins in the original three-candidate
fpA-fpC election; then A must win in the new election).

One of the problems of extending fpA-fpC is that there's no obvious
cloneproof way to do first preferences (apart from DAC/DSC). Perhaps
such "clone continuations" could give some ideas.

(But fpA-fpC could also be an uncontinuable dead end. I'll have to check
when I get more RAM to run my manipulability simulations on.)
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Forest Simmons
In reply to this post by Kevin Venzke
Kevin, 

Thanks for holding my feet to the fire!

...Weinstein approval comment in line below. We seem to understand it differently in two ways...

On Thursday, December 24, 2020, Kevin Venzke <[hidden email]> wrote:
Hi Forest, two replies in one:

>On Wednesday, December 23, 2020, Kevin Venzke <[hidden email]> wrote:
>>
>> I thought it was odd that if one votes A>B (approving both) and B pairwise defeats A, then A can't get credit for this 
>>vote. So I took the liberty of devising another method called BTP (P=preferred). In BTP, instead of checking for losses 
>>to all the approved candidates, you check for losses to the candidates strictly preferred to the candidate you're 
>>scoring. This revised method turns out to be incredibly similar to MinMax(WV). It's not so obvious to me yet why it 
>>should be, but for now I'm amazed.
>>
>We're getting close with BTP!
>
>My tweak: x gets a point from every ballot B on which it is both ranked AND it pairwise beats every alternative 
>ranked strictly above it on that ballot B.
>
>More generally, ... a point from every ballot on which it is both approved and it beats every alternative ranked above it.
>
>(No alternative gets a point from any ballot on which it is not approved, i.e. not ranked in the case of implicit approval)
>
>How about that?

I call this BTPA. (But I used beat-or-tie, not strictly beat.) It is quite different from BTP or BTA, and appears extremely similar to Condorcet//DSC, especially with 3 candidates. For my taste this is not very good. It's also pretty close to fpA-fpC though, with 3 candidates.

Basically with BTPA your score as a candidate is capped by your implicit approval, and you can be deprived of it by weaker candidates who beat you pairwise. In contrast it seems to be important to BTP's properties that candidates can score off of ballots that didn't vote for them, which only voted for candidates that were beaten by them.

Also, it seems to me to be an advantage of BTP over BTA or BTPA that you don't need any implicit approval concept.

---

Regarding HBH and Weinstein, I'm having a lot of trouble getting this to work reasonably. For one thing, I can't find a way to interpret single-round Weinstein DSV Approval so that it is monotone. Also, if approval can extend into the bottom rank, it violates Plurality a lot. I can disallow that, but this creates a lot more monotonicity issues.

(One could suggest that the approval cutoff be placed prior to the rank that exceeds 50% of the random ballot odds, but this doesn't seem workable because it means a majority favorite can't receive his votes.)

Here's a Weinstein mono-raise example for your consideration.

0.311: D>C>A>B approves DCA
But .311+ .186 +.270 > .50 so only D & C can be approved. "the total probability of approved alternatives on a ballot cannot exceed 50 percent" 
0.270: A>B>C>D approves AB
0.186: C>B>D>A approves CBD
But .186 +(.143+ .087) + .311 > .50 so only C and B can be approved.
0.143: B>D>A=C approves BD
0.087: B>D>A=C approves BD

D wins. Now change the 0.143 bloc to vote D>B at the top instead of B>D. 

In my version this transposition is actually two moves because equal ranking must be allowed for random ballot probabilities to split (between B and D in this case). So raising D leads to B=D, and it takes another move to lower B.

That said, it seems like the approval cutoff rising on a faction where D was approved and B not, could lead to D falling out of approval, etc.

I find that this causes the .311 bloc to stop approving A (since D carries more weight now), and the .270 bloc to start approving C (since B carries less weight). So now C wins.

Kevin

I'm starting to think of the points awarded as a kind of updating of approvals in light of the pairwise information; an alternative that beats every alternative ranked above it is a threat to be reckoned with, so perhaps the new info might justify lowering the approval cutoff adjacent to the threat ... below it if the threat is ranked ... above it otherwise.

Running with this idea ... run one pass of a bubble sort from the bottom ranked (but not truncated) alternative upward (Llull applied to the ballot order of the ranked alternatives). This Llull winner becomes the (inclusive) approval cutoff.

A refinement of this idea starts with a (tentative) explicit approval cutoff.  If the Llull winner falls below the tentatve cutoff, then the new cutoff is immediately above the Llull winner.  In every case the new cutoff is obtained by moving from the tentative cutoff to a position immediately adjacent to the Lull winner (stopping as soon as adjacency has been achieved).

This seems to be taking us back to Rob LeGrand ...

Joyeux Noel!

Forest



----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Best Deterministic Ranked Preference Method?

Kevin Venzke
Hi Forest,

Real quick:

Le vendredi 25 décembre 2020 à 00:15:20 UTC−6, Forest Simmons <[hidden email]> a écrit : 
>> (One could suggest that the approval cutoff be placed prior to the rank that exceeds 50% of the random ballot odds, 
>> but this doesn't seem workable because it means a majority favorite can't receive his votes.)
>>
>> Here's a Weinstein mono-raise example for your consideration.
>>
>> 0.311: D>C>A>B approves DCA
>
>But .311+ .186 +.270 > .50 so only D & C can be approved. "the total probability of approved alternatives on a ballot 
>cannot exceed 50 percent" 

I considered that initially. But what about majority favorites? They wouldn't receive any of their top rankings as approval.

>> D wins. Now change the 0.143 bloc to vote D>B at the top instead of B>D. 
>
>In my version this transposition is actually two moves because equal ranking must be allowed for random ballot 
>probabilities to split (between B and D in this case). So raising D leads to B=D, and it takes another move to lower B.

I could see permitting a method that allows ER to perform the transition in two steps. However, for Mono-raise, two steps is strictly a harder test. If you change the winner taking a single step, you will still change the winner when taking two steps to get to the same place.

Kevin
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] extending fpA-fpC

Kevin Venzke
In reply to this post by Kristofer Munsterhjelm-3
Hi Kristofer,

Le jeudi 24 décembre 2020 à 20:56:20 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :

>About fpA-fpC, one way to get an idea of what a four-candidate fpA-fpC
>method may be like could be to investigate elections where clone
>independence demands that some candidate wins (e.g. you can get to the
>election by cloning A, and B wins in the original three-candidate
>fpA-fpC election; then A must win in the new election).
>
>One of the problems of extending fpA-fpC is that there's no obvious
>cloneproof way to do first preferences (apart from DAC/DSC). Perhaps
>such "clone continuations" could give some ideas.
>
>(But fpA-fpC could also be an uncontinuable dead end. I'll have to check
>when I get more RAM to run my manipulability simulations on.)

I took a look at this problem. You can use a different route to get to the same 3-candidate scores, while trying to make sense of what the fpA-fpC metric represents. I think it's a measure of doubt as to whether the A>B win is genuine. An A-top ballot is definitely a genuine expression of A>B. A C-top ballot may not be. A B-top ballot is irrelevant. (A C>A=B or C>B>A vote would also be irrelevant. There could be a possible refinement to be found in this point, though so far I haven't had much luck.)

My best attempt to extend the method has better monotonicity than C//IRV, has a few Plurality failures, and appears to satisfy Schwartz without imposing it explicitly... I'm not sure if that's correct though. It could be that with a large number of candidates it becomes possible to make a scenario that fails Schwartz.

Here is the definition:

Define singlescore(a,b,c) like this:
If candidate C doesn't beat A, return positive infinity.
Otherwise, return:
( number of votes preferring A to both of B and C ) minus ( number of votes preferring C to both of A and B).

Define combinedscore(a,b) like this:
The lowest possible singlescore(a,b,x) where a/b/x are distinct candidates.
If there are no values to consider, return positive infinity.

Define winscore(a,b) like this:
Undefined if A doesn't beat B pairwise. Otherwise combinedscore(a,b).

Define candidatescore(a) like this:
The greatest value of winscore(a,x) given some other candidate x.
If there are no values to consider, return negative infinity.

Elect the candidate with the greatest candidatescore.

There are perhaps some options available to change whether min or max is used in various places, but the above seemed to work the best. For example combinedscore could return the *greatest* value (though this seems illogical to me), and the candidatescore could use the *least* value of winscore as the measure of a candidate.

I originally intended to run the scored contests through the River mechanism, but that doesn't match how fpA-fpC simply elects the candidate with the best score. My extension interprets the score to belong originally to a contest, not the candidate. There could be implications for clone independence and Plurality.

The Plurality failures aren't common, but here is an example of one:
0.331: D
0.307: B>C
0.270: C>A
0.089: A

All candidates are in Schwartz. There are only a couple of positive singlescores: singlescore(b,c,a) is the highest (signifying that the B>C win was not fabricated by A voters, who don't even express it), followed by (d,b,c) indicating that D>B was not fabricated by C voters. But none of the combinedscores are positive. The final candidate scores are:
B: -.024 for singlescore(b,c,d)
D: -.028 for ss(d,b,a).
C: -.037 for either (c,a,b) or (c,d,b)
A: -.181 for (a,b,c)

So B wins. The algorithm seems to get lost in specific details, I'd say, and doesn't really assess candidates' overall merit. But maybe there's a way to redesign it.

Kevin
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] extending fpA-fpC

Kristofer Munsterhjelm-3
A very late reply, but:

On 26/12/2020 22.25, Kevin Venzke wrote:

> Hi Kristofer,
>
> Le jeudi 24 décembre 2020 à 20:56:20 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :
>> About fpA-fpC, one way to get an idea of what a four-candidate fpA-fpC
>> method may be like could be to investigate elections where clone
>> independence demands that some candidate wins (e.g. you can get to the
>> election by cloning A, and B wins in the original three-candidate
>> fpA-fpC election; then A must win in the new election).
>
> I took a look at this problem. You can use a different route to get
> to the same 3-candidate scores, while trying to make sense of what the
> fpA-fpC metric represents. I think it's a measure of doubt as to whether
> the A>B win is genuine. An A-top ballot is definitely a genuine
> expression of A>B. A C-top ballot may not be. A B-top ballot is
> irrelevant. (A C>A=B or C>B>A vote would also be irrelevant. There could
> be a possible refinement to be found in this point, though so far I
> haven't had much luck.)
>
> My best attempt to extend the method has better monotonicity than
> C//IRV, has a few Plurality failures, and appears to satisfy Schwartz
> without imposing it explicitly... I'm not sure if that's correct though.
> It could be that with a large number of candidates it becomes possible
> to make a scenario that fails Schwartz.

I think this method also fails DMTBR, if I've implemented it right.

Before:

1: A>C>D>B
1: A>D>B>C
1: B>C>D>A
1: C>A>B>D
1: D>B>A>C

A wins. Now let a C>A voter bury A:

1: A>C>D>B
1: A>D>B>C
1: B>C>D>A
1: C>B>D>A  (A is buried here)
1: D>B>A>C

and A and C tie for first.

Replacing min and max with leximin and leximax where possible helps, but
doesn't seem to fix that particular problem instance.
----
Election-Methods mailing list - see https://electorama.com/em for list info