Métrica de Helly

En teoría de juegos, la métrica de Helly es utilizada para evaluar la distancia entre dos estretegias. Debe su nombre al matemático austríaco Eduard Helly.

Considerado un juego $\Gamma =\left\langle {\mathfrak {X}},{\mathfrak {Y}},H\right\rangle$ entre los jugadores 1 y 2. Aquí, ${\mathfrak {X}}$ and ${\mathfrak {Y}}$ son los conjuntos de estrategia pura para los jugadores 1 y 2 respectivamente; mientras que $H=H(\cdot ,\cdot )$ es la función de pago.

Dicho de otra manera, si el jugador 1 juega $x\in {\mathfrak {X}}$ y el jugador 2 juega $y\in {\mathfrak {Y}}$, entonces el jugador 1 paga $H(x,y)$ al jugador 2.

La métrica de Helly $\rho (x_{1},x_{2})$ se define como

$\rho (x_{1},x_{2})=\sup _{y\in {\mathfrak {Y}}}\left|H(x_{1},y)-H(x_{2},y)\right|.$

La métrica así definida es simétrica, reflexiva, y satisface la desigualdad triangular.

La métrica de Helly mide distancias entre estrategias, no en términos de diferencias entre las estrategias mismas, si no en términos de las consecuencias de las estrategias. Dos estrategias son distantes si sus pagos son diferentes. Nótese que $\rho (x_{1},x_{2})=0$ no incluye $x_{1}=x_{2}$, pero sí incluye que las consecuencias de $x_{1}$ y $x_{2}$ son idénticas; y de hecho esto induce una relación de equivalencia.

Si uno estipula que $\rho (x_{1},x_{2})=0$ implica $x_{1}=x_{2}$, entonces la topología así inducida es llamada topología natural.

La métrica en el espacio de las estrategias del jugador 2 son análogas:

$\rho (y_{1},y_{2})=\sup _{x\in {\mathfrak {X}}}\left|H(x,y_{1})-H(x,y_{2})\right|.$

Nótese que $\Gamma$ define dos métricas de Helly: una para cada espacio de estrategia de cada jugador.

Compacidad condicional

Notación (definición de una $\epsilon$-net). Un conjunto $X_{\epsilon }$ es una $\epsilon$-net en el espacio $X$ con métrica $\rho$ si para cada $x\in X$ existe una $x_{\epsilon }\in X_{\epsilon }$ con $\rho (x,x_{\epsilon })<\epsilon$.

Un espacio métrico $P$ es condicionalmente compacto si para cada $\epsilon >0$ existe un $\epsilon$-net finito en $P$.

Un juego que es condicionalmente compacto en la métrica de Helly tiene una estrategia de $\epsilon$ óptima para cada $\epsilon >0$.

Otros resultados

Si el espacio de estrategias para un jugador es condicionalmente compacto, entonces el espacio de estrategias para el otro jugador es condicionalmente compacto (en su métrica de Helly).

Referencias

• Vorob'ev, N. N. (1977). Game theory lectures for economists and systems scientists (S. Kotz, trad.) (en inglés). Springer. 

• Datos: Q5709140