Tournament solution

A tournament solution is a social choice function operating on orientations of complete graphs (tournaments).

A tournament on 4 vertices: $A=\{1,2,3,4\}$, $\succ =\{(1,2),(1,4),(2,4),$$(3,1),(3,2),(4,3)\}$

Definition

A tournament (graph) $T$ is a tuple $(A,\succ )$ where $A$ is a set of vertices (called alternatives) and $\succ$ is a connex and asymmetric binary relation over the vertices, which can be obtained from a preference profile by pairwise majority comparison.

A tournament solution is a function $f$ that maps each tournament $T=(A,\succ )$ to a nonempty subset $f(T)$ of its alternatives $A$ called the choice set and does not distinguish between isomorphic tournaments:

If $h:A\rightarrow B$ is a graph isomorphism between two tournaments $T=(A,\succ )$ and ${\widetilde {T}}=(B,{\widetilde {\succ }})$, then $a\in f(T)\Leftrightarrow h(a)\in f({\widetilde {T}})$

Examples

Common examples of tournament solutions are:

• Copeland's method
• Top cycle
• Slater set
• Bipartisan set
• Uncovered set
• Minimal covering set
• Tournament Equilibrium Set

Applications

Tournaments solutions are used in various areas such as sports competition, webpage ranking, dueling bandit problems, and biology.

References

Category:Voting theory