Optimización

Teoría de Juegos

Árboles de Juego

Representan las decisiones y sus posibles consecuencias.

Conjuntos de Información:

Indican qué información tienen los jugadores en cada punto del juego.

Estrategias:

Planes de acción que define cada jugador.

Ejercicio

Imagina un juego simple entre dos jugadores, Ana y Bob, que se turnan para elegir entre dos opciones: A o B. El juego se desarrolla en dos etapas:

• En la primera etapa, Ana elige entre A o B sin que Bob lo sepa.
• En la segunda etapa, Bob elige, sabiendo lo que Ana eligió.

Los pagos dependen de las combinaciones de elecciones. Aquí hay un ejemplo de matriz de pagos:

Ana \ Bob	A	B
A	2,1	0,3
B	3,0	1,2

1. Dibuja el Árbol de Juego

graph TD
    A[Ana] -->|A| B[Bob]
    A -->|B| C[Bob]
    B -->|A| BA((2,1))
    B -->|B| BB((3,0))
    C -->|A| CA((0,3))
    C -->|B| CB((1,2))

    style BA fill:#44f,stroke:#333,stroke-width:2px
    style BB fill:#44f,stroke:#333,stroke-width:2px
    style CA fill:#44f,stroke:#333,stroke-width:2px
    style CB fill:#44f,stroke:#333,stroke-width:2px

2. ¿Cuál sería una estrategia óptima para Ana y para Bob?

La estrategia óptima para un jugador depende de lo que espera que el otro jugador haga. Vamos a desglosar esto usando el concepto de estrategia dominante.

Para Ana:

• Si Ana cree que Bob elegirá A, entonces su mejor respuesta es elegir B (ya que 3 > 2).
• Si Ana cree que Bob elegirá B, entonces también le conviene elegir B (ya que 1 > 0).

Así que, independientemente de lo que Ana piense que hará Bob, le conviene más elegir B. Por lo tanto, elegir B es una estrategia dominante para Ana.

Para Bob:

• Si Ana elige A, a Bob le conviene más elegir B (ya que 3 > 1).
• Si Ana elige B, a Bob también le conviene más elegir B (ya que 2 > 0).

Entonces, independientemente de lo que elija Ana, a Bob le conviene más elegir B. Por lo tanto, elegir B es una estrategia dominante para Bob.

Conclusión:

La estrategia óptima para ambos jugadores en este juego es elegir siempre B. 👍

Esto nos muestra un aspecto fascinante de la teoría de juegos: a veces, la mejor estrategia no depende de lo que el otro jugador haga, sino de maximizar nuestro propio resultado en todas las situaciones posibles.

3. Si Ana elige A, ¿qué debería elegir Bob?

Si Ana elige A, la mejor opción para Bob es elegir B. Veamos por qué:

En el escenario donde Ana ha elegido A, Bob tiene dos opciones:

Elegir A, lo que resulta en un pago de 1 para él.
Elegir B, lo que resulta en un pago de 3 para él.

Dado que el objetivo de Bob es maximizar su propio pago, la opción que le da el mayor beneficio es elegir B (3 > 1). Por lo tanto, si Ana elige A, la mejor respuesta de Bob es elegir B.

Es interesante observar cómo las decisiones en la teoría de juegos a menudo dependen de las elecciones previas de otros jugadores. En este caso, la elección óptima de Bob se basa directamente en la acción inicial de Ana. 🔄

Ejercicio de Teoría de Juegos: El Dilema del Prisionero Iterado

En este ejercicio, exploraremos una variante del clásico Dilema del Prisionero, pero en una versión iterada. En el Dilema del Prisionero, dos criminales son arrestados y encarcelados en celdas separadas, sin posibilidad de comunicarse entre ellos. La policía ofrece a cada uno de ellos un trato: si uno confiesa y el otro no, el que confiesa sale libre y el otro recibe la pena máxima. Si ambos confiesan, ambos reciben una pena media. Si ninguno confiesa, ambos reciben una pena leve.

En la versión iterada, este escenario se juega varias veces seguidas, y los jugadores pueden adaptar su estrategia en función de las decisiones previas de su oponente. Preguntas del Ejercicio

Si el juego se juega exactamente tres veces, ¿cuál sería una estrategia óptima para cada jugador, asumiendo que ambos quieren minimizar su tiempo en prisión?

¿Cómo cambia tu respuesta si el número de rondas es desconocido o indefinido?

Podemos empezar por analizar la situación. Para ello podemos usar una matriz y un arbol. En este se pueden apreciar los siguientes casos

Ana\Bob	Confiesa	No Confiesa
Confiesa	50,50	0,100
No Confiesa	100,0	1,1

Codificación (Base 4):

