Transitividad estocástica

Los modelos de transitividad estocástica ^{[1] [2] [3] [4]} son ​​versiones estocásticas de la propiedad de transitividad de las relaciones binarias estudiadas en matemáticas . Existen varios modelos de transitividad estocástica y se han utilizado para describir las probabilidades involucradas en experimentos de comparaciones por pares , específicamente en escenarios donde se espera transitividad, sin embargo, las observaciones empíricas de la relación binaria son probabilísticas. Por ejemplo, se podría esperar que las habilidades de los jugadores en un deporte sean transitivas, es decir, "si el jugador A es mejor que B y B es mejor que C, entonces el jugador A debe ser mejor que C"; sin embargo, en cualquier partido dado, un jugador más débil aún podría terminar ganando con una probabilidad positiva. Los jugadores estrechamente emparejados podrían tener una mayor probabilidad de observar esta inversión, mientras que los jugadores con grandes diferencias en sus habilidades solo podrían ver que estas inversiones ocurren raramente. Los modelos de transitividad estocástica formalizan tales relaciones entre las probabilidades (por ejemplo, de un resultado de un partido) y la relación transitiva subyacente (por ejemplo, las habilidades de los jugadores).

Una relación binaria en un conjunto se denomina transitiva , en el sentido estándar no estocástico , si y implica para todos los miembros de . ${\textstyle \succsim }$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle a\succsim b}$ ${\displaystyle b\succsim c}$ ${\displaystyle a\succsim c}$ ${\displaystyle a,b,c}$ ${\displaystyle {\mathcal {A}}}$

Las versiones estocásticas de la transitividad incluyen:

1. Transitividad estocástica débil (WST): e implica , para todos ; ^{[5] : 12  [6] : 43rg} ${\displaystyle \mathbb {P} (a\succsim b)\geq {\tfrac {1}{2}}}$ ${\displaystyle \mathbb {P} (b\succsim c)\geq {\tfrac {1}{2}}}$ ${\displaystyle \mathbb {P} (a\succsim c)\geq {\tfrac {1}{2}}}$ ${\displaystyle a,b,c\in {\mathcal {A}}}$
2. Transitividad Estocástica Fuerte (SST): e implica , para todos ; ^{[5] : 12} ${\displaystyle \mathbb {P} (a\succsim b)\geq {\tfrac {1}{2}}}$ ${\displaystyle \mathbb {P} (b\succsim c)\geq {\tfrac {1}{2}}}$ ${\displaystyle \mathbb {P} (a\succsim c)\geq \max\{\mathbb {P} (a\succsim b),\mathbb {P} (b\succsim c)\}}$ ${\displaystyle a,b,c\in {\mathcal {A}}}$
3. Transitividad Estocástica Lineal (LST): , para todo , donde es una función creciente y simétrica ^{[ aclarar ] (llamada} función de comparación ), y es una aplicación del conjunto de alternativas a la línea real (llamada función de mérito ). ${\displaystyle \mathbb {P} (a\succsim b)=F(\mu (a)-\mu (b))}$ ${\displaystyle a,b\in {\mathcal {A}}}$ ${\displaystyle F:\mathbb {R} \to [0,1]}$ ${\displaystyle \mu :{\mathcal {A}}\to \mathbb {R} }$ ${\displaystyle {\mathcal {A}}}$

Un ejemplo de juguete

El juego de las canicas : supongamos que dos niños, Billy y Gabriela, coleccionan canicas. Billy colecciona canicas azules y Gabriela canicas verdes. Cuando se juntan, juegan a un juego en el que mezclan todas sus canicas en una bolsa y toman una muestra al azar. Si la canica muestreada es verde, entonces Gabriela gana y si es azul, Billy gana. Si es la cantidad de canicas azules y es la cantidad de canicas verdes en la bolsa, entonces la probabilidad de que Billy gane contra Gabriela es ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle \mathbb {P} ({\text{Billy}}\succsim {\text{Gabriela}})}$

${\displaystyle \mathbb {P} ({\text{Billy}}\succsim {\text{Gabriela}})={\frac {B}{B+G}}={\frac {e^{\ln(B)}}{e^{\ln(B)}+e^{\ln(G)}}}={\frac {1}{1+e^{\ln(G)-\ln(B)}}}}$.

En este ejemplo, el juego de canicas satisface la transitividad estocástica lineal, donde la función de comparación está dada por y la función de mérito está dada por , donde es el número de canicas del jugador. Este juego resulta ser un ejemplo de un modelo Bradley-Terry . ^[7] ${\displaystyle F:\mathbb {R} \to [0,1]}$ ${\displaystyle F(x)={\frac {1}{1+e^{-x}}}}$ ${\displaystyle \mu :{\mathcal {A}}\to \mathbb {R} }$ ${\displaystyle \mu (M)=\ln(M)}$ ${\displaystyle M}$

Aplicaciones

