Un equipo de científicos informáticos de la Universidad de Maryland, la Universidad de Stanford y Microsoft Research es el primero en resolver un escenario de teoría de juegos que ha enfadado a los investigadores durante casi un siglo. El juego, conocido como "Coronel Blotto", se ha utilizado paraanalizar los posibles resultados de las elecciones y otros conflictos bipartidistas similares desde su invención en 1921. Hasta ahora, sin embargo, el juego ha sido de uso limitado porque carecía de una solución definitiva.
Un nuevo algoritmo desarrollado por el equipo liderado por UMD es capaz de resolver el escenario del Coronel Blotto. Un logro notable por derecho propio, el algoritmo también podría proporcionar a los estrategas políticos, líderes empresariales y otros tomadores de decisiones una poderosa herramienta nueva parahaciendo elecciones informadas
"Nuestro algoritmo se puede utilizar potencialmente para calcular la mejor estrategia de inversión de recursos para cualquier competidor frente a un solo oponente", dijo Mohammad Hajiaghayi, profesor asociado de informática de Jack y Rita G. Minker en UMD y líder del proyecto."Siempre que tengamos datos suficientes sobre un escenario determinado, podemos usar nuestro algoritmo para encontrar la mejor estrategia para una amplia variedad de líderes, como candidatos políticos, equipos deportivos, empresas y líderes militares".
El Coronel Blotto enfrenta a dos competidores entre sí y requiere que cada uno tome decisiones difíciles sobre cómo desplegar recursos limitados. En su forma más simple, cada jugador asigna un número limitado de recursos o tropas a varios campos de batalla. Los jugadores deben haceresto sin ningún conocimiento de la estrategia de su oponente. Los jugadores ganan un campo de batalla dado si asignan más tropas que su oponente; el jugador que gana la mayor cantidad de campos de batalla también gana el juego.
El juego puede extenderse a escenarios del mundo real, como las elecciones generales presidenciales de los EE. UU. En este ejemplo, cada candidato es un jugador; los recursos como el personal de la campaña, el tiempo y la financiación son las tropas; y cada estado es unEl juego también puede aplicarse a la competencia de productos de consumo de alto perfil, como la batalla en curso entre el iPhone de Apple y los productos de teléfonos móviles Android de Google.
"Desde las elecciones presidenciales hasta las decisiones de marketing, la competencia por la atención y la lealtad es parte de la vida diaria. Sin embargo, el comportamiento de las personas en respuesta a tales competencias aún no se comprende bien", dijo Hajiaghayi, quien también tiene una cita conjunta enInstituto de Estudios Avanzados de Computación de la Universidad de Maryland UMIACS. "Mostramos que dicho comportamiento estratégico es manejable computacionalmente. Dada una descripción de la competencia, podemos determinar qué estrategias maximizarán los resultados para un jugador dado".
Aunque las reglas del Coronel Blotto son relativamente simples, las estrategias potenciales que un jugador puede emplear son casi ilimitadas, dependiendo de la cantidad de campos de batalla y los recursos totales disponibles para cada jugador. La solución lograda por Hajiaghayi y sus colegas no necesariamente favoreceun jugador sobre otro, sino que representa un equilibrio en el que ambos jugadores han desplegado la mejor estrategia posible en relación con la estrategia de su oponente.
La gran variedad de estrategias posibles ha sido el obstáculo clave para encontrar una solución computacional para el juego. Hajiaghayi y su equipo superaron este problema al limitar el número total de estrategias posibles a un puñado relativo de opciones representativas.
"Descubrimos que las estrategias de los jugadores pueden representarse con precisión mediante un número razonablemente pequeño de posibilidades", dijo Hajiaghayi. "Este es un enfoque más general, pero funciona bien como una prueba de concepto. Muchos otros tienentrató de resolver el Coronel Blotto para escenarios específicos, pero somos los primeros en adoptar un enfoque más general y resolver la teoría ".
Esta solución permitió al equipo desarrollar un algoritmo generalizado, que ahora se puede aplicar a escenarios específicos, como las elecciones presidenciales de 2016.
"Nuestro algoritmo solo funciona para dos competidores, por lo que tendremos que esperar a las elecciones generales para intentar esto", dijo Saeed Seddighin, un estudiante graduado en ciencias de la computación en la UMD que presentará los hallazgos del grupo en la reunión de la AAAI ".Si sabemos cómo votó un estado determinado en elecciones anteriores en relación con los recursos que cada candidato invirtió en ese estado, entonces podemos usar los mismos datos de inversión del ciclo electoral de este año para predecir si cada candidato ha desplegado su mejor estrategia posible en todo el país."
El estudio, "From Duels to Battlefields: Computing Equilibria of Blotto and Other Games," AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini y Saeed Seddighin, se presentará el 15 de febrero de 2016 en la Asociaciónpara la Conferencia sobre el Avance de la Inteligencia Artificial AAAI en Phoenix, Arizona.
Este trabajo fue apoyado por la National Science Foundation Premios Nos. 1053605 y CCF-1161626, la Oficina de Investigación Naval Premio No N000141110662, la Agencia de Proyectos de Investigación Avanzada de Defensa Premio No. FA9550-12-1-0423 y Google. El contenido de este artículo no refleja necesariamente los puntos de vista de estas organizaciones.
Fuente de la historia :
Materiales proporcionados por Universidad de Maryland . Nota: El contenido puede ser editado por estilo y longitud.
Cita esta página :