Метрика Хелли - Helly metric

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

Рассмотрим игру ${ displaystyle Gamma = left langle { mathfrak {X}}, { mathfrak {Y}}, H right rangle}$, между игроком I и II. Здесь, ${ displaystyle { mathfrak {X}}}$ и ${ displaystyle { mathfrak {Y}}}$ наборы чистые стратегии для игроков I и II соответственно; и ${ Displaystyle ЧАС = ЧАС ( CDOT, CDOT)}$ - функция выплаты.

(другими словами, если игрок I играет ${ displaystyle x in { mathfrak {X}}}$ и игрок II играет ${ displaystyle y in { mathfrak {Y}}}$, затем игрок I платит ${ Displaystyle Н (х, у)}$ игроку II).

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

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

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

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

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

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

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

Обратите внимание, что ${ displaystyle Gamma}$ таким образом определяет два Показатели Helly: по одной для области стратегии каждого игрока.

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

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

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

Рекомендации

Н. Н. Воробьев 1977. Лекции по теории игр для экономистов и системологов. Springer-Verlag (перевод С. Коца).

Этот теория игры статья - это заглушка. Вы можете помочь Википедии расширяя это.