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

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

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.

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