Glosario de teoría de juegos

Lista de definiciones de términos y conceptos utilizados en la teoría de juegos.

La teoría de juegos es la rama de las matemáticas en la que se estudian los juegos : es decir, los modelos que describen el comportamiento humano. Este es un glosario de algunos términos de la materia.

Definiciones de un juego

Convenciones de notación

Numeros reales

${\displaystyle \mathbb {R} }$.

El conjunto de jugadores.

${\displaystyle \mathrm {N} }$.

Espacio de estrategia

${\displaystyle \Sigma \ =\prod _{i\in \mathrm {N} }\Sigma \ ^{i}}$, dónde

Espacio de estrategia del jugador i

${\displaystyle \Sigma \ ^{i}}$es el espacio de todas las formas posibles en las que el jugador puede jugar el juego.

Una estrategia para el jugador i

${\displaystyle \sigma \ _{i}}$ es un elemento de . ${\displaystyle \Sigma \ ^{i}}$

Complementos

${\displaystyle \sigma \ _{-i}}$ un elemento de , es una tupla de estrategias para todos los jugadores excepto i . ${\displaystyle \Sigma \ ^{-i}=\prod _{j\in \mathrm {N} ,j\neq i}\Sigma \ ^{j}}$

Espacio de resultados

${\displaystyle \Gamma }$es en la mayoría de los libros de texto idéntico a -

Pagos

${\displaystyle \mathbb {R} ^{\mathrm {N} }}$, que describe cuánta ganancia (dinero, placer, etc.) reciben los jugadores al final del juego.

Juego en forma normal

Un juego en forma normal es una función:

${\displaystyle \pi \ :\prod _{i\in \mathrm {N} }\Sigma \ ^{i}\to \mathbb {R} ^{\mathrm {N} }}$

Dada la tupla de estrategias elegidas por los jugadores, a uno se le asigna una asignación de pagos (dada en números reales).

Se puede lograr una mayor generalización dividiendo el juego en una composición de dos funciones:

${\displaystyle \pi \ :\prod _{i\in \mathrm {N} }\Sigma \ ^{i}\to \Gamma }$

la función de resultado del juego (algunos autores llaman a esta función "la forma de juego"), y:

${\displaystyle \nu \ :\Gamma \ \to \mathbb {R} ^{\mathrm {N} }}$

la asignación de pagos (o preferencias ) a los jugadores, para cada resultado del juego.

Juego de forma extensa

Esto viene dado por un árbol , donde en cada vértice del árbol un jugador diferente tiene la opción de elegir una arista . El conjunto de resultados de un juego de forma extensiva suele ser el conjunto de hojas de los árboles.

juego cooperativo

Un juego en el que a los jugadores se les permite formar coaliciones (y hacer cumplir la disciplina de coalición). Un juego cooperativo se da estableciendo un valor para cada coalición:

${\displaystyle \nu \ :2^{\mathbb {P} (N)}\to \mathbb {R} }$

Siempre se supone que la coalición vacía gana cero. Los conceptos de solución para juegos cooperativos generalmente suponen que los jugadores forman una gran coalición , cuyo valor luego se divide entre los jugadores para dar una asignación. ${\displaystyle N}$ ${\displaystyle \nu (N)}$

juego sencillo

Un juego simple es una forma simplificada de juego cooperativo, donde se supone que la posible ganancia es "0" o "1". Un juego simple es el de pareja ( N , W ), donde W es la lista de coaliciones "ganadoras" , capaces de hacerse con el botín ('1'), y N es el conjunto de jugadores.

Glosario

Juego aceptable

es una forma de juego tal que para todos los perfiles de preferencia posibles , el juego tiene equilibrios de Nash puros , todos los cuales son eficientes en el sentido de Pareto .

Asignación de bienes

es una función . La asignación es un enfoque cardinal para determinar el bien (por ejemplo, dinero) que se concede a los jugadores según los diferentes resultados del juego. ${\displaystyle \nu \ :\Gamma \ \to \mathbb {R} ^{\mathrm {N} }}$

mejor respuesta

la mejor respuesta a un complemento dado es una estrategia que maximiza el pago del jugador i . Formalmente queremos: . ${\displaystyle \sigma \ _{-i}}$ ${\displaystyle \tau \ _{i}}$
${\displaystyle \forall \sigma \ _{i}\in \ \Sigma \ ^{i}\quad \quad \pi \ (\sigma \ _{i},\sigma \ _{-i})\leq \pi \ (\tau \ _{i},\sigma \ _{-i})}$

Coalición

es cualquier subconjunto del conjunto de jugadores: . ${\displaystyle \mathrm {S} \subseteq \mathrm {N} }$

