Solución de torneo

Una solución de torneo es una función que asigna un gráfico completo orientado a un subconjunto no vacío de sus vértices . Se puede considerar informalmente como una forma de encontrar las "mejores" alternativas entre todas las alternativas que están "compitiendo" entre sí en el torneo. Las soluciones de torneo se originan en la teoría de la elección social , ^{[1] [2] [3] [4]} pero también se han considerado en la competencia deportiva , la teoría de juegos , ^[5] el análisis de decisiones de criterios múltiples , la biología , ^{[6] [7]} la clasificación de páginas web , ^[8] y los problemas de duelo de bandidos . ^[9]

En el contexto de la teoría de la elección social , las soluciones de torneo están estrechamente relacionadas con las funciones de elección social C1 de Fishburn ^[10] y, por lo tanto, buscan mostrar quiénes son los candidatos más fuertes en algún sentido.

Un torneo en 4 vértices: , ${\displaystyle A=\{1,2,3,4\}}$ ${\displaystyle \succ =\{(1,2),(1,4),(2,4),}$ ${\displaystyle (3,1),(3,2),(4,3)\}}$

Definición

Un gráfico de torneo es una tupla donde es un conjunto de vértices (llamados alternativas ) y es una relación binaria conexa y asimétrica sobre los vértices. En la teoría de la elección social, la relación binaria representa típicamente la comparación mayoritaria por pares entre alternativas. ${\displaystyle T}$ ${\displaystyle (A,\succ )}$ ${\displaystyle A}$ ${\displaystyle \succ }$

Una solución de torneo es una función que asigna cada torneo a un subconjunto no vacío de las alternativas (llamado conjunto de elección ^[2] ) y no distingue entre torneos isomorfos: ${\displaystyle f}$ ${\displaystyle T=(A,\succ )}$ ${\displaystyle f(T)}$ ${\displaystyle A}$

Si es un isomorfismo gráfico entre dos torneos y , entonces ${\displaystyle h:A\rightarrow B}$ ${\displaystyle T=(A,\succ )}$ ${\displaystyle {\widetilde {T}}=(B,{\widetilde {\succ }})}$ ${\displaystyle a\in f(T)\Leftrightarrow h(a)\in f({\widetilde {T}})}$

Ejemplos

Algunos ejemplos comunes de soluciones de torneos son: ^{[1] [2]}

• Conjunto Copeland
• Ciclo superior
• Conjunto Slater ^{[ se necesita aclaración ]}
• Conjunto bipartidista
• Conjunto Landau
• Los bancos se establecen
• Conjunto de cobertura mínima
• Conjunto de equilibrio del torneo ^{[ aclaración necesaria ]}

Referencias

1. Laslier, J.-F. [en francés] (1997). Soluciones de torneo y votación por mayoría . Springer Verlag.
2. Felix Brandt; Markus Brill; Paul Harrenstein (28 de abril de 2016). "Capítulo 3: Soluciones de torneo" (PDF) . En Felix Brandt; Vincent Conitzer; Ulle Endriss; Jérôme Lang; Ariel D. Procaccia (eds.). Manual de elección social computacional . Cambridge University Press. ISBN 978-1-316-48975-8.
3. Brandt, F. (2009). Soluciones de torneo: extensiones de la maximalidad y sus aplicaciones a la toma de decisiones . Tesis de habilitación, Facultad de Matemáticas, Informática y Estadística, Universidad de Múnich.
4. Scott Moser. "Capítulo 6: Regla de la mayoría y soluciones de torneo". En JC Heckelman; NR Miller (eds.). Manual de elección social y votación . Edgar Elgar.
5. Fisher, DC; Ryan, J. (1995). "Juegos de torneo y torneos positivos". Revista de teoría de grafos . 19 (2): 217–236. doi :10.1002/jgt.3190190208.
6. Allesina, S.; Levine, JM (2011). "Una teoría de redes competitivas de la diversidad de especies". Actas de la Academia Nacional de Ciencias . 108 (14): 5638–5642. Bibcode :2011PNAS..108.5638A. doi : 10.1073/pnas.1014428108 . PMC 3078357 . PMID  21415368. 
7. Landau, HG (1951). "Sobre las relaciones de dominancia y la estructura de las sociedades animales: I. Efecto de las características inherentes". Boletín de Biofísica Matemática . 13 (1): 1–19. doi :10.1007/bf02478336.
8. Felix Brandt; Felix Fischer (2007). "PageRank como una solución de torneo débil" (PDF) . Apuntes de clase en informática (LNCS) . Tercer taller internacional sobre economía de Internet y redes (WINE). Vol. 4858. San Diego, EE. UU.: Springer. págs. 300–305.
9. Siddartha Ramamohan; Arun Rajkumar; Shivani Agarwal (2016). Duelo de bandidos: más allá de los ganadores de Condorcet hasta las soluciones generales para torneos (PDF) . 29.ª Conferencia sobre sistemas de procesamiento de información neuronal (NIPS 2016). Barcelona, ​​España.
10. Fishburn, PC (1977). "Funciones de elección social de Condorcet". Revista SIAM de Matemáticas Aplicadas . 33 (3): 469–489. doi :10.1137/0133030.