Czy istnieje gra, która nie może być reprezentowana przez drzewo gry?

Czy istnieje skończona gra, która nie może być reprezentowana przez obszerna forma lub drzewo gry?

Wiem, że wiele gier jest zbyt długich i złożonych, aby mogły być reprezentowane przez drzewo o rozsądnym rozmiarze, ale to nie jest to, czego szukam, ponieważ jest to częściowo ograniczenie obliczeniowe.

Zamiast tego zastanawiam się, czy jest tam coś prostego, które po prostu nie pasuje do obszernej formy? Wszystkie książki, które przeczytałem, mówią coś w rodzaju

Różne gry mogą być reprezentowane przez drzewa

Ale nigdzie nie widziałem roszczenia „wszystkie gry”. Czy są jakieś znane wyjątki?

game-theory

— Arthur Tarasov
źródło

Odpowiedzi:

Cóż, do tego trzeba zdefiniować, czym jest „skończona gra”. Zwykłym sposobem na to jest zdefiniowanie go jako obszernej gry w formie, która sprawia, że cały problem jest okrągły. Istnieją jednak różne sposoby modelowania rozległych gier na różnych poziomach ogólności. Na przykład pierwsza definicja z powodu Johna von Neumanna i Oskara Morgensterna wprowadziła szereg silnych ograniczeń czasowych, które wyglądają nieco archaicznie z dzisiejszej perspektywy. Kolejna definicja Harolda Kuhna znacznie uogólniła klasę możliwych obszernych gier form. Niejawne ograniczenie sposobu, w jaki Kuhn definiował rozległe gry formularzy, polegało na tym, że żaden gracz nie może poruszać się po tych samych informacjach ustawionych dwukrotnie, założenie osłabia się w Ph.D. teza Johna Isbella. Istnieją więc różne koncepcje obszernych gier formalnych na różnych poziomach ogólności, w tym wersje, które pozwalają na nieskończone gry.

— Michael Greinecker
źródło

Dziękuję Ci! Czy mógłbyś wskazać mi kierunek książki lub papieru, który opisuje, jak modelować nieskończoną grę w szerokiej formie?

— Arthur Tarasov

Podręcznik Osborne & amp; Rubinstein powinien mieć dość, żebyś zaczął. Jeśli potrzebujesz więcej lub czegoś konkretnego, daj mi znać.

— Michael Greinecker

Ciekawa myśl ...

Sądzę, że recursive games, w których wynik zależy od grania w tę samą grę, w dynamicznej liczbie razy, nie może być reprezentowany w formie lub matrycy

Częstszym przypadkiem jest jednoczesne gry wieloosobowe, gdy ma 2 graczy wymaga macierzy 2d, każdy nowy gracz doda wymiar do macierzy, więcej niż 3 nie będzie w stanie reprezentować wykresu, ale tylko bazę danych, taką jak schemat

— Guy Louzon
źródło

Gry z pętlami i grami recourive nie są grami skończonymi. Ze względu na pętle liczba punktów decyzyjnych, a tym samym liczba strategii, jest nieskończona.

— denesp

Być może źle zrozumiałem twój ostatni akapit, ale drzewa gier mogą łatwo przedstawiać gry $ n $ -player, nawet jeśli $ n> 3 $. Musisz tylko dodać punkty decyzji.

— denesp

@denesp w odniesieniu do ostatniego akapitu, gry symultaniczne są opisane za pomocą 2d macierzy, gdzie każdy wymiar reprezentuje gracza, więc dodanie trzeciej gry będzie opisane jako sześcian, aw przypadku gry 4 nie można wyświetlić czwartej

— Guy Louzon

@denesp dlaczego nie? skończona, ale nieznana liczba iteracji, kiedy każdy koniec pętli może prowadzić do innego wyniku, jest grą skończoną bez możliwości modelowania przez drzewo

— Guy Louzon

Chciałbym powtórzyć mój drugi komentarz, który, jak się zdaje, oblałeś. Gry $ n $ -player, nawet gry symultaniczne mogą być łatwo przedstawione za pomocą grafów drzewa. Przykład (aczkolwiek w przypadku gry bez jednoczesnego ruchu, ale logika jest taka sama).

— denesp