Ganador de Condorcet

Dada una preferencia ν en el espacio de resultados , un resultado a es un ganador condorcet si todos los jugadores no ficticios prefieren a a todos los demás resultados.

Decidibilidad

En relación con la teoría de juegos, se refiere a la cuestión de la existencia de un algoritmo que pueda devolver, y lo hará, una respuesta sobre si un juego se puede resolver o no. ^[1]

Determinación

Un subcampo de la teoría de conjuntos que examina las condiciones bajo las cuales uno u otro jugador de un juego tiene una estrategia ganadora y las consecuencias de la existencia de tales estrategias. Los juegos estudiados en la teoría de conjuntos son juegos de Gale-Stewart: juegos de dos jugadores con información perfecta en los que los jugadores realizan una secuencia infinita de movimientos y no hay empates.

Juego determinado (o juego estrictamente determinado )

En teoría de juegos, un juego estrictamente determinado es un juego de suma cero entre dos jugadores que tiene al menos un equilibrio de Nash en el que ambos jugadores utilizan estrategias puras . ^{[2] [3]}

Dictador

Un jugador es un dictador fuerte si puede garantizar cualquier resultado independientemente de los demás jugadores. es un dictador débil si puede garantizar algún resultado, pero sus estrategias para lograrlo podrían depender del vector de estrategia del complemento. Naturalmente, todo dictador fuerte es un dictador débil. Formalmente: n es un dictador fuerte si: m es un dictador débil si: ${\displaystyle m\in \mathbb {N} }$

${\displaystyle \forall a\in \mathrm {A} ,\;\exists \sigma \ _{n}\in \Sigma \ ^{n}\;s.t.\;\forall \sigma \ _{-n}\in \Sigma \ ^{-n}:\;\Gamma \ (\sigma \ _{-n},\sigma \ _{n})=a}$

${\displaystyle \forall a\in \mathrm {A} ,\;\forall \sigma \ _{-m}\in \Sigma \ ^{-m}\;\exists \sigma \ _{m}\in \Sigma \ ^{m}\;s.t.\;\Gamma \ (\sigma \ _{-m},\sigma \ _{m})=a}$

Otra forma de decirlo es:

Un dictador fuerte es eficaz para todos los resultados posibles. ${\displaystyle \alpha }$

Un dictador débil es eficaz para todos los resultados posibles. ${\displaystyle \beta }$

Un juego no puede tener más de un dictador fuerte . Algunos juegos tienen múltiples dictadores débiles (en piedra, papel y tijera, ambos jugadores son dictadores débiles pero ninguno es un dictador fuerte ).

Véase también Efectividad . Antónimo: tonto .

Resultado dominado

Dada una preferencia ν en el espacio de resultados , decimos que un resultado a está dominado por el resultado b (por lo tanto, b es la estrategia dominante ) si es preferido por todos los jugadores. Si, además, algún jugador prefiere estrictamente b a a , entonces decimos que a está estrictamente dominado . Formalmente: por dominación y por dominación estricta. Un resultado a está (estrictamente) dominado si está (estrictamente) dominado por algún otro resultado . Un resultado a está dominado para una coalición S si todos los jugadores en S prefieren algún otro resultado a a . Véase también Ganador Condorcet .
${\displaystyle \forall j\in \mathrm {N} \;\quad \nu \ _{j}(a)\leq \ \nu \ _{j}(b)}$
${\displaystyle \exists i\in \mathrm {N} \;s.t.\;\nu \ _{i}(a)<\nu \ _{i}(b)}$

Estrategia dominada

Decimos que la estrategia está (fuertemente) dominada por la estrategia si para cualquier tupla de estrategias complementarias , el jugador i se beneficia al jugar . Formalmente hablando: y . Una estrategia σ está (estrictamente) dominada si está (estrictamente) dominada por alguna otra estrategia . ${\displaystyle \tau \ _{i}}$ ${\displaystyle \sigma \ _{-i}}$ ${\displaystyle \tau \ _{i}}$
${\displaystyle \forall \sigma \ _{-i}\in \ \Sigma \ ^{-i}\quad \quad \pi \ (\sigma \ _{i},\sigma \ _{-i})\leq \pi \ (\tau \ _{i},\sigma \ _{-i})}$
${\displaystyle \exists \sigma \ _{-i}\in \ \Sigma \ ^{-i}\quad s.t.\quad \pi \ (\sigma \ _{i},\sigma \ _{-i})<\pi \ (\tau \ _{i},\sigma \ _{-i})}$

Ficticio

