Trabajo de Io2teoria de Juegos
-
Upload
juan-jpayehuanca -
Category
Documents
-
view
37 -
download
0
Transcript of Trabajo de Io2teoria de Juegos
INVESTIGACIÓN DE OPERACIONES II
EQUIPO DE TRABAJO:ALEJO ÑAHUIN SAMUEL HUGOATAUCURI CASANOVA YANCARLO
GAMARRA TERAN CHARLES
PINTO HERRERA YHOEL HAROLD
PAYEHUANCA RAMOS, JUAN
INVESTIGACIÓN DE OPERACIONES II
APLICACIÓN PRACTICA DE TEORÍA DE JUEGOS
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
TEORIA DE JUEGOS
EJEMPLO # 1
1. “Compañía contra sindicato”
1.1 Estrategia Pura
En el año 2011 el sindicato de La Iberica entro en huelga, exigiendo el aumento de cuatro soles diarios, la
instalación de un comedor, refrigerio para los trabajadores del turno noche y un centro médico
Simulando el problema como si fuese un caso actual
Teniendo la suposición de hubiéramos formado parte del grupo de gerentes que está a cargo determinar la estrategia
que deben seguir durante las negociaciones. Después de considerar la experiencia en otros años, se está de acuerdo
en que las estrategias factibles para la compañía son:
C1 = Negociaciones agresivas. (si o si)
C2 = Estrategia conciliatoria
C3 = Estrategia permisiva
¿Cuál es la mejor estrategia para la compañía?
Solución:
La respuesta dependió de la estrategia que elija el sindicato, la cual no se conoce. Pero se puede suponer, por los
antecedentes del sindicato, que puede usar uno de los siguientes procedimientos:
U1 = Negociaciones agresivas.
U2 = Estrategia conciliatoria
U3 = Estrategia permisiva
Ahora hay que considerar las consecuencias de cada una de las estrategias, condicionadas por el hecho de que el
sindicato adopte una de sus estrategias posibles. Con ayudar de un mediador externo, logramos construir la siguiente
tabla # 1:
1
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Tabla # 1: “Ganancias condicionales del sindicato (costos para la compañía en soles)”
Estrategias
del Sindicato
Estrategias de la Compañía Maximos de las
filas
C1 C3 C4
U1 2.5 3.5 5 5
U2 1 2.5 3.5 3.5
U3 0.5 1.5 3 3
Minimos de las
columnas 0.5 1.5 3
Haciendo uso de la estrategia Minimax y maximin, la compañía podría adoptar la estrategia que maximice el menor
aumento de salarios que tendría que otorgar, sin importar la acción del sindicato. Si el sindicato sigue esta regla,
escogería la estrategia que minimice el aumento máximo de los salarios.
Como se ve en el ejemplo, la estrategia tiene punto de equilibrio por lo que por mutuo acuerdo se puede llegar al
aumento de S/3.00 nuevos soles por trabajador y con la promesa de instalar un comedor y dar refrigerio a
trabajadores del turno de la noche para el siguiente año
Estrategias mixtas
Supongamos que los sindicatos piden una nueva negociación esta vez adoptan una postura mas agresiva pidiendo
mayores aumentos
Realizamos nuevamente el análisis MINIMAX y MAXIMIN
Estrategias
del Sindicato
Estrategias de la Compañía Maximos de las
filas
C1 C2 C3
U1 4 3 3.5 4
U2 2 2.5 4 4
U3 1.5 3.5 6 6
Minimos de las
columnas 1.5 2.5 3.5
En este caso haremos uso de estrategias mixtas al no existir punto de equilibrio
1.2 Estrategias Mixtas
2
3
3
4
3.5
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Tabla # 2: “Ganancias condicionales del sindicato (costos para la compañía en centavos)”
Estrategias
del Sindicato
Estrategias de la
Compañía
Maximos de las
filas
C1 C2
U1 4 3 4
U2 2 2.5 4
Minimos de las
columnas 1.5 2.5
También la fila U3 queda descartada porque el sindicato de trabajadores ya no asumen una posición permisiva.
Tabla # 2: “Estrategias no dominadas”
Ahora el objetivo es obtener una estrategia mixta que mejore la posición de las dos partes con respecto a las
estrategias puras disponibles. Entonces, tenemos:
A) Análisis de Probabilidades:
Valor de U1 = Valor de U3
V U1 = V U3
4 Q1 + 3 (1 – Q1) = 2 Q1 + 2.5 (1 – Q1)
4 Q1 + 3 – 3 Q1 = 2 Q1 + 2.5 – 2.5 Q1
3 + Q1 = 2.5 – 0.5 Q1
1.5 Q1 = -0.5
3
Estrategias
del Sindicato
Estrategias de la
Compañía
C1 C2
U1 4 3
U2 2 2.5
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Valor de C2 = Valor de C3
V C2 = V C3
4 P1 + 2 (1 – P1) = 3 P1 + 2.5 (1 – P1)
4 P1 + 2 – 2 P1 = 3 P1 + 2.5 – 2.5 P1
2 + 2 P1 = 2.5 + 0.5 P1
1.5 P1 = 0.5
B) Análisis de cruce de Probabilidades:
Valor de juego para el Sindicato:
V = 4 (1/3) + 2 (2/3) = 2.666
V = 3 (1/3) + 2.5 (2/3) = 2.666
Valor de juego para la Compañía:
V = 4 (-1/3) + 3 (4/3) = 2,666
V = 2 (-1/3) + 2.5 (4/3) = 2.6666
Con la nueva negociación el aumento optimo permitido por parte de la empresa es de S/2.66 nuevos soles por cada
trabajador, que es menor a la primera negociación, como tal, nos lleva a la conclusión de que la estrategia mixta da
como resultado el menor costo máximo para la compañía y el mayor aumento mínimo para el sindicato
4
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
EJEMPLO # 2
2.1 Estrategia De Von Newman
El general Luis Valdivia López tenia la opción de llevar su producción para el reconocimiento de sus nuevos
clientes, en este caso le ofrece que lleve la producción por tres rutas que son Y 1, Y2, Y3 una vez localizado se verá
cual de las tres rutas escogidas por el general será la mejor.
a. Función objetivo
Y1 Y2 Y3
4 7 2 1
5 8 3 1
2 1 4 1
[1 1 1]
Estandarizar
Max (Z) = Y1 + Y2 + Y3 + U1 + U2 + U3
b. Restricciones
4Y1 + 7Y2 + 2Y3 <= 1
5Y1 + 8Y2 + 3Y3 <= 1
2Y1 + 1Y2 + 4Y3 <=1
c. Solución Simplex
Cj 1 1 1 0 0 0 Ratio
ck kk B Y1 Y2 Y3 U1 U2 U3
0 U1 1,0 4 7 2,0 1,0 0,0 0,0 0,3
0 U2 1,0 5 8 3,0 0,0 1,0 0,0 0,2
0 U3 1,0 2 1 4,0 0,0 0,0 1,0 0,5
Zj -> 0 0 0 0,0 0,0 0,0 0,0 El+
Cj – Zj 1 1 1,0 0,0 0,0 0,0 <R+
0 U1 1,0 0 -9,0 -8,5 1,0 -0,5 0,0 -0,1
1 Y1 5,0 0 5,5 -13,0 0,0 1,0 -0,5 -0,4
0 U3 1,0 1 0,5 2,0 0,0 0,0 0,5 0,5
Zj -> 0,6 0 5,5 -13 0,0 1,0 -0,5 El+
5
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Cj - Zj -> 1,00 -4,50 14,00 0,00 -1,00 0,50 <R+
0 U1 1,0 0,0 14,4 0,0 1,0 -1,0 0,0 indef
1 Y1 5,0 -2,8 8,8 0,0 0,0 1,0 -1,0 -5,0
1 Y3 0,5 0,5 0,3 1,0 0,0 0,0 0,3 2,0
Zj -> 5,5 2 9,0 1,0 0,0 1,0 -0,8
Cj - Zj -1 -8 0 0 -1 1 <=(S.O)
0 U1 1,0 -134 14,4 0,0 1,0 -1,0 0,0 0,0
1 Y1 5,0 12,0 8,8 0,0 0,0 1,0 0,0 0,4
0 U3 2,0 2,0 1,0 3,0 0,0 0,0 1,0 1,0
Zj -> 7,0 12,0 8,8 0,0 0,0 1,0 0,0
Cj - Zj -11,0 -7,8 1,0 0,0 -1,0 0,0 <=(S.O)
0 U1 1,0 -192 14,40 0,0 1,0 -1,3 0,0
1 Y1 5,0 6,13 8,8 0,0 0,0 0,0 0,3
1 Y1 1,0 0,7 0,3 1,0 0,0 0,0 0,3
Zj -> 6,0 6,8 9,1 1,0 0,0 0,0 0,7
Cj - Zj -6 -8 0 0 0 -1 <=(S.O)
d. Beneficio Neto
VB = ½ = 1/6 = 0.1667
VA = VB - Z
VA = 1-6
VA= -5
Si el general escoge la segunda ruta entonces la producción no llega bien a los clientes y este tendrá una perdida
de $.5’000.000.00
5.- Análisis
VB = ½ = 1/6 = 0.1667
VA = VB /Z
Optimizando las rutas escogidas para optimizar las ganancias llegando al máximo rendimiento.
Y*= [ Y1 , Y2 , Y3] = [1 1 1]
G* = VY* = 0.17 [1 1 1] = [0.17 0.17 0.17 ]
X* = [X1 , X2 , X3]= [1 1 1]
Q *= VX* = 0.17[1 1 1]= [0.17 0.17 0.17]
6
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
CONCLUSIONES
El problema general de cómo tomar una decisión en un medio competitivo es bastante común e
importante, pero por por lo general no se hace uso de métodos para optimizar las decisiones, sino se limitan
a decisiones empiricas
La contribución general de la Teoría de Juegos es que proporciona un marco conceptual básico para
formular y analizar los problemas de cómo tomar una decisión en situaciones sencillas.
Existe un gran abismo entre lo que la teoría puede manejar y la complejidad de la mayor parte de las
situaciones de competencia que surgen en la practica.
Las herramientas conceptuales de la teoría de Juegos por lo general desempeñan un papel suplementario
cuando se aplican en las situaciones de competencia que surgen en la práctica.
7
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Bibliografía
Libro : Investigación de Operaciones
Autor : Hamdy A. Taha
Edición : 7ma Edicion
Libro : Métodos y modelos de investigación de operaciones
Autor : Juan Prawda,Juan Prawda Witenberg
Edición : 1ra Edicion
Libro : Manual de investigación de operaciones
Autor : Angel león Gonzales Ariza
Edición : 3ra Edicion
Libro : Formulación y solución de casos de investigación de operaciones
Autor : Elizabeth Coto de Morales
Edición : Única edición 2004
8
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
ANEXOS 1
Historia de la teoría de juegos
La primera discusión conocida de la teoría de juegos aparece en una carta escrita por James Waldegrave en 1713. En
esta carta, Waldegrave proporciona una solución minimax de estrategia mixta a una versión para dos personas del
juego de cartas le Her. Sin embargo no se publicó un análisis teórico de teoría de juegos en general hasta la
publicación de Recherches sur les príncipes mathématiques de la théorie des richesses, de Antoine Augustin
Cournot en 1838. En este trabajo, Cournot considera un duopolio y presenta una solución que es una versión
restringida del equilibrio de Nash.
Aunque el análisis de Cournot es más general que el de Waldegrave, la teoría de juegos realmente no existió como
campo de estudio aparte hasta que John von Neumann publicó una serie de artículos en 1928. Estos resultados
fueron ampliados más tarde en su libro de 1944, The Theory of Games and Economic Behavior, escrito junto con
Oskar Morgenstern. Este trabajo contiene un método para encontrar soluciones óptimas para juegos de suma cero de
dos personas. Durante este período, el trabajo sobre teoría de juegos se centró, sobre todo, en teoría de juegos
cooperativos. Este tipo de teoría de juegos analiza las estrategias óptimas para grupos de individuos, asumiendo que
pueden establecer acuerdos entre sí acerca de las estrategias más apropiadas.
En 1950, aparecieron las primeras discusiones del dilema del prisionero, y se emprendió un experimento acerca de
este juego en la corporación RAND. Alrededor de esta misma época, John Nash desarrolló una definición de una
estrategia óptima para juegos de múltiples jugadores donde el óptimo no se había definido previamente, conocido
como equilibrio de Nash. Este equilibrio es suficientemente general, permitiendo el análisis de juegos no
cooperativos además de los juegos cooperativos.
La teoría de juegos experimentó una notable actividad en la década de 1950, momento en el cual los conceptos base,
el juego de forma extensiva, el juego ficticio, los juegos repetitivos, y el valor de Shapley fueron desarrollados.
Además, en ese tiempo, aparecieron las primeras aplicaciones de la teoría de juegos en la filosofía y las ciencias
políticas.
En 1965, Reinhard Selten introdujo su concepto de solución de los equilibrios perfectos del subjuego, que más
adelante refinó el equilibrio de Nash. En 1967 John Harsanyi desarrolló los conceptos de la información completa y
de los juegos bayesianos. Él, junto con John Nash y Reinhard Selten, ganaron el Premio Nobel de Economía en
1994.
En la década de 1970 la teoría de juegos se aplicó extensamente a la biología, en gran parte como resultado del
trabajo de John Maynard Smith y su concepto estrategia estable evolutiva. Además, los conceptos del equilibrio
correlacionado, la perfección del temblor de la mano, y del conocimiento común fueron introducidos y analizados.5
En 2005, los teóricos de juegos Thomas Schelling y Robert Aumann ganaron el premio Nobel de Economía.
Schelling trabajó en modelos dinámicos, los primeros ejemplos de la teoría de juegos evolutiva. Por su parte,
Aumann contribuyó más a la escuela del equilibrio.
9
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
En el 2007, Roger Myerson, junto con Leonid Hurwicz y Eric Maskin, recibieron el premio Nobel de Economía por
"sentar las bases de la teoría de diseño de mecanismos."
La Teoría de Juegos
La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en
estructuras formalizadas de incentivos (los llamados juegos) y llevar a cabo procesos de decisión. Sus investigadores
estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos. Tipos de
interacción aparentemente distintos pueden, en realidad, presentar estructuras de incentivos similares y, por lo tanto,
se puede representar mil veces conjuntamente un mismo juego.
Desarrollada en sus comienzos como una herramienta para entender el comportamiento de la economía, la teoría de
juegos se usa actualmente en muchos campos, desde la biología a la filosofía. Experimentó un crecimiento
sustancial y se formalizó por primera vez a partir de los trabajos de John von Neumann y Oskar Morgenstern, antes
y durante la Guerra Fría, debido sobre todo a su aplicación a la estrategia militar —en particular a causa del
concepto de destrucción mutua garantizada. Desde los setenta, la teoría de juegos se ha aplicado a la conducta
animal, incluyendo el desarrollo de las especies por la selección natural. A raíz de juegos como el dilema del
prisionero, en los que el egoísmo generalizado perjudica a los jugadores, la teoría de juegos se ha usado en
economia, ciencias políticas, ética y filosofía. Finalmente, ha atraído también la atención de los investigadores en
informática, usándose en inteligencia artificial y cibernética.
Aunque tiene algunos puntos en común con la teoría de la decisión, la teoría de juegos estudia decisiones realizadas
en entornos donde interaccionan. En otras palabras, estudia la elección de la conducta óptima cuando los costes y los
beneficios de cada opción no están fijados de antemano, sino que dependen de las elecciones de otros individuos. Un
ejemplo muy conocido de la aplicación de la teoría de juegos a la vida real es el dilema del prisionero, popularizado
por el matemático Albert W. Tucker, el cual tiene muchas implicaciones para comprender la naturaleza de la
cooperación humana. La teoría psicológica de juegos, que se arraiga en la escuela psicoanalítica del análisis
transaccional, es enteramente distinta.
Los analistas de juegos utilizan asiduamente otras áreas de la matemática, en particular las probabilidades, las
estadísticas y la programación lineal, en conjunto con la teoría de juegos. Además de su interés académico, la teoría
de juegos ha recibido la atención de la cultura popular. La vida del matemático teórico John Forbes Nash,
desarrollador del Equilibrio de Nash y que recibió un premio Nobel , fue el tema de la biografía escrita por Sylvia
Nasar, Una mente brillante (1998), y de la película del mismo nombre (2001). Varios programas de televisión han
explorado situaciones de teoría de juegos, como el concurso de la televisión de Cataluña (TV3) Sis a traïció (seis a
traición), el programa de la televisión estadounidense Friend or foe? (¿Amigo o enemigo?) y, hasta cierto punto, el
concurso Supervivientes.
10
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Tipos de juegos y ejemplos
La teoría clasifica los juegos en muchas categorías que determinan qué métodos particulares se pueden aplicar para
resolverlos (y, de hecho, también cómo se define "resolución" en una categoría particular). Las categorías comunes
incluyen:
Juegos simétricos y asimétricos [editar]
Un juego simétrico es un juego en el que las recompensas por jugar una estrategia en
particular dependen sólo de las estrategias que empleen los otros jugadores y no de quién
las juegue. Si las identidades de los jugadores pueden cambiarse sin que cambien las
recompensas de las estrategias, entonces el juego es simétrico. Muchos de los juegos 2×2
más estudiados son simétricos. Las representaciones estándar del juego de la gallina, el
dilema del prisionero y la caza del ciervo son juegos simétricos.2
Los juegos asimétricos más estudiados son los juegos donde no hay conjuntos de estrategias idénticas para ambos
jugadores. Por ejemplo, el juego del ultimátum y el juego del dictador tienen diferentes estrategias para cada
jugador; no obstante,
puede haber juegos asimétricos con estrategias idénticas para cada jugador. Por ejemplo, el juego mostrado a la
derecha es asimétrico a pesar de tener conjuntos de estrategias idénticos para ambos jugadores.
Juegos de suma cero y de suma no cero
En los juegos de suma cero el beneficio total para todos los jugadores del juego, en
cada combinación de estrategias, siempre suma cero (en otras palabras, un jugador
se beneficia solamente a expensas de otros). El go, el ajedrez, el póker y el juego del
oso son ejemplos de juegos de suma cero, porque se gana exactamente la cantidad
que pierde el oponente. Como curiosidad, el fútbol dejó hace unos años de ser de
suma cero, pues las victorias reportaban 2 puntos y el empate 1 (considérese que
ambos equipos parten inicialmente con 1 punto), mientras que en la actualidad las
victorias reportan 3 puntos y el empate 1.
La mayoría de los ejemplos reales en negocios y política, al igual que el dilema del prisionero, son juegos de suma
no cero, porque algunos desenlaces tienen resultados netos mayores o menores que cero. Es decir, la ganancia de un
jugador no necesariamente se corresponde con la pérdida de otro. Por ejemplo, un contrato de negocios involucra
idealmente un desenlace de suma positiva, donde cada oponente termina en una posición mejor que la que tendría si
no se hubiera dado la negociación.
11
E F
E 1, 2 0, 0
F 0, 0 1, 2
Un juego asimétrico
A B C
1 30, -30 -10, 10 20, -20
2 10, -10 20, -20 -20, 20
Un juego de suma cero
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
Se puede analizar más fácilmente un juego de suma cero, y cualquier juego se puede transformar en un juego de
suma cero añadiendo un jugador "ficticio" adicional ("el tablero" o "la banca"), cuyas pérdidas compensen las
ganancias netas de los jugadores.
La matriz de pagos de un juego es una forma conveniente de representación. Por ejemplo, un juego de suma cero de
dos jugadores con la matriz que se muestra a la derecha.
Juegos cooperativos
Un juego cooperativo se caracteriza por un contrato que puede hacerse cumplir. La teoría de los juegos cooperativos
da justificaciones de contratos plausibles. La plausibilidad de un contrato está muy relacionada con la estabilidad.
Dos jugadores negocian qué tanto quieren invertir en un contrato. La teoría de la negociación axiomática nos
muestra cuánta inversión es conveniente para nosotros. Por ejemplo, la solución de Nash para la negociación
demanda que la inversión sea justa y eficiente.
De cualquier forma, podríamos no estar interesados en la justicia y exigir más. De hecho, existe un juego no-
cooperativo creado por Ariel Rubinstein consistente en alternar ofertas, que apoya la solución de Nash
considerándola la mejor, mediante el llamado equilibrio de Nash.
Simultáneos y secuenciales
Los juegos simultáneos son juegos en los que los jugadores mueven simultáneamente o en los que éstos desconocen
los movimientos anteriores de otros jugadores. Los juegos secuenciales (o dinámicos) son juegos en los que los
jugadores posteriores tienen algún conocimiento de las acciones previas. Este conocimiento no necesariamente tiene
que ser perfecto; sólo debe consistir en algo de información. Por ejemplo, un jugador1 puede conocer que un
jugador2 no realizó una acción determinada, pero no saber cuál de las otras acciones disponibles eligió.
La diferencia entre juegos simultáneos y secuenciales se recoge en las representaciones discutidas previamente. La
forma normal se usa para representar juegos simultáneos, y la extensiva para representar juegos secuenciales.
Juegos de información perfecta
Un juego de información imperfecta (las líneas punteadas
representan la ignorancia de la parte del jugador 2)
Un subconjunto importante de los juegos secuenciales es el
conjunto de los juegos de información perfecta. Un juego
es de información perfecta si todos los jugadores conocen
los movimientos que han efectuado previamente todos los
otros jugadores; así que sólo los juegos secuenciales pueden ser juegos de información perfecta, pues en los juegos
simultáneos no todos los jugadores (a menudo ninguno) conocen las acciones del resto. La mayoría de los juegos
estudiados en la teoría de juegos son juegos de información imperfecta, aunque algunos juegos interesantes son de
12
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
información perfecta, incluyendo el juego del ultimátum y el juego del ciempiés. También muchos juegos populares
son de información perfecta, incluyendo el ajedrez y el go.
La información perfecta se confunde a menudo con la información completa, que es un concepto similar. La
información completa requiere que cada jugador conozca las estrategias y recompensas del resto pero no
necesariamente las acciones.
En los juegos de información completa cada jugador tiene la misma "información relevante al juego" que los demás
jugadores. El ajedrez y el dilema del prisionero ejemplifican juegos de información completa. Los juegos de
información completa ocurren raramente en el mundo real, y los teóricos de los juegos, usualmente los ven sólo
como aproximaciones al juego realmente jugado.
John Conway desarrolló una notación para algunos juegos de información completa y definió varias operaciones en
esos juegos, originalmente para estudiar los finales de go, aunque buena parte de este análisis se enfocó en nim. Esto
devino en la teoría de juegos combinatoria. Descubrió que existe una subclase de esos juegos
que pueden ser usados como números, como describió en su libro On Numbers and Games, llegando a la clase muy
general de los números surreales.
Juegos de longitud infinita (SuperJuegos)
Por razones obvias, los juegos estudiados por los economistas y los juegos del mundo real finalizan generalmente
tras un número finito de movimientos. Los juegos matemáticos puros no tienen estas restricciones y la teoría de
conjuntos estudia juegos de infinitos movimientos, donde el ganador no se conoce hasta que todos los movimientos
se conozcan.
El interés en dicha situación no suele ser decidir cuál es la mejor manera de jugar a un juego, sino simplemente qué
jugador tiene una estrategia ganadora (Se puede probar, usando el axioma de elección, que hay juegos —incluso de
información perfecta, y donde las únicas recompensas son "perder" y "ganar"— para los que ningún jugador tiene
una estrategia ganadora.) La existencia de tales estrategias tiene consecuencias importantes en la teoría descriptiva
de conjuntos
13
INVESTIGACION DE OPERACIONES II | Teoria de Juegos
ANEXO 2
14