Pytania otagowane jako gt.game-theory

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

5
Dowód, że PPAD jest trudny?
Często cytowane jest filozoficzne uzasadnienie, by wierzyć, że P! = NP nawet bez dowodu. Inne klasy złożoności mają dowody na ich odrębność, ponieważ jeśli nie, miałyby „zaskakujące” konsekwencje (takie jak upadek hierarchii wielomianowej). Moje pytanie brzmi: jaka jest podstawa przekonania, że ​​klasa PPAD jest trudna do rozwiązania? Gdyby istniał algorytm …
1
Referencyjne gry z niepowiązanymi półprywatnymi monetami
Byłem (i nadal jestem) bardzo zainteresowany odpowiedzią na to pytanie, ponieważ jest to interesująca odmiana złożoności gier, która nie została jeszcze rozwiązana, więc zaoferowałem nagrodę. Pomyślałem, że pierwotne pytanie jest prawdopodobnie zbyt trudne, więc zamieściłem trzy powiązane pytania, które również byłyby warte nagrody. Nikt nie opublikował żadnych odpowiedzi przed wygaśnięciem …
3
Czy ta odmiana TQBF jest wciąż kompletna z PSPACE?
Decydowanie, czy skwantyfikowana formuła boolowska, taka jak ∀ x1∃ x2)∀ x3)⋯ ∃ xnφ ( x1, x2), … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), zawsze ocenia na prawdę, to klasyczny problem z PSPACE. Można to postrzegać jako grę między dwoma graczami, z naprzemiennymi …
4
Wybór społeczny, twierdzenie strzały i otwarte problemy?
W ostatnich miesiącach zacząłem wykładać na temat wyboru społecznego, twierdzenia strzały i powiązanych wyników. Po przeczytaniu o przełomowych wynikach zadałem sobie pytanie, co dzieje się z częściowymi preferencjami porządku, odpowiedź znajduje się w pracy Pini i in. : Agregowanie częściowo uporządkowanych preferencji: wyniki niemożliwości i możliwości . Następnie zastanawiałem się, …
4
Redutacja gry permutacyjnej
Jest to powtórzenie wcześniejszego pytania . Rozważ następującą bezstronną idealną grę informacyjną między dwoma graczami, Alice i Bobem. Gracze otrzymują permutację liczb całkowitych od 1 do n. Jeśli w każdej turze wzrasta bieżąca permutacja, obecny gracz przegrywa, a drugi gracz wygrywa; w przeciwnym razie aktualny gracz usuwa jeden z numerów …
1
Wybór tematu badań z wykorzystaniem teorii gier
Ta ostatnia teoria gier pytanie dało mi do myślenia (to jest styczna, oczywiście): Czy jest możliwe, aby skutecznie zoptymalizować osobistą strategię wyboru pytania badawcze do pracy na wykorzystaniu teorii gier? Aby przejść do sformalizowania pytania, przyjmuję następujące (nieformalnie) założenia: Równie „lubię” każdy konkretny problem dostępny dla mnie do pracy (aby …
2
Jak ciężka jest mafia?
Mafia to popularna gra fabularna na imprezach, szczegółowy opis jest dostępny na stronie wikipedia http://en.wikipedia.org/wiki/Mafia_%28game%29 . Zasadniczo działa w następujący sposób: Na początku każdemu z graczy potajemnie przypisywana jest rola, dostosowana do mafii lub miasta. Każda rola może mieć specjalne umiejętności; więcej o tym później.N.N.N Istnieją dwie fazy gry: dzień …
1
Separacja między zgrubnie skorelowanych równowag i skorelowanych równowag
Szukam przykładów technik dowodzenia ceny granic anarchii, które mogą oddzielić cenę anarchii od zgrubnie skorelowanych równowag (ograniczający zestaw dynamiki bezżałowania zewnętrznego) od ceny anarchii nad skorelowanymi równowagami (ograniczenie zestaw dynamiki bez żalu). Czy znane są naturalne separacje tego typu? Jedną z przeszkód w rozdzielaniu tych dwóch klas jest to, że …
3
Źródła algorytmicznej ewolucyjnej teorii gier
Używam tytułowego terminu w bardzo luźnym znaczeniu. Dużo pracy poświęcono ewolucyjnej teorii gier, w tym jej matematycznym fundamentom. Polecono mi „Gry ewolucyjne i dynamika populacji”, ale jeszcze się w to nie zagłębiłem. Istnieje również znaczna ilość pracy nad algorytmiczną teorią gier, która jest popularnym tematem na tej stronie. Chciałbym zobaczyć …
1
Obliczeniowa wersja równowagi Nasha?
Zastanawiam się, czy istnieje obliczeniowa wersja koncepcji równowagi Nasha, coś podobnego do tego. Wyobraź sobie jakąś idealną grę informacyjną dla dwóch graczy, która jest rozgrywana na planszy , i która jest złożona w tym sensie, że optymalna gra jest trudna WYGODNIE. Załóżmy również dla uproszczenia, że ​​losowanie nie jest możliwe. …
3
Wymiana prezentów od białego słonia: mechanizmy sprawiedliwego podziału
Popularną grą na wakacyjnych imprezach w Ameryce Północnej jest wymiana prezentów z białym słoniem . W skrócie (ignorowanie odmian) działa to w następujący sposób: Jest ludzi i n zapakowanych prezentów. Gracze są sortowani arbitralnie. W í th okrągłym, odtwarzacz i albonnnnnnjathjathi^{\text{th}}jajai wybiera zapakowany prezent i rozpakowuje go jako prezent „kradnie” …
7
Zastosowania teorii gier w informatyce?
Jako student informatyki zapoznałem się z teorią gier, ale nie widziałem zbyt wielu szczegółów na ten temat. Szukałem w Google i przeglądałem książki o teorii gier, które potwierdziły jej wykorzystanie w informatyce. Rozpocząłem formalne studium teorii gier z perspektywy ekonomisty. Teraz chcę poznać zastosowania teorii gier w informatyce. Jakie są …
2
Gra polegająca na ustawianiu nakładających się kręgów, aby zmaksymalizować czas podróży między nimi
Spotkałem następującą grę. Przeprowadzę migrację zgodnie z żądaniem. Błąd odwiedza kręgi, a przeciwnik chce zmaksymalizować swój czas podróży. Przeciwnik umieszcza koło na każdym kroku. Błąd przesuwa się z bieżącej pozycji bezpośrednio w kierunku środka najnowszego kręgu, a następnie zatrzymuje się, gdy napotka wnętrze koła (w ten sposób: nie chodzi, jeśli …
3
Gra na kilku wykresach
Rozważ następującą grę na ukierunkowanym wykresie ważonym solGG z chipem w pewnym węźle. Wszystkie węzły solGG oznaczone są literą A lub B. Jest dwóch graczy Alice i Bob. Celem Alicji (Bob) jest przesunięcie czipa do węzła oznaczonego literą A (B). Początkowo Alice i Bob mają odpowiednio mZAmAm_A i mbmBm_B dolarów. …
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.