Un jugador i es un muñeco si no tiene ningún efecto sobre el resultado del juego. Es decir, si el resultado del juego es insensible a la estrategia del jugador i .

Antónimos: decir , vetar , dictador .

Eficacia

Una coalición (o un solo jugador) S es efectiva para a si puede obligar a a a ser el resultado del juego. S es α-efectivo si los miembros de S tienen estrategias st, sin importar lo que haga el complemento de S , el resultado será a .

S es β-efectivo si para cualquier estrategia del complemento de S , los miembros de S pueden responder con estrategias que aseguren el resultado a .

juego finito

Es un juego con un número finito de jugadores, cada uno de los cuales tiene un conjunto finito de estrategias .

Gran coalición

se refiere a la coalición que contiene a todos los jugadores. En los juegos cooperativos a menudo se supone que se forma una gran coalición y que el propósito del juego es encontrar imputaciones estables.

Estrategia mixta

para el jugador i es una distribución de probabilidad P en . Se entiende que el jugador i elige una estrategia aleatoriamente según P. ${\displaystyle \Sigma \ ^{i}}$

Equilibrio de Nash mixto

Igual que el Equilibrio Puro de Nash , definido en el espacio de estrategias mixtas . Todo juego finito tiene equilibrios de Nash mixtos .

eficiencia de Pareto

Un resultado a de la forma de juego π es (fuertemente) eficiente en términos de Pareto si no está dominado en todos los perfiles de preferencia .

Perfil de preferencia

es una función . Este es el enfoque ordinal para describir el resultado del juego. La preferencia describe cuán "complacidos" están los jugadores con los posibles resultados del juego. Ver asignación de bienes . ${\displaystyle \nu \ :\Gamma \ \to \mathbb {R} ^{\mathrm {N} }}$

Equilibrio puro de Nash

Un elemento del espacio de estrategia de un juego es un punto de equilibrio de Nash puro si ningún jugador puede beneficiarse desviándose de su estrategia , dado que los otros jugadores están jugando . Formalmente: . Ningún punto de equilibrio está dominado. ${\displaystyle \sigma \ =(\sigma \ _{i})_{i\in \mathrm {N} }}$ ${\displaystyle \sigma \ _{i}}$ ${\displaystyle \sigma }$
${\displaystyle \forall i\in \mathrm {N} \quad \forall \tau \ _{i}\in \ \Sigma \ ^{i}\quad \pi \ (\tau \ ,\sigma \ _{-i})\leq \pi \ (\sigma \ )}$

Decir

Un jugador i tiene un Say si no es un Dummy , es decir, si hay alguna tupla de estrategias de complemento st π (σ_i) no es una función constante.

Antónimo: tonto .

número de shannon

Un límite inferior conservador de la complejidad del árbol de juegos del ajedrez (10 ¹²⁰ ).

juego resuelto

Un juego cuyo resultado (ganar, perder o empatar) se puede predecir correctamente suponiendo que todos los jugadores jueguen perfectamente.

Valor

El valor de un juego es un resultado esperado racionalmente . Hay más de unas pocas definiciones de valor que describen diferentes métodos para obtener una solución al juego.

Veto

Un veto denota la capacidad (o derecho) de algún jugador de impedir que una alternativa específica sea el resultado del juego. Un jugador que tiene esa habilidad se llama jugador con veto .

Antónimo: tonto .

Juego débilmente aceptable

es un juego que tiene equilibrios de Nash puros, algunos de los cuales son eficientes en Pareto .

Juego de suma cero

Es un juego en el que la asignación es constante en diferentes resultados . Formalmente: wlg podemos suponer que esa constante es cero. En un juego de suma cero, lo que gana un jugador es la pérdida de otro. La mayoría de los juegos de mesa clásicos (por ejemplo, ajedrez , damas ) son de suma cero .
${\displaystyle \forall \gamma \ \in \Gamma \ \sum _{i\in \mathrm {N} }\nu \ _{i}(\gamma \ )=const.}$

Referencias

1. Mathoverflow.net/Decidabilidad-del-ajedrez-en-un-tablero-infinito Decidibilidad-del-ajedrez-en-un-tablero-infinito
2. Saúl Stahl (1999). "Soluciones de juegos de suma cero". Una suave introducción a la teoría de juegos . Librería AMS. pag. 54.ISBN​ 9780821813393.
3. Abraham M. Glicksman (2001). "Aspectos elementales de la teoría de juegos". Introducción a la programación lineal y la teoría de juegos . Publicaciones de Courier Dover. pag. 94.ISBN​ 9780486417103.

enlaces externos

• Diccionario de teoría de juegos - Game Theory.net