Gra bez wartości

Kwadrat gry (czyli wypłata dla gracza I) za grę bez wartości ze względu na Sion i Wolfe. Wypłata wynosi 0 wzdłuż dwóch ukośnych linii

W matematycznej teorii gier , w szczególności w badaniu ciągłych gier o sumie zerowej , nie każda gra ma wartość minimax . Jest to oczekiwana wartość dla jednego z graczy, gdy obaj grają idealną strategią (czyli wybierają z konkretnego pliku PDF ).

W tym artykule podano przykład gry o sumie zerowej , która nie ma żadnej wartości . To zasługa Siona i Wolfe'a .

Wiadomo, że gry o sumie zerowej ze skończoną liczbą czystych strategii mają wartość minimax (pierwotnie udowodnioną przez Johna von Neumanna ), ale niekoniecznie tak jest, jeśli gra ma nieskończony zestaw strategii. Oto prosty przykład gry bez wartości minimax.

Istnienie takich gier o sumie zerowej jest interesujące, ponieważ wiele wyników teorii gier staje się niemożliwych do zastosowania, jeśli nie ma wartości minimaksu.

Gra

Gracze I i II wybierają liczby odpowiednio od 0 do 1. Wypłata dla gracza I wynosi ${\ displaystyle x}$ i ${\ displaystyle y}$

$${\ Displaystyle K (x, y) = {\ rozpocząć {przypadki} -1 i {\ tekst {jeśli}} x <y <x + 1/2, \\ 0 & {\ tekst {jeśli}} x = y {\ text{ lub }}y=x+1/2,\\1&{\text{inaczej.}}\end{przypadki}}}$$

$graczowi$ że po dokonaniu wyborów gracz II płaci I (więc gra sumie

Jeśli para jest interpretowana jako punkt na $kwadracie$ jednostkowym, rysunek przedstawia wypłatę dla gracza I. Gracz I może przyjąć strategię mieszaną, funkcja gęstości prawdopodobieństwa (pdf) $i$$podobnie$ wybiera spośród . Gracz I stara się zmaksymalizować wypłatę $gracz II,$ drugiego

Wartość gry

Sion i Wolfe to pokazują

$${\ Displaystyle \ sup _ {f} \ inf _ {g} \ iint K \, df \, dg = {\ Frac {1} {3}}}$$

Ale

$${\ Displaystyle \ inf _ {g} \ sup _ {f} \ iint K \, df \, dg = {\ Frac {3} {7}}.}$$

Są to maksymalne i minimalne oczekiwania dotyczące wartości gry gracza odpowiednio I i II.

Sup ${\ displaystyle \ sup}$ i ${\ displaystyle \ inf}$ odpowiednio biorą supremum i infimum nad pdf w przedziale jednostkowym (właściwie prawdopodobieństwa Borela ). Reprezentują one (mieszane) strategie gracza I i gracza II. Tak więc gracz I może zapewnić sobie wypłatę co najmniej 3/7, jeśli zna strategię gracza II, a gracz II może ograniczyć wypłatę do 1/3, jeśli zna strategię gracza I.

Nie ma równowagi epsilon dla wystarczająco małych , w szczególności, jeśli $({\frac {3}{7}}-{\frac {1}{3}}\right)\simeq 0,0476}$$lewo$$\ Displaystyle \ varepsilon <{\ Frac {1} {2}} \$ . Dasgupta i $II ,$ gracz I przyłoży wagę prawdopodobieństwa tylko do zestawu i gracza gracz kładzie ciężar tylko na ${\ Displaystyle \ lewo \ {1/4,1/2,1 \ prawo \}}$ .

  Twierdzenie Glicksberga pokazuje, że każda gra o sumie zerowej z górną lub dolną półciągłą funkcją wypłaty ma wartość (w tym kontekście górna (dolna) półciągła funkcja K to taka, w której zbiór ${\ displaystyle \ {P \ mid K (P) <c \}}$ (resp ${\ Displaystyle \ {P \ mid K (P)> c \}} )$ jest otwarty na wszelkie realne numer C ).

Funkcja wypłaty w przykładzie Siona i Wolfe'a nie jest półciągła. Można to jednak zrobić, zmieniając wartość K ( x , x ) i K ( x , x + 1/2) (wypłata wzdłuż dwóch nieciągłości) na +1 lub -1, zwiększając wypłatę lub odpowiednio dolny półciągły. Jeśli tak się stanie, gra ma wtedy wartość.

Uogólnienia

Kolejna praca Heuera omawia klasę gier, w których kwadrat jednostkowy jest podzielony na trzy regiony, przy czym funkcja wypłaty jest stała w każdym z regionów.