Investigación de Operaciones II

Teoría de juegos

1. MARCO GENERAL  Estrategia pura es cuando ambos jugadores coinciden en

la misma estrategia, es decir, el juego tiene una solución
1.1. Introducción estable.

Son situaciones de decisión en la que dos oponentes inteligentes 2. DESARROLLO CONCEPTUAL

con objetivos conflictivos (si suman 0) compiten hasta superar al
otro. En un combate, cada uno de los jugadores (oponentes) tiene 2.1. Formulación con 2 jugadores y suma 0
una cantidad de alternativas o estrategias (finita o infinita). De
acuerdo a cada estrategia, está la retribución que un jugador recibe Esta teoría tiene que ver con situaciones de decisión en la que dos
del otro. oponentes inteligentes con objetivos conflictivos (en caso de suma
cero) compiten intensamente para superar al otro.
1.1 Marco conceptual
En un conflicto, cada uno de los dos jugadores (oponentes) tiene
Valor de juego es el pago que un jugador tiene garantizado que una cantidad (finita o infinita) de alternativas o estrategias.
puede recibir de un juego si toma una decisión racional, Asociada con cada par de estrategias está la retribución que un
independientemente de las decisiones de los demás jugadores1. Se jugador recibe del otro. Tal situación se conoce como juego de
dice que se trata de un juego justo cuando el juego tiene valor 0. suma cero entre dos personas porque la ganancia de un jugador es
igual a la pérdida del otro. Esto significa que podemos representar
Punto de silla es un pago que es simultáneamente un mínimo de
el juego en función de la retribución que recibe un jugador.
su renglón y un máximo de su columna.
Designando los dos jugadores A y B con m y n estrategias, el juego
http://teoriadejuegosblog.blogspot.com.co/p/punto-de- se presenta usualmente en función de la matriz de retribuciones
silla.html que recibe el jugador A como

Estrategia es una regla predeterminada que especifica por

completo cómo se intenta responder a cada circunstancia posible
en cada etapa del juego.
‫ܤ‬ଵ ‫ܤ‬ଶ .... ‫ܤ‬௡
‫ܣ‬ଵ ܽ ܽͳʹ ‫݊ͳܽ ڮ‬
 Estrategia dominante es aquella que es preferida por un ଵଵ
‫ܣ‬ଶ ܽ ܽଶଶ ‫ܽ ڮ‬ଶ௡
ଶଵ
jugador por sobre las demás estrategias que tiene. ‫ڭ‬ ‫ڭ‬ ‫ڭ‬ ‫ڭ ڭ‬
‫ܣ‬௠ ܽ௠ଵ ܽ௠ ଶ ǥ ܽ௠ ௡

1
Tomado de “valor de juego” (2011)
Tomado de http://teoriadejuegosblog.blogspot.com.co/p/valor-del-juego.html
Investigación de Operaciones II
Teoría de juegos

La representación indica que si A utiliza la estrategia i y B utiliza la dos valores no son iguales. Si el jugador A selecciona AH, el jugador
estrategia j, la retribución para A es aij, y la retribución para B es B puede seleccionar BT para recibir $1 de A. Si es así, A puede
2aij. cambiar a la estrategia AT para invertir el resultado al recibir $1 de
B. De acuerdo al cambio de estrategia, cuando es pura no es
Criterio minimax y maximin aceptable, lo que se requieres es que ambos jugadores combinen
al azar sus estrategias puras respectivas. El valor óptimo del juego
 En el criterio minimax, se deben identificar los valores
ocurrirá entre los valores maximin y minimin del juego
mayores de cada columna y seleccionar el menor pago.
Valor maximin (menor) ≤ Valor del juego ≤ Valor minimax (mayor).
 En el criterio maximax, se deben identificar los valores
menores de cada fila y luego seleccionar el mayor pago.
2.2. Formulación estrategias mixtas
Cuando un juego no tiene punto silla, se aconseja a cada jugador
Ejemplo 1.1 Dos jugadores, A y B, juegan a tirar la moneda. Cada asignar una distribución de probabilidad sobre su conjunto de
jugador, sin saberlo el otro, escoge cara (H) o cruz (T). Ambos estrategias, y luego determinar cuál de ellas es la que se utilizara.
jugadores revelan sus elecciones al mismo tiempo. Si coinciden Para expresar esto de manera matemática, sea:
(HH o TT), el jugador A recibe $1 de B. De lo contrario, A le paga
$1a B. La siguiente matriz de retribuciones para el jugador A da los
valores de fila min y columna máx. correspondientes a las
x i=Probabilidad de que el jugador use la estrategiai ( i=1 ,2 , … , m ) .
estrategias de A y B, respectivamente.
x j=Probabilidad de que el jugador use laestrategia j ( j=1, 2 , … , n ) .
  BH BT Fila min