• Clasificación y calificación : los modelos de transitividad estocástica se han utilizado como base de varios métodos de clasificación y calificación. Algunos ejemplos incluyen el sistema de calificación Elo utilizado en ajedrez, go y otros deportes clásicos, así como TrueSkill de Microsoft utilizado para la plataforma de juegos Xbox.
• Modelos de psicología y racionalidad - Los modelos thurstonianos ^[8] (ver Caso 5 en la ley del juicio comparativo ), los modelos fechnerianos ^[3] y también el axioma de elección de Luce ^[9] son ​​teorías que tienen fundamentos en las matemáticas de la transitividad estocástica. Asimismo, los modelos de la teoría de la elección racional se basan en el supuesto de transitividad de las preferencias (ver la utilidad de von Neumann y los teoremas de Debreu ), estas preferencias, sin embargo, a menudo se revelan con ruido de manera estocástica. ^{[10] [11] [12]}
• Aprendizaje automático e inteligencia artificial (consulte Aprenda a clasificar ) : si bien Elo y TrueSkill se basan en modelos LST específicos, se han desarrollado modelos de aprendizaje automático para clasificar sin conocimiento previo del modelo de transitividad estocástica subyacente o bajo suposiciones más débiles de lo habitual sobre la transitividad estocástica. ^{[13] [14] [15]} El aprendizaje a partir de comparaciones por pares también es de interés, ya que permite que los agentes de IA aprendan las preferencias subyacentes de otros agentes.
• Teoría de juegos : la imparcialidad de los torneos eliminatorios aleatorios depende en gran medida del modelo de transitividad estocástica subyacente. ^{[16] [17] [18]} La teoría de la elección social también tiene fundamentos que dependen de los modelos de transitividad estocástica. ^[19]

Conexiones entre modelos

Resultados positivos:

1. Todo modelo que satisface la Transitividad Estocástica Lineal también debe satisfacer la Transitividad Estocástica Fuerte, que a su vez debe satisfacer la Transitividad Estocástica Débil. Esto se representa como: LST SST WST ${\displaystyle \implies }$ ${\displaystyle \implies }$  ;
2. Dado que los modelos Bradley-Terry y el modelo Case V de Thurstone ^[8] son ​​modelos LST , también satisfacen SST y WST ;
3. Debido a la conveniencia de modelos más estructurados ^{[ aclarar ]} , algunos autores ^{[1] [2] [3] [4] [20] [21] han identificado} justificaciones axiomáticas ^{[ aclarar ]} de la transitividad estocástica lineal (y otros modelos), más notablemente Gérard Debreu mostró que: ^[10] Condición Cuádruple ^{[ aclarar ]} + Continuidad ^{[ aclarar ]} LST ${\displaystyle \implies }$ (ver también Teoremas de Debreu );
4. Dos modelos LST dados por funciones de comparación invertibles y son equivalentes ^{[ aclarar ]} si y solo si para algún ^[22] ${\displaystyle F(x)}$ ${\displaystyle G(x)}$ ${\displaystyle F(x)=G(\kappa x)}$ ${\displaystyle \kappa \geq 0.}$

Resultados negativos:

1. Los modelos de transitividad estocástica son empíricamente inverificables ^{[ aclarar ]} , ^[4] sin embargo, pueden ser falsables;
2. Distinguir ^{[ aclarar ]} entre funciones de comparación LST y puede ser imposible incluso si se proporciona una cantidad infinita de datos sobre un número finito de puntos ^{[ aclarar ]} ; ^[23] ${\displaystyle F(x)}$ ${\displaystyle G(x)}$
3. El problema de estimación ^{[ aclarar ]} para los modelos WST , SST y LST es en general NP-Hard , ^[24] sin embargo, se conocen procedimientos de estimación computables polinomialmente casi óptimos para los modelos SST y LST . ^{[13] [14] [15]}

Véase también

• Juego no transitivo
• Teoría de la decisión
• Utilitarismo

Referencias

