Solución de torneo

Una solución de torneo es una función que asigna a un grafo completo orientado un subconjunto no vacío de sus vértices . De manera informal, puede considerarse como una forma de encontrar las "mejores" alternativas entre todas las que "compiten" entre sí en el torneo. Las soluciones de torneo tienen su origen en la teoría de la elección social , ^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]} pero también se han considerado en la competición deportiva , la teoría de juegos , ^{[ 5 ]} el análisis de decisiones multicriterio , la biología , ^{[ 6 ] [ 7 ]} la clasificación de páginas web , ^{[ 8 ]} y los problemas del bandido duelista . ^{[ 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 gráfico de torneo${\displaystyle T}$es una tupla${\displaystyle (A,\succ )}$dónde${\displaystyle A}$es un conjunto de vértices (llamados alternativas ) y${\displaystyle \succ }$es una relación binaria asimétrica y conectada sobre los vértices. En la teoría de la elección social, la relación binaria suele representar la comparación por pares de alternativas.

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

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

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

• Conjunto Copeland
• Conjunto Smith ( también conocido como ciclo Top)
• Slater estableció
• Conjunto bipartidista
• Conjunto Landau
• Bancos establecen
• Juego de cobertura mínimo
• conjunto de equilibrio del torneo