AH 1 -1 -1
AT -1 1 -1 Donde m y n son los números respectivos de estrategias
Columna disponibles. Como estos valores son probabilidades, tendrán que
Máx. 1 1   ser no negativos y sumar 1.
m n

Los valores maximin y minimax de los juegos son -$1 y $1, Pago esperado por el jugador=∑ ∑ Pij x i y j
i=1 j=1
respectivamente, y el juego no tiene una estrategia pura porque los
Investigación de Operaciones II
Teoría de juegos

Donde Pij representa el pago del jugador 1 si usa la estrategia pura restricciones válidas en programación lineal. Es por eso que
cualquier solución (x1, x2, x3,…, xm) que satisfaga el conjunto
i y el pago del jugador 2 si usa la estrategia pura j.
completo de restricciones de programación lineal es la estrategia
En el caso de las estrategias mixtas, el criterio minimax sostiene mixta óptima deseada.
que un jugador debe elegir la estrategia mixta que minimice la
Queda así entonces reducido el problema de encontrar una
máxima pérdida que espera para sí mismo y el criterio maximin es
solución mixta óptima a encontrar una solución factible para un
maximizar el pago esperado mínimo para el jugador.
problema de programación lineal. Para esto, cabe resaltar que,
v=valor minimaxv=valor maximin como se desconoce v y no se cuenta con una función objetivo, la
forma de solucionarlo es sustituyendo la constante desconocida v
Lo ideal en los juegos con estrategias mixtas es que v=v para que por la variable xm+1, y después maximizarla; así, xm+1 será igual a v
la solución sea estable. en la solución óptima del problema de programación lineal. Se
concluye entonces que, el jugador 1 encontrará su estrategia mixta
óptima al emplear el método Simplex para resolver el problema de
2.2.1. Solución con programación lineal programación lineal.

Cualquier juego de estrategias mixtas puede resolverse, de forma Para el jugador 2, este puede encontrar su estrategia óptima mixta
más sencilla, si se transforma a un problema de programación si reescribe la matriz de pagos como los pagos a sí mismo en lugar
lineal. de al jugador 1, y luego realizando lo mencionado anteriormente;
pero, en general, siempre se pueden encontrar las estrategias
Primero, debe considerarse como se encuentra la estrategia mixta mixtas de ambos jugadores con solo elegir uno de los modelos y
del jugador 1, es decir, su pago esperado y cuándo la estrategia es usar el método simplex para obtener una solución óptima y una
óptima. Dicha desigualdad, debe cumplirse para cada una de las solución óptima dual.
estrategias puras del jugador 2; quiere decir que, al sustituirse los
valores de yj en la desigualdad, implicará a ese conjunto de n En dado caso que xm+1 y yn+1 no estés restringidas en signo en sus
desigualdades, y, a su vez, ese conjunto de n desigualdades formulaciones de programación lineal, es decir, v < 0, debe hacerse
implicará la desigualdad original. un ajuste. Una de las más utilizadas es agregar una constante fija
grande a todos los elementos de la matriz de pagos, para que así el
Como la implicación va en ambas direcciones, se concluye que nuevo valor del juego sea positivo.
imponer dicho conjunto de n desigualdades lineales, es igual a
requerir que la desigualdad original se cumpla para todas las
estrategias (y1, y2, y3,…, yn); pero estas n desigualdades son
Investigación de Operaciones II
Teoría de 1.2.1:
Ejemplo juegos El valor del juego v, queda entre -2 y 2 Programa lineal del jugador B

Maximizar Z=v
  B1 B2 B3 Fila min
A1 3 -1 -3 -3 v+3 y 1 + y 2 +3 y 3 ≥ 0
A2 -2 4 -1 -2 v+ 2 y 1−4 y 2 + y 3 ≥ 0
A3 -5 -6 2 -6
Columna v+5 y 1 +6 y 2−2 y 3 ≥0
máx. 3 4 2  
y 1 + y 2+ y 3=1

Programa lineal del jugador A v irrestricta

Maximizar Z=v La solución da y1 =0.32, y2= 0.08, y3= 0.60, y v= -0.91.

v−3 x1 +2 x 2+5 x 3 ≤0
3. EJERCICIOS
v+ x 1−4 x 2+ 6 x3 ≤ 0

v+3 x 1 + x 2−2 x 3 ≤0 1. Dos compañías promueven dos productos competidores. En la

