Talk:Schwartz set

From Wikipedia, the free encyclopedia

Contents 1 Weak Condorcet winners 2 Example given is incorrect 3 Kosaraju's algorithm 4 Schwarz criterion

[edit] Weak Condorcet winners

The article says: "If there are any weak Condorcet winners in the election, then the Schwartz set consists of exactly all of them." This statement is incorrect. Example:

• A pairwise beats B.
• B pairwise beats C.
• C pairwise beats A.
• A pairwise ties with D.
• B pairwise ties with D.
• C pairwise ties with D.

Only candidate D is a weak Condorcet winner. However, the Schwartz set is { A, B, C, D }. Markus Schulze 20:07, 17 January 2006 (UTC)

You're right. I'll withdraw the statement. -- Dissident (Talk) 19:24, 18 January 2006 (UTC)

[edit] Example given is incorrect

  " 3 voters preferring candidate A to B to C
    1 voter preferring candidate B to C to A
    1 voter preferring candidate C to A to B
    1 voter preferring candidate C to B to A
    
    then we have A pairwise beating B, B pairwise beating C, and A tying with C in their pairwise comparison, making A the only member of the Schwartz set, 
    while the Smith set on the other hand consists of all the candidates"

-

This statement is doubly inaccurate. Firstly, B does not beat C. B is preferrred twice to C, and C is likewise preferred twice to B. They tie. To see this more clearly (and this type of illustration should be used in whatever example is eventually decided upon):

