viernes, 3 de junio de 2011

Teoria de Juegos


Juego


Se denomina juego a la situación interactiva especificada por el conjunto de participantes, los posibles cursos de acción que puede seguir cada participante, y el conjunto de utilidades.
La matriz de pagos (a veces también llamada matriz de recompensas) es una matriz que resume la información dada por las funciones de pago en un juego rectangular o en un juego extensivo en su forma normal.

Estrategia

Es un plan de acción completo para cualquier situación que pueda acaecer; determina completamente la conducta del jugador. Euna estrategia el  jugador tiene en cuenta las reacciones de otros jugadores para realizar su elección, se dice que el jugador tiene una estrategia. Una estrategia es un plan de acciones completo que se lleva a cabo cuando se juega el juego. Se explicita antes de que comience el juego, y prescribe cada decisión que los agentes deben tomar durante el transcurso del juego, dada la información disponible para el agente. La estrategia puede incluir movimientos aleatorios.

Estrategias Mixtas y puras, y Valor esperado

Un jugador usa una estrategia pura si usa la misma acción a cada turno del juego. El jugador usa una estrategia mixta si a cada turno escoge al azar un acción para que cada acción se está usado una fracción determinada del tiempo.
Representamos una estrategia mixta (o pura) del jugador reglón por una matriz con un solo renglón (vector probabilidad):
R = [a   b   c  . . . ]
Con lo mismo número de entradas que renglones, y en cual cada entrada representa la fracción de tiempo que está usada la correspondiente acción (o la probabilidad de usar aquel acción) y donde a + b + . . . = 1.
Una estrategia mixta para el jugador renglón se represente por un vector probabilidad similar, pero en forma de columna C. Para ambos jugadores, estrategias puras son representadas por vectores probabilidad con un solo 1 y el resto de las entradas 0.

El valor esperado del juego con matriz de pago P que resulta por las estrategias mixtas R y C es dado por:
e= RPC
El valor esperado del juego es el pago promedio por turno si cada jugador usa su estrategia mixta especificada por R y C después de un gran número de turno


Ejemplo
Aquí es una variante de "piedra, papel, tijera" en la que "papel/papel" y "piedra/piedra" ya no está un empate.

suponga el jugador de renglón usa la estrategia mixta

R = [0.75   0   0.25]
(juega papel 75% del tiempo, tijeras 0% del tiempo y piedra 25% del tiempo) y el jugador columna juega tijeras y piedra 50% del tiempo cada uno;

Entonces el valor esperado del juego es


Juego de Suma Cero

Un Juego de Suma Cero (“Zero Sum Game”) describe una situación en la cual la ganancia de un participante está balanceada exactamente con la pérdida de los demás. Se llama suma cero porque si la ganancia está representada por un número positivo y la pérdida por un número negativo, la suma de todas éstas a la finalización del juego es cero.
El poker es un juego de suma cero: hay un pozo y al final del juego un jugador lo gana, los demás pierden lo que apostaron. La suma de ganancias y pérdidas da cero.

Ejemplo

Piedra, papel, tijera
Piedra vence a las tijeras rompiéndolas, las tijeras vencen al papel cortándolo, y el papel vence a la piedra envolviéndola.

Cada entrada +1 indica una ganancia para el jugador renglón, -1 indica una pérdida, y 0 indica un empate.


Juegos estrictamente determinados y no estrictamente determinados
Los juegos de punta de silla están estrictamente determinados; es decir, los jugadores adoptan estrategia pura, y el curso del juego se determina por adelantado (suponiendo que los jugadores son agresivos y capaces). Los juegos sin punto de silla no están estrictamente determinados; si un jugador emplea una estrategia aleatoria, el curso del juego estará sujeto al azar, y todo puede suceder. No hay valor fijo para el juego; solo hay un valor muy probable o esperado.



Punto de silla


El punto de silla consiste en localizar el mínimo valor de las filas y al lado derecho de cada fila y el máximo de las columnas al pie de cada columna, luego se determina el máximo de los mínimos y el mínimo de los máximos. Si el máximo de los mínimos es igual al mínimo de los máximos entonces se ha encontrado el punto de silla que se convertirá automáticamente en el valor del juego
Es aquella en donde el jugador renglón elige un renglón al azar, de acuerdo con cierta distribución de probabilidad. Por ejemplo, el jugador renglón podría la siguiente distribución de probabilidad:
RESULTADO
PROBABILIDAD
Renglón1
2/3
Renglón 2
1/3
Si el jugador renglón utiliza esta distribución de forma predecible, como cuando selecciona repetidamente el renglón 1 dos veces y luego el renglón 2 una vez, el jugador columna podría descubrir la estrategia de responder con el fin de reducir al mínimo su eficacia. Por lo tanto, el jugador renglón debe emplear algún dispositivo aleatorio, como la rueda giratoria que se mostró anteriormente (ruleta de pueblo), con el cual elegiría 1  dos terceras partes del tiempo.



Criterio Minimax

Un jugador quien usa el criterio minimax escoge una estrategia que, entre todas las estrategias posibles, minimiza el daño de la mejor contra-estrategia del otro jugador. Es decir, una estrategia óptima según el criterio minimax es una que minimiza el daño máximo que puede hacer el contrincante.
Ejemplo 1



Jugador columna

I
II
Minimax

jugador renglon
I
3
2
2

II
4
-9
-9

Maximin
4
2

juego estrictamente determinado
Valor esperado

2


Ejemplo 2




Jugador columna
I
II
Minimax
jugador renglon
I
3
-2
-2
II
-1
5
-1
Maximin
3
5
juego no estrictamente determinado


Jugador
Estrategia
Proporcion
Renglon
I
3/4
II
1/4
Columna
I
1/3
II
2/3


Valor esperado
3*(3/4) - 1*(1/4)= 2
Jugador Renglon → Jugador columna EI
-2*(3/4) + 5*(1/4)= -1/4
Jugador Renglon → Jugador columna EII



P2= 1 - P1
P(1)= 0 →
3P1 - 1 (1 - P1)= 0
4P1 - 1 = 0
Si P1=0 →
P(1) = -1
Si P1=1 →
P(1) = 3
P(1)= 1 →
-2P1+5(1-P1)=0
-7P1 + 5= 0
Si P1=0 →
P(1) = 5
Si P1=1 →
P(1) = -2


4P - 1= -7P + 5
4P + 7P = 5 + 1
11P = 6
P = 6/11

Q1 + Q2 = 1
Q2= 1 - Q1
Q(1)= 0 →
3Q1 - 2 (1 - Q1)= 0
5Q1 - 2 = 0
Si Q1=0 →
Q(1) = -2
Si Q1=1 →
Q(1) = 3
Q(1)= 1 →
-Q1+ 5(1-Q1)=0
-6Q1 + 5= 0
Si Q1=0 →
Q(1) = 5
Si Q1=1 →
Q(1) = -1



5Q - 2= -6Q + 5
5Q + 6Q = 5 + 2
11Q = 7
Q = 7/11








No hay comentarios:

Publicar un comentario