Jump to content

Tournament solution

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Chstdu (talk | contribs) at 13:09, 18 November 2016 (Category disabled for draft conforming to Wikipedia:Drafts#Preparing_drafts). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Template:New unreviewed article

Electoral systems
Part of the Politics series

Single-winner/winner-take-all Plurality First-past-the-post Plurality at-large (plurality block voting) General ticket (party block voting) Multi-round voting Two-round Exhaustive ballot Primary election Nonpartisan unified top-four Majority at-large (two-round block voting) Ranked / preferential systems Instant-runoff (alternative vote) Contingent vote Coombs' method Condorcet methods (Copeland's, Dodgson's, Kemeny–Young, Minimax, Nanson's, ranked pairs, Schulze, Alternative Smith) Positional voting (Borda count, Nauru/Dowdall method) Bucklin voting Oklahoma primary electoral system Preferential block voting Cardinal / graded systems Score voting Approval voting Combined approval voting Unified primary Usual judgment Satisfaction approval voting Majority judgment STAR voting
Proportional representation Party-list Electoral list open list closed list local lists Apportionment Sainte-Laguë D'Hondt Huntington–Hill Hare Droop Imperiali Hagenbach-Bischoff National remnant Highest averages Largest remainder Proportional forms of ranked voting Single transferable vote Gregory Wright Schulze STV CPO-STV Ranked party list PR Spare vote Proportional forms of cardinal voting Proportional approval voting Sequential proportional approval voting Method of Equal Shares Phragmen's voting rules Biproportional apportionment Fair majority voting Weighted voting Direct representation Interactive representation Liquid democracy
Mixed systems By type of representation Mixed-member majoritarian Mixed-member proportional Non-compensatory mixed systems Parallel voting Majority bonus Compensatory mixed systems Additional member system Mixed single vote (positive vote transfer) Scorporo (negative vote transfer) Mixed ballot transferable vote Alternative Vote Plus Dual-member proportional Rural–urban proportional
Other systems and related theory Semi-proportional representation Single non-transferable vote Limited voting Cumulative voting Binomial voting Other systems Multiple non-transferable vote Double simultaneous vote Proxy voting Delegated voting Indirect STV Liquid democracy Random selection (sortition, random ballot) Supermajority Social choice theory Arrow's theorem Gibbard–Satterthwaite theorem Public choice theory Veto Players List of electoral systems List of electoral systems by country Comparison of electoral systems Effects of electoral systems Political fragmentation Political efficacy Voter turnout
Politics portal
v t e

A tournament solution is a social choice function operating on orientations of complete graphs (tournaments).

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, which can be obtained from a preference profile by pairwise majority comparison.

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^[1] 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
Minimal covering set
Tournament Equilibrium Set

Applications

Tournaments solutions are used in various areas such as sports competition, webpage ranking^[2], dueling bandit problems^[3], and biology.

References

^ Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (28 April 2016). "Chapter 3: Tournament Solutions". Handbook of Computational Social Choice (PDF). Cambridge University Press. ISBN 978-1-316-48975-8.
^ Felix Brandt; Felix Fischer (2007). "PageRank as a Weak Tournament Solution" (PDF). Lecture Notes in Computer Science (LNCS). 3rd International Workshop on Internet and Network Economics (WINE). Vol. 4858. San Diego, USA: Springer. pp. 300–305.
^ Siddartha Ramamohan; Arun Rajkumar; Shivani Agarwal (2016). Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions (PDF). 29th Conference on Neural Information Processing Systems (NIPS 2016). Barcelona, Spain.

Category:Voting theory

Retrieved from "https://en.wikipedia.org/w/index.php?title=Tournament_solution&oldid=750224410"