A tournament solution is a

function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...

that maps an oriented complete graph to a nonempty

subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...

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 Social choice theory or social choice is a theoretical framework for analysis of combining individual opinions, preferences, interests, or welfares to reach a ''collective decision'' or ''social welfare'' in some sense.Amartya Sen (2008). "Soci ...

, but have also been considered in

sports competition Competition is a rivalry where two or more parties strive for a common goal which cannot be shared: where one's gain is the other's loss (an example of which is a zero-sum game). Competition can arise between entities such as organisms, indivi ...

game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...

multi-criteria decision analysis Multiple-criteria decision-making (MCDM) or multiple-criteria decision analysis (MCDA) is a sub-discipline of operations research that explicitly evaluates multiple conflicting criteria in decision making (both in daily life and in settings ...

biology Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary i ...

, 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 the best candidates are among all candidates.

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 In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...

over the vertices. In social choice theory, the binary relation typically represents the pairwise majority comparison between alternatives. A tournament solution is a

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 \rightarrow B

is a

graph isomorphism In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) a ...

between two tournaments

T = (A,\succ)

and

\widetilde = (B,\widetilde)

, then

a \in f(T) \Leftrightarrow h(a) \in f(\widetilde)

Examples

Common examples of tournament solutions are: *

Copeland's method Copeland's method is a ranked voting method based on a scoring system of pairwise "wins", "losses", and "ties". The method has a long history: * Ramon Llull described the system in 1299, so it is sometimes referred to as "Llull's method" * The ...

* Top cycle * Slater set * Bipartisan set * Uncovered set * Banks set * Minimal covering set * Tournament equilibrium set

References

{{Reflist Voting theory