El impacto de la intransitividad en el sistema de calificación Elo

1 Introducción

El modelo Bradley Terry es un modelo estadístico utilizado para estimar la probabilidad del resultado de una comparación por pares. Existen estimadores de máxima verosimilitud de forma cerrada de los parámetros del modelo (1). En la práctica, estos parámetros a menudo se estiman mediante un descenso de gradiente estocástico en un proceso llamado Sistema de calificación Elo (2–5).

El sistema de clasificación Elo se utiliza para proporcionar clasificaciones numéricas a los jugadores en muchos contextos competitivos. elo (6) utilizó originalmente el sistema para calificar a los jugadores de ajedrez, pero desde entonces se ha aplicado en una amplia gama de juegos, incluidos muchos deportes y, más recientemente, en los deportes electrónicos, y ha influido en muchos sistemas de calificación más recientes. p.ej, el sistema Glicko (7), y el sistema de clasificación mElo (9).

Las calificaciones también son de interés para la comunidad de aprendizaje automático (ML), que utiliza con frecuencia técnicas de calificación matemática (8,9), por ejemplo en el entrenamiento de redes neuronales.

Si bien es muy popular, todavía se sabe poco sobre el sistema de calificación Elo (17), la importancia de una investigación teórica como esta es colocar el sistema de calificación Elo sobre bases matemáticas firmes. Esta comprensión de cómo se comportan las calificaciones Elo es lo que nos da la capacidad de confiar en nuestras conclusiones extraídas del algoritmo.

La mayoría de los sistemas de clasificación, incluido Elo, asumen que la habilidad de un jugador puede codificarse con un solo número. Una implicación es que los sistemas de calificación suelen asumir que la habilidad es transitiva. Si Alice derrota a Bob y Bob derrota a Charlie, entonces es probable que Alice gane contra Charlie. Pero hay muchos juegos con algún elemento de no transitividad, siendo Piedra, Papel y Tijera el ejemplo canónico. Nos centramos en el fenómeno de la intransitividad porque ha sido ignorado en gran medida en investigaciones anteriores sobre el sistema de calificación Elo. No hemos podido encontrar ningún análisis matemáticamente riguroso de cómo se comporta el sistema de calificación Elo en datos que muestran intransitividad y estamos escribiendo este artículo para cerrar esta brecha existente en la literatura.

Este artículo analiza cómo se comporta el sistema de calificación Elo en presencia de intransitividad. Mostramos que incluso cuando la intransitividad está presente, Elo exhibe la propiedad indeseable de que las calificaciones estimadas dependen de quién interpreta a quién. Más precisamente, el resultado a largo plazo del sistema de clasificación no depende sólo de la habilidad de los jugadores, sino de las probabilidades con las que los jugadores son seleccionados para enfrentarse entre sí. Los parámetros del modelo de calificación Elo a menudo se han comparado con el rango de Hodge de la matriz de pago esperado (9). Esta dependencia de la selección de jugadores introduce un sesgo en la estimación del rango de Hodge de la matriz de pago esperado.

Para aclarar, para cada conjunto de probabilidades q con el que se seleccionan los jugadores para enfrentarse entre sí, existe un punto fijo correspondiente en el sistema de clasificación Elo. Las clasificaciones Elo se centrarán en este punto siempre que se seleccionen parejas de jugadores usando q. Si q Si cambiara, también lo haría la ubicación de este punto fijo.

Esto es sorprendente. Obviamente, los resultados de las calificaciones dependen de los juegos particulares jugados, pero una creencia implícita de quienes usan Elo y sus descendientes es que, a largo plazo, siempre que se jueguen juegos lo suficientemente diversos, las calificaciones de Elo convergerán en estimaciones significativas de las habilidades de los jugadores. Sin embargo, si las puntuaciones dependen de la distribución de los juegos jugados, entonces las puntuaciones pierden significado. La implicación es que las calificaciones en muchos campos, p.ej, Los deportes, los deportes electrónicos y el entrenamiento de algoritmos de aprendizaje automático pueden no ser medidas útiles. Por tanto, es importante comprender por qué surge este fenómeno para poder cuantificarlo y quizás evitarlo.