actualidad, cada producto controla 50% del mercado. Debido a
x 1+ x2 + x 3 ≤ 0
mejoras recientes en los dos productos, cada compañía planea
x1 , x2 , x3 ≥ 0 lanzar una campaña publicitaria. Si ninguna de las dos compañías
se anuncia, continuarán iguales las partes del mercado. Si alguna
v irrestricta de las compañías lanza una campaña más agresiva, la otra
compañía con toda certeza perderá un porcentaje proporcional de
Solución óptima es x1 =0.39, x2 =0.31, x3= 0.29, y v =-0.91 sus clientes. Una encuesta del mercado muestra que se puede
llegar a 50% de los clientes potenciales por medio de la televisión,
a 30% por medio de periódicos, y a 20% por medio de la radio.
 A4 7 4 -2 -5

Investigación de Operaciones
(a) Formule el problema como un juego de II
suma cero entre dos
personas, y determine el medio publicitario para cada compañía.
Teoría de juegos
c) d)
(b) Determine un intervalo para el valor del juego. ¿Puede operar   B1 B2 B3   B1 B2 B3 B4
cada compañía con una estrategia pura única? A1 3 6 1 A1 3 7 1 3
2. En los juegos (a) y (b) dados a continuación, la retribución es A2 5 2 3 A2 4 8 0 -6
para el jugador A. Cada juego tiene una solución de estrategia A3 4 2 -5 A3 6 -9 -2 4
pura. En cada caso, determine las estrategias que definan el punto
de silla y el valor del juego.
  4. Considere el siguiente juego de suma cero entre dos personas:
a)  b)
B1 B2 B3 B4   A1 B1 B2 B3 B4
A1 8 6 2 8   B1 B2 B3
A1 4 -4 -5 6
A2 8 9 4 5 A2 -3 -4 -9 -2 A1 5 50 50
A3 7 5 3 5 A3 6 7 -8 -9 A2 1 1 1
A4 7 3 -9 5 A3 10 1 10

(a) Compruebe que las estrategias para A y para B son óptimas, y

3. En los juegos (a) y (b) dados a continuación, la retribución es
determine el valor del juego.
para el jugador A. Especifique el intervalo del valor del juego en
cada caso. (b) Demuestre que el valor óptimo del juego es igual a:
3 3
a)
 
b) ∑ ∑ aijXijYij
B1 B2 B3 B4   B1 B2 B3 B4
i=1 J=1

A1 1 9 6 0 A1 -1 9 6 8
A2 2 3 8 4 A2 -2 10 4 6
A3 -5 -2 10 -3 A3 5 3 0 7
A4   -2 8 4
Investigación de Operaciones II
Teoría de juegos

