[EM] Re: Automatic Criterion Checking

[Jobst Heitzig]

Dear Rob!

You wrote:
> Jobst, could you post mathematical definitions and intuitive
> explanations for each of these sets?

The sets I mentioned are all defined in the wonderful book by Laslier on
"Tournament Solutions and Majority Voting".

Here are some definitions as I recall them. We assume that for each pair
of options X,Y, either X>Y or Y>X.

Smith Set = Top Cycle = Schwartz Set = smallest set such that everything
inside beats everything outside.

Uncovered Set = set of uncovered candidates = set of candidates which
have beatpaths of length at most 2 to every other candidate. In this, A
covers B iff A>B and, for all C, C>A implies C>B and B>C implies A>C.
The covering relation is a strict (partial) ordering.

Banks Set = all candidates for which there is a maximal chain of defeats
having the candidate on top. A chain is a sequence A1>A2>...>Ak such
that also Ai>Aj for all i<j<=k. The Banks Set is component consistent (a
strong version of cloneproofness) but not monotonic as a set.

Markov Set = set of candidates which have nonzero probability in the
limit distribution of the following Markov process: Start with a
candidate chosen uniformly at random, move to a candidate chosen
uniformly at random from all candidates beating him, repeat
indefinitely. (See my posting on Markov Chain approaches from this spring)

Minimal Covering Set, Tournament Equilibrium Set: more complicated
definition -- I will have to look this up.

Inclusions: Minimal Covering Set is included in Banks Set is included in
Uncovered Set is included in Smith Set.

Yours, Jobst