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

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

Рассмотрим игру между игроками I и II. Здесь и – множества чистых стратегий для игроков I и II соответственно; и является функцией выигрыша. ${\displaystyle \Gamma =\left\langle {\mathfrak {X}},{\mathfrak {Y}},H\right\rangle }$ ${\displaystyle {\mathfrak {X}}}$ ${\displaystyle {\mathfrak {Y}}}$ ${\displaystyle H=H(\cdot ,\cdot )}$

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

Метрика Хелли определяется как ${\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 }$

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

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

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

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

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