Tournament solution explained

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

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

Definition

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. In social choice theory, the binary relation typically represents the pairwise majority comparison between alternatives.f that maps each tournament T = (A,\succ) to a nonempty subset f(T) of the alternatives A (called the choice set^[10]) and does not distinguish between isomorphic tournaments:

If

h: A → 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 the:

• Copeland set
• Top cycle
• Slater set
• Bipartisan set
• Landau set
• Banks set
• Minimal covering set
• Tournament equilibrium set

Notes and References

1. Book: [[:fr:Jean-François Laslier|Laslier]], J.-F.. Tournament Solutions and Majority Voting. Springer Verlag. 1997.
2. Book: Brandt, F.. Tournament Solutions - Extensions of Maximality and Their Applications to Decision-Making. Habilitation Thesis, Faculty for Mathematics, Computer Science, and Statistics, University of Munich. 2009.
3. Book: Scott Moser. J. C. Heckelman. N. R. Miller. Handbook of Social Choice and Voting. Edgar Elgar. Chapter 6: Majority rule and tournament solutions.
4. Fisher. D. C.. Ryan. J.. 1995. Tournament games and positive tournaments. Journal of Graph Theory. 19 . 2. 217–236. 10.1002/jgt.3190190208.
5. Allesina. S.. Levine. J. M.. 2011. A competitive network theory of species diversity. Proceedings of the National Academy of Sciences. 108 . 14. 5638–5642. 10.1073/pnas.1014428108. 21415368. 3078357. 2011PNAS..108.5638A . free.
6. Landau. H. G.. 1951. On dominance relations and the structure of animal societies: I. Effect of inherent characteristics. Bulletin of Mathematical Biophysics. 13 . 1. 1–19. 10.1007/bf02478336.
7. PageRank as a Weak Tournament Solution. Felix Brandt. Felix Fischer. 2007. 3rd International Workshop on Internet and Network Economics (WINE). http://www.math.ucsd.edu/~wawnwine/wine2007/index.html. 4858. Lecture Notes in Computer Science (LNCS). Springer. San Diego, USA. 300–305.
8. Dueling Bandits: Beyond Condorcet Winners to General Tournament Solutions. Siddartha Ramamohan. Arun Rajkumar. Shivani Agarwal. 2016. 29th Conference on Neural Information Processing Systems (NIPS 2016). https://nips.cc/Conferences/2016. Barcelona, Spain.
9. Fishburn. P. C.. 1977. Condorcet Social Choice Functions. SIAM Journal on Applied Mathematics. 33 . 3. 469–489. 10.1137/0133030.
10. Book: Felix Brandt. Markus Brill. Paul Harrenstein. Felix Brandt. Vincent Conitzer. Ulle Endriss. Jérôme Lang. Ariel D. Procaccia. Ariel D. Procaccia. Handbook of Computational Social Choice. http://dss.in.tum.de/files/brandt-research/tsolutions.pdf. 28 April 2016. Cambridge University Press. 978-1-316-48975-8. Chapter 3: Tournament Solutions.