• 0: Nadie confiesa.
• 1: Solo Ana confiesa.
• 2: Solo Bob confiesa.
• 3: Ambos confiesan.

 - 000...0: Ninguno de los dos confiesa en ninguna ronda.
 - 111...1: Ana confiesa en todas las rondas.
 - 222...2: Bob confiesa en todas las rondas.
 - 333...3: Ambos confiesan en todas las rondas.
 - Combinaciones como 0123: Representan una secuencia de decisiones variadas a lo largo del juego.

Estrategias	en base 4	3 rondas	n rondas	total
Ambos confiesan siempre	333...3	150,150	n50,n50	$100n$
Ana confiesa siempre	111...1	0,300	0,n100	$100n$
Bob confiesa siempre	222...2	300,0	n100,0	$100n$
Nadie Confiesa	000...0	3,3	n,n	$2n$
Tit 4 Tat	121212...	100,200	50n,50n	$100n$
Trust Break	012333...3	101,101	1+50(n-1),1+50(n-1)	$2+100(n-1)$
Last Confesion	000...1	2,102	n-1, 100+n-1	$100+2n-2$
Last Betray	000...3	52,52	n-1+50,n-1+50	$100+2n-2$

Juegos Bipersonales de Suma Cero

Este es un área fascinante de la teoría de juegos que trata sobre situaciones en las que lo que gana un jugador lo pierde el otro, manteniendo la suma total de las utilidades como constante (cero).

Puntos de Silla

Son situaciones en las que la elección de un jugador minimiza el máximo beneficio que el otro jugador puede obtener.

Un punto de silla es una situación en un juego bipersonal de suma cero donde la estrategia elegida por un jugador resulta en el peor resultado posible para el otro jugador, dado que ese jugador también ha elegido su mejor estrategia. En otras palabras, es un punto en la matriz de pagos donde la elección de un jugador maximiza su propio pago mínimo y al mismo tiempo minimiza el pago máximo del oponente.

Estrategias Mixtas

Cuando los jugadores eligen sus estrategias de manera aleatoria siguiendo una distribución de probabilidad.

Para encontrar las estrategias óptimas en un juego bipersonal de suma cero sin un punto de silla, a menudo recurrimos a las estrategias mixtas. Una estrategia mixta es una en la que un jugador elige aleatoriamente entre dos o más estrategias puras, con ciertas probabilidades asignadas a cada una.

Dado el juego:

Alice \ Bob	Estrategia A	Estrategia B
Estrategia 1	-1, 1	2, -2
Estrategia 2	0, 0	-1, 1

Vamos a calcular las estrategias mixtas óptimas para ambos jugadores.

1. Asignar Probabilidades a las Estrategias

   Supongamos que Alice elige la Estrategia 1 con probabilidad $p$ y la Estrategia 2 con probabilidad $1−p$. De manera similar, Bob elige la Estrategia A con probabilidad $q$ y la Estrategia B con probabilidad $1−q$.

2. Calcular los Pagos Esperados

El pago esperado para Alice, dado sus elecciones, es:

• Estrategia 1:
  • $-1·q + 2(1-q)$
• Estrategia 2:
  • $0·q + (-1)·(1-q)$
    Para que Alice esté indiferente entre sus estrategias y así maximizar su mínimo pago, estos dos pagos esperados deben ser iguales.
    Por lo tanto, igualamos las dos expresiones y resolvemos para $q$:
  • $−1q+2(1−q)=0q−1(1−q)$
    Realizando los cálculos:
  • $q=4/3​$

Entonces, Bob debería elegir la Estrategia A con una probabilidad de $3/4$​ y la Estrategia B con una probabilidad de $1/4$​.

La solución con estrategias mixtas nos dice cómo Alice y Bob pueden "aleatorizar" sus estrategias para maximizar sus pagos esperados mínimos. En este caso, encontramos la probabilidad con la que Bob debería elegir cada una de sus estrategias. Un proceso similar se aplicaría para encontrar la mezcla óptima de estrategias para Alice.

Dominancia de Estrategias

Una estrategia domina a otra si siempre resulta en un mejor (o igual) resultado, independientemente de lo que haga el otro jugador.

Solución Óptima y Equilibrio de Nash

En estos juegos, el equilibrio de Nash ocurre en puntos donde ninguno de los jugadores puede mejorar su situación cambiando unilateralmente su estrategia.

Métodos de Resolución

Para juegos matriciales pequeños, se pueden aplicar métodos analíticos para encontrar la solución óptima.

Ejercicio: Juego de Elección Estratégica

Imagina un juego entre dos jugadores, Carla y Daniel, con la siguiente matriz de pagos:

Carla \ Daniel	Estrategia X	Estrategia Y
Estrategia A	3, -3	-2, 2
Estrategia B	-1, 1	4, -4

1. Puntos de Silla

   • Comprueba si hay algún valor en la matriz que sea el mínimo en su fila y el máximo en su columna (o viceversa).

     • No tiene.

