Clase de teoremas sobre los perfiles de pagos del equilibrio de Nash en juegos repetidos
En teoría de juegos , los teoremas populares son una clase de teoremas que describen una gran cantidad de perfiles de pagos de equilibrio de Nash en juegos repetidos (Friedman 1971). [1] El teorema popular original se refería a los pagos de todos los equilibrios de Nash de un juego repetido infinitamente. Este resultado se denominó teorema popular porque era ampliamente conocido entre los teóricos de juegos en la década de 1950, aunque nadie lo había publicado. El teorema de Friedman (1971) se refiere a los pagos de ciertos equilibrios de Nash perfectos en subjuegos (SPE) de un juego repetido infinitamente, y por lo tanto fortalece el teorema popular original al utilizar un concepto de equilibrio más fuerte: equilibrios de Nash perfectos en subjuegos en lugar de equilibrios de Nash. [2]
El teorema de Folk sugiere que si los jugadores son lo suficientemente pacientes y previsores (es decir, si el factor de descuento ), entonces la interacción repetida puede resultar en prácticamente cualquier pago promedio en un equilibrio SPE. [3] "Prácticamente cualquiera" se define aquí técnicamente como "factible" e "individualmente racional".
Configuración y definiciones
Comenzamos con un juego básico , también conocido como el juego de escenario , que es un juego de n jugadores . En este juego, cada jugador tiene un número finito de acciones para elegir, y hace sus elecciones simultáneamente y sin conocimiento de las elecciones del otro jugador. Las elecciones colectivas de los jugadores conducen a un perfil de pagos, es decir, a un pago para cada uno de los jugadores. La correspondencia entre las elecciones colectivas y los perfiles de pagos es conocida por los jugadores, y cada jugador tiene como objetivo maximizar su pago. Si la elección colectiva se denota por x, el pago que recibe el jugador i , también conocido como la utilidad del jugador i , se denotará por .
A continuación, consideramos una repetición de este juego de etapa, finita o infinitamente veces. En cada repetición, cada jugador elige una de sus opciones de juego de etapa y, al hacer esa elección, puede tener en cuenta las elecciones de los otros jugadores en las iteraciones anteriores. En este juego repetido, una estrategia para uno de los jugadores es una regla determinista que especifica la elección del jugador en cada iteración del juego de etapa, en función de las elecciones de todos los demás jugadores en las iteraciones anteriores. La elección de estrategia para cada uno de los jugadores es un perfil de estrategia y conduce a un perfil de pago para el juego repetido. Hay varias formas diferentes en las que un perfil de estrategia de este tipo se puede traducir en un perfil de pago, que se describen a continuación.
Cualquier perfil de pagos de equilibrio de Nash de un juego repetido debe satisfacer dos propiedades:
- Racionalidad individual : el resultado debe dominar débilmente el perfil de resultados minmax del juego de la etapa constituyente. Es decir, el resultado de equilibrio de cada jugador debe ser al menos tan grande como el resultado minmax de ese jugador. Esto se debe a que un jugador que logra menos que su resultado minmax siempre tiene incentivos para desviarse simplemente jugando su estrategia minmax en cada historia.
- Viabilidad : el pago debe ser una combinación convexa de los posibles perfiles de pago del juego de etapa. Esto se debe a que el pago en un juego repetido es simplemente un promedio ponderado de los pagos en los juegos básicos.
Los teoremas populares son afirmaciones parcialmente inversas: dicen que, bajo ciertas condiciones (que son diferentes en cada teorema popular), cada perfil de pagos que sea individualmente racional y factible puede realizarse como un perfil de pagos de equilibrio de Nash del juego repetido.
Existen varios teoremas populares; algunos se relacionan con juegos que se repiten un número finito de veces, mientras que otros se relacionan con juegos que se repiten un número infinito de veces. [4]
Juegos repetidos infinitamente sin descuento
En el modelo no descontado, los jugadores son pacientes y no diferencian entre utilidades en diferentes períodos de tiempo. Por lo tanto, su utilidad en el juego repetido está representada por la suma de las utilidades en los juegos básicos.
Cuando el juego es infinito, un modelo común para la utilidad en el juego repetido infinitamente es el límite inferior de la utilidad media: si el juego da como resultado una trayectoria de resultados , donde denota las elecciones colectivas de los jugadores en la iteración t ( t=0,1,2,...), la utilidad del jugador i se define como
donde es la función de utilidad del juego básico del jugador i .
A un juego que se repite infinitas veces y sin descuentos se le suele llamar "superjuego".
El teorema popular en este caso es muy simple y no contiene condiciones previas: cada perfil de pago individualmente racional y factible en el juego básico es un perfil de pago de equilibrio de Nash en el juego repetido.
La prueba emplea lo que se denomina una estrategia sombría [5] o de activación sombría [6] . Todos los jugadores comienzan realizando la acción prescrita y continúan haciéndolo hasta que alguien se desvía. Si el jugador i se desvía, todos los demás jugadores pasan a elegir la acción que minimiza el máximo del jugador i para siempre. La ganancia de una etapa por la desviación contribuye con 0 a la utilidad total del jugador i . La utilidad de un jugador que se desvía no puede ser mayor que su pago mínimo-máximo. Por lo tanto, todos los jugadores permanecen en el camino previsto y este es, de hecho, un equilibrio de Nash.
Perfección del subjuego
El equilibrio de Nash anterior no siempre es perfecto en subjuegos . Si el castigo es costoso para quienes castigan, la amenaza de castigo no es creíble.
Un equilibrio perfecto en subjuegos requiere una estrategia ligeramente más complicada. [5] [7] : 146–149 El castigo no debería durar para siempre; debería durar solo un tiempo finito que sea suficiente para eliminar las ganancias de la desviación. Después de eso, los otros jugadores deberían regresar a la trayectoria de equilibrio.
El criterio del límite de medias garantiza que cualquier castigo por tiempo finito no tenga efecto en el resultado final. Por lo tanto, el castigo por tiempo limitado es un equilibrio perfecto en subjuegos.
- Equilibrios perfectos en subjuegos de coalición : [8] Un equilibrio se denomina equilibrio de Nash de coalición si ninguna coalición puede obtener beneficios desviándose. Se denomina equilibrio perfecto en subjuegos de coalición si ninguna coalición puede obtener beneficios desviándose después de cualquier historia. [9] Con el criterio del límite de medias, se puede alcanzar un perfil de pagos en equilibrio de Nash de coalición o en equilibrio perfecto en subjuegos de coalición, si y solo si es eficiente en términos de Pareto y débilmente racional en cuanto a coalición individual. [10]
Adelantamiento
Algunos autores sostienen que el criterio del límite de medias no es realista, porque implica que las utilidades en cualquier lapso de tiempo finito contribuyen con 0 a la utilidad total. Sin embargo, si las utilidades en cualquier lapso de tiempo finito contribuyen con un valor positivo, y el valor no se descuenta, entonces es imposible atribuir una utilidad numérica finita a una secuencia de resultados infinita. Una posible solución a este problema es que, en lugar de definir una utilidad numérica para cada secuencia de resultados infinita, simplemente definamos la relación de preferencia entre dos secuencias infinitas. Decimos que el agente prefiere (estrictamente) la secuencia de resultados sobre la secuencia , si: [6] [7] : 139 [8]
Por ejemplo, considere las secuencias y . Según el criterio del límite de medias, proporcionan la misma utilidad al jugador i, pero según el criterio de adelantamiento, es mejor que para el jugador i . Consulte el criterio de adelantamiento para obtener más información.
Los teoremas populares con el criterio de adelantamiento son ligeramente más débiles que con el criterio del límite de medias. En el equilibrio de Nash sólo se pueden alcanzar resultados que sean estrictamente racionales individualmente. Esto se debe a que, si un agente se desvía, gana en el corto plazo, y esta ganancia sólo se puede eliminar si el castigo le da al desviado una utilidad estrictamente menor que la del camino acordado. Los siguientes teoremas populares son conocidos para el criterio de adelantamiento:
- Equilibrios estacionarios estrictos : [6] Un equilibrio de Nash se denomina estricto si cada jugador prefiere estrictamente la secuencia infinita de resultados obtenidos en equilibrio, por sobre cualquier otra secuencia a la que pueda desviarse. Un equilibrio de Nash se denomina estacionario si el resultado es el mismo en cada período de tiempo. Un resultado es alcanzable en equilibrio estacionario estricto si y solo si para cada jugador el resultado es estrictamente mejor que el resultado minimax del jugador. [11]
- Equilibrios estrictos estacionarios en subjuegos perfectos : [6] Un resultado es alcanzable en un equilibrio estricto estacionario en subjuegos perfecto si para cada jugador el resultado es estrictamente mejor que el resultado minimax del jugador (nótese que este no es un resultado "si y solo si"). Para lograr un equilibrio en subjuegos perfecto con el criterio de adelantamiento, se requiere castigar no solo al jugador que se desvía de la ruta de acuerdo, sino también a todos los jugadores que no cooperan en castigar al desviado. [7] : 149–150
- El concepto de "equilibrio estacionario" se puede generalizar a un "equilibrio periódico", en el que se repite periódicamente un número finito de resultados y el resultado en un período es la media aritmética de los resultados. Esa media de resultados debería ser estrictamente superior al resultado mínimo. [6]
- Equilibrios de coalición estacionarios estrictos : [8] Con el criterio de adelantamiento, si un resultado es alcanzable en equilibrio de coalición de Nash, entonces es eficiente en el sentido de Pareto y débilmente racional en cuanto a la coalición individual. Por otro lado, si es eficiente en el sentido de Pareto y fuertemente racional en cuanto a la coalición individual [12], se puede lograr en equilibrio de coalición estacionario estricto.
Juegos repetidos infinitamente con descuento
Supongamos que el pago de un jugador en un juego repetido infinitamente está dado por el criterio de descuento promedio con factor de descuento 0 < δ < 1:
El factor de descuento indica la paciencia de los jugadores. El factor se introduce para que la recompensa permanezca acotada cuando .
El teorema popular en este caso requiere que el perfil de pago en el juego repetido domine estrictamente el perfil de pago mínimo máximo (es decir, cada jugador recibe estrictamente más que el pago mínimo máximo).
Sea a un perfil de estrategia del juego de etapa con perfil de pago u que domina estrictamente el perfil de pago minmax. Se puede definir un equilibrio de Nash del juego con u como perfil de pago resultante de la siguiente manera:
- 1. Todos los jugadores comienzan jugando a y continúan jugando a si no se produce ninguna desviación.
- 2. Si algún jugador, digamos el jugador i , se desvía, juegue el perfil de estrategia m que minimiza i para siempre.
- 3. Ignorar las desviaciones multilaterales.
Si el jugador i obtiene ε más que su pago mínimo máximo en cada etapa al seguir 1, entonces la pérdida potencial por castigo es
Si δ está cerca de 1, esto supera cualquier ganancia finita de una etapa, lo que hace que la estrategia sea un equilibrio de Nash.
Una formulación alternativa de este teorema popular [4] permite que el perfil de pagos de equilibrio u sea cualquier perfil de pagos individualmente racionalmente factible; solo requiere que exista un perfil de pagos individualmente racionalmente factible que domine estrictamente el perfil de pagos minmax. Entonces, el teorema popular garantiza que es posible aproximarse a u en equilibrio con cualquier precisión deseada (para cada ε existe un equilibrio de Nash donde el perfil de pagos está a una distancia ε de u ).
Perfección del subjuego
Alcanzar un equilibrio perfecto en subjuegos en juegos descontados es más difícil que en juegos no descontados. El costo del castigo no desaparece (como sucede con el criterio del límite de medias). No siempre es posible castigar a quienes no castigan de manera indefinida (como sucede con el criterio de adelantamiento), ya que el factor de descuento hace que los castigos que se dan en un futuro lejano sean irrelevantes para el presente. Por lo tanto, se necesita un enfoque diferente: se debe recompensar a quienes castigan.
Esto requiere una suposición adicional: que el conjunto de perfiles de pago factibles es de dimensión completa y que el perfil mínimo-máximo se encuentra en su interior. La estrategia es la siguiente.
- 1. Todos los jugadores comienzan jugando a y continúan jugando a si no se produce ninguna desviación.
- 2. Si algún jugador, digamos el jugador i , se desvió, juegue el perfil de estrategia m que minimiza i durante N períodos. (Elija N y δ lo suficientemente grande para que ningún jugador tenga incentivos para desviarse de la fase 1).
- 3. Si ningún jugador se desvió de la fase 2, todos los jugadores j ≠ i obtienen una recompensa ε por encima del mínimo-máximo de j para siempre, mientras que el jugador i continúa recibiendo su mínimo-máximo. (Aquí se necesita la dimensionalidad completa y el supuesto interior).
- 4. Si el jugador j se desvió de la fase 2, todos los jugadores reinician la fase 2 con j como objetivo.
- 5. Ignorar las desviaciones multilaterales.
El jugador j ≠ i ahora no tiene ningún incentivo para desviarse de la fase de castigo 2. Esto demuestra el teorema popular de la perfección en subjuegos.
Juegos repetidos finitamente sin descuento
Supongamos que la ganancia del jugador i en un juego que se repite T veces está dada por una media aritmética simple:
Un teorema popular para este caso tiene el siguiente requisito adicional: [4]
- En el juego básico, para cada jugador i , existe un equilibrio de Nash que es estrictamente mejor, para i , que su pago mínimo-máximo.
Este requisito es más fuerte que el requisito para juegos infinitos descontados, que a su vez es más fuerte que el requisito para juegos infinitos sin descontar.
Este requisito es necesario debido al último paso. En el último paso, el único resultado estable es un equilibrio de Nash en el juego básico. Supongamos que un jugador i no obtiene nada del equilibrio de Nash (ya que solo le da su pago mínimo-máximo). Entonces, no hay forma de castigar a ese jugador.
Por otra parte, si para cada jugador existe un equilibrio básico que es estrictamente mejor que minmax, se puede construir un equilibrio de juego repetido en dos fases:
- En la primera fase, los jugadores alternan estrategias en las frecuencias requeridas para aproximarse al perfil de pago deseado.
- En la última fase, los jugadores juegan el equilibrio preferido de cada uno de los jugadores en su turno.
En la última fase, ningún jugador se desvía, ya que las acciones ya forman parte del equilibrio básico del juego. Si un agente se desvía en la primera fase, se le puede castigar llevándolo a su nivel mínimo máximo en la última fase. Si el juego es lo suficientemente largo, el efecto de la última fase es insignificante, por lo que el resultado del equilibrio se aproxima al perfil deseado.
Aplicaciones
Los teoremas populares se pueden aplicar a una gran variedad de campos. Por ejemplo:
- Antropología : en una comunidad donde todo comportamiento es bien conocido y donde los miembros de la comunidad saben que seguirán teniendo que tratar unos con otros, entonces cualquier patrón de comportamiento ( tradiciones , tabúes , etc.) puede ser sostenido por normas sociales siempre y cuando los individuos de la comunidad estén mejor permaneciendo en la comunidad que si la abandonaran (la condición minimax).
- Política internacional: los acuerdos entre países no se pueden hacer cumplir de manera efectiva, pero se mantienen porque las relaciones entre los países son de largo plazo y los países pueden usar "estrategias minimax" unos contra otros. Esta posibilidad a menudo depende del factor de descuento de los países en cuestión. Si un país es muy impaciente (presta poca atención a los resultados futuros), puede ser difícil castigarlo (o castigarlo de manera creíble). [5]
Por otra parte, el economista del MIT Franklin Fisher ha señalado que el teorema popular no es una teoría positiva. [13] Al considerar, por ejemplo, el comportamiento del oligopolio , el teorema popular no le dice al economista qué harán las empresas, sino que las funciones de costo y demanda no son suficientes para una teoría general del oligopolio, y los economistas deben incluir el contexto dentro del cual operan los oligopolios en su teoría. [13]
En 2007, Borgs et al. demostraron que, a pesar del teorema popular, en el caso general calcular los equilibrios de Nash para juegos repetidos no es más fácil que calcular los equilibrios de Nash para juegos finitos de una sola vez, un problema que se encuentra en la clase de complejidad PPAD . [14] La consecuencia práctica de esto es que no se conoce ningún algoritmo eficiente (de tiempo polinomial) que calcule las estrategias requeridas por los teoremas populares en el caso general.
Resumen de teoremas populares
La siguiente tabla compara varios teoremas populares en varios aspectos:
- Horizonte: si el juego de escenario se repite un número finito o infinito de veces.
- Utilidades: cómo se determina la utilidad de un jugador en el juego repetido a partir de las utilidades del jugador en las iteraciones del juego de etapa.
- Condiciones en G (el juego de escenario): si existen condiciones técnicas que deberían cumplirse en el juego de una sola partida para que el teorema funcione.
- Condiciones sobre x (el vector de pago objetivo del juego repetido): si el teorema funciona para cualquier vector de pago individualmente racional y factible, o solo para un subconjunto de estos vectores.
- Tipo de equilibrio: si se cumplen todas las condiciones, ¿qué tipo de equilibrio garantiza el teorema: Nash o subjuego perfecto?
- Tipo de castigo: ¿qué tipo de estrategia de castigo se utiliza para disuadir a los jugadores de desviarse?
Teoremas populares en otros contextos
En alusión a los teoremas populares para juegos repetidos, algunos autores han utilizado el término "teorema popular" para referirse a los resultados sobre el conjunto de posibles equilibrios o pagos de equilibrio en otros entornos, especialmente si los resultados son similares en cuanto a los pagos de equilibrio que permiten. Por ejemplo, Tennenholtz demuestra un "teorema popular" para el equilibrio de programas . Muchos otros teoremas populares se han demostrado en entornos con compromiso. [19] [20] [21] [22]
Notas
- ^ En matemáticas, el término teorema popular se refiere en general a cualquier teorema que se cree y se discute, pero que no se ha publicado. Roger Myerson ha recomendado el término más descriptivo "teorema de viabilidad general" para los teoremas de teoría de juegos que se analizan aquí. Véase Myerson, Roger B. Game Theory, Analysis of conflict , Cambridge, Harvard University Press (1991)
- ^ R. Gibbons (1992). Introducción a la teoría de juegos . Harvester Wheatsheaf. pág. 89. ISBN 0-7450-1160-8.
- ^ Jonathan Levin (2002). "Negociación y juegos repetidos" (PDF) .
- ^ abc Michael Maschler; Eilon Solan ; Shmuel Zamir (2013). Teoría de juegos . Cambridge University Press . págs. 176–180. ISBN 978-1-107-00548-8.
- ^ abcde Aumann, Robert J.; Shapley, Lloyd S. (1994). "Competencia a largo plazo: un análisis de la teoría de juegos" (PDF) . Ensayos sobre teoría de juegos . p. 1. doi :10.1007/978-1-4612-2648-2_1. ISBN 978-1-4612-7621-0.
- ^ abcdef Rubinstein, Ariel (1979). "Equilibrio en superjuegos con el criterio de adelantamiento". Journal of Economic Theory . 21 : 1–9. doi :10.1016/0022-0531(79)90002-4.
- ^ abcdef Osborne, Martin J.; Rubinstein, Ariel (12 de julio de 1994). Un curso de teoría de juegos . ISBN 0-262-15041-7. Número de serie 94008308. OL 1084491M.
- ^ abcdef Rubinstein, A. (1980). "Equilibrio perfecto fuerte en superjuegos". Revista internacional de teoría de juegos . 9 : 1–12. doi :10.1007/BF01784792. S2CID 122098115.
- ^ En el artículo se utiliza el término "equilibrio fuerte". Para evitar ambigüedades, en este trabajo se utiliza en su lugar el término "equilibrio de coalición".
- ^ ab Para cada coalición no vacía , existe una estrategia de los otros jugadores ( ) tal que para cualquier estrategia jugada por , la recompensa cuando juega no es [estrictamente mejor para todos los miembros de ].
- ^ En el artículo de 1979, Rubinstein afirma que un resultado es alcanzable en un equilibrio estacionario estricto si y solo si, para cada jugador, el resultado es O estrictamente mejor que el resultado minimax del jugador O el resultado es débilmente mejor que cualquier otro resultado al que el jugador pueda desviarse unilateralmente. No está claro cómo se puede alcanzar la segunda opción en un equilibrio estricto. En el libro de 1994, esta afirmación no aparece.
- ^ ab para cada coalición no vacía , existe una estrategia de los otros jugadores ( ) tal que para cualquier estrategia jugada por , la recompensa es estrictamente peor para al menos un miembro de .
- ^ ab Fisher, Franklin M. Games Economists Play: A Noncooperative View The RAND Journal of Economics, Vol. 20, No. 1. (Primavera de 1989), pp. 113-124, este análisis en particular se encuentra en la página 118
- ^ Christian Borgs; Jennifer Chayés; Nicole Inmorlica ; Adam Tauman Kalai ; Vahab Mirrokni; Christos Papadimitriou (2007). "El mito del teorema popular" (PDF) . págs. 365–372.
- ^ Benoit, Jean-Pierre; Krishna, Vijay (1985). "Juegos finitamente repetidos". Econometrica . 53 (4): 905. doi :10.2307/1912660. JSTOR 1912660.
- ^ Rubinstein, Ariel (1994). "Equilibrio en superjuegos". Ensayos sobre teoría de juegos . pp. 17–27. doi :10.1007/978-1-4612-2648-2_2. ISBN 978-1-4612-7621-0.
- ^ abcd Fudenberg, Drew; Maskin, Eric (1986). "El teorema de Folk en juegos repetidos con descuento o con información incompleta". Econometrica . 54 (3): 533. CiteSeerX 10.1.1.308.5775 . doi :10.2307/1911307. JSTOR 1911307.
- ^ Hay una colección de resultados IR posibles , uno por jugador, tales que para cada jugador , y .
- ^ Forges, Françoise (2013). "Un teorema popular para juegos bayesianos con compromiso". Juegos y comportamiento económico . 78 : 64–71. doi :10.1016/j.geb.2012.11.004.
- ^ Oesterheld, Caspar; Treutlein, Johannes; Grosse, Roger; Conitzer, Vincent; Foerster, Jakob (2023). "Equilibrio cooperativo basado en similitud". Actas de los Sistemas de procesamiento de información neuronal (NeurIPS) .
- ^ Kalai, Adam Tauman ; Kalai, Aod ; Lehrer, Aod; Samet, Dov (2010). "Un teorema popular del compromiso". Juegos y comportamiento económico . 69 (1): 127-137. doi :10.1016/j.geb.2009.09.008.
- ^ Block, Juan I.; Levine, David K. (2017). "Un teorema popular con códigos de conducta y comunicación". Boletín de Teoría Económica . 5 (1): 9–19. doi : 10.1007/s40505-016-0107-y .
Referencias
- Friedman, J. (1971). "Un equilibrio no cooperativo para superjuegos". Review of Economic Studies . 38 (1): 1–12. doi :10.2307/2296617. JSTOR 2296617.
- Ichiishi, Tatsuro (1997). Teoría Microeconómica . Oxford: Blackwell. págs. 263–269. ISBN 1-57718-037-2.
- Mas-Colell, A .; Whinston, M.; Green, J. (1995). Teoría microeconómica . Nueva York: Oxford University Press. ISBN 0-19-507340-1.
- Ratliff, J. (1996). "Un ejemplo de teorema popular" (PDF) . Un conjunto de notas introductorias al Teorema de Folk.