Piekielna metryka

W teorii gier metryka Helly'ego służy do oceny odległości między dwiema strategiami . Nosi imię Eduarda Helly'ego .

Rozważmy grę między graczem I i ${\ Displaystyle \ Gamma = \ lewo \ langle {\ mathfrak {X}}, {\ mathfrak {Y}}, H \ prawo \ rangle}$ . Tutaj i $są$ czystych strategii odpowiednio $dla$ graczy I i II i ${\ Displaystyle H = H (\ cdot, \ cdot)}$ jest funkcją wypłaty.

(innymi słowy, jeśli gracz I gra ${\ Displaystyle x \ in {\ mathfrak {X$$a$ gracz II gra , to gracz } Płacę graczowi II H. $\ Displaystyle H (x, y)} .$

Metryka Helly'ego jest zdefiniowana jako ${\ Displaystyle \ rho (x_ {1}, x_ {2})}$

${\ Displaystyle \ rho (x_ {1}, x_ {2}) = \ sup _ {y \ w {\ mathfrak {Y}}} \ lewo | H (x_ {1}, y) -H (x_ {2} },y)\prawo|.}$

Tak zdefiniowana metryka jest symetryczna, zwrotna i spełnia nierówność trójkąta .

Metryka Helly'ego mierzy odległości między strategiami, nie w kategoriach różnic między samymi strategiami, ale w kategoriach konsekwencji strategii. Dwie strategie są odległe, jeśli ich wypłaty są różne. Zauważ, że ${\ Displaystyle \ rho (x_ {1}, x_ {2}) = 0}$ nie implikuje ${\ Displaystyle x_ {1} = x_ {2} },$ ale oznacza to, że $displaystyle x_ {1}}$ 1 { i są identyczne; ${\ displaystyle x_ {2}}$ i rzeczywiście indukuje to relację równoważności .

ρ $\ Displaystyle \ rho (x_ {1}, x_ {2}) = 0}$${\ Displaystyle x_ {1} = x_ {2} }$ implikuje to tak indukowana topologia nazywana jest topologią naturalną .

Metryka dotycząca przestrzeni strategii gracza II jest analogiczna:

${\ Displaystyle \ rho (y_ {1}, y_ {2}) = \ sup _ {x \ w {\ mathfrak {X}}} \ lewo | H (x, y_ {1}) -H (x, y_ {2})\prawo|.}$

Zauważ, że w ten sposób definiuje się dwie metryki Helly: $po$ dla przestrzeni strategicznej każdego gracza.

Warunkowa zwartość

$epsilon$$}$ definicję -net: zbiór jest $displaystyle \$ -net w przestrzeni z metryką ρ ${\ Displaystyle \ rho}$${\ displaystyle X _ {\ epsilon}$ jeśli dla dowolnego ${\ Displaystyle x \ w X}$ istnieje ${\ Displaystyle x _ {\ epsilon} \ w X_ {\ epsilon}}$ z ${\ Displaystyle \ rho (x, x _ {\ epsilon}) <\ epsilon}$ .

Przestrzeń metryczna $jest$ warunkowo zwarta (lub $przedzwarta$ ), jeśli dla dowolnego w $displaystyle$ { $P$ } . Każda gra $> 0}$ która jest warunkowo zwarta w metryce Helly, ma -optymalną strategię dla każdego $epsilon$ . Co więcej, jeśli przestrzeń strategii jednego gracza jest warunkowo zwarta, to przestrzeń strategii drugiego gracza jest warunkowo zwarta (w ich metryce Helly).

NN Vorob'ev 1977. Wykłady z teorii gier dla ekonomistów i naukowców systemów . Springer-Verlag (przekład S. Kotz).