[EM] finding the beat path winner with just one pass through the ranked pairs
I tried to design a method to find the beat path winner and to resolve beat path ties all in just one pass through the ranked pairs. But Markus demonstrated that my tie resolver was not monotonic. So here, I believe, is a way to get the beat path winner(s) with just one pass through the ranked pairs. Beat path ties remain ties. Now a winner is only reclassified as a loser when there is at least one non-reciprocal winner in its set. Candidates are classed in two categories: Winners and Losers. Initially, all candidates are Winners. Every candidate has an associated Set of candidates that includes itself and those candidates that have defeated it. Every candidate initially has a set composed of itself and no other candidates. Affirm each group of equally ranked pairs in order, from highest to lowest. The count can be ended before all pairs have been affirmed if only one Winner remains. Affirming is composed of two steps: Combining sets and Reclassifying candidates. Affirming Step 1: Combining When A > B is affirmed, the set for candidate A is added to every set that includes candidate B (not just candidate B’s set). The Combining step is performed for all pairs of the same rank before moving on to the Reclassifying step. Affirming Step 2: Reclassifying Winning candidate C is reclassified as a loser if there is at least one winner in C’s set that does not have C in its set. Example C>D A>C and B>C D>A and D>B A>B affirm C>D A(W): A(W) B(W): B(W) C(W): C(W) D(L):C(W), D(L) D was reclassified as a Loser since C(W) is in its set. affirm A>C and B > C A(W): A(W) B(W): B(W) C(L): A(W), B(W), C(L) D(L): A(W), B(W), C(L), D(L) C was reclassified as a Loser since A(W) and B(W) are in its set. affirm D > A and D > B A(W): A(W), B(W)*, C(L), D(L) B(W): A(W)*, B(W), C(L), D(L) C(L): A(W), B(W), C(L), D(L) D(L): A(W), B(W), C(L), D(L) A and B remain winners. A is in B's set and B is in A's set. affirming A > B has no effect. A and B are tied. Same as beat path. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
One can resolve ties and find second and third place winners, etc, by doing additional passes through the ranked pairs. Ties can be resolved by passing through the ranked pairs again, this time eliminating candidates that have not won. Second, third, etc, place winners can be found by passing through the ranked pairs again with higher ranked winners classed as losers. Example B>D, C>D A>B, A>C D>A B>C affirm B>D,C>D A(W):A(W) B(W):B(W) C(W):C(W) D(L):B(W),C(W),D(L) affirm A>B,A>C A(W):A(W) B(L):A(W),B(L) C(L):A(W),C(L) D(L):A(W),B(L),C(L),D(L) A is the first place winner. To find the second place winner restart with: A(L):A(L) B(W):B(W) C(W):C(W) D(W):D(W) affirm B>D,C>D A(L):A(L) B(W):B(W) C(W):C(W) D(L):B(W),C(W),D(L) affirm A>B,A>C A(L):A(L) B(W):A(L),B(W) C(W):A(L),C(W) D(L):A(L),B(W),C(W),D(L) affirm D>A A(L):A(L),B(W),C(W),D(L) B(W):A(L),B(W),C(W),D(L) C(W):A(L),B(W),C(W),D(L) D(L):A(L),B(W),C(W),D(L) affirming B>C does not change the sets. B and C are tied. To resolve the tie for second place, restart with D eliminated. A>B, A>C B>C A(L):A(L) B(W):B(W) C(W):C(W) affirm A>B,A>C A(L):A(L) B(W):A(L),B(W) C(W):A(L),C(W) affirm B>C A(L):A(L) B(W):A(L),B(W) C(L):A(L),B(W),C(L) B is the second place winner. --- On Fri, 12/9/11, Ross Hyman wrote: > From: Ross Hyman > Subject: finding the beat path winner with just one pass through the ranked > pairs > To: election-methods@lists.electorama.com > Date: Friday, December 9, 2011, 4:36 AM > I tried to design a method to find > the beat path winner and to resolve beat path ties all in > just one pass through the ranked pairs. But Markus > demonstrated that my tie resolver was not monotonic. > > So here, I believe, is a way to get the beat path winner(s) > with just one pass through the ranked pairs. Beat path > ties remain ties. Now a winner is only reclassified as > a loser when there is at least one non-reciprocal winner in > its set. > > Candidates are classed in two categories: Winners and > Losers. Initially, all candidates are Winners. > Every candidate has an associated Set of candidates that > includes itself and those candidates that have defeated > it. Every candidate initially has a set composed of > itself and no other candidates. > > Affirm each group of equally ranked pairs in order, from > highest to lowest. The count can be ended > before all pairs have been affirmed if only one Winner > remains. Affirming is composed of two steps: Combining > sets and Reclassifying candidates. > > Affirming Step 1: Combining > When A > B is affirmed, the set for candidate A is > added > to every set that includes candidate B (not just candidate > B’s set). The Combining step is performed for all > pairs of the same rank before moving on to the Reclassifying > step. > > Affirming Step 2: Reclassifying > Winning candidate C is reclassified as a loser if there is > at least one winner in C’s set that does not have C in its > set. > > Example > C>D > A>C and B>C > D>A and D>B > A>B > > affirm C>D > A(W): A(W) > B(W): B(W) > C(W): C(W) > D(L):C(W), D(L) > D was reclassified as a Loser since C(W) is in its set. > > affirm A>C and B > C > A(W): A(W) > B(W): B(W) > C(L): A(W), B(W), C(L) > D(L): A(W), B(W), C(L), D(L) > C was reclassified as a Loser since A(W) and B(W) are in > its set. > > affirm D > A and D > B > A(W): A(W), B(W)*, C(L), D(L) > B(W): A(W)*, B(W), C(L), D(L) > C(L): A(W), B(W), C(L), D(L) > D(L): A(W), B(W), C(L), D(L) > A and B remain winners. A is in B's set and B is in A's > set. > > > affirming A > B has no effect. A and B are tied. > Same as beat path. > > Election-Methods mailing list - see http://electorama.com/em for list info
[EM] MMT2 meets FBC, fails Mono-Add-Plump, as it should.
Mike,
Sorry, there was a typo (20 B>A voters instead of 10) in my
demonstration of MMT2's failure of FBC in my last post. So I'll go
through it again.
MMT2 defines "mutual-majority candidate set" as:
A set of candidates who are each voted above bottom by each member of the
same majority of voters--where that set includes at least one
top-rated candidate
on the ballot of every member of that majority.
45: C
06: D>A
39: A>B
10: B>A
So in this example {A,B,D} isn't a "mutual-majority candidate set"
because D isn't "voted above bottom by each member of the same majority
of voters", right? And because there is no such set the MMT2 winner is
C, right?
Say those votes were all sincere. If the 6 D>A voters change to A>B (or
A=B or B>A) the winner changes to A, a candidate those voters prefer to C.
45: C
06: A>B (sincere is D>A)
39: A>B
10: B>A
Now {A,B} is a "mutual-majority candidate set" and MMT2 elects A.If the
method meets the FBC, those 6 voters must have some way of voting D not
below equal-top and get a result they like as much. What is it?
Mono-Add-Plump makes even less sense for MMT than for MDDTR.
The failure scenario is:
Your favorite wins by having the most top ratings among a
mutual-majority candidate
set. Now some new voters arrive and plump for hir. As plumpers, they
aren't counted
in the mutual majority. But they are counted in the total number of
voters, thereby
increasing the majority requirement. No longer is there a
mutual-majority candidate
set. No longer is your favorite the winner.
Is anyone claiming that that result is wrong?
Err..yes, I claim that at least one of the results must be "wrong". Even
if we ignore the mono-add-plump failure and look at the two elections
independently (of each other), it is highly likely that at least one of
them will be a failure of some other desirable criterion compliance.
And, by the way, with MMT, the Mono-Add-Plump "failure", and the LNHa
compliance
and LNHe "failure" don't create a random-fill incentive.
Logically, I don't see how it couldn't.
49: C
21: A (new voters, whose ballots switch the MMT2 winner from A to C)
27: A>B
24: B>A
(121 ballots, majority threshold = 61)
If the 21 A truncators randomly choose between middle-rating B or C then
A's chance of winning changes from zero to more than 50% (more than
11/21 have to middle-rate C for A to not win).
Chris Benham
Mike Ossipoff wrote (8 Dec 2011):
FBC:
In MMT2, if you top-rate a compromise, along with your favorite, then you'll
be counted in the majority supporting a mutual-majority candidate set that
s/he is in.
That's because MMT2 defines "mutual-majority candidate set" as:
A set of candidates who are each voted above bottom by each member of the
same majority of voters--where that set includes at least one top-rated
candidate
on the ballot of every member of that majority.
Mono-Add-Plump:
Mono-Add-Plump makes even less sense for MMT than for MDDTR.
The failure scenario is:
Your favorite wins by having the most top ratings among a
mutual-majority candidate
set. Now some new voters arrive and plump for hir. As plumpers, they
aren't counted
in the mutual majority. But they are counted in the total number of
voters, thereby
increasing the majority requirement. No longer is there a
mutual-majority candidate
set. No longer is your favorite the winner.
Is anyone claiming that that result is wrong?
Your favorite initially won only because of mutual majority support. The
plumpers
declined that mutual support, as is their right. Having declined mutual
support,
should it be surprising or unfair if they no longer have it?
And, by the way, with MMT, the Mono-Add-Plump "failure", and the LNHa
compliance
and LNHe "failure" don't create a random-fill incentive.
The LNHe "failure" consists only of perhaps being able to benefit from
mutual majority
support.
I should say again that, henceforth, when I say "MMT", without a
distinguishing number,
I'm referring to MMT2, the MMT version that I discussed above here.
I'm curious about MMMPO's compliance with FBC, LNHa and Mono-Add-Plump,
and its
compliance in Kevin's MMPO bad-example--a previously unattainable
combination of
properties. If MMMPO can be presented to the public in a simple,
naturally and obviously
motivated manner, then it would have the advantage that it wouldn't even
be necessary
to answer any Mono-Add-Plump criticism.
Mike Ossipoff
Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Chris: Criterion compliances of MMT2
My latest MMT version is still MMT2. It’s my latest, final,
and best MMT version.
By its definition of a mutual-majority candidate set, in
your example, {A,B} is a mutual-majority candidate set.
But if it weren’t big enough, and if the D voters wanted to
add themselves to it, then they’d have only to vote
D=A>B. By MMT2’s
definition of a mutual majority candidate set.
Therefore, there would be no violation of FBC in your
example.
Your example illustrates a general fact: It’s possible to be
counted in support of any mutual majority candidate set without voting anyone
over your favorite. MMT2 meets FBC.
I agree that MMT (by which I mean MMT2) fails
Mono-Add-Plump. As I explained yesterday, it wouldn’t make any sense for it to
meet that criterion. Mono-Add-Plump isn’t a useful or meaningful criterion.
I’ve told why that is.
That statement is perfectly acceptable as an expression of
your own personal impression. But if it were to be an _assertion_, then of
course you’d need to support it. Unless you wanted to define “reasonable” in
terms of one particular example.
I’m going to guess that, by “reasonable”, you mean
“Condorcet-complying”. Or maybe
“Woodall-acceptable”.
I’ll be glad to explain that to them:
First, let me tell you two things that are _not_ why we
switched from FPP:
One: Because it’s important that we never get the same
result that Plurality would give.
Two: Because Plurality’s standard, “favorite of the most”,
isn’t a good standard.
“Favorite of the most” is a good standard. Some good methods
don’t use it. Some good methods use it.
By itself, it doesn’t furnish any majority-rule protection.
With any method, a majority can get its way. If the method doesn’t enforce
majority rule, then the voters will have to, which often creates an undesirable
need for drastic strategy. For example, in FPP, many or most voters were afraid
to vote for their favorite, always voting instead for some not-really-liked
“compromise”, thereby burying their favorite.
That’s why we switched from FPP. We’ve replaced FPP with a
method in which you’ll never have any need to vote someone else over your
favorite. It’s also a method that provides good majority-rule enforcement.
[end of explanation for why we switched from FPP]
Condorcet’s criterion is incompatible with FBC.
…which would only mean something if you justified Mutual
Dominant Third.
As I’ve said before, Chris isn’t wrong. His standards,
purposes, goals are different from mine, but that doesn’t mean that he’s wrong.
I’m interested in avoiding the strategy problems that
prevent a majority from getting their wishes or make it unnecessarily
difficult. Chris is interested in…..something else. That’s ok. He isn’t wrong.
Well, where he starts being wrong is when he becomes
absolutist about what’s reasonable, what’s right, what’s wrong, etc.
Outcomes are right or wrong _with respect to some particular
goal_.
Mike Ossipoff
Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Oops! Forgot to include Chris's text. Chris MMT reply, complete this time.
When I first posted this, a few minutes ago, I forgot to include the text that
I was replying to.
In this posting, that text is present, and my replies are interspersed where
they go.
Chris said:
> As far as I can see the examples I gave apply equally well to "MMT2".
> I've pasted them in at the bottom.
He was referring to his posting copied and replied to below:
>
> I think this (MMT2) fails the FBC. Say sincere is:
>
> 45: C
> 06: D>A
> 39: A>B
> 20: B>A
>
> There is no "mutual majority set" (by your latest definition)
My latest MMT version is still MMT2. It’s my latest, final,
and best MMT version.
By its definition of a mutual-majority candidate set, in
your example, {A,B} is a mutual-majority candidate set.
But if it weren’t big enough, and if the D voters wanted to
add themselves to it, then they’d have only to vote
D=A>B. By MMT2’s
definition of a mutual majority candidate set.
Therefore, there would be no violation of FBC in your
example.
Your example illustrates a general fact: It’s possible to be
counted in support of any mutual majority candidate set without voting anyone
over your favorite. MMT2 meets FBC.
Chris continued:
> It also fails Mono-add-Plump.
I agree that MMT (by which I mean MMT2) fails
Mono-Add-Plump. As I explained yesterday, it wouldn’t make any sense for it to
meet that criterion. Mono-Add-Plump isn’t a useful or meaningful criterion.
I’ve told why that is.
> I think all reasonable methods will elect A in both cases.
That statement is perfectly acceptable as an expression of
your own personal impression. But if it were to be an _assertion_, then of
course you’d need to support it. Unless you wanted to define “reasonable” in
terms of one particular example.
I’m going to guess that, by “reasonable”, you mean
“Condorcet-complying”. Or maybe
“Woodall-acceptable”.
> Electing C in
> the second case will have voters wondering why they bothered switching
> from FPP
I’ll be glad to explain that to them:
First, let me tell you two things that are _not_ why we
switched from FPP:
One: Because it’s important that we never get the same
result that Plurality would give.
Two: Because Plurality’s standard, “favorite of the most”,
isn’t a good standard.
“Favorite of the most” is a good standard. Some good methods
don’t use it. Some good methods use it.
By itself, it doesn’t furnish any majority-rule protection.
With any method, a majority can get its way. If the method doesn’t enforce
majority rule, then the voters will have to, which often creates an undesirable
need for drastic strategy. For example, in FPP, many or most voters were afraid
to vote for their favorite, always voting instead for some not-really-liked
“compromise”, thereby burying their favorite.
That’s why we switched from FPP. We’ve replaced FPP with a
method in which you’ll never have any need to vote someone else over your
favorite. It’s also a method that provides good majority-rule enforcement.
[end of explanation for why we switched from FPP]
> , and is a very bad case of failing Condorcet
Condorcet's Criterion is incompatible with FBC.
> and Mutual Dominant Third (DMT).
For that to mean anything, you'd have to justify that criterion.
Mike Ossipoff
Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Reply to a posting from Chris on November 17th, re: MDDTR
This is a reply to a posting from Chris, on November 17th. The discussion is about this example: > 49: C > 27: A>B > 24: B Chris said: Truncation isn't a "problem" (for the full-rankers) as an "offensive strategy". The problem is that it isn't fair to the sincere truncators. [endquote] I answered that in the paragraph that you quote next. > How does A lack legitimacy? Among the candidates not majority-defeated, A > has more favoriteness-supporters than any other candidate. Translation: "I love this arbitrary algorithm, so any winner it produces is by definition legitimate." [endquote] Chris’s interpretation loses something in the translation :-) Someone is confused. I was answering a claim that MDDTR’s way of choosing lacked legitimacy, justification or rightness. So forgive me if, to that end, I mentioned MDDTR’s way of choosing :-) So then, how wrong, illegitimate or unjustified is MDDTR’s way of choosing?: I’ll say this again: A majority has the power to get its way. So that it won’t have to do so by undesirably drastic strategy, it’s desirable that the method itself enforce majority rule in some way. Different methods do that in different ways. One way, not the only way, would be to listen to people when they say that they’d rather have x than y. There is someone more preferred than y, by a majority of the voters. One way for a method to respond to that statement (but not the only way) would be to disqualify y. That’s what MDDTR does. Now, the question is: How to choose among the undisqualified candidates? Again, there are many good ways, many standards. Here’s an obvious standard: Act on the fact that more people want x as favorite than want y as favorite. That isn’t the only way of choosing, or the only right way of choosing. As I’ve said, by itself, as a whole method, that standard wouldn’t be enough, because it doesn’t provide majority-rule protection. But MDDTR’s first stage, the majority-defeat-disqualification, accomplishes that. Chris continued: A's win lacks legitimacy simply because there is another candidate that was vastly better supported on the ballots. [endquote] Oh, so now we must do the election by Plurality’s standard :-) Chris continued: If we add between 2 and 21 ballots that plump for A, then C's "majority-defeatedness" goes away and the winner changes from A to C, another failure of Mono-add-Plump [endquote] Perhaps Chris has forgotten that I answered that last time he said it. We’ve already been over that, and I’ve replied regarding the Mono-Add-Plump criticism of MDDTR. Chris continued: If we nonetheless accept that C but not A should be immediately disqualified, electing the undisqualified candidate with the most top-ratings is just another arbitrary feature of the algorithm. [endquote] This from someone who has just finished advocating Plurality’s standard :-) Chris probably doesn’t know what he means by “arbitrary”. As I already said, each method uses different ways of choosing, judging by different standards. That’s why they’re called “different methods”, you know. One could come up with all sorts of competing standards, and it could be argued that the choice between them is arbitrary, There’s certainly obvious and undeniable justification in preferring the election of someone who is favorite to more people. Then why don’t we just keep Plurality, or (along with Chris) adjudicate the ABE entirely by Plurality’s standard? …Because we want majority rule, in some form, that’s why. A good reason for wanting that is to avoid the strategy problems that result when the method doesn’t, in some way, honor majority rule. One way to do that is to disqualify majority-defeated candidates. That isn’t the only way. Other good methods implement majority rule in different ways. MMPO, MDDTR, MTAOC, and MMT do so in their own different ways, via different rules. But doing so in some way is necessary in order to avoid the worst strategy problems. Anyway, not knowing exactly what Chris means by “arbitrary” I’ll say that I didn’t choose MMPO, MDDTR, MTAOC and MMT arbitrarily. I chose them for their properties. In the ABE, I’m not saying that A must win, though I prefer that outcome. If C wins, because a majority against C fail to mutually co-operate, I have no objection to that. That’s one of the solutions to the ABE. MTAOC and MMT solve it in that way. In other words, not recognizing one-sided “coalitions” is one solution to the ABE. Or, alternatively, make it that one-side is all that is needed to define a majority and assure that the winner must come from that majority. MMPO and MMT do that. But don’t use that majority support, the support that makes the winner be one of the favorites among that majority, against the candidate(s) of the people who gave the support. Use any other reasonable way to choose among the favorite candidates among that majority of the voters. Chr
[EM] Acquiescing majority MMT
Forest-- Let's find out what its properties are. Just preliminarily, it sounds like one of the MMT ideas that I considered. But it seemed to me, at the time (if it's the same method I was considering) that, if a ballot can be counted in that majority merely by rating each candidate in the set equal to or over every candidate outside the set, then, in the ABE, the B votes could rate A at bottom, with C, and still be part of the relevant majority. So there there is the set required by the acquiescing rule, and there is one candidate rated above bottom by everyone in that set: Candidate B. So, the method that I'd considered wouldn't pass in the ABE. I don't know if the method you describe is the same one, but, preliminarily, it sounds similar. But maybe not. Any possibility could yield improvement. My definition of that set was something like this: A set of candidates rated equal to or over everyone outside the set by each member of the same majority of the voters. Mike Ossipoff Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] This might be the method we've been looking for:
> > Here’s a method that seems to have the important properties that we have > been worrying about lately: > > (1) For each ballot beta, construct two matrices M1 and M2: > In row X and column Y of matrix M1, enter a one if ballot beta rates X > above Y or if beta gives a top > rating to X. Otherwise enter a zero. > IN row X and column y of matrix M2, enter a 1 if y is rated strictly above > x on beta. Otherwise enter a > zero. > > (2) Sum the matrices M1 and M2 over all ballots beta. > > (3) Let M be the difference of these respective sums > . > (4) Elect the candidate who has the (algebraically) greatest minimum > row value in matrix M. > > Consider the scenario > 49 C > 27 A>B > 24 B>A > Since there are no equal top ratings, the method elects the same candidate > A as minmax margins > would. > > In the case > 49 C > 27 A>B > 24 B > There are no equal top ratings, so the method gives the same result as > minmax margins, namely C wins > (by the tie breaking rule based on second lowest row value between B and > C). > > Now for > 49 C > 27 A=B > 24 B > In this case B wins, so the A supporters have a way of stopping C from > being elected when they know > that the B voters really are indifferent between A and C. > > The equal top rule for matrix M1 essentially transforms minmax into a > method satisfying the FBC. > > Thoughts? > To me, it doesn't seem like this fully solves our Approval Bad Example. There still seems to be a chicken dilemma. Couldn't you also say that the B voters should equal-top-rank A to stop C from being elected: 49 C 27 A 24 B=A Then A wins, right? But now the A and B groups have a chicken dilemma. They should equal-top-rank each other to prevent C from winning, but if one group defects and doesn't equal-top-rank the other, then they get the outright win. Am I wrong? ~ Andy Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] This might be the method we've been looking for:
No, the B group has nothing to gain by defecting; all they can do is bring about a C win. Honestly, A group doesn't have a lot to gain from defecting, either; either they win anyway, or they misread the election and they're actually the B's. Jameson 2011/12/9 Andy Jennings > Here’s a method that seems to have the important properties that we have >> been worrying about lately: >> >> (1) For each ballot beta, construct two matrices M1 and M2: >> In row X and column Y of matrix M1, enter a one if ballot beta rates X >> above Y or if beta gives a top >> rating to X. Otherwise enter a zero. >> IN row X and column y of matrix M2, enter a 1 if y is rated strictly >> above x on beta. Otherwise enter a >> zero. >> >> (2) Sum the matrices M1 and M2 over all ballots beta. >> >> (3) Let M be the difference of these respective sums >> . >> (4) Elect the candidate who has the (algebraically) greatest minimum >> row value in matrix M. >> >> Consider the scenario >> 49 C >> 27 A>B >> 24 B>A >> Since there are no equal top ratings, the method elects the same >> candidate A as minmax margins >> would. >> >> In the case >> 49 C >> 27 A>B >> 24 B >> There are no equal top ratings, so the method gives the same result as >> minmax margins, namely C wins >> (by the tie breaking rule based on second lowest row value between B and >> C). >> >> Now for >> 49 C >> 27 A=B >> 24 B >> In this case B wins, so the A supporters have a way of stopping C from >> being elected when they know >> that the B voters really are indifferent between A and C. >> >> The equal top rule for matrix M1 essentially transforms minmax into a >> method satisfying the FBC. >> >> Thoughts? >> > > > To me, it doesn't seem like this fully solves our Approval Bad Example. > There still seems to be a chicken dilemma. Couldn't you also say that the > B voters should equal-top-rank A to stop C from being elected: > 49 C > 27 A > 24 B=A > Then A wins, right? > > But now the A and B groups have a chicken dilemma. They should > equal-top-rank each other to prevent C from winning, but if one group > defects and doesn't equal-top-rank the other, then they get the outright > win. > > Am I wrong? > > ~ Andy > > > > > Election-Methods mailing list - see http://electorama.com/em for list info > > Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] MMPO and Symmetric Completion
Jameson, good idea and valuable comments. However, I'm not sure that regret is the right word. I regret something after I make a bad choice. I resent something when I make a good choice that is over-ridden by somebody with the power to do so. I suggest "Least Resentment Voting," LRV. Forest - Original Message - From: Jameson Quinn Date: Thursday, December 8, 2011 4:46 pm Subject: Re: [EM] MMPO and Symmetric Completion To: fsimm...@pcc.edu Cc: election-methods@lists.electorama.com > > > > > > Now let's come up with a good name for this MMPO with partial > symmetric> completion. Actually we > > need a good technical name as well as a catchy name for public > proposal.> > > This is indeed a good method. In simple parlance, you want the > candidatewho is least disliked against any other candidate, > counting equal bottom as > half-disliked. So I suggest "Least Regret Voting" as a name. > > Unfortunately, this philosophy -- choosing the least-worst -- is less > intuitively-appealing to most people than majoritarian > philosophies. If I > didn't know how the two systems worked, I'd probably be more > inclined to > like a system called "Majority Judgment" than a system called > "Least Regret > Voting". > > (Actually, even knowing their content, I'd still probably pick > MJ; though > I'd pick LRV if you modified it slightly by using a ballot with > meaningfulrating categories, which is perfectly compatible with > the system. I'll > still be pushing MJ and SODA over rated-LRV, though, until > there's at least > a few dozen people in the world not on this list who've heard of LRV. > Anyway, regardless of which methods I support, I still think > it's a pity > that the naming has an inherent bias towards MJ over LRV; the systems > should win or lose on their merits, not on their names.) > > As for a technical name... I guess I'd choose "BSC-MMPO", > Bottom-symmetrically-completed etc. But I'm one who's perfectly > happy to > call MJ, "MJ", rather than "Cardinal Median//Median Drop Median" > or some > such technically-descriptive name. So I don't really care about the > technical names. > > Jameson > > ps. I know that BR fans might object to the different definition of > "regret" implicit in calling it LRV; but I was never a fan of > the "BR" name > myself so I can't say I worry about that. BR is a great idea > but, I feel, a > poor name. > Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
Dear Ross, the runtime to calculate the strongest path from every candidate to every other candidate is O(C^3). However, the runtime to sort O(C^2) pairwise defeats is already O(C^4). So you cannot get a faster algorithm by sorting the pairwise defeats. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
Markus wrote: > the runtime to calculate the strongest path from > every candidate to every other candidate is O(C^3). > However, the runtime to sort O(C^2) pairwise defeats > is already O(C^4). So you cannot get a faster > algorithm by sorting the pairwise defeats. Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n) algorithm such as heapsort? -- Rob LeGrand r...@approvalvoting.org Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] Acquiescing majority MMT (MIKE OSSIPOFF)
Mike,
yes it is the same as the one you repeated at the end of your reply below.
But notice that in the ballot set
49 C
27 A>B
24 B
there are two Acquiescing Majorities, namely both {A, B} and {B, C}, and that C
has more top votes than B.
Forest
> From: MIKE OSSIPOFF
> To:
> Subject: [EM] Acquiescing majority MMT
> Message-ID:
> Content-Type: text/plain; charset="iso-8859-1"
>
>
> Forest--
>
> Let's find out what its properties are.
>
> Just preliminarily, it sounds like one of the MMT ideas that I
> considered.
>
> But it seemed to me, at the time (if it's the same method I was
> considering) that, if a ballot can be counted in that majority
> merely by rating each candidate
> in the set equal to or over every candidate outside the set,
> then, in the ABE, the B votes could
> rate A at bottom, with C, and still be part of the relevant
> majority. So there there is
> the set required by the acquiescing rule, and there is one
> candidate rated above bottom
> by everyone in that set: Candidate B.
>
> So, the method that I'd considered wouldn't pass in the ABE. I
> don't know if the method
> you describe is the same one, but, preliminarily, it sounds similar.
>
> But maybe not. Any possibility could yield improvement.
>
> My definition of that set was something like this:
>
> A set of candidates rated equal to or over everyone outside the
> set by each member of the
> same majority of the voters.
>
> Mike Ossipoff
>
>
> -- next part --
> An HTML attachment was scrubbed...
> URL: > electorama.com/attachments/20111209/a13f00db/attachment.htm>
> --
>
> ___
> Election-Methods mailing list
> Election-Methods@lists.electorama.com
> http://lists.electorama.com/listinfo.cgi/election-methods-
> electorama.com
>
> End of Election-Methods Digest, Vol 90, Issue 24
>
>
Election-Methods mailing list - see http://electorama.com/em for list info
[EM] Least Resentment Voting (LRV) in the context of Approval
If I remember correctly Kevin Venzke's first post to this list was a geometric argument that the MMPO winner was apt to be closer to the voter median position in Approval than the Approval winner. The scenario he had in mind was something like this Scenario One: 26 A 24 A=C 24 B=C 26 B The geometry was something like this: AB _ It weemed pretty obvious that the MMPO winner C was more likely the true majority choice than than either of the tied approval winners A.or B. Not long after that Kevin came up with his MMPO bad example: Senario Two: 48 A 2 A=C 2 B=C 48 B. The MMPO winner C lacked too much approval to be the real winner. Kevin took back his proposal, and went on the bigger and better things like trying to convince Juho that MinMax (margins) was not an acceptable public proposal. either. But as I mentioned in a recent posting MMPO with symmetric completion is the same as MinMax(margins), and by exempting the top rank or slot from the symmetric completion, we get a really nice compromise between MMPO and MinMax(margins), and what's more this version gives the "right" answer in both scenarios above. Kevin was ever so close to proposing what I now call LRV "Least Resentment Voting" or more technically Bottom- Symmetric-Completion MMPO. In the first scenario above both A and B have max opposition of fifty, while the max opposition of C is 26 + 13 = 39, so C wins. In the second scenario, A and B still have max opposition of 50 each, but now C's max opposition is 48 + 24 = 72, so C loses, to a tie betwen A and B. Where is the cutoff where all three are tied? Scenario Three: 34 A 17 A=C 17 B=C 34 B In this scenario the max opposition (with the bottom symmetric completion rule in effect) is 34+17 for A, 34+17 for B, and 34 +17 for C. The second largest opposition to either A or B is 17+17=34, while the second largest opposition to C is still 34+17, so C loses the tied situation , and the winner is a toss up between A and B. Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
On 7/22/64 2:59 PM, Rob LeGrand wrote: Markus wrote: the runtime to calculate the strongest path from every candidate to every other candidate is O(C^3). However, the runtime to sort O(C^2) pairwise defeats is already O(C^4). So you cannot get a faster algorithm by sorting the pairwise defeats. Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n) algorithm such as heapsort? Yes, this is correct. In practice quicksort is faster than heapsort (though not asymptotically). The strongest path algorithm is solved in O(C^3) using the Floyd-Warshall algorithm, applied to a different commutative semiring (max, min) than the usual (min, +). However, faster algorithms are known for solving the same problem (all-pairs shortest path). For example, there is a paper by Melhorn and Priebe that shows how to solve it in O(C^2 log C) expected time. I don' t know if these faster algorithms work on all commutative semirings, though. -- Andrew Election-Methods mailing list - see http://electorama.com/em for list info
