Teoría de juegos composicional

La teoría de juegos composicional es una rama de la teoría de juegos y la informática que busca presentar juegos complejos de gran tamaño como una composición de juegos pequeños y simples. ^{[ 1 ] [ 2 ] [ 3 ]}

Un tema central en la informática es la capacidad de construir bloques de construcción simples (por ejemplo, funciones o procedimientos en un lenguaje de programación ) y combinarlos para formar estructuras más grandes (por ejemplo, funciones o programas más complejos). Este principio también se conoce como modularidad .

En cambio, en la teoría de juegos clásica , incluso los juegos complejos se tratan como objetos únicos y monolíticos. Esto dificulta la escalabilidad del análisis de juegos.

La teoría de juegos compositiva (TGC) busca aplicar el principio de modularidad a la teoría de juegos. Su principal objetivo es facilitar el análisis de juegos complejos mediante herramientas de software.

Un juego simultáneo de orden superior ^{[ 4 ]} es una generalización de un juego simultáneo en el que los jugadores se definen mediante funciones de selección en lugar de funciones de utilidad . Formalmente, un juego simultáneo de orden superior para n jugadores contiene los siguientes elementos:

• Un conjunto R de resultados .
• Para cada jugador i , un conjunto X _i de opciones (acciones posibles).
  • Definimos Σ como el producto cartesiano de todos los X _i , y lo llamamos el conjunto de perfiles de estrategia .
• Una función de resultado , de Σ a R. Esta función determina, para cada combinación de acciones de los jugadores, cuál será el resultado.
• Para cada jugador i , hay una función de selección denotada d _i . La función de selección toma como entrada un contexto , que es una función de X _i a R ; y devuelve un conjunto de mejores respuestas , que es un subconjunto de X _i .

El término "de orden superior" proviene de este último elemento. La correspondencia de mejor respuesta de cada jugador es una función de orden superior , al igual que su entrada es en sí misma una función. Cada perfil de estrategia s ₁ en Σ define para cada jugador i una función de X _i a R : la función asigna a cada acción posible x _i en X _i el resultado que se produciría si todos los jugadores, excepto i, jugaran como en s ₁ , mientras que el jugador i cambia su acción a x _i . En otras palabras, s ₁ define el contexto en el que opera el jugador i .

Dadas dos tuplas de estrategia s ₁ y s ₂ en Σ , decimos que s ₂ es una mejor respuesta a s ₁ si, para cada jugador i , s _2,i está contenida en la salida de d _i en el contexto generado por s ₁ . La relación de mejor respuesta es una relación binaria contenida en Σ x Σ , denotada por B .

En un juego estándar, en lugar de la función de selección, existe una función de utilidad u _i para cada jugador i. Una función de utilidad toma como entrada un resultado de R y devuelve un número real . Dicho juego puede representarse como un juego de orden superior de la siguiente manera: para cada jugador i , la función de selección devuelve el conjunto de acciones de X _i que maximizan la utilidad del agente i , dado el contexto.

El principal objeto de estudio en la Teoría de la Computación Global (TCG) es el juego abierto . Un juego abierto tiene los siguientes elementos:

• Un conjunto X de observaciones ;
• Un conjunto Y de resultados;
• Un conjunto Σ de perfiles de estrategia .
• Una función de juego P , que es una función de Σ x X a Y ;
• Una función de juego conjunto C , que es una función de Σ x X x R a S;
• Una función de mejor respuesta B, que es una función de X x (Y -> R) a una relación en Σ x Σ.

Es una abstracción de un juego de orden superior.

Los juegos abiertos se pueden descomponer de dos maneras: ^{[ 2 ]}

• En secuencia, dando como resultado un juego secuencial ;
• En paralelo, dando como resultado un juego simultáneo .

• Juegos abiertos bayesianos. ^{[ 5 ]}

• Motor de juegos de código abierto : código Haskell para construir y analizar juegos de código abierto.
• Instituto de Cibernética Categórica : el instituto de investigación responsable de la creación del Open Game Engine y de la investigación posterior sobre la Teoría de Juegos Composicionales y sus aplicaciones a la Cibernética.