Las calificaciones Elo pueden verse como una cadena de Markov de tiempo discreto (DTMC), suponiendo que los resultados de los juegos se determinan al azar (con probabilidades que dependen de las habilidades de los jugadores). Luego, el conjunto de calificaciones Elo de cada jugador forma el espacio de estados de la cadena de Markov. Con cada victoria y derrota, las calificaciones cambian dependiendo únicamente de las calificaciones actuales y del resultado, sin memoria.

Los métodos de Markov Chain Monte Carlo como este abundan en estadísticas (10). Los estados visitados por el sistema de calificación Elo DTMC tenderán a estar cerca de los estimadores de máxima verosimilitud.

Sin embargo, este DTMC es difícil de analizar porque el espacio de estados es continuo pero nada fluido. Las transiciones son binarias y dan como resultado un aumento o una disminución en las calificaciones de los jugadores, pero el tamaño de estos cambios depende del estado actual a través de una relación logística no lineal. Como resultado, no podemos demostrar que esta cadena de Markov tiene una distribución estacionaria, incluso cuando los supuestos subyacentes a Elo son verdaderos, y mucho menos cuando se violan.

Sin embargo, aunque no podemos obtener una expresión cerrada para la distribución límite del DTMC, aún podemos determinar el comportamiento a largo plazo del sistema de calificación Elo. En este artículo lo hacemos y utilizamos los resultados para comprender cómo la intransitividad afecta las calificaciones Elo.

En resumen, las contribuciones (Este artículo se basa en la tesis doctoral (11).) de este trabajo son:

• Caracterizamos el comportamiento a largo plazo del sistema de calificación Elo y mostramos que se necesita una noción de comportamiento a largo plazo más débil (que la estacionariedad).
• Proporcionamos una métrica para el grado de no transitividad en un juego y un conjunto de jugadores a través de la matriz de ventaja de la verdad sobre el terreno Aque expresa (en términos libres de calificaciones) la ventaja/desventaja de cada jugador sobre los demás.
• lo demostramos en Sección 4 que cuando A no es un matriz de comparación aditiva fuertemente transitivaentonces el comportamiento a largo plazo del sistema de clasificación Elo depende de la probabilidad con la que los jugadores son seleccionados para enfrentarse entre sí.
• mostramos en Sectas 5 y 6que si la matriz de ventajas reales y la probabilidad con la que se seleccionan los jugadores permanecen constantes, entonces existe una única calificación Elo final.

2 Antecedentes y trabajos relacionados

Este artículo se encuadra en el ahora amplio campo de la calificación y clasificación estadística. Para presentaciones ver (12) y (6). Hay una gran cantidad de enfoques para estimar calificaciones en estadística y ciencia de datos, pero dentro de ellos, Elo y sus variantes son quizás los más comúnmente utilizados en calificaciones reales.

El Sistema de calificación Elo es un método para estimar la habilidad de los jugadores en un juego de suma cero de 2 jugadores. Es bien conocido por su uso en ajedrez (13) pero se ha aplicado a muchos otros escenarios (14–16). El sistema de calificación Elo funciona asumiendo que la habilidad de cada jugador se puede cuantificar con un número escalar. r. Cuando dos jugadores i y j jugar entre sí, la probabilidad de que ese jugador i derrota al jugador j está dado por

dónde es una función sigmoidea (típicamente la función logística). Entonces, la regla de actualización para las calificaciones dadas los resultados del partido retrocede implícitamente en esta relación. Por lo tanto, el sistema de calificación Elo funciona como modelo de resultados del juego y como algoritmo de estimación del sistema de calificación. Existe una gran cantidad de literatura sobre el sistema Elo (por ejemplo, ver (9,13,16,17)) aunque mucho de eso no es directamente relevante aquí, ya que poca literatura se refiere al supuesto de transitividad implícito en este modelo.

