Jump to content

Tournament solution

From Wikipedia, the free encyclopedia
(Redirected from Tournament set)

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

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

A tournament on 4 vertices: ,

Definition

[edit]

A tournament graph is a tuple where is a set of vertices (called alternatives) and 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.

A tournament solution is a function that maps each tournament to a nonempty subset of the alternatives (called the choice set[2]) and does not distinguish between isomorphic tournaments:

If is a graph isomorphism between two tournaments and , then

Examples

[edit]

Common examples of tournament solutions are the:[1][2]

References

  1. ^ a b Laslier, J.-F. [in French] (1997). Tournament Solutions and Majority Voting. Springer Verlag.
  2. ^ a b c Felix Brandt; Markus Brill; Paul Harrenstein (28 April 2016). "Chapter 3: Tournament Solutions" (PDF). In Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Handbook of Computational Social Choice. Cambridge University Press. ISBN 978-1-316-48975-8.
  3. ^ Brandt, F. (2009). Tournament Solutions - Extensions of Maximality and Their Applications to Decision-Making. Habilitation Thesis, Faculty for Mathematics, Computer Science, and Statistics, University of Munich.
  4. ^ Scott Moser. "Chapter 6: Majority rule and tournament solutions". In J. C. Heckelman; N. R. Miller (eds.). Handbook of Social Choice and Voting. Edgar Elgar.
  5. ^ Fisher, D. C.; Ryan, J. (1995). "Tournament games and positive tournaments". Journal of Graph Theory. 19 (2): 217–236. doi:10.1002/jgt.3190190208.
  6. ^ Allesina, S.; Levine, J. M. (2011). "A competitive network theory of species diversity". Proceedings of the National Academy of Sciences. 108 (14): 5638–5642. Bibcode:2011PNAS..108.5638A. doi:10.1073/pnas.1014428108. PMC 3078357. PMID 21415368.
  7. ^ 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. doi:10.1007/bf02478336.
  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.
  9. ^ 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.
  10. ^ Fishburn, P. C. (1977). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030.