Jakie przypuszczenia i główne otwarte problemy są najważniejsze w algorytmicznej teorii gier (lub ogólnie teorii gier w odniesieniu do CS)? Na przykład rozdzielczość NASH jako kompletna z PPAD byłaby, jak sądzę, największa do czasu jej rozwiązania.
(Dodano: rozwiązanie stosunku PPAD do P i NP to jeden dobry otwarty problem, ale fajne byłyby również inne, nie tak głęboko zakorzenione w złożoności obliczeniowej).
big-list
gt.game-theory
daveagp
źródło
źródło
Odpowiedzi:
Oto kilka otwartych problemów:
1-Głównym otwartym problemem jest problem obliczania przybliżonych równowag Nasha.
2- Istnienie wydajnego algorytmu do obliczania równowagi Nasha w grach z przeciążeniem?
3-znalezienie równowagi przy minimalnej nieefektywności?
4-Tim Roughgarden w komunikacie ACM postawił następujący otwarty problem:
Algorytmiczna teoria gier, Komunikat ACM, tom 53, wydanie 7, (lipiec 2010 r.)
Odnośniki te zawierają również pewne otwarte problemy: redaktorzy Nisan, Roughgarden, Tardos i Vazirani. Algorytmiczna teoria gier. Cambridge University Press, 2007.
T. Roughgarden. Algorytmiczna teoria gier: niektóre największe trafienia i przyszłe kierunki. W TCS '08, str. 21–42.
źródło
W tej publikacji Papadimitriou i Roughgarden stwarzają 6 otwartych problemów związanych z obliczaniem skorelowanych równowag:
Papadimitriou i Tim Roughgarden, Obliczanie skorelowanych równowag w grach wieloosobowych
Ponadto w tym artykule Papadimitriou przedstawia kilka otwartych problemów związanych z teorią gier i Internetem:
Papadimitriou, Algorytmy, gry i Internet, Proc. STOC 2001
źródło