Juego no atómico

En teoría de juegos , un juego no atómico (GNA) es una generalización del juego en forma normal a una situación en la que hay tantos jugadores que pueden considerarse como un continuo. Los GNA fueron introducidos por David Schmeidler ; ^{[ 1 ]} extendió el teorema sobre la existencia de un equilibrio de Nash , que John Nash demostró originalmente para juegos finitos, a los GNA.

Schmeidler motiva el estudio de los NAG-s de la siguiente manera: ^{[ 1 ]}

Los juegos no atómicos nos permiten analizar una situación de conflicto donde el jugador individual no tiene influencia, pero el comportamiento colectivo de grandes grupos de jugadores puede modificar los resultados. Los ejemplos son numerosos: elecciones, muchos pequeños compradores de unas pocas empresas competidoras, conductores que pueden elegir entre varias carreteras, etc.

En un juego estándar ("atómico"), el conjunto de jugadores es un conjunto finito. En un NAG, el conjunto de jugadores es un conjunto infinito y continuo.${\displaystyle P}$, que puede modelarse, por ejemplo, mediante el intervalo unitario${\displaystyle [0,1]}$Existe una medida de Lebesgue definida sobre el conjunto de jugadores, que representa cuántos jugadores hay de cada "tipo".

Cada jugador puede elegir uno de${\displaystyle m}$acciones ("estrategias puras"). Nótese que el conjunto de acciones, a diferencia del conjunto de jugadores, permanece finito como en los juegos estándar. Los jugadores también pueden elegir una estrategia mixta: una distribución de probabilidad sobre las acciones. Un perfil de estrategia es una función medible del conjunto de jugadores.${\displaystyle P}$al conjunto de distribuciones de probabilidad sobre acciones; la función asigna a cada punto${\displaystyle p}$en${\displaystyle P}$una distribución de probabilidad${\displaystyle x(p)}$; representa el hecho de que el jugador infinitesimal${\displaystyle p}$ha optado por la estrategia mixta${\displaystyle x(p)}$.

Dejar${\displaystyle x}$ser un perfil de estrategia. La elección de un jugador infinitesimal${\displaystyle p}$no tiene efecto en el resultado general, pero afecta su propia recompensa. Específicamente, para cada acción pura${\displaystyle j}$en${\displaystyle \{1,\dots ,m\}}$hay una función${\displaystyle u_{j}}$que mapea a cada jugador${\displaystyle p}$en${\displaystyle P}$y cada perfil de estrategia${\displaystyle x}$a la utilidad que ese jugador${\displaystyle p}$recibe cuando juega${\displaystyle j}$y todos los demás jugadores juegan como en${\displaystyle x}$Como jugador${\displaystyle p}$juega una estrategia mixta${\displaystyle x(p)}$, su recompensa es el producto interno${\displaystyle x(p)\cdot u(p,x)}$.

Perfil estratégico${\displaystyle x}$se llama puro si${\displaystyle x(p)}$es una estrategia pura para casi todos${\displaystyle p}$en${\displaystyle P}$.

Perfil estratégico${\displaystyle x}$Se denomina equilibrio si para casi todos los jugadores${\displaystyle p}$y cada estrategia mixta${\displaystyle y}$, sostiene que$${\displaystyle x(p)\cdot u(p,x)\geq y\cdot u(p,x).}$$

David Schmeidler demostró los siguientes teoremas para el caso${\displaystyle P=[0,1]}$: ^{[ 1 ]}

Teorema 1. Si para todo${\displaystyle p}$la función${\displaystyle u(p,\cdot )}$es débilmente continua desde${\displaystyle L^{1}([0,1])}$a${\displaystyle \mathbb {R} }$y para todos${\displaystyle x}$y${\displaystyle i}$,${\displaystyle j}$el conjunto${\displaystyle \{p\mid u_{i}(p,x)>u_{j}(p,x)\}}$Si es medible, entonces existe un equilibrio.

La demostración utiliza el teorema del punto fijo de Glicksberg .

Teorema 2. Si, además de las condiciones anteriores,${\displaystyle u(p,x)}$depende únicamente de las integrales de acción del perfil estratégico, es decir, de$${\displaystyle \left(\int _{P}x_{j}(t)\,\mathrm {d} t\right)_{j\in \{1,\dots ,m\}},}$$Entonces existe un equilibrio de estrategia pura.

La demostración utiliza un teorema de Robert Aumann . La condición adicional del Teorema 2 es esencial: existe un ejemplo de un juego que satisface las condiciones del Teorema 1, sin equilibrio de estrategia pura. David Schmeidler también demostró que el teorema de equilibrio de Nash se deduce como corolario del Teorema 2. Específicamente, dado un juego finito en forma normal${\displaystyle G}$con${\displaystyle n}$jugadores, se puede construir un juego no atómico${\displaystyle H}$de tal manera que cada jugador en${\displaystyle G}$corresponde a un subintervalo de${\displaystyle P}$de longitud${\displaystyle 1/n}$. La función de utilidad se define de manera que satisface las condiciones del Teorema 2. Un equilibrio de estrategia pura en${\displaystyle H}$corresponde a un equilibrio de Nash (con posibles estrategias mixtas) en${\displaystyle G}$.

