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,^[1][2][3][4] but have also been considered in sports competition, game theory,^[5] multi-criteria decision analysis, biology,^[6][7] webpage ranking,^[8] and dueling bandit problems.^[9]

In the context of social choice theory, tournament solutions are closely related to Fishburn's C1 social choice functions,^[10] and thus seek to show who are the strongest candidates in some sense.

A tournament graph T {\displaystyle T} is a tuple ( A , ≻ ) {\displaystyle (A,\succ )} where A {\displaystyle A} is a set of vertices (called alternatives) and ≻ {\displaystyle \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 {\displaystyle f} that maps each tournament T = ( A , ≻ ) {\displaystyle T=(A,\succ )} to a nonempty subset f ( T ) {\displaystyle f(T)} of the alternatives A {\displaystyle A} (called the choice set^[2]) and does not distinguish between isomorphic tournaments:

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

Common examples of tournament solutions are the:^[1][2]

• Copeland set
• Smith set (aka Top cycle)
• Slater set^{[clarification needed]}
• Bipartisan set
• Landau set
• Banks set
• Minimal covering set
• Tournament equilibrium set^{[clarification needed]}