stringtranslate.com

Teorema popular (teoría de juegos)

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:

  1. 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.
  2. 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.

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:

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 ji 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 ji 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:

  1. En la primera fase, los jugadores alternan estrategias en las frecuencias requeridas para aproximarse al perfil de pago deseado.
  2. 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:

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:

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

  1. ^ 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)
  2. ^ R. Gibbons (1992). Introducción a la teoría de juegos . Harvester Wheatsheaf. pág. 89. ISBN 0-7450-1160-8.
  3. ^ Jonathan Levin (2002). "Negociación y juegos repetidos" (PDF) .
  4. ^ 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.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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".
  10. ^ 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 ].
  11. ^ 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.
  12. ^ 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 .
  13. ^ 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
  14. ^ 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.
  15. ^ Benoit, Jean-Pierre; Krishna, Vijay (1985). "Juegos finitamente repetidos". Econometrica . 53 (4): 905. doi :10.2307/1912660. JSTOR  1912660.
  16. ^ 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.
  17. ^ 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. 
  18. ^ Hay una colección de resultados IR posibles , uno por jugador, tales que para cada jugador , y .
  19. ^ 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.
  20. ^ 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) .
  21. ^ 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.
  22. ^ 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