Talk:Smith set

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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)

[edit] 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)