2. Estrategias Mixtas

   • Analisis de Pago Esperado:

     Si no hay un punto de silla, considera que cada jugador elige sus estrategias con ciertas probabilidades. Supongamos que Carla elige la Estrategia $A$ con probabilidad $p$ y la Estrategia $B$ con probabilidad $1−p$. Similarmente, Daniel elige la Estrategia $X$ con probabilidad $q$ y la Estrategia $Y$ con probabilidad $1−q$.

     • A: $3q-2q̚ = 3q-2(1-q) = 5q - 2$
     • B: $-q+4q̚ = -q+4(1-q) = -5q + 4$
     • X: $-3p + 1p̚ = -3p + (1-p) = -4p + 1$
     • Y: $ 2p -4p̚ = -2p - 4(1-p) = 6p - 4$

3. Igualar Pagos Esperados

   • Para encontrar las estrategias mixtas óptimas, iguala los pagos esperados de cada jugador entre sus estrategias y resuelve las ecuaciones resultantes para $p$ y $q$.
     • Para que Carla esté indiferente entre sus estrategias y así maximizar su mínimo pago, igualamos los pagos esperados de Estrategia A y B:

     • $( 5q - 2 = -5q + 4 )$
       • $( 10q - 6 = 0 )$
       • $( q = 6:10 = \frac{3}{5} )$

     • Para Daniel, igualamos los pagos esperados de Estrategia X y Y:

     • $( -4p + 1 = 6p - 4 )$
       • $(10p - 5 )$
       • $( p = 5:10 = \frac{1}{2} )$

   • Así, la estrategia mixta óptima para Carla sería elegir la Estrategia A con una probabilidad de $(\frac{1}{2})$ y la Estrategia B con una probabilidad de $(\frac{1}{2})$ . Para Daniel, sería elegir la Estrategia X con una probabilidad de $(\frac{3}{5})$
     y la Estrategia Y con una probabilidad de $(\frac{2}{5})$ .

Programación Lineal

Ejercicio: Problema de Programación Lineal

Supongamos que tienes que resolver un problema de programación lineal que involucra maximizar una función objetivo sujeta a ciertas restricciones.

El Escenario:

Imagina que eres el gerente de producción de una fábrica que produce dos tipos de productos: A y B. Para fabricar cada unidad del producto A, se necesitan 2 horas de trabajo y 3 kg de materia prima. Para el producto B, se requieren 4 horas de trabajo y 1 kg de materia prima. La fábrica dispone de un máximo de 16 horas de trabajo y 12 kg de materia prima por día. Cada unidad del producto A aporta un beneficio de 3 unidades monetarias, mientras que cada unidad del producto B aporta 4 unidades monetarias.

Objetivo:

Maximizar el beneficio diario de la fábrica.

Producto	horas	Material	Beneficio
A	2h	3kg	3u
B	4h	1kg	4u
Max	16h	12kg

• $( U = 3a + 4b )$
• $( 2a + 4b ≤ 16)$
• $( 3a + 1b ≤ 12)$
• Maximizar: $U$

Cada línea divide el plano en dos mitades: una que satisface la desigualdad (debajo o al lado de la línea) y otra que no la satisface (encima o al otro lado de la línea). La región factible, donde se superponen las áreas que satisfacen ambas desigualdades, es donde posiblemente se encuentre tu solución óptima.

Para encontrar la solución óptima, debes identificar los vértices de la región factible, que son los puntos donde se cruzan las líneas de las restricciones. Estos vértices son puntos clave porque la solución óptima a un problema de programación lineal siempre se encuentra en uno de los vértices de la región factible.

$(a,b)$	$( U(a,b) = 3a + 4b )$
(0,4)	16
(4,0)	12
(3,2)	17
(2,3)	18
(3.2,2.4)	19.2

Equilibrio de Nash en Juegos de Estrategia Simultánea

Supongamos que tienes dos empresas, A y B, que pueden elegir entre dos estrategias: Invertir en publicidad o no hacerlo. Las ganancias dependen de la elección simultánea de ambas empresas. La matriz de pagos es como sigue:

.	B invierte	B no invierte
A invierte	(2,2)	(4,1)
A no invierte	(1,4)	(3,3)

Equilibrio de Nash

Explica que un Equilibrio de Nash ocurre cuando ningún jugador tiene nada que ganar cambiando solo su propia estrategia, dado que los otros jugadores mantienen las suyas sin cambios.

.	B invierte	B change?	B no invierte
A invierte	(2,2)	←	(4,1)
A Change?	↑	.	↑
A no invierte	(1,4)	←	(3,3)

Identificación de Equilibrios

Mira cada combinación de estrategias y verifica si cambiar la estrategia beneficiaría a alguna de las empresas, asumiendo que la otra empresa no cambia la suya.

Incentivos para Desviarse

Si encuentras un Equilibrio de Nash, considera si hay incentivos externos o cambios posibles en el juego que podrían hacer que una estrategia diferente sea más atractiva.