1. Fishburn, Peter C. (noviembre de 1973). "Probabilidades de elección binaria: sobre las variedades de transitividad estocástica". Journal of Mathematical Psychology . 10 (4): 327–352. doi :10.1016/0022-2496(73)90021-7. ISSN  0022-2496.
2. Clark, Stephen A. (marzo de 1990). "Un concepto de transitividad estocástica para el modelo de utilidad aleatoria". Revista de Psicología Matemática . 34 (1): 95–108. doi :10.1016/0022-2496(90)90015-2.
3. Ryan, Matthew (21 de enero de 2017). "Incertidumbre y elección estocástica binaria". Teoría económica . 65 (3): 629–662. doi :10.1007/s00199-017-1033-4. ISSN  0938-2259. S2CID  125420775.
4. Oliveira, IFD; Zehavi, S.; Davidov, O. (agosto de 2018). "Transitividad estocástica: axiomas y modelos". Revista de psicología matemática . 85 : 25–35. doi :10.1016/j.jmp.2018.06.002. ISSN  0022-2496.
5. Donald Davidson y Jacob Marschak (julio de 1958). Pruebas experimentales de una teoría de decisiones estocásticas (PDF) (Informe técnico). Universidad de Stanford.
6. Michel Regenwetter y Jason Dana y Clintin P. Davis-Stober (2011). "Transitividad de las preferencias" (PDF) . Psychological Review . 118 (1): 42–56. doi :10.1037/a0021150. PMID  21244185.
7. Bradley, Ralph Allan; Terry, Milton E. (diciembre de 1952). "Análisis de rangos de diseños de bloques incompletos: I. El método de comparaciones por pares". Biometrika . 39 (3/4): 324. doi :10.2307/2334029. JSTOR  2334029.
8. Thurstone, LL (1994). "Una ley del juicio comparativo". Psychological Review . 101 (2): 266–270. doi :10.1037/0033-295X.101.2.266. ISSN  0033-295X.
9. Luce, R. Duncan (Robert Duncan) (2005). El comportamiento de elección individual: un análisis teórico . Mineola, NY: Dover Publications. ISBN 0486441369.OCLC 874031603  .
10. Debreu, Gerard (julio de 1958). "Elección estocástica y utilidad cardinal" (PDF) . Econometrica . 26 (3): 440–444. doi :10.2307/1907622. ISSN  0012-9682. JSTOR  1907622.
11. Regenwetter, Michel; Dana, Jason; Davis-Stober, Clintin P. (2011). "Transitividad de las preferencias". Psychological Review . 118 (1): 42–56. doi :10.1037/a0021150. ISSN  1939-1471. PMID  21244185.
12. Cavagnaro, Daniel R.; Davis-Stober, Clintin P. (2014). "Transitivo en nuestras preferencias, pero transitivo de diferentes maneras: un análisis de la variabilidad de la elección". Decisión . 1 (2): 102–122. doi :10.1037/dec0000011. ISSN  2325-9973.
13. Shah, Nihar B.; Balakrishnan, Sivaraman; Guntuboyina, Adityanand; Wainwright, Martin J. (febrero de 2017). "Modelos transitivos estocásticos para comparaciones por pares: cuestiones estadísticas y computacionales". IEEE Transactions on Information Theory . 63 (2): 934–959. arXiv : 1510.05610 . doi : 10.1109/tit.2016.2634418 . ISSN  0018-9448.
14. Chatterjee, Sabyasachi; Mukherjee, Sumit (junio de 2019). "Estimación en torneos y gráficos bajo restricciones de monotonía". IEEE Transactions on Information Theory . 65 (6): 3525–3539. arXiv : 1603.04556 . doi :10.1109/tit.2019.2893911. ISSN  0018-9448. S2CID  54740089.
15. Oliveira, Ivo FD; Ailon, Nir; Davidov, Ori (2018). "Un enfoque nuevo y flexible para el análisis de datos de comparación por pares". Revista de investigación en aprendizaje automático . 19 : 1–29.
16. Israel, Robert B. (diciembre de 1981). "Los jugadores más fuertes no necesitan ganar más torneos eliminatorios". Revista de la Asociación Estadounidense de Estadística . 76 (376): 950–951. doi :10.2307/2287594. ISSN  0162-1459. JSTOR  2287594.
17. Chen, Robert; Hwang, FK (diciembre de 1988). "Los jugadores más fuertes ganan torneos eliminatorios más equilibrados". Gráficos y combinatoria . 4 (1): 95–99. doi :10.1007/bf01864157. ISSN  0911-0119. S2CID  44602228.
18. Adler, Ilan; Cao, Yang; Karp, Richard; Peköz, Erol A.; Ross, Sheldon M. (diciembre de 2017). "Torneos eliminatorios aleatorios". Investigación de operaciones . 65 (6): 1589–1596. arXiv : 1612.04448 . doi :10.1287/opre.2017.1657. ISSN  0030-364X. S2CID  1041539.
19. Sen, Amartya (enero de 1977). "Teoría de la elección social: un nuevo examen". Econometrica . 45 (1): 53–89. doi :10.2307/1913287. ISSN  0012-9682. JSTOR  1913287.
20. Blavatskyy, Pavlo R. (2007). Teorema de utilidad estocástica . Instituto de Investigación Empírica en Economía. OCLC  255736997.
21. Dagsvik, John K. (octubre de 2015). "Modelos estocásticos para elecciones arriesgadas: una comparación de diferentes axiomatizaciones". Journal of Mathematical Economics . 60 : 81–88. doi :10.1016/j.jmateco.2015.06.013. ISSN  0304-4068.
22. Yellott, John I. (abril de 1977). "La relación entre el axioma de elección de Luce, la teoría del juicio comparativo de Thurstone y la distribución exponencial doble". Revista de psicología matemática . 15 (2): 109–144. doi :10.1016/0022-2496(77)90026-8. ISSN  0022-2496.
23. Rockwell, Christina; Yellott, John I. (febrero de 1979). "Una nota sobre modelos equivalentes de Thurstone". Revista de Psicología Matemática . 19 (1): 65–71. doi :10.1016/0022-2496(79)90006-3. ISSN  0022-2496.
24. deCani, John S. (diciembre de 1969). "Clasificación de comparación por pares de máxima verosimilitud mediante programación lineal". Biometrika . 56 (3): 537–545. doi :10.2307/2334661. ISSN  0006-3444. JSTOR  2334661.