5. El sindicato y la administración de una compañía negocian el El jugador 1 tendrá cuatro estrategias puras que especifican cómo
nuevo contrato colectivo. Por ahora las negociaciones están respondería a cada uno de los dos resultados que le muestra el
congeladas, pues la empresa ha hecho una oferta “final” de un árbitro; el jugador 2 tendrá dos estrategias puras que especifican
aumento salarial de $1.10 por hora y el sindicato una demanda cómo respondería si el jugador 1 apuesta.)
“final” de un aumento de $1.60 por hora. Ambas partes han (b) Desarrolle la matriz de pagos de este juego con valores
acordado que un árbitro imparcial establezca el aumento en alguna esperados de los elementos, cuando sea necesario. Identifique y
cantidad entre $1.10 por hora y $1.60 por hora (inclusive). El elimine las estrategias dominadas.
arbitraje ha pedido a cada parte que le presente una propuesta
confidencial de un aumento salarial económicamente razonable y (c) Muestre que ninguno de los elementos de la matriz de pagos
justo (redondeado a los diez centavos más cercanos). Por que se obtuvo son punto silla. Explique por qué cualquier elección
experiencias anteriores, ambas partes saben que por lo general el 󿬁ja de una estrategia pura de cada jugador tiene que ser una
árbitro acepta la propuesta del lado que cede más en su cifra final. solución inestable, por lo que, en su lugar, deben usarse
Si ningún lado cambia su cantidad final o si ambos ceden en la estrategias mixtas.
misma cantidad, el arbitraje suele establecer una cifra a la mitad
7. Robín viaja entre dos ciudades y puede utilizar dos rutas. La ruta
($1.35 en este caso). Ahora, cada parte necesita determinar qué
A es una carretera rápida de cuatro carriles, y la ruta B es una larga
aumento proponer para obtener un beneficio máximo. Formule este
carretera sinuosa. Robín maneja “súper rápido”. La patrulla de
problema como un juego de dos personas y suma cero
caminos cuenta con una fuerza policial limitada. Si se asignara toda
6. Considere el siguiente juego de mesa entre dos jugadores. Un la fuerza a la ruta por la que maneja Robín, con toda certeza
árbitro tira una moneda al aire, anota si cae cara o cruz y la recibiría una multa de $100 por exceso de velocidad. Si la fuerza se
muestra sólo al jugador uno. Este jugador puede: pasar y pagar 5 reparte 50-50 entre las dos rutas, hay 50% de probabilidades de
dólares al jugador dos, o apostar. que reciba una multa de $100 en la ruta A, y sólo 30% de que
reciba la misma multa en la ruta B. Desarrolle una estrategia tanto
Si el jugador uno pasa, el juego se termina, pero si apuesta, el para Robín como para la patrulla de caminos.
juego sigue y el jugador dos puede: pasar y pagar 5 dólares al
jugador uno, o apostar. 8. En un paseo campestre, 2 equipos de dos personas juegan a las
escondidas. Hay cuatro escondites (A, B, C y D) y los dos
Si el jugador dos apuesta, el árbitro le muestra la moneda; si es miembros del equipo que se esconden pueden hacerlo por
cara, el jugador dos paga 10 dólares al jugador uno; si es cruz, el separado en dos de los cuatro escondites. El otro equipo puede
jugador dos recibe 10 dólares del jugador uno. entonces buscar en los otros dos escondites restantes. El equipo
(a) Proporcione las estrategias puras de cada jugador. (Sugerencia: que busca obtiene un punto si encuentra a los dos miembros del
equipo que se esconde; si no encuentra a los dos pierde un punto. U de A3 -1 2 -2 2
De lo contrario, el resultado es un empate.
U de A4 -1 -2 4 1
*(a) Desarrolle el problema como un juego de suma cero entre dos

(a) Resuelva el juego mediante programación lineal, y determine

una estrategia para el juego de campeonato.
(b) Basado en la información dada, ¿cuál de los dos equipos se
perfila para ganar el campeonato?
personas. (c) Suponga que todo el juego constará de 60 posesiones (30 para
Investigación de Operaciones
(b) Determine la estrategia II juego
óptima y el valor del cada equipo). Pronostique el número de puntos esperado con el
cual se ganará el campeonato.
Teoría de juegos
9. La U de A y la U de D están ideando sus estrategias para el
juego de básquetbol colegial varonil del campeonato de 1994. 10. El ejército del coronel Blotto está peleando por el control de dos
Valorando las fuerzas de sus respectivas “bancas”, cada posiciones estratégicas. Blotto dispone de dos regimientos y el
entrenador aparece con cuatro estrategias para rotar a los enemigo de tres. Una posición caerá ante el ejército con más
jugadores durante el encuentro. La habilidad de cada equipo de regimientos. De lo contrario, el resultado de la batalla es un
encestar canastas de 2 puntos, 3 puntos y tiros libres es la clave empate.
para determinar el marcador final del juego. La siguiente tabla (a) Formule el problema como un juego de suma cero entre dos
resume los puntos netos que la U de A anotará por posesión como personas y resuélvalo mediante programación lineal.
una función de las diferentes estrategias disponibles para cada
equipo: (b) ¿Cuál ejército ganará la batalla?

U de U de 11. En el juego Morra de dos dedos entre dos jugadores, cada

  U de D1 D2 D3 U de D4 jugador muestra uno o dos dedos, y al mismo tiempo adivina
cuántos dedos mostrará el oponente. El jugador que adivina
U de A1 3 -2 1 2
correctamente gana una cantidad igual al número de dedos
U de A2 2 3 -3 0 mostrados. De lo contrario, el juego es un empate. Desarrolle el
problema como un juego de suma cero entre dos personas, y
resuélvalo mediante programación lineal.

12. Considere un juego de mesa entre dos personas. Cada una

comienza con tres fichas: una roja, una blanca y una azul. Cada
ficha se puede usar una sola vez. Para comenzar, cada jugador
elige una de sus fichas y la coloca sobre la mesa, tapada; después
ambos la destapan y determinan el pago para el ganador. En
particular, si ambos tienen el mismo color, es un empate; de otra
manera, la tabla que sigue indica el ganador y el pago que debe
recibir del otro jugador. En seguida, cada jugador elige una de sus
dos 󿬁chas restantes y se repite el proceso con un nuevo pago de
acuerdo con la tabla. Por último, cada jugador juega la ficha que le
queda y se determina el tercer pago, que es el final.

Ficha ganadora Pago ($)

Rojo gana a blanco 90
Blanco gana a azul 70
Azul gana a rojo 50
Fichas iguales 0

Formule este problema como un juego de suma cero entre dos

personas, e identifique la forma de las estrategias y pagos.