smith/schwartz/landau
Hi, as a side project I’m writing a scala script that determines the smith set and schwartz set from ranked ballots. (I’m not currently interested in implementing any tiebreakers/completion algorithms. Just condorcet winner, smith set, schwartz set.)
I’m uncertain about my implementations for smith and schwartz. I followed some pseudocode algorithms I found online but I’m not sure they’re quite right. The schwartz algorithm I found looks more like how landau is described. Part of my challenge is also that I’m trying to do them functional-style without mutable variables like loops and counters.
Could someone post an example of a simple collection of ballots where the smith set, schwartz set, and landau sets are all different?
Also if we have a collection of ballot example somewhere that show odd examples of condorcet winner, smith set, schwartz set, etc, and what the count should yield, I’d love to collect them because they’d make a good test suite.
Thanks,
Curt
On 03/07/2018 04:48 AM, Curt wrote:
Hi, as a side project I’m writing a scala script that determines the smith set and schwartz set from ranked ballots. (I’m not currently interested in implementing any tiebreakers/completion algorithms. Just condorcet winner, smith set, schwartz set.)
I’m uncertain about my implementations for smith and schwartz. I followed some pseudocode algorithms I found online but I’m not sure they’re quite right. The schwartz algorithm I found looks more like how landau is described. Part of my challenge is also that I’m trying to do them functional-style without mutable variables like loops and counters.
Could someone post an example of a simple collection of ballots where the smith set, schwartz set, and landau sets are all different?
Also if we have a collection of ballot example somewhere that show odd examples of condorcet winner, smith set, schwartz set, etc, and what the count should yield, I’d love to collect them because they’d make a good test suite.
A partial answer: The Wikipedia article on the Schwartz set,
https://en.wikipedia.org/wiki/Schwartz_set, gives an example where the
Schwartz set is a single candidate but the Smith set consists of every
candidate.
Sets like Schwartz and Smith are usually maximal elements of a partially
ordered set.
https://wiki.electorama.com/wiki/Maximal_elements_algorithms gives more
information about this, as well as how to use Floyd-Warshall or
Kosaraju's algorithms to find maximal elements.
In graph theory terms, we're interested in the smallest set so that
there's a cycle from any candidate in that set to any other candidate in
that set, according to a relation (X beats Y pairwise for the Schwartz
set, X beats or ties Y pairwise for the Smith set). Any strongly
connected components algorithm should work, if given a directed graph
where there's an edge from X to Y iff X is ranked ahead of Y according
to the relation being used.
https://stackoverflow.com/a/15905986 links to a paper detailing
(somewhat complex) Haskell code for Kosaraju's algorithm, and the
accepted answer has Scala code for Tarjan's algorithm (which also finds
strongly connected components). I imagine that Floyd-Warshall could be
implemented relatively simply in a functional style by just using the
dynamic programming equation that drives it, and memoization.
The wiki page https://wiki.electorama.com/wiki/Maximal_elements_algorithms https://wiki.electorama.com/wiki/Maximal_elements_algorithms confused me because it says (as you paraphrased) “X beats Y pairwise for the Schwartz set, X beat or ties Y pairwise for the Smith Set”.
Isn’t that backwards? I thought the Smith set was the smallest set of candidates who all defeat candidates outside of the set (as wikipedia says), while Schwartz set was the one that allowed ties.
On Mar 8, 2018, at 11:28 AM, Kristofer Munsterhjelm km_elmet@t-online.de wrote:
On 03/07/2018 04:48 AM, Curt wrote:
Sets like Schwartz and Smith are usually maximal elements of a partially ordered set. https://wiki.electorama.com/wiki/Maximal_elements_algorithms gives more information about this, as well as how to use Floyd-Warshall or Kosaraju's algorithms to find maximal elements.
In graph theory terms, we're interested in the smallest set so that there's a cycle from any candidate in that set to any other candidate in that set, according to a relation (X beats Y pairwise for the Schwartz set, X beats or ties Y pairwise for the Smith set). Any strongly connected components algorithm should work, if given a directed graph where there's an edge from X to Y iff X is ranked ahead of Y according to the relation being used.
On 03/09/2018 05:35 AM, Curt wrote:
The wiki page
https://wiki.electorama.com/wiki/Maximal_elements_algorithms confused me
because it says (as you paraphrased) “X beats Y pairwise for the
Schwartz set, X beat or ties Y pairwise for the Smith Set”.
Isn’t that backwards? I thought the Smith set was the smallest set of
candidates who all defeat candidates outside of the set (as wikipedia
says), while Schwartz set was the one that allowed ties.
Suppose the relation is beats-or-ties. Then that implies that for all
pairs of candidates X, Y inside the Smith set, there's a path from X to
Y where X beats or ties A who beats or ties B who beats or ties... who
beats or ties Y.
Then all candidates in the Smith set must beat every candidate outside.
Suppose that this were not true; that X is in the Smith set and Z is
not, but X doesn't beat Z. Then there are two possibilities. Either X
ties Z, or Z beats X.
If X ties Z, then Z is in the Smith set because there's a path from Z
(through X) to everyone else in the Smith set. If Z beats X, then
there's similarly also a path from Z to everyone else in the Smith set.
Thus Z must be in the Smith set as well.
For the Schwartz set, there's a beat (no tie) path from any X to any Y
in the Schwartz set. Because you can no longer bridge a gap using ties,
the Schwartz set is a subset of the Smith set. So the Schwartz set is
never larger than the Smith set.
Since there's a path from any X in the Schwartz set to any Y also in it
using only the beats relation, every member in the Schwartz set must
beat or tie everyone outside.
So the confusion is, I think, about whether you're on the outside
looking in or on the inside looking at others on the inside. Every Smith
set member beats everyone outside, but the Smith set consists of
candidates with beat-or-tie paths to each other. Every Schwartz set
member beats or ties everyone outside, but the Schwartz set consists of
candidates with beat-relation paths to each other.
I think Schwartz members don't actually have to have beatpaths to each other though. Suppose there are five candidates. A>B>C>A cycle. E is the Condorcet loser. All of D's contests are ties except for D>E. Then the Schwartz set is {A,B,C,D}.
Kevin
De : Kristofer Munsterhjelm <km_elmet@t-online.de>
À : Curt accounts@museworld.com; election-methods@lists.electorama.com
Envoyé le : Vendredi 9 mars 2018 6h22
Objet : Re: [EM] smith/schwartz/landau
On 03/09/2018 05:35 AM, Curt wrote:
The wiki page
https://wiki.electorama.com/wiki/Maximal_elements_algorithms confused me
because it says (as you paraphrased) “X beats Y pairwise for the
Schwartz set, X beat or ties Y pairwise for the Smith Set”.
Isn’t that backwards? I thought the Smith set was the smallest set of
candidates who all defeat candidates outside of the set (as wikipedia
says), while Schwartz set was the one that allowed ties.
Suppose the relation is beats-or-ties. Then that implies that for all
pairs of candidates X, Y inside the Smith set, there's a path from X to
Y where X beats or ties A who beats or ties B who beats or ties... who
beats or ties Y.
Then all candidates in the Smith set must beat every candidate outside.
Suppose that this were not true; that X is in the Smith set and Z is
not, but X doesn't beat Z. Then there are two possibilities. Either X
ties Z, or Z beats X.
If X ties Z, then Z is in the Smith set because there's a path from Z
(through X) to everyone else in the Smith set. If Z beats X, then
there's similarly also a path from Z to everyone else in the Smith set.
Thus Z must be in the Smith set as well.
For the Schwartz set, there's a beat (no tie) path from any X to any Y
in the Schwartz set. Because you can no longer bridge a gap using ties,
the Schwartz set is a subset of the Smith set. So the Schwartz set is
never larger than the Smith set.
Since there's a path from any X in the Schwartz set to any Y also in it
using only the beats relation, every member in the Schwartz set must
beat or tie everyone outside.
So the confusion is, I think, about whether you're on the outside
looking in or on the inside looking at others on the inside. Every Smith
set member beats everyone outside, but the Smith set consists of
candidates with beat-or-tie paths to each other. Every Schwartz set
member beats or ties everyone outside, but the Schwartz set consists of
candidates with beat-relation paths to each other.
Election-Methods mailing list - see http://electorama.com/em for list info
On 03/09/2018 02:04 PM, Kevin Venzke wrote:
I think Schwartz members don't actually have to have beatpaths to each
other though. Suppose there are five candidates. A>B>C>A cycle. E is the
Condorcet loser. All of D's contests are ties except for D>E. Then the
Schwartz set is {A,B,C,D}.
Ah, right, for the Schwartz set there may be disjoint smallest sets of
candidates having beatpaths to everybody else inside that set. The
smaller sets are called Schwartz set components, and the Schwartz set
itself is the union of all those disjoint sets.
I think that strictly speaking holds for Smith, too, but the use of ties
to bridge gaps means there won't be more than one such smallest set
(unless you use a pairwise matrix setup that allows for, say, pairwise
contests that are entirely unknown, so you neither have A beats B, A
ties B, or B beats A).
You also gave the following description in a private reply:
I like to define the Schwartz set as every candidate X who has a
beatpath to every other candidate Y who has a beatpath to X.
That works for both Schwartz and Smith with respectively the beats
relation and the beats-or-ties relation. That is,
X is in the set if
for every other Y where Y has a path to X using the relation,
X also has a path to Y using the relation.
D above is in the Schwartz set because nobody has a path of pairwise
defeats to D, and D trivially has a path of pairwise defeats to every
candidate in the empty set.
Thanks to Kristofer for explaining my “beats” vs “beats or ties” confusion.
For anyone interested, here is the software package of me using scala to compute Smith and Schwartz sets. It’s not super-advanced, but it at least avoids mutable variables. In the future I may try to use more expressive FP concepts, and pull in one of the faster Schwartz algorithms. I don’t entirely understand the graph algorithms yet.
https://github.com/tunesmith/condorcet-counter https://github.com/tunesmith/condorcet-counter
I opined a bit in the README but that’s not really the point of the project. I just wanted an easy way to identify Smith and Schwartz sets for myself.
Curt
On Mar 9, 2018, at 7:41 AM, Kristofer Munsterhjelm km_elmet@t-online.de wrote:
On 03/09/2018 02:04 PM, Kevin Venzke wrote:
I think Schwartz members don't actually have to have beatpaths to each other though. Suppose there are five candidates. A>B>C>A cycle. E is the Condorcet loser. All of D's contests are ties except for D>E. Then the Schwartz set is {A,B,C,D}.
Ah, right, for the Schwartz set there may be disjoint smallest sets of candidates having beatpaths to everybody else inside that set. The smaller sets are called Schwartz set components, and the Schwartz set itself is the union of all those disjoint sets.
I think that strictly speaking holds for Smith, too, but the use of ties to bridge gaps means there won't be more than one such smallest set (unless you use a pairwise matrix setup that allows for, say, pairwise contests that are entirely unknown, so you neither have A beats B, A ties B, or B beats A).
You also gave the following description in a private reply:
I like to define the Schwartz set as every candidate X who has a
beatpath to every other candidate Y who has a beatpath to X.
That works for both Schwartz and Smith with respectively the beats relation and the beats-or-ties relation. That is,
X is in the set if
for every other Y where Y has a path to X using the relation,
X also has a path to Y using the relation.
D above is in the Schwartz set because nobody has a path of pairwise defeats to D, and D trivially has a path of pairwise defeats to every candidate in the empty set.
---------------------------- Original Message ----------------------------
Subject: Re: [EM] smith/schwartz/landau
From: "Curt" accounts@museworld.com
Date: Fri, March 23, 2018 4:33 pm
To: "election-methods@lists.electorama.com" election-methods@lists.electorama.com
Thanks to Kristofer for explaining my “beats” vs “beats or ties” confusion.
For anyone interested, here is the software package of me using scala to compute Smith and Schwartz sets. It’s not super-advanced, but it at least avoids mutable variables. In the future I may try to use more expressive FP concepts, and pull in one of the faster Schwartz algorithms. I
don’t entirely understand the graph algorithms yet.
I opined a bit in the README but that’s not really the point of the project. I just wanted an easy way to identify Smith and Schwartz sets for myself.
�
to wit: "It's this author's view that a
method should only be called a Condorcet if it is limited to identifying the Smith Set,"
seems to me that your view is that the current definition of "Condorcet-compliant-method" should be changed.� so is Tideman Ranked-Pairs or Schulze Beat-Path methods not
"Condorcet methods"?
--
r b-j� � � � � � � � � � � � �rbj@audioimagination.com
"Imagination is more important than knowledge."
�
�
�
�
On Mar 23, 2018, at 6:36 PM, robert bristow-johnson rbj@audioimagination.com wrote:
---------------------------- Original Message ----------------------------
From: "Curt" accounts@museworld.com
https://github.com/tunesmith/condorcet-counter https://github.com/tunesmith/condorcet-counter
I opined a bit in the README but that’s not really the point of the project. I just wanted an easy way to identify Smith and Schwartz sets for myself.
to wit: "It's this author's view that a method should only be called a Condorcet if it is limited to identifying the Smith Set,"
seems to me that your view is that the current definition of "Condorcet-compliant-method" should be changed. so is Tideman Ranked-Pairs or Schulze Beat-Path methods not "Condorcet methods"?
Yes, that is my view. They should not be called “Condorcet Methods”, because they are not guaranteed to select the candidate(s) that would defeat all other candidates.
There is a clear difference between a “Condorcet Method” that finds a Condorcet Winner or Smith Set, and a “tiebreaking" method that tries to pick a single winner from a multi-candidate Smith Set. The latter fails criteria that the former does not. I don’t know what we should call these tiebreaking algorithms - perhaps they are not quite “tiebreaking” methods since a cycle is not exactly a tie. But it isn’t appropriate to call them “Completion” methods either as that implies something that it isn’t.
The actual objection I have is that when both are described as “Condorcet Methods”, then it’s too easy in the literature (and the blogs, and the wikipedia articles, particularly from Condorcet detractors) to paint with a broad brush and argue that all Condorcet Methods are flawed in some manner, same as how all other methods are “unfair” in some way, which ultimately does a disservice to the Condorcet Method. An election that has a Condorcet Winner is not unfair in those ways, compared to something like IRV or Plurality or Top-Two.
It might worth a survey of what a Smith Set actually means. I believe it signifies something valuable about the electorate, beyond just an indication that the election is “incomplete” and that we should apply some algorithm to divine a single winner from it.
(Regarding the typo in my README - I meant “should only be called a Condorcet Method if it is…”)
Curt
---------------------------- Original Message ----------------------------
Subject: Re: [EM] smith/schwartz/landau
From: "Curt" accounts@museworld.com
Date: Sat, March 24, 2018 12:20 am
To: "election-methods@lists.electorama.com" election-methods@lists.electorama.com
On Mar 23, 2018, at 6:36 PM, robert bristow-johnson rbj@audioimagination.com wrote:
---------------------------- Original Message ----------------------------
From: "Curt" accounts@museworld.com
I opined a bit in the README but that’s not really the point of the project. I just wanted an easy way to identify Smith and Schwartz sets for myself.
to wit: "It's this author's view that a method should only be called a Condorcet if it is limited to identifying the Smith Set,"
seems to me that your view is that the current definition of "Condorcet-compliant-method" should be changed. so is Tideman Ranked-Pairs or Schulze Beat-Path methods not "Condorcet methods"?
Yes, that is my view. They should not be called “Condorcet Methods”, because they are not guaranteed to select the candidate(s) that would defeat all other candidates.
There is a clear difference between a “Condorcet Method” that finds a Condorcet Winner or Smith Set, and a “tiebreaking" method that tries to pick a single winner from a multi-candidate Smith Set. The latter fails criteria that the former does not. I don’t know what
we should call these tiebreaking algorithms - perhaps they are not quite “tiebreaking” methods since a cycle is not exactly a tie. But it isn’t appropriate to call them “Completion” methods either as that implies something that it isn’t.
The actual objection I have is that when both are described as “Condorcet Methods”, then it’s too easy in the literature (and the blogs, and the wikipedia articles, particularly from Condorcet detractors) to paint with a broad brush and argue that all Condorcet Methods are
flawed in some manner, same as how all other methods are “unfair” in some way, which ultimately does a disservice to the Condorcet Method. An election that has a Condorcet Winner is not unfair in those ways, compared to something like IRV or Plurality or Top-Two.
It might worth a survey of what a Smith Set actually means. I believe it signifies something valuable about the electorate, beyond just an indication that the election is “incomplete” and that we should apply some algorithm to divine a single winner from it.
well, arguing
about the semantics is one thing, arguing about theory or ideals is another, and arguing about practice is yet another.
so whether you call it "Condorcet-compliant" or call it a turnip, there are ranked-ballot tabulation procedures that are 1. Decisive (they will elect someone) and 2. If a Condorcet Winner exists, the procedure will elect the CW.� we gotta call that something and
"Condorcet-compliant method" is more descriptive than "turnip".� And it serves a purpose.� It separates both practice and "theory and ideals" of these aforementioned procedures from other ranked-ballot systems such as IRV, Borda, or Bucklin.
both Ranked-Pairs and Schulze are fundamentally not defined as some post algorithm to divine a single winner from a Smith set that is larger than 1.� They are well-defined procedures, in their own right, that happen to elect the CW if a CW exists.� IRV may elect the CW if one
exists, but of course we know that hasn't always been the case in practice.� They are not "tiebreaking" a Smith set.� they are not a procedure to be applied after it is discovered no single CW exists.� they are procedures that will elect a candidate by the same rules
whether a CW exists or not.� But the candidate elected will be the CW if one exists. So the only practical difference between these turnips is what their outcome might be if there was a Smith set greater than 3 and some weird voting alignment.
So we need a term to draw the line between Ranked-Pairs or Schulze or BTR-IRV on one side and Bucklin, Borda, or IRV on the other.� What semantic would you suggest?
the salient difference is simply what happened in my town 9 years ago: A candidate for mayor was elected to office when the voters in the city unambiguously marked their ballots that they preferred a different specific candidate.� that is the problem with any non-turnip method.�
it's the converse of who a CW is.� if everyone's vote carries the same weight (this is the "one-person-one-vote" principle), if Candidate A is preferred by more voters than Candidate B, what possible reason in the world should the less-preferred candidate be tapped to serve than the
more-preferred candidate?� especially when no other candidate is preferred over the more-preferred candidate?
When at all possible (because it isn't always, at least in theory), if more voters mark their ballots preferring Candidate A over Candidate B than the number of voters marking their ballots to the contrary, then Candidate B is not elected.� What semantic should be used for the previous
sentence?
--
r b-j� � � � � � � � � � � � �rbj@audioimagination.com
"Imagination is more important than knowledge."
�
�
�
