Editing Tournament (graph theory) (section)

== Majority relations ==
In [[social choice theory]], tournaments naturally arise as majority relations of preference profiles.{{sfnp|Brandt|Brill|Harrenstein|2016}} Let <math>A</math> be a finite set of alternatives, and consider a list <math>P = (\succ_1, \dots, \succ_n)</math> of [[linear order]]s over <math>A</math>. We interpret each order <math>\succ_i</math> as the [[preference relation|preference ranking]] of a voter <math>i</math>. The (strict) majority relation <math>\succ_{\text{maj}}</math> of <math>P</math> over <math>A</math> is then defined so that <math>a \succ_{\text{maj}} b</math> if and only if a majority of the voters prefer <math>a</math> to <math>b</math>, that is <math>|\{ i \in [n] : a \succ_i b \}| > |\{ i \in [n] : b \succ_i a \}|</math>. If the number <math>n</math> of voters is odd, then the majority relation forms the dominance relation of a tournament on vertex set <math>A</math>.

By a lemma of McGarvey, every tournament on <math>m</math> vertices can be obtained as the majority relation of at most <math>m(m-1)</math> voters.<ref>{{harvtxt|McGarvey|1953}}; {{harvtxt|Brandt|Brill|Harrenstein|2016}}</ref> Results by [[Richard E. Stearns|Stearns]] and Erdős & Moser later established that <math>\Theta(m/\log m)</math> voters are needed to induce every tournament on <math>m</math> vertices.<ref>{{harvtxt|Stearns|1959}}; {{harvtxt|Erdős|Moser|1964}}</ref>

Laslier (1997) studies in what sense a set of vertices can be called the set of "winners" of a tournament.{{sfnp|Laslier|1997}} This revealed to be useful in Political Science to study, in formal models of political economy, what can be the outcome of a democratic process.{{sfnp|Austen-Smith|Banks|1999}}