Pytania otagowane jako gt.game-theory

Zagadnienie teoretyczne związane z informatyką i teorią gier

2
Złożoność częściowych gier informacyjnych o skończonym stanie
Biorąc pod uwagę deterministyczną grę z sumą zerową z częściową informacją i tylko skończoną liczbą stanów, których możliwymi rezultatami są odpowiednio [przegrana, remis, wygrana] o wartościach odpowiednio [-1,0, + 1], jaka jest złożoność przybliżenia wartości takich gra w dodatku ?ϵϵ\epsilon W szczególności nie mogę wymyślić żadnego algorytmu do tego. Pozostała …
3
Implementacja surrealistycznych liczb do gier
Conway ma bardzo ładną konstrukcję o surrealistycznych liczbach. Są to „liczby”, które zawierają zarówno liczby rzeczywiste, jak i liczby porządkowe, są całkowicie uporządkowane i mają wszystkie właściwości pola (z wyjątkiem, że nie tworzą zbioru, ale klasę). Zobacz na przykład ten plik pdf lub Wikipedię w celu wprowadzenia. Można je jeszcze …
2
Jak trudno policzyć liczbę lokalnych optymów dla problemu w PLS?
W przypadku wielomianowego problemu wyszukiwania lokalnego wiemy, że musi istnieć co najmniej jedno rozwiązanie (lokalne optimum). Jednak może istnieć wiele innych rozwiązań, jak trudno jest policzyć liczbę rozwiązań problemu z kompletnym PLS? Jestem szczególnie zainteresowany w problemu decyzyjnego: nie wystąpienie tego problemu PLS-complete mają dwa lub więcej rozwiązań? Czy złożoność …
5
Algorytmiczna teoria gier - niestandardowe koncepcje równowagi?
Zaczynam studia nad algorytmiczną teorią gier i wydaje się, że zwykle pojęcie równowagi jest oparte na punkcie stałym na wykresie. Jednak czy ludzie przyglądali się alternatywnym koncepcjom równowagi, takim jak cykle graniczne? Mogę sobie wyobrazić, że „ciasny” cykl graniczny - to znaczy cykl na wykresie o bardzo małej długości - …
1
Jaka jest złożoność tej gry?
To jest uogólnienie mojego poprzedniego pytania . Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle . Początkowo jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech będzie ciągiem znaków.MMMAAAAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio …
1
Czy ta gra jest EXPSPACE?
Niech będzie wielomianem czasie deterministyczny urządzenie, które może zadać pytania do jakiegoś oracle A . Początkowo A jest puste, ale można to zmienić po grze, która zostanie opisana poniżej. Niech x będzie ciągiem znaków.M.MMZAAAZAAAxxx Rozważ następującą grę Alice and Bob. Początkowo Alice i Bob mają odpowiednio i m B dolarów. …
1
Równowaga w grze w postój
Rozważ następującą grę 2-osobową: Natura losowo wybiera program Każdy gracz gra liczbę w [0, nieskończoność] włącznie w odpowiedzi na ruch natury Weź minimalną liczbę graczy i uruchom program dla (maksymalnie) tak wielu kroków (chyba że obaj gracze wybiorą nieskończoność) Jeśli program się zatrzyma, gracz, który zagrał minimalną liczbę, otrzymuje 1 …
3
Udoskonalenia aproksymacji par do analizy sieci
Rozważając interakcje w sieci, zwykle bardzo trudno jest analitycznie obliczyć dynamikę i stosuje się przybliżenia. Przybliżenia pola średniego zwykle całkowicie ignorują strukturę sieci, a zatem rzadko są dobrym przybliżeniem. Popularnym aproksymacją jest aproksymacja pary, która uwzględnia korelacje nieodłączne między sąsiednimi węzłami (intuicyjnie możemy myśleć o tym jako o typie aproksymacji …
3
Problem wyboru słowa kluczowego w aukcji marketingu w wyszukiwarkach
Po pierwsze, wciąż nie jestem pewien, czy cstheory jest dobrze przystosowana do tego pytania, więc nie obrażę się, jeśli tłum uzna, że ​​tak nie jest ... W marketingu w wyszukiwarkach interesujących jest kilka problemów. Zaprojektowanie uczciwych (i rentownych) mechanizmów aukcyjnych oraz obliczenie optymalnych strategii licytacji w ramach ograniczonych zasobów pieniężnych …
3
Algorytmy obliczania równowagi Nasha.
Przeszukałem forum, aby sprawdzić, czy zostało to już zadane, i chociaż omawiamy teorię gier algorytmicznych, nie mogłem znaleźć rozwiązania tego konkretnego problemu. Próbuję dowiedzieć się, jaki jest najbardziej znany algorytm obliczania przybliżonej (mieszanej strategii) równowagi Nasha w skończonej grze n-person. Oczywiście algorytmem tym byłby PPAD. Bardziej interesuje mnie szybkość / …
1
Sekretarka zatrudniająca
Jest to rozszerzenie klasycznego problemu sekretarza . W grze o zatrudnianie masz zestaw kandydatów i porządek na temat umiejętności każdego pracownika.C={c1,…,cN}C={c1,…,cN}\mathcal C=\{c_1,\ldots,c_N\} Wlog, zakładamy, że jest najbardziej wykwalifikowany, a następnie itd.c1c1c_1c2c2c_2 Kolejność, w jakiej kandydaci są wybierani losowo, jest jednolita i (oczywiście) nieznana pracodawcom. Załóżmy teraz, że masz rynek z …
1
Kiedy strategie -Nash Equilibrium zbiegają się ze strategiami Nash Equilibrium?
Równowagi Nasha ogólnie nie można obliczyć. -Nash równowaga jest zbiorem strategii, gdzie podane strategie rywalek, każdy gracz uzyska w ciągu maksymalnej możliwej oczekiwanego wypłat. Znalezienie równowagi Nash, biorąc pod uwagę i grę, jest .ϵϵ\epsilonϵϵ\epsilonϵϵ\epsilonϵϵ\epsilonP P A DPPAD\mathsf{PPAD} Idąc ściśle za definicjami, wydaje się, że nie ma szczególnego powodu, aby sądzić, …
1
Uproszczona wersja Zwycięzca gry karcianej
Zadałem ten problem w MathOverflow , bez zadowalającej odpowiedzi. Rozważ następującą grę dla dwóch graczy, która jest uproszczeniem gry karcianej o nazwie Zwycięzca . (Poniższe sformułowanie zostało zaczerpnięte z komentarza Guillaume Brunerie na temat MathOverflow.) Jest dwóch graczy A i B. Każdy gracz ma zestaw kart (podzbiór { 1 , …
2
Zrozumienie dowodu projektu mechanizmu
Walczyłem ze szczegółami technicznymi dowodu dotyczącego teorii aukcji w tym artykule: http://users.eecs.northwestern.edu/~hartline/omd.pdf W szczególności Twierdzenie 2.5: Warunki konieczne i wystarczające dla prawdziwego mechanizmu. Mówiąc dokładniej, kierunek dowodu do przodu, podany na stronie 6. Definiując prawdziwą wartość jako oraz ogólną, być może fałszywą, wartość (np. Ofertę) jako , autor kontynuuje postulowanie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.