Glosario de teoría de juegos - Glossary of game theory

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

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 maneras posibles en las que el jugador i 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}}}$ , describiendo cuánta ganancia (dinero, placer, etc.) se les asigna a 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 (expresados como números reales).

Se puede lograr una generalización adicional 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 del juego"), y:

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

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

Juego de forma extenso

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

Juego cooperativo

Un juego en el que los jugadores pueden formar coaliciones (y hacer cumplir la disciplina de la coalición). Se da un juego cooperativo indicando un valor para cada coalición:

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

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

Juego simple

Un juego simple es una forma simplificada de un juego cooperativo, donde se supone que la posible ganancia es '0' o '1'. Un juego simple es pareja ( N , W ), donde W es la lista de coaliciones "ganadoras" , capaces de obtener 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 nash puros , todos los cuales son pareto eficientes .

Asignación de bienes: es una función . La asignación es un enfoque fundamental para determinar el bien (por ejemplo, el dinero) que se les otorga 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 que no son muñecos prefieren a a todos los demás resultados.

Decidibilidad: En relación a la teoría de juegos, se refiere a la cuestión de la existencia de un algoritmo que pueda y devolverá una respuesta sobre si un juego puede resolverse o no.

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 los juegos de Gale-Stewart, juegos de dos jugadores de información perfecta en los que los jugadores hacen 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 para dos jugadores que tiene al menos un equilibrio de Nash con ambos jugadores usando estrategias puras .

Dictador

Un jugador es un dictador fuerte si puede garantizar cualquier resultado independientemente de los otros jugadores. es un dictador débil si puede garantizar cualquier resultado, pero sus estrategias para hacerlo pueden depender del vector de estrategia del complemento. Naturalmente, todo dictador fuerte es un dictador débil. Formalmente: m es un dictador fuerte si: m es un dictador débil si:

{\ Displaystyle m \ in \ mathbb {N}}

{\ Displaystyle \ forall a \ in \ mathrm {A}, \; \ existe \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ forall \ sigma \ _ {- n} \ en \ Sigma \ ^ {- n}: \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}

{\ Displaystyle \ forall a \ in \ mathrm {A}, \; \ forall \ sigma \ _ {- n} \ in \ Sigma \ ^ {- n} \; \ existe \ sigma \ _ {n} \ in \ Sigma \ ^ {n} \; st \; \ Gamma \ (\ sigma \ _ {- n}, \ sigma \ _ {n}) = a}

Otra forma de decirlo es:

un dictador débil es eficaz para todos los resultados posibles.

{\ Displaystyle \ alpha}

Un dictador fuerte es efectivo 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-tijera ambos jugadores son dictadores débiles pero ninguno es un dictador fuerte ).

También vea 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 todos los jugadores lo prefieren. Si, además, algún jugador prefiere estrictamente b sobre 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 por una coalición S si todos los jugadores en S prefieren algún otro resultado a a . Véase también Ganador de Condorcet .
${\ Displaystyle \ forall j \ in \ mathrm {N} \; \ quad \ nu \ _ {j} (a) \ leq \ \ nu \ _ {j} (b)}$
${\ Displaystyle \ existe i \ in \ mathrm {N} \; st \; \ 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 jugando . Hablando formalmente: 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 \ existe \ sigma \ _ {- i} \ in \ \ Sigma \ ^ {- i} \ quad st \ quad \ pi \ (\ sigma \ _ {i}, \ sigma \ _ {- i}) <\ pi \ (\ tau \ _ {i}, \ sigma \ _ {- i})}$

Tonto: Un jugador i es un muerto 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 , veto , dictador .

Eficacia: Una coalición (o un solo jugador) S es eficaz 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 β-eficaz 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 asume que la gran coalición se forma y 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 aleatoria de acuerdo con P . ${\ Displaystyle \ Sigma \ ^ {i}}$

Equilibrio de Nash mixto: Igual que Pure Nash Equilibrium , 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) pareto eficiente si no está dominado bajo 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 "satisfechos" están los jugadores con los posibles resultados del juego. Ver asignación de bienes . ${\ Displaystyle \ nu \: \ Gamma \ \ to \ mathbb {R} ^ {\ mathrm {N}}}$

Equilibrio de Nash puro: Un elemento del espacio de estrategias de un juego es un punto de equilibrio de Nash pura si ningún jugador i puede beneficiar al desviarse de su estrategia , dado que los otros jugadores están jugando en . Formalmente: . No se domina ningún punto de equilibrio. ${\ 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 complementarias, st π (σ_i) no es una función constante.; Antónimo: Dummy .

Número de Shannon: Un límite inferior conservador de la complejidad del árbol de juego del ajedrez (10 ¹²⁰ ).

Juego resuelto: Un juego cuyo resultado (ganar, perder o empatar) se puede predecir correctamente asumiendo un juego perfecto de todos los jugadores.

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 el derecho) de un jugador para evitar que una alternativa específica sea el resultado del juego. Un jugador que tiene esa habilidad se llama jugador con veto .; Antónimo: Dummy .

Juego débilmente aceptable: es un juego que tiene equilibrios nash puros, algunos de los cuales son pareto eficientes .

Juego de suma cero: es un juego en el que la asignación es constante en diferentes resultados . Formalmente: wlg podemos asumir que la constante es cero. En un juego de suma cero, la ganancia de un jugador es la pérdida de otro jugador. 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.}$

Languages

In other projects