Znakomite przypuszczenia i otwarte problemy w (algorytmicznej) teorii gier?

14

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).

daveagp
źródło
3
To pytanie działałoby lepiej, jeśli oflagowałeś je jako CW (Wiki Wiki). Zobacz tutaj: meta.cstheory.stackexchange.com/questions/225/…
Daniel Apon
2
Zgadzam się. proszę zaznaczyć to CW.
Suresh Venkat

Odpowiedzi:

5

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:

w jakim stopniu wydajne obliczenia „zgodne z zachętami” są zasadniczo mniej wydajne niż wydajne obliczenia „klasyczne”?

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.

Mohammad Al-Turkistany
źródło
Ostatnia ankieta jest bardzo pomocna. Rzeczywiście spojrzałem na książkę Nisana +++ - wyszukiwanie tekstu „domniemanie” daje tylko kilka trafień! --- ale rzeczywiście istnieje wiele otwartych problemów. Wszelkie szczególne domniemania lub mniej techniczne specyficzne otwarte problemy nadal byłyby mile widziane w moich poszukiwaniach.
daveagp
Obliczenie czystej równowagi Nasha w ogólnej grze o zatorach jest kompletne z PLS, więc mało prawdopodobne jest istnienie wydajnego algorytmu.
Rahul Savani
1

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

Mohammad Al-Turkistany
źródło
2
Ankieta Papadimitriou jest nieco przestarzała, ponieważ od 2001 r. Poczyniono znaczne postępy w większości otwartych problemów.
Ryan Williams