Talk:Smith set

Mistakes, May 2006

The article currently begins:

In voting systems, the Smith set is the smallest set of candidates in a particular election such that each member beats every other candidate outside the set in a pairwise election.

The smallest such set is clearly the empty set. Does the writer mean the smallest non-empty set? The largest non-universal set? What?

The article also states that

If we contract each of these cliques to a single vertex representing a set of candidates, we have a directed acyclic graph, which necessarily has a vertex with zero in-degree, and the set of candidates this vertex corresponds to is the Smith set.

The antecedent of "this vertex" is not clear. After all, it is quite possible for a directed acyclic graph to have more than one vertex with zero in-degree. Can an election have more than one Smith set? If not, then we need either an algorithm for deciding which vertex corresponds to the Smith set, or a proof that this particular graph has only one vertex with zero in-degree. Saying it's directed and acyclic is not enough.

I hope someone can clean up this article; I know just enough about the subject to know it's wrong, not enough to fix it. :) --Quuxplusone 00:06, 9 May 2006 (UTC)

Ah, I figured out what was intended. Suppose we have two sources (vertices with zero in-degree). These sources are necessarily part of the same clique, and should be contracted together. This could happen to everything (in which case the DAG is just a point), which corresponds to the case that the Smith set is the set of all candidates (A>B>C>A, for example). I don't think I'll return that the article, though; that's more confusing than it's worth. CRGreathouse 22:34, 21 July 2006 (UTC)

It should be the smallest non-empty set. The last paragraph that tries to "clearly" demonstrate that the Smith set always exists by showing how to construct it is wrong, it is unreferenced, wasn't first properly reviewed, and certainly isn't clear. But it is fixable. For now I'm deleting it, but will come back with fixes in 3-6 weeks with a revision for that content. --DCary 15:50, 3 July 2006 (UTC)

Ok, 3-4 months, not weeks, later I finally made my changes. The paragraph I deleted earlier at least triggered a look at using Kosaraju's algorithm to calculate both the Smith and Schwartz sets faster than Floyd-Warshall.

With this change I deleted the problematic paragraph on clones. It had problems with accuracy ("2 members is impossible"), vagueness and/or consistency ("clone-like (strictly worse than one of the other 3)"), and NPOV ("appear deceptively large"). Someone may want to try to fix that paragraph, but it didn't seem worthwhile to me. DCary 21:17, 18 October 2006 (UTC)

Smith criterion vs Smith set

The Smith criterion article has essentially all of the information here, and a fair amount not in this article. I think we should delete this article and redirect to the other. CRGreathouse 03:55, 20 July 2006 (UTC)

I plan to add some material about the Smith set, and also about the Schwartz set in its article. It is taking me longer than I had expected to get it prepared. Now I'm estimating another 1-3 months. It might be worthwhile to defer the decision about deleting/merging this article until then. DCary 22:02, 20 July 2006 (UTC)

I would have thought it better to add it all in one place, since I can't imagine the conceptual difference between Smith set and Smith criterion, but very well. I withdraw my suggestion until that time. In any case, Schwartz set could certainly use some work! Thanks. CRGreathouse 23:35, 20 July 2006 (UTC)

Thanks for waiting. I've added my material and cleaned up the article for what I think would be a good separate article. If we keep them separate, some of the redundancy in the Smith Criterion article could be cleaned out. I'm neutral on merging this into the Smith Criterion. I see some value in keeping the two separate, one focused on the definition and structure of the Smith set, the other looking at the interrelation of the Smith criterion to other criterion. But I also recognize some value to merging this into the Smith criterion article. I'll volunteer to do the merge if there is still some interest in that and no objections otherwise. Or if someone else wants to do it, go for it. DCary 21:17, 18 October 2006 (UTC)

Original terminology

What did Smith call the Smith set originally (say, in his 1973 paper)? CRGreathouse 22:10, 21 July 2006 (UTC)

Heh, that's funny -- Smith's paper doesn't actually give the so-called "Smith criterion" at all, but a stronger condition he calls the "Condorcet criterion" (p. 1038, although he acknowledges that it's a generalization of Condorcet's original). CRGreathouse (talk | contribs) 04:06, 16 August 2006 (UTC)

As far as I know, the terms "Smith set" and "Schwartz set" have been introduced by Fishburn in his paper "Condorcet Social Choice Functions" (SIAM Journal on Applied Mathematics, vol. 33, p. 469--489, 1977). Markus Schulze 13:10, 16 August 2006 (UTC)

Thanks! I actually have that one, but I haven't gotten around to reading it yet. CRGreathouse (talk | contribs) 16:22, 17 August 2006 (UTC)

