Tournament solution

A tournament solution is a function that maps an oriented complete graph to a nonempty subset of its vertices. Tournament solutions originate from social choice theory., but have also been considered in sports competition, game theory, multi-criteria decision analysis, biology, webpage ranking, and dueling bandit problems.

In the context of social choice theory, tournament solutions are closely related to Fishburn's C1 social choice functions.

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. In social choice theory, the binary relation typically represents the pairwise majority comparison between alternatives.

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
• Banks set
• Minimal covering set
• Tournament equilibrium set