El sistema de calificación Elo en sí es un objeto matemático bien estudiado. Existen numerosos análisis estadísticos que utilizan el sistema de calificación Elo en el campo del análisis deportivo (14,15,18–21), así como en aplicaciones más novedosas, como la evaluación de la calidad de los tejidos (22), comparando metodologías de ciberseguridad (16,23), y como método para determinar si un juego se gana debido a la suerte o a la habilidad (24).

Los detalles del sistema de calificación Elo y, más ampliamente, los problemas de intransitividad en los sistemas de calificación también son de gran interés para la comunidad de aprendizaje automático, que utiliza con frecuencia técnicas de calificación matemática (8,9,34). En particular, (35) muestra que diferentes sistemas de calificación pueden dar resultados muy diferentes en la misma matriz de comparación por pares cuando está presente la intransitividad, lo cual es una motivación clave para nuestro estudio.

Algunos investigadores han estudiado el propio sistema de calificación Elo, utilizando técnicas de procesos estocásticos para obtener información sobre cómo se comporta (4,5,25). Por ejemplo, (3) estudia el problema de optimizar los parámetros utilizados en el sistema de calificación Elo y el equilibrio entre la varianza y el sesgo de los estimadores resultantes.

Muchos investigadores han notado las limitaciones del sistema de calificación Elo y han tratado de mejorarlo. Por ejemplo, (7,26–29) ven el sistema de calificación Elo como un modelo oculto de Markov y tratan las variaciones de las puntuaciones de cada jugador como una variable. Otros métodos buscan incorporar más información que solo ganancias y pérdidas (2,30–32).

Sin embargo, en la base de todo este trabajo, la mayoría de los autores suponen que se cumplen los supuestos del modelo (en particular la transitividad) del sistema de calificación Elo. los papeles (9,33), y (8) son excepciones y consideran los efectos de la intransitividad en las calificaciones Elo. Sin embargo, difieren de nuestra investigación en que utilizan la intransitividad para motivar nuevos sistemas de calificación, mientras que nosotros estudiamos el impacto de la intransitividad en el propio sistema de calificación Elo.

Nuestro trabajo se centra en lo que se denomina puntuación final Elo. Este es el conjunto de números al que se le asigna la calificación Elo de cada jugador. Idealmente, nos gustaría que hubiera una única puntuación Elo final para cada población de jugadores y nos gustaría que éste fuera el conjunto de niveles de habilidad para cada jugador. El sistema de calificación Elo fue diseñado como un medio para aproximarse a esta puntuación Elo final. Nuestra definición de puntuación Elo final coincide con la introducida en (9), que afirma sin pruebas que el sistema de calificación Elo falla cuando hay intransitividad, los autores no proporcionan una definición precisa de falla. Aquí ampliamos esto mostrando que tiene éxito en un sentido pero fracasa en otro.

Más recientemente (36) señaló que cuando los jugadores se seleccionan de forma adaptativa en función de sus calificaciones Elo actuales, es posible que las calificaciones no converjan. Nuestro artículo explica por qué esto puede ocurrir: está relacionado con la dependencia entre el método con el que se seleccionan las comparaciones y el comportamiento a largo plazo del sistema de calificación Elo.

Para poner el comportamiento del sistema de calificación Elo sobre una base matemática firme, comenzamos estudiando matrices de comparación por pares (37,38) así como funciones que asignan estas matrices a vectores, es decir, que convierte un comparación de metro jugadores en una clasificación única para cada jugador. Para ello hacemos uso de teoría combinatoria de Hodgeuna descripción matemática de transitividad e intransitividad en matrices de comparación por pares (35,39–41). Para ayudar a explicar nuestra metodología, presentamos las siguientes ideas de la teoría combinatoria de Hodge:

El operador de gradiente combinatorio es una función que mapea un metro-vector dimensional v en una matriz METRO semejante…