Tournament solution: Difference between revisions

Content deleted Content added

Inline

Revision as of 14:13, 19 December 2016

A tournament solution is a function that maps an oriented complete graph to a nonempty subset of its vertices. 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]

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. In social choice theory, the binary relation typically represents the pairwise majority comparison between alternatives.

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^[2] 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:^[1]^[2]

Copeland's method
Top cycle
Slater set
Bipartisan set
Uncovered set
Banks set
Minimal covering set
Tournament equilibrium set

References

^ ^a ^b Laslier, J.-F. (1997). Tournament Solutions and Majority Voting. Springer Verlag.
^ ^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.
^ 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.
^ 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.
^ Fisher, D. C.; Ryan, J. (1995). "Tournament games and positive tournaments". Journal of Graph Theory. 19(2): 217–236.
^ Allesina, S.; Levine, J. M. (2011). "A competitive network theory of species diversity". Proceedings of the National Academy of Sciences. 108(14): 5638–5642.
^ 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.
^ 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.
^ Fishburn, P. C. (1977). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33(3): 469–489.

[:0-1] Laslier, J.-F. (1997). Tournament Solutions and Majority Voting. Springer Verlag.

[BrandtConitzer2016-2] 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.

[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.

[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.

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{Electoral systems}}
-A '''tournament solution''' is a [[Function (engineering)|function]] that maps an [[Tournament (graph theory)|oriented complete graph]] to a nonempty [[subset]] of its [[vertice]]s. Tournament solutions originate from [[Social choice theory|social choice theory]].<ref name=":0">{{Cite book|title=Tournament Solutions and Majority Voting|last=Laslier|first=J.-F.|publisher=Springer Verlag|year=1997|isbn=|location=|pages=|quote=|via=}}</ref><ref name="BrandtConitzer2016" /><ref>{{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|isbn=|location=|pages=|quote=|via=}}</ref><ref>{{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}}</ref>, but have also been considered in [[sports competition]], [[game theory]]<ref>{{Cite journal|last=Fisher|first=D. C.|last2=Ryan|first2=J.|year=1995|title=Tournament games and positive tournaments|url=|journal=Journal of Graph Theory|volume=19(2)|pages=217–236|via=}}</ref>, [[Multi-Criteria Decision Analysis|multi-criteria decision analysis]], [[biology]]<ref>{{Cite journal|last=Allesina|first=S.|last2=Levine|first2=J. M.|year=2011|title=A competitive network theory of species diversity|url=|journal=Proceedings of the National Academy of Sciences|volume=108(14)|pages=5638–5642|via=}}</ref><ref>{{Cite journal|last=Landau|first=H. G.|year=1951|title=On dominance relations and the structure of animal societies: I. Effect of inherent characteristics|url=|journal=Bulletin of Mathematical Biophysics|volume=13(1)|pages=1–19|via=}}</ref>, [[Web search engine|webpage ranking]]<ref>{{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|editor=|volume=4858|book-title=Lecture Notes in Computer Science (LNCS)|publisher=Springer|location=San Diego, USA|pages=300–305}}</ref>, and [[Multi-armed bandit#Dueling Bandit|dueling bandit problems]]<ref>{{cite conference|url=http://www.shivani-agarwal.net/Publications/2016/nips16-dueling-bandits.pdf|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}}</ref>
+A '''tournament solution''' is a [[Function (mathematics)|function]] that maps an [[Tournament (graph theory)|oriented complete graph]] to a nonempty [[subset]] of its [[Vertex (graph theory)|vertices]]. Tournament solutions originate from [[Social choice theory|social choice theory]].<ref name=":0">{{Cite book|title=Tournament Solutions and Majority Voting|last=Laslier|first=J.-F.|publisher=Springer Verlag|year=1997|isbn=|location=|pages=|quote=|via=}}</ref><ref name="BrandtConitzer2016" /><ref>{{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|isbn=|location=|pages=|quote=|via=}}</ref><ref>{{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}}</ref>, but have also been considered in [[sports competition]], [[game theory]]<ref>{{Cite journal|last=Fisher|first=D. C.|last2=Ryan|first2=J.|year=1995|title=Tournament games and positive tournaments|url=|journal=Journal of Graph Theory|volume=19(2)|pages=217–236|via=}}</ref>, [[Multi-Criteria Decision Analysis|multi-criteria decision analysis]], [[biology]]<ref>{{Cite journal|last=Allesina|first=S.|last2=Levine|first2=J. M.|year=2011|title=A competitive network theory of species diversity|url=|journal=Proceedings of the National Academy of Sciences|volume=108(14)|pages=5638–5642|via=}}</ref><ref>{{Cite journal|last=Landau|first=H. G.|year=1951|title=On dominance relations and the structure of animal societies: I. Effect of inherent characteristics|url=|journal=Bulletin of Mathematical Biophysics|volume=13(1)|pages=1–19|via=}}</ref>, [[Web search engine|webpage ranking]]<ref>{{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|editor=|volume=4858|book-title=Lecture Notes in Computer Science (LNCS)|publisher=Springer|location=San Diego, USA|pages=300–305}}</ref>, and [[Multi-armed bandit#Dueling Bandit|dueling bandit problems]]<ref>{{cite conference|url=http://www.shivani-agarwal.net/Publications/2016/nips16-dueling-bandits.pdf|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}}</ref>.
 In the context of social choice theory, tournament solutions are closely related to Fishburn's C1 social choice functions.<ref>{{Cite journal|last=Fishburn|first=P. C.|year=1977|title=Condorcet Social Choice Functions|url=|journal=SIAM Journal on Applied Mathematics|volume=33(3)|pages=469–489|via=}}</ref>