Tournament solution

{{Electoral systems}}

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,{{Cite book|title=Tournament Solutions and Majority Voting|last=Laslier|first=J.-F.|publisher=Springer Verlag|year=1997}}{{Cite book|title=Tournament Solutions - Extensions of Maximality and Their Applications to Decision-Making|last=Brandt|first=F.|publisher=Habilitation Thesis, Faculty for Mathematics, Computer Science, and Statistics, University of Munich|year=2009}}{{cite book|author1=Scott Moser|editor1=J. C. Heckelman|editor2=N. R. Miller|title=Handbook of Social Choice and Voting|publisher=Edgar Elgar|chapter=Chapter 6: Majority rule and tournament solutions}} but have also been considered in sports competition, game theory,{{Cite journal|last1=Fisher|first1=D. C.|last2=Ryan|first2=J.|year=1995|title=Tournament games and positive tournaments|journal=Journal of Graph Theory|volume=19 |issue=2|pages=217–236|doi=10.1002/jgt.3190190208}} multi-criteria decision analysis, biology,{{Cite journal|last1=Allesina|first1=S.|last2=Levine|first2=J. M.|year=2011|title=A competitive network theory of species diversity|journal=Proceedings of the National Academy of Sciences|volume=108 |issue=14|pages=5638–5642|doi=10.1073/pnas.1014428108|pmid=21415368|pmc=3078357|bibcode=2011PNAS..108.5638A |doi-access=free}}{{Cite journal|last=Landau|first=H. G.|year=1951|title=On dominance relations and the structure of animal societies: I. Effect of inherent characteristics|journal=Bulletin of Mathematical Biophysics|volume=13 |issue=1|pages=1–19|doi=10.1007/bf02478336}} webpage ranking,{{cite conference|url=http://dss.in.tum.de/files/brandt-research/pagerank.pdf|title=PageRank as a Weak Tournament Solution|author=Felix Brandt|author2=Felix Fischer|year=2007|conference=3rd International Workshop on Internet and Network Economics (WINE)|conference-url=http://www.math.ucsd.edu/~wawnwine/wine2007/index.html|volume=4858|book-title=Lecture Notes in Computer Science (LNCS)|publisher=Springer|location=San Diego, USA|pages=300–305}} and dueling bandit problems.{{cite conference|url=http://www.shivani-agarwal.net/Publications/2016/nips16-dueling-bandits.pdf|archive-url=https://web.archive.org/web/20161226161354/http://www.shivani-agarwal.net/Publications/2016/nips16-dueling-bandits.pdf|url-status=usurped|archive-date=December 26, 2016|title=Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions|author=Siddartha Ramamohan|author2=Arun Rajkumar|author3=Shivani Agarwal|year=2016|conference=29th Conference on Neural Information Processing Systems (NIPS 2016)|conference-url=https://nips.cc/Conferences/2016|location=Barcelona, Spain}}

In the context of social choice theory, tournament solutions are closely related to Fishburn's C1 social choice functions,{{Cite journal|last=Fishburn|first=P. C.|year=1977|title=Condorcet Social Choice Functions|journal=SIAM Journal on Applied Mathematics|volume=33 |issue=3|pages=469–489|doi=10.1137/0133030}} and thus seek to show who are the strongest candidates in some sense.

Image:4-tournament.svg