Herausragende Vermutungen und offene Probleme in der (algorithmischen) Spieltheorie?

14

Welche Art von Vermutungen und offenen Hauptproblemen sind in der algorithmischen Spieltheorie (oder der Spieltheorie im Allgemeinen in Bezug auf CS) am wichtigsten? Zum Beispiel wäre die Auflösung von NASH als PPAD-vollständig meines Erachtens die größte gewesen, bis sie aufgelöst wurde.

(Hinzugefügt: PPADs Beziehung zu P und NP zu lösen ist ein gutes offenes Problem, aber andere, die nicht so tief in der Komplexität der Berechnung verankert sind, wären auch nett.)

daveagp
quelle
3
Diese Frage würde besser funktionieren, wenn Sie sie als CW (Community Wiki) kennzeichnen. Siehe hier: meta.cstheory.stackexchange.com/questions/225/…
Daniel Apon
2
Genau. bitte CW ankreuzen.
Suresh Venkat

Antworten:

5

Hier sind einige offene Probleme:

Das offene 1-Hauptproblem ist das Problem der Berechnung des ungefähren Nash-Gleichgewichts.

2- Gibt es einen effizienten Algorithmus zur Berechnung des reinen Nash-Gleichgewichts in Überlastungsspielen?

3-Finding-Gleichgewichte bei minimaler Ineffizienz?

4-Tim Roughgarden stellte in Communications of the ACM das folgende offene Problem:

Inwieweit ist eine "anreizkompatible" effiziente Berechnung grundsätzlich weniger leistungsfähig als eine "klassische" effiziente Berechnung?

Algorithmische Spieltheorie, Mitteilungen des ACM, Band 53, Ausgabe 7, (Juli 2010)

Diese Referenzen enthalten auch einige offene Probleme: Nisan, Roughgarden, Tardos und Vazirani, Herausgeber. Algorithmische Spieltheorie. Cambridge University Press, 2007.

T. Roughgarden. Algorithmische Spieltheorie: Einige der größten Hits und zukünftigen Richtungen. In TCS '08, p. 21–42.

Mohammad Al-Turkistany
quelle
Die aktuelle Umfrage ist sehr hilfreich. Ich hatte mir tatsächlich das Buch von Nisan +++ angesehen - eine Textsuche nach "Vermutung" liefert nur ein paar Treffer! --- aber es gibt in der Tat viele offene Probleme. Irgendwelche spezifischen Vermutungen oder weniger technische offene Probleme wären bei meiner Suche immer noch willkommen.
Daveagp
Die Berechnung eines reinen Nash-Gleichgewichts eines allgemeinen Überlastungsspiels ist PLS-vollständig, so dass es wahrscheinlich keinen effizienten Algorithmus gibt.
Rahul Savani
1

In dieser Referenz werfen Papadimitriou und Roughgarden 6 offene Probleme im Zusammenhang mit der Berechnung korrelierter Gleichgewichte auf:

Papadimitriou und Tim Roughgarden, die korrelierte Gleichgewichte in Multiplayer-Spielen berechnen

Außerdem wirft Papadimitriou in diesem Artikel einige offene Probleme im Zusammenhang mit der Spieltheorie und dem Internet auf:

Papadimitriou, Algorithmen, Spiele und das Internet, Proc. STOC 2001

Mohammad Al-Turkistany
quelle
2
Papadimitrious Umfrage ist etwas veraltet, da bei den meisten offenen Problemen seit 2001 erhebliche Fortschritte
Ryan Williams