Pagos en un juego de repetición infinita con descuento

Question

Consideremos un juego con la siguiente matriz de pagos:

3,5   0,0   0,0
0,0   5,3   0,0
0,0   0,0   0,0

Supongamos que el juego se juega infinitas veces, y que ambos jugadores tienen un factor de descuento $\delta$ .

Los jugadores quieren crear el resultado $4,4$ utilizando sólo estrategias puras. Intuitivamente, deberían alternar entre el (3,5) y el (5,3). Esto dará al jugador de la fila:

$$(1-\delta)\sum_{t=0}^\infty \delta^{2t}*3 + \delta^{2t+1}*5 = \frac{3+5\delta}{1+\delta} $$

y el jugador de la columna: $$(1-\delta)\sum_{t=0}^\infty \delta^{2t}*5 + \delta^{2t+1}*3 = \frac{5+3\delta}{1+\delta} $$

El vector de pagos va a $(4,4)$ cuando $\delta \to 1$ , pero por lo demás no es exactamente $(4,4)$ .

Estoy buscando referencias sobre las siguientes cuestiones: ¿en qué condiciones es posible alcanzar exactamente un vector de pagos deseado con sólo estrategias puras (para un juego arbitrario y un número arbitrario de jugadores)? ¿Y cómo se puede construir este vector de pagos?

He mirado algunos artículos sobre teoremas populares para juegos descontados de repetición infinita. El problema es que suelen suponer que $\delta\to 1$ lo que no siempre es cierto en la práctica.

Answer 1

Descargo de responsabilidad: sólo tengo una ligera idea sobre juegos repetidos y no tengo prácticamente ninguna idea sobre codificación (excepto las cosas obligatorias que tuve que hacer en la escuela de posgrado). Dicho esto, considere esta corriente de conciencia como la forma en que abordaría este problema (si supiera cómo codificar). No estoy seguro de que esto realmente funcione, tal vez alguien podría apoyar esta respuesta con un diagrama (que puede sugerir, no funciona, ver el comentario al final). Como ves, no puedo proporcionar una referencia. Tómenlo por lo que vale y por favor díganme si mi idea falla. Me interesa. Principalmente respondo para que esta pregunta reciba atención de nuevo.

Le interesa una estrategia que produzca un ( $\delta$ -ponderado) de 4 para ambos jugadores en el juego infinitamente repetido. Construyo una secuencia finita de perfiles estratégicos para el juego por etapas que produce una recompensa arbitrariamente cercana a 4 para ambos jugadores alternando entre el (3,5) y el (5,3). Esta secuencia se puede repetir infinitamente.

Dejemos que $\Pi^i_t$ ser jugador $i$ 's ( $\delta$ -ponderada) de la secuencia (a construir) en el paso $t$ . Dejemos que $NPV_t$ sea el valor actual neto del pago de la secuencia del jugador $i$ en la iteración $t$ tal que: $$ \Pi_t^i = NPV_t^i \frac{1-\delta}{1-\delta^{t+1}}$$

Comience con $\Pi^1_0 = NPV^1_0 =5$ y $\Pi^2_0=NPV^2_0 =3$ (por lo que se empieza con el resultado (5,3)). En cada punto de la iteración, tenemos $\Delta_t = |\Pi^1_t - 4| = |\Pi^2_t -4|$ . Entonces hay algún vector $s$ que registra si se juega el resultado (3,5) o el (5,3). Es una secuencia de $i$ s y $j$ s indicando quién tiene el 5 de pago. Así que empieza con $s_0 = 1$ (así que por la construcción posterior $s_1 = (1, 2)$ )

Toma un poco de $\delta$ como se ha dado y tomar algunas $\varepsilon >0$ .

Ahora viene la parte de codificación que intuitivamente debería funcionar:

Comienza con $t=0$ .

Si $\Delta_t > \varepsilon$ continúe.

Si $\Pi^i_t > 4$ : Set $NPV^i_{t+1} = NPV^i_{t} +3 \delta^t$ y $NPV^j_{t+1} = NPV^j_{t} +5 \delta^t$ . $s_{t+1} = s_t$ con una entrada adicional $i$ .

Una vez $\Delta_t \leq \varepsilon$ , parar y fijar $T$ igual a la actual $t$ . La repetición infinita de esta secuencia produce, por supuesto, un pago medio $\Pi^i_T$ para todos los jugadores, porque la media (ponderada) es $$\Pi^i = (1-\delta) NPV^i = (1-\delta) NPV_T \frac{1}{1-\delta^{T+1}}=\Pi^i_T.$$

Obsérvese que los pagos $\Pi_t$ puede NO converger a 4. Como no programo lo hice manualmente para algunas iteraciones para $\delta =0.9$ . $\Delta$ salta alrededor. Pero los saltos parecen ser más pequeños. A continuación, enumero los resultados $\Delta$ siguiendo este procedimiento para $t\in \{1,\dots,12\}$ . Cada vez $\Delta$ salta hacia arriba es negrita, ver que la secuencia de negrita parece disminuir.

1: 0.05263

2: 0.26199

3: 0.00552

4: 0.15558

5: 0.00995

6: 0.09293

7: 0.00115

8: 0.0692

9: 0.00561

10: 0.04549

11: 0.00023

12: 0.03765

13: 0.00345

Answer 2

Voy a construir estrategias puras, tomando como variable de estado el promedio de los pagos hasta el momento, que logran los pagos $(4,4)$ en el juego infinitamente repetido.

Llamar a las acciones del jugador de la fila $T$ , $M$ y $B$ para la parte superior, media e inferior, respectivamente. Del mismo modo, llame a las acciones del jugador de la columna $L$ , $C$ y $R$ .

Definir

$$v_i^t = \frac{1 - \delta}{1 - \delta^t} \sum_{k = 0}^{t-1} \delta^k u_i (a^k)$$

para $t \geq 1$ , donde $a^t$ es el perfil de acción realizado en la etapa $t$ . Claramente, $v_i^t$ es la retribución media obtenida por el jugador $i$ de todos los períodos anteriores $t$ .

Ahora, define las estrategias de forma inductiva:

$$ a^0 = (T,L) $$ $$ a^1 = (M,C) $$ $$ \vdots $$ $$ a^t = \begin{cases} (T,L) & \text{if }v_1^t \ge v_2^t \\ (M,C) & \text{if }v_1^t < v_2^t \end{cases} $$

Es sencillo demostrar que $v_i^t$ converge (las secuencias monótonas acotadas convergen), y que $v_i^t \to 4$ . (Supongamos que no, y entonces consideremos las acciones resultantes para grandes $t$ .)

También es fácil ver que estas estrategias forman un equilibrio subjuego perfecto.

En cuanto a tu pregunta más general, en cuanto a qué condiciones garantizan que un determinado vector de pagos puede ser soportado por algún equilibrio en estrategias puras:

Quiero decir que todos los pagos de equilibrio pueden ser apoyados con estrategias puras por una construcción similar a la dada anteriormente -- al menos, en juegos repetidos de información completa con monitoreo perfecto(*). Sin embargo, admito que no he pensado en esto con mucho cuidado, ni he visto este resultado formalmente en ningún sitio, así que advertencia a los interesados ¿supongo? Como mínimo, debería ser capaz de soportar cualquier resultado que se encuentre en el casco convexo de la estrategia pura del juego por etapas NE.

(*) El resultado "bang-bang" de Abreu, Pearce y Stachetti debería extenderse, bajo algunas condiciones, al caso de un control público imperfecto.