This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||
|
The article currently begins:
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
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)
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)
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)
What did Smith call the Smith set originally (say, in his 1973 paper)? CRGreathouse 22:10, 21 July 2006 (UTC)
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)
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)
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 ; }
@ 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)
"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)