UNIVERSIDAD BICENTENARIA DE ARAGUA
FACULTAD DE INGENIERÍA
ESCUELA DE INGENIERÍA
DE SISTEMAS
NUCLEO PUERTO ORDAZ
CATEDRA:
SISTEMAS OPERATIVOS
|
Profesora:
Bachilleres:
Ricardo Guevara Diego Pérez C.I.19.301.665
Oswaldo Patriz
C.I. 20.885.097
Teoría de Juegos
La
Teoría de Juegos consiste en la elaboración de recomendaciones sobre la forma
razonable de las acciones de cada uno de los contrincantes en el curso de una situación
de conflicto; es prácticamente una teoría matemática de las situaciones en
conflicto. En un conflicto de juego los dos oponentes son llamados jugadores y
cada uno de ellos tendrá un número finito o infinito de estrategias; a cada
estrategia se encuentra asociada una recompensa que un jugador paga a otro.
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 estructura de incentivo similar y, por lo tanto, se puede
representar mil veces conjuntamente un mismo juego.
Forma normal de un juego
La
forma normal (o forma estratégica) de un juego es una matriz de pagos, que
muestra los jugadores, las estrategias, y las recompensas. Hay dos tipos de
jugadores; uno elige la fila y otro la columna. Cada jugador tiene dos
estrategias, que están especificadas por el número de filas y el número de
columnas. Las recompensas se especifican en el interior. El primer número es la
recompensa recibida por el jugador de las filas (el Jugador 1 en nuestro
ejemplo); el segundo es la recompensa del jugador de las columnas (el Jugador 2
en nuestro ejemplo). Si el jugador 1 elige arriba y el jugador 2 elige
izquierda entonces sus recompensas son 4 y 3, respectivamente.
Cuando
un juego se presenta en forma normal, se presupone que todos los jugadores
actúan simultáneamente o, al menos, sin saber la elección que toma el otro. Si
los jugadores tienen alguna información acerca de las elecciones de otros
jugadores el juego se presenta habitualmente en la forma extensiva.
También
existe una forma normal reducida. Ésta combina estrategias asociadas con el
mismo
pago.
Forma extensiva de un juego
La
representación de juegos en forma extensiva modela juegos con algún orden que
se debe considerar. Los juegos se presentan como árboles. Cada vértice o nodo
representa un punto donde el jugador toma decisiones. El jugador se especifica
por un número situado junto al vértice. Las líneas que parten del vértice
representan acciones posibles para el jugador. Las recompensas se especifican
en las hojas del árbol.
En el
juego que se muestra en el ejemplo hay dos jugadores. El jugador 1 mueve
primero y elige F o U. El jugador 2 ve el movimiento del jugador 1 y elige A o
R. Si el jugador 1 elige U y entonces el jugador 2 elige A, entonces el jugador
1 obtiene 8 y el jugador 2 obtiene 2.
Los
juegos en forma extensiva pueden modelar también juegos de movimientos
simultáneos. En esos casos se dibuja una línea punteada o un círculo alrededor
de dos vértices diferentes para representarlos como parte del mismo conjunto de
información (por ejemplo, cuando los jugadores no saben en qué punto se
encuentran).
La
forma normal da al matemático una notación sencilla para el estudio de los
problemas de equilibrio, porque desestima la cuestión de cómo las estrategias
son calculadas o, en otras palabras, de cómo el juego es jugado en realidad. La
notación conveniente para tratar estas cuestiones, más relevantes para la
teoría combinatoria de juegos, es la forma extensiva del
juego.
Juegos de Suma 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 futbol, 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.
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 continuación.
La
matriz de recompensas de un juego es una forma de representación conveniente.
Considérese el ejemplo del juego de suma cero mostrado a continuación:
|
A
|
B
|
C
|
|
|
1
|
30, -30
|
-10, 10
|
20, -20
|
|
2
|
10, -10
|
20, -20
|
-20, 20
|
|
Un juego de suma cero
|
|||
El
orden de juego es el siguiente: el primer jugador elige en secreto una de las
dos acciones 1 o 2; el segundo jugador; sin conocer la elección del primero,
elige en secreto una de las tres acciones A, B o C. Entonces se revelan las
elecciones de cada jugador y el total de puntos se ve afectado de acuerdo a la
recompensa por tales elecciones.
Ejemplo:
el primer jugador elige 2 y el segundo elige B. Cuando se asignan las
recompensas, el primer jugador gana 20 puntos y el segundo pierde 20 puntos.
En
este ejemplo los dos jugadores conocen la matriz de recompensas y tratan de
maximizar sus puntos, ¿Qué deben hacer?
El
jugador 1 puede razonar de la siguiente forma: "con la acción 2, puedo
perder 20 puntos y ganar sólo 20, mientras que con la 1 puedo perder sólo 10
pero puedo ganar 30, así que 1 parece mucho mejor." Con un razonamiento
similar, 2 elegirá C. Si los dos jugadores toman esas elecciones, el primer
jugador ganará 20 puntos. ¿Pero qué pasa si el jugador 2 anticipa el
razonamiento de 1, y elige B, para ganar 10 puntos? ¿o si el primer jugador
anticipa este truco y elige 2, para ganar 20 puntos?
Para
el ejemplo de arriba, resulta que el primer jugador debe de elegir 1 con
probabilidad 57%, y la acción 2 con probabilidad 43%, mientras que el segundo
debería asignar las probabilidades 0%, 57% y 43% a las tres opciones A, B y C.
El
jugador 1 ganará entonces 2.85 puntos de media por juego.
Solución por Programación Lineal
Pasos
del método de la programación lineal para determinar la estrategia aleatorizada
Óptima.
1.
Determine la matriz de recompensa R.
2. Si
R tiene elementos no positivos, forme Rʼ
sumando una constante a cada elemento de R. Si E y Eʼ constituyen los
valores esperados del juego asociados con las matrices de recompensa R y Rʼ,
respectivamente, entonces Eʼ = E + (La Constante añadida).
3. Si
el jugador renglón adopta una estrategia aleatorizada, donde las probabilidades
de selecciones de los renglones 1 a n son P1 a Pnʼ respectivamente, entonces:
Pr = [
P1 P2 …. Pn ] donde P1 + P2 +…. + Pn = 1
Si el
jugador columna adopta una estrategia pura, los valores esperados de dichas
estrategias puras se incluyen en la matriz.
E
(Pura)= Pr * Rʼ
Calcule
E (Pura)
4.
Resuelva P1 + P2 +…. + Pn = 1 para Pn = 1 y sustituya el resultado en E (Pura).
5. El
valor esperado Eʼ del juego es menor o
igual que cada uno de los elementos de la matriz del paso 4. Cada una de esas
desigualdades resultantes constituye una restricción en el problema de
programación lineal. Liste estas restricciones.
6.
Cada una de las probabilidades P1, P2, P3 , … debe ser menor o igual que 1.
Liste estas restricciones.
7. Establezca
el objetivo, que consiste en obtener el valor máximo de Z= Eʼ.
8. Resuelva
el problema de programación lineal y determine los valores de P1 P2 …. Pn, y Eʼ.
9.
Describa la estrategia aleatorizada óptima del jugador renglón proporcionando
la probabilidad con la que el jugador debería elegir cada renglón.
10.
Reste la constante del paso 2 de Eʼ para obtener E, el valor esperado del
juego.
EJEMPLO: JUEGO DE DOS
JUGADORES DE SUMA NULA
http://www.youtube.com/watch?v=wixlx1R4IE8
http://www.youtube.com/watch?v=zFTS_ZOSnhU
No hay comentarios:
Publicar un comentario