Хелли метрика

В теории игр метрика Хелли используется для оценки расстояния между двумя стратегиями . Он назван в честь Эдуарда Хелли .

Определение

Рассмотрим игру $\Gamma =\left\langle {\mathfrak {X}},{\mathfrak {Y}},H\right\rangle$, между игроком I и II. Здесь, ${\mathfrak {X}}$ и ${\mathfrak {Y}}$ — множества чистых стратегий для игроков I и II соответственно. Функция выигрыша обозначается $H=H(\cdot ,\cdot )$. Другими словами, если игрок I играет $x\in {\mathfrak {X}}$ и игрок II играет $y\in {\mathfrak {Y}}$, затем игрок I платит $H(x,y)$ игроку II.

Хелли Метрика $\rho (x_{1},x_{2})$ определяется как

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

Определенная таким образом метрика является симметричной, рефлексивной и удовлетворяет неравенству треугольника .

Свойства

Метрика Хелли измеряет расстояния между стратегиями не с точки зрения различий между самими стратегиями, а с точки зрения последствий стратегий. Две стратегии являются далекими, если их выигрыши различны. Обратите внимание, что $\rho (x_{1},x_{2})=0$ не подразумевает $x_{1}=x_{2}$ но это подразумевает, последствия что $x_{1}$ и $x_{2}$ идентичны; и действительно, это порождает отношение эквивалентности .

Если оговорить, что $\rho (x_{1},x_{2})=0$ подразумевает $x_{1}=x_{2}$, то индуцированная таким образом топология называется естественной топологией .

Метрика в пространстве стратегий игрока II аналогична:

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

Обратите внимание, что $\Gamma$ таким образом определяет две метрики Хелли: по одной для стратегического пространства каждого игрока.

Условная компактность

Напомним определение $\epsilon$-net: набор $X_{\epsilon }$ это $\epsilon$-сеть в космосе $X$ с метрикой $\rho$ если для любого $x\in X$ существует $x_{\epsilon }\in X_{\epsilon }$ с $\rho (x,x_{\epsilon })<\epsilon$.

Метрическое пространство $P$ ( условно компактен или предкомпактен), если для любого $\epsilon >0$ существует конечное $\epsilon$-нет в $P$. Любая игра, условно компактная в метрике Хелли, имеет $\epsilon$-оптимальная стратегия для любого $\epsilon >0$. fПри этом если пространство стратегий одного игрока условно компактно, то пространство стратегий другого игрока условно компактно (в их метрике Хелли).

Ссылки

• Воробьев, Николай Николаевич (1977). Теория игр: Лекции для экономистов и системологов . Перевод Коца, Сэмюэля. Спрингер-Верлаг . ISBN  9783540902386 .