OK, I read the paper. Fishburn does use the term (actually "Smith's Condorcet Principle"), but he uses it in the same strong sense as Smith. CRGreathouse (talk | contribs) 04:51, 18 August 2006 (UTC)

That will be great in the article. --Homunq 22:53, 18 August 2006 (UTC)

Article omissions

The article uses the jargon term "beat" without defining it, and never mentions majorities. It neglects the synonyms "top cycle" and "GETCHA set" used in some of the literature of social choice theory. The article doesn't include any helpful examples. (I suggest a 3-candidate example in which Instant Runoff defeats a Condorcet winner and a 4-candidate example in which Minmax defeats the entire Smith set.) The article could compare the Smith set to other subsets of the Smith set besides the Schwartz set, such as "uncovered" sets and the (Jeffrey) Banks Set (which is the set of alternatives that can win assuming strategically sophisticated voting using the sequential pairwise elimination voting method of Robert's Rules) as in the paper The Banks Set and the Uncovered Set in Budget Allocation Problems by Dutta, Jackson and Le Breton. And it would help if the article distinguishes between the sincere Smith set and the voted Smith set, since electing a candidate in the sincere Smith set is considered more desirable than electing a candidate in a set manipulated by strategic voting. SEppley (talk) 15:36, 22 November 2012 (UTC)

Even Google can't tell you what GETCHA and GOCHA stand for. John Moser (talk) 13:39, 28 August 2018 (UTC)

Algorithms

The article has always mentioned some (graph-theoretic?) algorithms which can be used to find the Smith set, all with quadratic or cubic work factors. Recently GreekApple123 added a direct algorithm starting from the Copeland score, whose work factor so far as I can see is quadratic. I made GreekApple’s account more precise, relabelling the candidates to make the need for a sorting step explicit; and I relegated mention of the alternatives, which don’t seem to serve any real purpose.

At the same time, boldly/rashly, I deleted the short section on ‘alternative formulations’ since I couldn’t see the interest of it. Maybe it’s linked from somewhere else... but I hope I haven’t introduced any errors. Colin.champion (talk) 20:08, 1 March 2021 (UTC)

I put in a snippet of rather telegraphic C code to illustrate calculation of the Smith set by the direct quadratic algorithm. It’s not unknown for programmers to make errors in this sort of thing. Here’s a simple-minded equivalent (cubic rather than quadratic in time, but does anyone care?).

 int smith(int **r,int n)
 { int i,j,m,all0 ; 
   for(m=1;m<n;m++)
   { for(all0=1,i=m;i<n;i++) for(j=0;j<m;j++) if(r[i][j]) all0 = 0 ; 
     if(all0) return m ; 
   }
   return n ; 
 }

I ran a validation comparing results of the two versions on 100 million randomly generated results matrices, which took 20s; there were no discrepancies. Colin.champion (talk) 14:43, 6 March 2021 (UTC)

Algorithms again

@Bluefoxicy: has added a ‘hand algorithm’ to the ‘Copeland score algorithm’ previously present. (I’m afraid I missed this change at the time through not receiving a notification.) I can see his reasoning but I think his addition is misleading: he has provided a vaguer and more digestible description of a slight variant of the Copeland method rather than a separate algorithm.

The algorithm works because of a property proved earlier in the article: dominating sets are nested by Copeland score. It follows that by adjusting the Copeland threshold you can work through the nested sets in increasing order of size until you come to a dominating set; and this set is necessarily the Smith set. There’s a nice description at the top of p 10 of Darlington’s Are Condorcet and minimax voting systems the best? (v8).

You can avoid mentioning the Copeland score by using other statistics which work as well; but unless you prove the necessary property, you’ve reduced the intelligibility of the algorithm. And you can avoid sorting an array by scanning it repeatedly rather than working through it once sequentially; but this is no real gain either.

Now it seems to me that the ‘Copeland algorithm’ goes into so much detail that it conceals the simplicity of the underlying idea – and still doesn’t make clear the connection with the logical properties proven earlier. I wanted to go into detail (a) so that the reader would feel confident that he or she could implement the algorithm by hand or software, and (b) to make its quadratic cost explicit to avoid the need to discuss alternatives on efficiency grounds.

So I suggest that rather than offering two supposedly different algorithms, the Copeland algorithm should be preceded by a short description explaining the principles, and saying that a precise algorithmic specification follows. And I propose deleting reference to fancy algorithms such as Floyd-Marshall which don’t add anything. Colin.champion (talk) 08:43, 25 June 2021 (UTC)

I have done this. If my explanation is too short, by all means amplify it. Colin.champion (talk) 09:50, 1 July 2021 (UTC)

Merge into Smith set

"Smith set, but without counting ties" doesn't seem to be notable enough to deserve its own wiki article. –Maximum Limelihood Estimator 03:38, 23 April 2024 (UTC)