Preference Tally (The value in each cell denotes how many voters prefer the candidate in the cell's column to the candidate in the cells row):

         A   B   C
      A| - | 4 | 3 |
      B| 2 | - | 2 |
      C| 3 | 2 | - |
      

Preference Result (In each cell 1 and 0 represent the truth value of the statement that the candidate in the associated column beats the candidate in the associated row. 1 indicates that it is true, 0 indicates that the contrary is true. T indicates that they tie.):

         A   B   C
      A| - | 1 | T |
      B| 0 | - | T |
      C| T | T | - |

Clearly A and C Tie, B and C tie, and A beats B. So A could not be the "only member of the Schwartz set", because A ties with C, and A and C are both unbeaten by any other candidate. Even so, the example still appears to be good, provided that the summarizing statement is changed to reflect reality and that the preference tally and preference result tables are added, so as to prevent the reader from having to tally the results himself.

--Comiscuous

You are mistaken. The example clearly shows that 4 people prefer B to C and only 2 people prefer C to B. -- Dissident (Talk) 01:56, 25 July 2006 (UTC)

Dissident, You are correct. My mistake. I still think the two corrcted tallies should be shown on the page. Here they are, let me know if I mess anything up:

         A   B   C
      A| - | 2 | 3 |
      B| 4 | - | 2 |
      C| 3 | 4 | - |

         A   B   C
      A| - | 0 | T |
      B| 1 | - | 0 |
      C| T | 1 | - |

--Comiscuous 22:50, 24 September 2006 (UTC) (Talk)

[edit] Kosaraju's algorithm

The article says:

The Schwartz set can be calculated using a version of Kosaraju's algorithm in time Θ(n²).

I question the validity of this statement because of two reasons.

First:

Kosaraju's algorithm finds the "strongly connected components" of a directed graph. But the Schwartz set is not identical to the "strongly connected components", but to the "communicating classes" of a directed graph.

A strongly connected component SCC is a set of vertices with the following property:

1. If vertex A is in SCC and vertex B is in SCC \ {A}, then there is a directed path from vertex A to vertex B, that consists only of vertices in SCC, and a directed path from vertex B to vertex A, that consists only of vertices in SCC.

On the other side, a communicating class CC is a set of vertices with the following properties:

1. If vertex A is in CC and vertex B is in CC \ {A}, then there is a directed path from vertex A to vertex B and a directed path from vertex B to vertex A.
2. If vertex A is in CC and there is a directed path from vertex B to vertex A, then also vertex B is in CC.

Second:

Kosaraju's algorithm uses DFS Θ(n) times. DFS has a runtime of Θ(n²), so that the total runtime of Kosaraju's algorithm is Θ(n³).

Markus Schulze 15:18, 3 November 2006 (UTC)

Thanks for looking at this. It still appears to me that the statement is valid and deserves to be reinstated.

Of the first concern, given these definitions, an SCC is maximal (by set inclusion) iff it is a CC. Kosaraju's algorithm finds the maximal SCC's for a graph. Note that there may be some confusion because of differing terminology. Some authors would consider the first definition to be for a "strongly connected set" of vertices, while reserving "strongly connected component" to refer only to a maximal (by set inclusion) strongly connected set. This use of terminology is motivated by the fact that the maximal (by set inclusion) strongly connected sets of a graph partition the set of vertices.

Of the second concern, again the discussion depends on definitions, but either way, the conclusion that Kosaraju's algorithm requires Θ(n³) time is wrong. If the terminology used limits a single DFS to only identify a single depth-first tree in the graph, then the premise is correct for worst cases. However, there are several ways to informally illuminate why Kosaraju's algorithm still only takes Θ(n²) time:

1. The estimates of Θ(n) repetitions of a Θ(n²) DFS are worst case, but the worst cases of the two never coincide. In fact they are complementary: The longer any DFS takes, the fewer repetitions have to be made and/or the faster the other repetitions will run.
2. For each of the two passes, every one of the n vertices is visited at most n times. Each first-of-a-pass visit is done in Θ(n) time, and all other visits are done in constant time.
3. Each first-of-a-pass visit to a vertex is done in Θ(n) because each of the n potential or actual outbound edges is considered (and traversed if the outbound edge exists) only 1 time in constant time.

There can be some confusion because of terminology, because some authors consider a DFS of a graph to include the repetitions needed to create a depth-first forest of all vertices. That more extensive variety of DFS still runs in Θ(n²) time for the reasons mentioned above. In this sense, Kosaraju's algorithm only runs DFS twice.

Unless I'm misunderstanding the concerns being raised, these issues are addressed in more detail and fairly authoritatively in the Introduction to Algorithms book listed in the references of the Wikipedia entry for Kosaraju's algorithm.

DCary 23:34, 7 November 2006 (UTC)

Dear David,

you wrote: "An SCC is maximal (by set inclusion) iff it is a CC."

Example:

Candidate A pairwise beats candidate B.

Candidate A pairwise beats candidate C.

Candidate A pairwise beats candidate D.

Candidate B pairwise beats candidate C.

Candidate C pairwise beats candidate D.

Candidate D pairwise beats candidate B.

The maximum SCC is {B, C, D}. However, {B, C, D} is not a CC.

Markus Schulze 13:28, 3 December 2006 (UTC)

I did misunderstand the consequences of the given definition for a communicating class and as a result mischaracterized the relationship it has to a maximal (by set inclusion) SCC. The rest of my comments are not effected by that error though.

I'll see what I can do to develop a clearer and better referenced version of the deleted material.

DCary 19:07, 10 December 2006 (UTC)

[edit] Schwarz criterion

Are Schwartz sets related to Schwarz criterion ? John Vandenberg 03:35, 8 November 2006 (UTC)

Schwartz set and Schwartz criterion are closely related, but those two are related to the Schwarz criterion only to the extent they are named after two people who have similarly spelled and perhaps indistinquishably pronounced last names. DCary 22:40, 8 November 2006 (UTC)

Thanks. I think it is very confusing that Schwartz criterion redirects to Schwarz criterion, and as a result the Schwarz criterion article has a general comment at the top trying to explain why someone looking for Schwartz criterion has arrived at the page for Schwarz criterion.

To simplify things, I propose the following:

1. Schwartz criterion should redirect to Schwartz set.
2. the top of Schwarz criterion should state:
   For a similar term in voting theory, see Schwartz set.
3. the top of Schwartz set should state:
   For a similar term in statistics, see Schwarz criterion.

Any objections to those changes? John Vandenberg 01:11, 9 November 2006 (UTC)

Good idea. Some things to consider:

• With Schwartz criterion redirected to Schwartz set, it might be good to have the disambiguation link at the top of Schwarz criterion point to Schwartz criterion and let the redirect do its work. That makes it more apparent to the reader what the similar term is.
• For the disambiguation link at the top of Schwartz set, it might be good to be more explicit about what term Schwarz criterion is similar to. If the reader got to the page directly, rather than through the Schwartz criterion redirect, it would not be clear what the link is disambiguating. Instead, you might try:

or the style currently in use on the Schwarz criterion page, but using a standard template:

If the Schwarz criterion page gets moved to the Bayesian information criterion page, the last method might be especially useful on that page.

-- DCary 19:40, 9 November 2006 (UTC)