Un caso especial del modelo general es que existe un conjunto finito${\displaystyle T}$de tipos de jugadores . Cada tipo de jugador${\displaystyle t}$está representado por un subintervalo de${\displaystyle P_{t}}$del conjunto de jugadores${\displaystyle P}$. La duración del subintervalo representa la cantidad de jugadores de ese tipo. Por ejemplo, es posible que${\displaystyle 1/2}$Los jugadores son de tipo${\displaystyle 1}$,${\displaystyle 1/3}$son de tipo${\displaystyle 2}$, y${\displaystyle 1/6}$son de tipo${\displaystyle 3}$Los jugadores del mismo tipo tienen la misma función de utilidad, pero pueden elegir estrategias diferentes.

Una subclase especial de juegos no atómicos contiene las variantes no atómicas de los juegos de congestión (NCG). Este caso especial se puede describir de la siguiente manera.

• Hay un conjunto finito${\displaystyle E}$de elementos congestionables (por ejemplo, carreteras o recursos).
• Hay${\displaystyle n}$tipos de jugadores. Para cada tipo${\displaystyle i}$hay un número${\displaystyle r_{i}}$, que representa la cantidad de jugadores de ese tipo (la tasa de tráfico para ese tipo).
• Para cada tipo${\displaystyle i}$hay un conjunto${\displaystyle S_{i}}$de posibles estrategias (posibles subconjuntos de${\displaystyle E}$).
• Diferentes jugadores del mismo tipo pueden elegir diferentes estrategias. Para cada estrategia${\displaystyle s}$en${\displaystyle S_{i}}$, dejar${\displaystyle x_{i,s}}$denotan la fracción de jugadores en tipo${\displaystyle i}$utilizando estrategia${\displaystyle s}$. Por definición,${\displaystyle \sum _{s\in S_{i}}x_{i,s}=r_{i}}$. Denotamos${\displaystyle x_{s}:=\sum _{i:s\in S_{i}}f_{s,i}}$
• Para cada elemento${\displaystyle e}$en${\displaystyle E}$, la carga en${\displaystyle e}$se define como la suma de fracciones de jugadores que utilizan${\displaystyle e}$, eso es,${\displaystyle x_{e}=\sum _{s\ni e}x_{s}}$. El retraso experimentado por los jugadores que utilizan${\displaystyle e}$se define mediante una función de retardo${\displaystyle d_{e}}$Esta función debe ser monótona, positiva y continua .
• La desutilidad total de cada jugador al elegir estrategia${\displaystyle s}$es la suma de los retrasos en todos los bordes del subconjunto${\displaystyle s}$:${\displaystyle d_{s}(x)=\sum _{e\in s}d_{e}(x_{e})}$.
• Un perfil de estrategia es un equilibrio si para cada tipo de jugador${\displaystyle i}$y por cada dos estrategias${\displaystyle s_{1},s_{2}}$en${\displaystyle S_{i}}$, si${\displaystyle x_{i,s_{1}}>0}$, entonces${\displaystyle d_{s_{1}}(x)\leq d_{s_{2}}(x)}$. Es decir: si una medida positiva de jugadores de tipo${\displaystyle i}$elegir${\displaystyle s_{1}}$, entonces ninguna otra estrategia posible les daría un retraso estrictamente menor.

Los NCG fueron estudiados por primera vez por Milchtaich, ^{[ 2 ]} Friedman ^{[ 3 ]} y Blonsky. ^{[ 4 ]} Roughgarden y Tardos ^{[ 5 ]} estudiaron el precio de la anarquía en los NCG.

El cálculo de un equilibrio en un NCG puede reformularse como un problema de optimización convexa y, por lo tanto, puede resolverse en tiempo polinomial débil (por ejemplo, mediante el método del elipsoide ). Fabrikant, Papadimitriou y Talwar ^{[ 6 ]} presentaron un algoritmo de tiempo polinomial fuerte para encontrar un PNE en el caso especial de NCG de red . En este caso especial hay un grafo${\displaystyle G}$; para cada tipo${\displaystyle i}$Hay dos nodos${\displaystyle s_{i}}$y${\displaystyle t_{i}}$de${\displaystyle G}$; y el conjunto de estrategias disponibles para escribir${\displaystyle i}$es el conjunto de todos los caminos desde${\displaystyle s_{i}}$a${\displaystyle t_{i}}$Si las funciones de utilidad de todos los jugadores son Lipschitz continuas con constante${\displaystyle L}$, entonces su algoritmo calcula un${\displaystyle e}$-aproximar PNE en tiempo fuertemente polinomial - polinomial en${\displaystyle n}$,${\displaystyle L}$y${\displaystyle 1/e}$.

Los dos teoremas de Schmeidler pueden generalizarse de varias maneras: ^{[ 1 ] : Observaciones finales}

• En el Teorema 2, en lugar de exigir que${\displaystyle u(p,x)}$depende únicamente de${\displaystyle \int _{P}x}$, se puede exigir que${\displaystyle u(p,x)}$depende únicamente de${\displaystyle \int _{P_{1}}x,\ldots ,\int _{P_{k}}x}$, dónde${\displaystyle P_{1},\dots ,P_{k}}$son subconjuntos medibles de Lebesgue de${\displaystyle P}$.
• En el Teorema 1, en lugar de requerir que el espacio de estrategias de cada jugador sea un simplex, es suficiente requerir que el espacio de estrategias de cada jugador sea un subconjunto convexo compacto de${\displaystyle \mathbb {R} ^{m}}$Si se cumple la suposición adicional del Teorema 2, entonces existe un equilibrio en el que la estrategia de casi todos los jugadores es la misma.${\displaystyle p}$es un punto extremo del espacio estratégico de${\displaystyle p}$.

• Juego continuo : un juego con un número finito de jugadores, pero con un conjunto de estrategias continuamente amplio.
• Juego de congestión#nonatomic .