Help me understand some notation
I just read this sentence:
"And going from Copeland//Borda to Copeland,Borda shouldn't make the method
that much harder to understand."
I remember seeing Kristofer say "Smith//IRV" and "Smith,IRV". Evidently
"//" and "," have particular meanings. Can someone explain what they are?
At least one of those must mean "Restrict to the Smith set then apply IRV".
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On 20.01.2022 01:05, Daniel Carrera wrote:
I just read this sentence:
"And going from Copeland//Borda to Copeland,Borda shouldn't make the
method that much harder to understand.">
I remember seeing Kristofer say "Smith//IRV" and "Smith,IRV". Evidently
"//" and "," have particular meanings. Can someone explain what they
are? At least one of those must mean "Restrict to the Smith set then
apply IRV".
Smith,IRV is the method where you first do IRV and then you pick the
highest ranked candidate in the resulting social ordering that's in the
Smith set. (In IRV's case this means: the last eliminated candidate
who's in the Smith set.)
Smith//IRV is the method where you first eliminate everybody not in the
Smith set and then do IRV. This is your "restrict to the Smith set
then apply IRV".
Smith//X methods are often nonmonotone because raising A might insert
someone else into (or kick someone else out of) the Smith set. If this
candidate is say, ranked in the middle in the social ordering of X, then
the whole social ordering can change and turn the winner from A to
someone else. Smith,X methods don't have that (unless X itself already
fails).
Maybe I should add a note about this somewhere on electowiki, but I'm
not sure where I would put it so that people who don't know about the
notation would know where to look.
-km
On Thu, Jan 20, 2022 at 4:22 AM Kristofer Munsterhjelm km_elmet@t-online.de
wrote:
On 20.01.2022 01:05, Daniel Carrera wrote:
I just read this sentence:
"And going from Copeland//Borda to Copeland,Borda shouldn't make the
method that much harder to understand.">
I remember seeing Kristofer say "Smith//IRV" and "Smith,IRV". Evidently
"//" and "," have particular meanings. Can someone explain what they
are? At least one of those must mean "Restrict to the Smith set then
apply IRV".
Smith,IRV is the method where you first do IRV and then you pick the
highest ranked candidate in the resulting social ordering that's in the
Smith set. (In IRV's case this means: the last eliminated candidate
who's in the Smith set.)
Smith//IRV is the method where you first eliminate everybody not in the
Smith set and then do IRV. This is your "restrict to the Smith set
then apply IRV".
Smith//X methods are often nonmonotone because raising A might insert
someone else into (or kick someone else out of) the Smith set. If this
candidate is say, ranked in the middle in the social ordering of X, then
the whole social ordering can change and turn the winner from A to
someone else. Smith,X methods don't have that (unless X itself already
fails).
Ha! So I want to look for methods similar to Smith,X. Hmm... let me try:
-
Every candidate has a 1-1 pairwise match against every other candidate.
-
The candidates with the most won matches are "finalists".
-
The finalist with the greatest margin of victory against any other
candidate is elected.
So step (2) basically gives the Copeland set. The whole method should be
"Copeland,X" where "X" is the method "elect the candidate with the largest
victory". Since X must be a monotonic method, would it follow that
Copeland,X is monotonic too? Conversely, if step (3) had said "... against
any other finalist" that would have created "Copeland//X" and it would
probably be non-monotonic. Does that sound right?
This is interesting because something like Smith,X or Copeland,X as in my
example allows you to consider methods X that you would normally have
considered too simple to be interesting. This might be a good way to design
good methods (e.g. Smith-efficient and monotone) without them being very
complicated.
Cheers,
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
On 20.01.2022 12:26, Daniel Carrera wrote:
Ha! So I want to look for methods similar to Smith,X. Hmm... let me try:
-
Every candidate has a 1-1 pairwise match against every other candidate.
-
The candidates with the most won matches are "finalists".
-
The finalist with the greatest margin of victory against any other
candidate is elected.
So step (2) basically gives the Copeland set. The whole method should be
"Copeland,X" where "X" is the method "elect the candidate with the
largest victory". Since X must be a monotonic method, would it follow
that Copeland,X is monotonic too? Conversely, if step (3) had said "...
against any other finalist" that would have created "Copeland//X" and
it would probably be non-monotonic. Does that sound right?
This is interesting because something like Smith,X or Copeland,X as in
my example allows you to consider methods X that you would normally have
considered too simple to be interesting. This might be a good way to
design good methods (e.g. Smith-efficient and monotone) without them
being very complicated.
Yes. I forgot to mention two things, though:
-
Borda is particularly nice in that Copeland//Borda is monotone. This
happens because you can infer the Borda score from the pairwise matrix,
and the remaining pairwise matrix entries don't change when you remove
candidates. So although as a rule X//Y is nonmonotone, some monotone
pairwise-based set restrictions of Borda (in particular Smith and
Copeland) will be monotone. However, Borda is unusually susceptible to
strategy, which is a problem, and neither Borda nor Copeland are cloneproof. -
X//Y methods give up monotonicity, but they get something in return:
if the X set itself is independent of candidates not in it (i.e. you
can't make the X set smaller or larger by introducing candidates not in
it), then X//Y is independent of X-dominated candidates. E.g. in
Smith//Plurality it doesn't matter if there's vote-splitting among the
losers as long as there's no vote-splitting in the Smith set itself. But
in Smith,Plurality, losers outside the Smith set may draw votes away
from the Smith set, making someone else inside it win.
(Note that Copeland fails the "independence of candidates not in it"
criterion. So Copeland//Borda doesn't get you independence of
Copeland-dominated candidates -- but it does get you independence of
Smith-dominated candidates.)
-km
In the case of a three candidate Smith set, the simplest way to get the
Smih,X winner is to use X finish order as the (reverse) agenda for SPE
(Sequential Pairwise Elimination): start at the least promising end of the
agenda (i.e. the last candidate in the finish order) and make one pass of
Bubble Sort. The candidate who ends up on top is the highest Smith
candidate (provided cardinality(Smith)=3).
The beauty of this is its seamless-ness ... no need to even construct or
even mention Smith.
Another Seamless (but not as simple) way is Agenda Based Landau applied to
the same finish order:
Initialize a variable w as the highest finish order candidate. Then ...
While w is covered, let t be the highest finish order candidate that covers
w. Store t in w: (t---->w).
The final value of w is the candidate we want.
El jue., 20 de ene. de 2022 2:22 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 20.01.2022 01:05, Daniel Carrera wrote:
I just read this sentence:
"And going from Copeland//Borda to Copeland,Borda shouldn't make the
method that much harder to understand.">
I remember seeing Kristofer say "Smith//IRV" and "Smith,IRV". Evidently
"//" and "," have particular meanings. Can someone explain what they
are? At least one of those must mean "Restrict to the Smith set then
apply IRV".
Smith,IRV is the method where you first do IRV and then you pick the
highest ranked candidate in the resulting social ordering that's in the
Smith set. (In IRV's case this means: the last eliminated candidate
who's in the Smith set.)
Smith//IRV is the method where you first eliminate everybody not in the
Smith set and then do IRV. This is your "restrict to the Smith set
then apply IRV".
Smith//X methods are often nonmonotone because raising A might insert
someone else into (or kick someone else out of) the Smith set. If this
candidate is say, ranked in the middle in the social ordering of X, then
the whole social ordering can change and turn the winner from A to
someone else. Smith,X methods don't have that (unless X itself already
fails).
Maybe I should add a note about this somewhere on electowiki, but I'm
not sure where I would put it so that people who don't know about the
notation would know where to look.
-km
Election-Methods mailing list - see https://electorama.com/em for list
info
On Thu, Jan 20, 2022 at 1:44 PM Forest Simmons forest.simmons21@gmail.com
wrote:
In the case of a three candidate Smith set, the simplest way to get the
Smih,X winner is to use X finish order as the (reverse) agenda for SPE
(Sequential Pairwise Elimination): start at the least promising end of the
agenda (i.e. the last candidate in the finish order) and make one pass of
Bubble Sort. The candidate who ends up on top is the highest Smith
candidate (provided cardinality(Smith)=3).
The beauty of this is its seamless-ness ... no need to even construct or
even mention Smith.
Ha! That's really neat. So that makes a family of methods with good
properties that are realistic options for real world elections. This family
is similar but simpler than BTR-IRV because they don't have the IRV vote
redistribution step. I scribbled a few diagrams and I can see how this will
always work for a 3-member Smith set, but not for larger ones. Still... it
should be really rare to see a real world election with cardinality(Smith)
- And even in those cases, the methods are at least Smith efficient.
--
Dr. Daniel Carrera
Postdoctoral Research Associate
Iowa State University
De-cloned Borda would go particularly well with de-cloned Copeland ... but
it is not necessary because one of the greatest advantages of de-cloning
Copeland is that it makes ties statistically rare: unlike standard Copeland
whose scores take on only integer values, de-cloned Copeland scores are
almost never integers.
And it would be a shame to help propose a clone dependent election method,
especially if there is a sufficiently simple clone free version.
Here's my first attempt at a greatly simplified version without sacrificing
its integrity:
Elect the candidate X that maximizes the number of its first place votes
minus the number of candidates that head-to-head defeat X, weighted by the
average of their first place votes.
In other words, the winner is the candidate X that maximizes the difference
between its own first place vote count and the total of the first place
counts of the candidates that defeat X head-to-head.
An equivalent formulation that is more likely to yield a positive
difference is ...
Elect the candidate X that minimizes the score S(X), defined as the total
first place vote count of the candidates that pairwise defeat X, minus X's
own first place count.
The first formulation of this method most clearly shows its comparison with
the standard version of Copeland, but the last formulation is easiest to
work with.
Now let's prove monotonicity:
- Raising X neither increases the number of candidates defeating X, nor
any of their first place votes. So raising X cannot increase S(X), unless
the first place votes of X decrease, which is not possible from raising X.
But could raising X decrease S(Y)?
If so it would either (1) have to decrease the number of candidates that
defeat Y, or (2)lower their total number of first place votes, or (3)
increase the number of first place votes of Y.
Let's look at the first possibility ... could raising X make Y defeat or
tie a candidate Z that defeated it before. Certainly not if Z=X. And if Z
!= X, then the relative pairwise count between Z and Y is not affected.
Saving the most difficult possibility for last, we consider (3) ... could
raising X, increase the first place count of Y. No, it could only decrease
Y's first place votes.
Lastly, (3) how about lowering the total number of first place votes among
the candidates that pairwise defeat Y?
If X replaces Z as first place on some ballot, then X's first place count
increases, (which decreases S(X)) while Z's first place count decreases,
possibly decreasing S(Y) by the same amount as S(X). This is no problem if
X defeats Y (because that would increase S(Y)), or if Z does not defeat Y,
because that would have no effect on S(Y).
The only problem is if S(Y) decreases by more than S(X) does.
The problematic case is where Z defeats Y (and Y defeats X). If Y defeats
X, then X contributes nothing to the total of first place votes of the
candidates defeating Y, so has no direct effect on S(Y) . But indirectly
decreasing Z's first place votes by one, decreases S(Y) by one unit. This
decrease maintains the difference between S(X) and S(Y).
So the difference S(X)-S(Y) either does not change with the raising of X,
or decreases.
This fact shows that raising X does not change the winner from X to Y.
The method satisfies mono-raise!
(But check me on this!)
El jue., 20 de ene. de 2022 4:22 a. m., Kristofer Munsterhjelm <
km_elmet@t-online.de> escribió:
On 20.01.2022 12:26, Daniel Carrera wrote:
Ha! So I want to look for methods similar to Smith,X. Hmm... let me try:
- Every candidate has a 1-1 pairwise match against every other
candidate.
-
The candidates with the most won matches are "finalists".
-
The finalist with the greatest margin of victory against any other
candidate is elected.
So step (2) basically gives the Copeland set. The whole method should be
"Copeland,X" where "X" is the method "elect the candidate with the
largest victory". Since X must be a monotonic method, would it follow
that Copeland,X is monotonic too? Conversely, if step (3) had said "...
against any other finalist" that would have created "Copeland//X" and
it would probably be non-monotonic. Does that sound right?
This is interesting because something like Smith,X or Copeland,X as in
my example allows you to consider methods X that you would normally have
considered too simple to be interesting. This might be a good way to
design good methods (e.g. Smith-efficient and monotone) without them
being very complicated.
Yes. I forgot to mention two things, though:
-
Borda is particularly nice in that Copeland//Borda is monotone. This
happens because you can infer the Borda score from the pairwise matrix,
and the remaining pairwise matrix entries don't change when you remove
candidates. So although as a rule X//Y is nonmonotone, some monotone
pairwise-based set restrictions of Borda (in particular Smith and
Copeland) will be monotone. However, Borda is unusually susceptible to
strategy, which is a problem, and neither Borda nor Copeland are
cloneproof. -
X//Y methods give up monotonicity, but they get something in return:
if the X set itself is independent of candidates not in it (i.e. you
can't make the X set smaller or larger by introducing candidates not in
it), then X//Y is independent of X-dominated candidates. E.g. in
Smith//Plurality it doesn't matter if there's vote-splitting among the
losers as long as there's no vote-splitting in the Smith set itself. But
in Smith,Plurality, losers outside the Smith set may draw votes away
from the Smith set, making someone else inside it win.
(Note that Copeland fails the "independence of candidates not in it"
criterion. So Copeland//Borda doesn't get you independence of
Copeland-dominated candidates -- but it does get you independence of
Smith-dominated candidates.)
-km
Election-Methods mailing list - see https://electorama.com/em for list
info