Universidad de Maryland
Aunque las reglas del coronel Blotto son relativamente simples, las estrategias potenciales que un jugador puede emplear son casi ilimitadas, dependiendo del número de campos de batalla y los recursos totales disponibles para cada jugador.
Un equipo de científicos de la computación de la Universidad de Maryland, la Universidad de Stanford y Microsoft Research es el primero en resolver un escenario de la teoría de juegos que ha desconcertado a los investigadores durante casi un siglo. El juego, conocido como "coronel Blotto," se ha utilizado para analizar los posibles resultados de las elecciones y otros conflictos entre dos partes similares desde su invención en 1921. Hasta ahora, sin embargo, el juego ha sido de uso limitado, ya que carecía de una definitiva solución.
Un nuevo algoritmo desarrollado por el equipo dirigido por la UMD es capaz de resolver el escenario coronel Blotto. Un logro notable en su propio derecho, el algoritmo podría también proporcionar estrategas políticos, líderes empresariales y otros tomadores de decisiones con una nueva y poderosa herramienta para la toma de decisiones informadas. El equipo informó de sus hallazgos en la Association for the Advancement of Artificial Intelligence (AAAI) Conference en Phoenix el 15 de febrero de 2016.
"Nuestro algoritmo potencialmente puede utilizarse para calcular la mejor estrategia de inversión de recursos para cualquier competidor contra un solo oponente," dijo Mohammad Hajiaghayi, el Jack y Rita G. Minker Profesor Asociado de Ciencias de la Computación en UMD y del plomo en el proyecto. "Siempre y cuando se dispone de datos suficientes sobre un escenario dado, podemos utilizar 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."
Coronel Blotto enfrenta a dos competidores contra otras, y cada uno requiere para tomar decisiones difíciles sobre cómo implementar recursos limitados. En su forma más simple, cada jugador asigna un número limitado de recursos, o tropas, a una serie de campos de batalla. Los jugadores deben hacer esto sin ningún conocimiento de la estrategia de su oponente. Los jugadores ganan un campo de batalla dada si se asignan más tropas que su oponente; el jugador que gana la mayoría de los campos de batalla también gana el juego.
El juego se puede extender a los escenarios del mundo real, tales como las elecciones generales presidenciales EE.UU.. En este ejemplo, cada candidato es un jugador; recursos como el personal de la campaña, el tiempo muñón y la financiación son las tropas; y cada estado es un campo de batalla. El juego también se puede aplicar a la competencia de alto perfil de productos de consumo, tales como la batalla en curso entre el iPhone de Apple y los productos de telefonía móvil Android de Google.
"A partir de las elecciones presidenciales a las decisiones de marketing, la competencia por la atención y la lealtad es una parte de la vida diaria. Sin embargo, el comportamiento de los individuos en respuesta a este tipo de competiciones aún no está bien entendido ", dijo Hajiaghayi, que también tiene un nombramiento conjunto en la Instituto de Altos Estudios de Informática de la Universidad de Maryland (UMIACS). "Se demuestra que este tipo de comportamiento estratégico es computacionalmente tratables. Dada la descripción de la competición, podemos determinar qué estrategias de maximizar 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 del número de campos de batalla y los recursos totales disponibles para cada jugador. La solución alcanzada por Hajiaghayi y sus colegas no favorece necesariamente a un jugador sobre otro, sino más bien representa un equilibrio en el que ambos jugadores han desplegado la mejor estrategia que sea posible en relación con la estrategia de su oponente.
La gran variedad de posibles estrategias ha sido el obstáculo clave para encontrar una solución computacional para el juego. Hajiaghayi y su equipo superaron este problema limitando el número total de posibles estrategias para un puñado de opciones representativas.
"Hemos encontrado que las estrategias de los jugadores se pueden representar con precisión por un razonablemente pequeño número de posibilidades", dijo Hajiaghayi. "Este es un enfoque más general, pero funciona bien como una prueba de concepto. Muchos otros han tratado de resolver el coronel Blotto para escenarios específicos, pero son los primeros en adoptar un enfoque más general y resolver la teoría ".
Esta solución permitió al equipo para desarrollar un algoritmo generalizado, que ahora se pueden aplicar a situaciones específicas, tales como la elección presidencial de 2016.
"Nuestro algoritmo sólo funciona para los dos competidores, por lo que tendrá que esperar a que la elección general para tratar de esto", dijo Saeed Seddighin, un estudiante graduado en ciencias de la computación en UMD que presentará los resultados del grupo en la reunión AAAI. "Si sabemos cómo votó un estado dado en las elecciones anteriores en relación con los recursos de cada candidato invertido en ese estado, entonces podemos utilizar los mismos datos de inversión del ciclo de las elecciones de este año para predecir si cada candidato ha desplegado su mejor estrategia posible en todo el país ".
Además de Hajiaghayi y Seddighin, UMD co-autores incluyen Sina Dehghani (estudiante graduado, Ciencias de la Computación) y Hamid Mahini (ex investigador postdoctoral, Ciencias de la Computación.)
El estudio, "A partir de duelos a los campos de batalla: Computación Equilibrios de Blotto y otros juegos," AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini y Saeed Seddighin, fue presentado en la Asociación para el Avance de la Inteligencia Artificial (AAAI) Conferencia en Phoenix.
Scientific Computing
No hay comentarios:
Publicar un comentario