Tournament solution

A tournament solution is a function that maps an oriented complete graph to a nonempty subset of its vertices. It can informally be thought of as a way to find the "best" alternatives among all of the alternatives that are "competing" against each other in the tournament. 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, and thus seek to show who are the strongest candidates in some sense.

File:4-tournament.svg

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 the alternatives $A$ (called the choice set) and does not distinguish between isomorphic tournaments:

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

Examples

Common examples of tournament solutions are the:

• Copeland set
• Smith set (aka Top cycle)
• Slater set
• Bipartisan set
• Landau set
• Banks set
• Minimal covering set
• Tournament equilibrium set