Welche Beziehung besteht zwischen

Antworten:

6

Wenn man die potentielle Funktion approximieren will, gibt es sogar ein vollständig polynomielles Zeitnäherungsschema (FPTAS). Sehen

James B. Orlin, Andreas S. Schulz, Abraham P. Punnen: Ungefähre lokale Suche in der kombinatorischen Optimierung. SIAM J. Comput. 33 (5): 1201 & ndash; 1214 (2004).

Für einige Einstellungen ist dies jedoch nicht interessant. Beispielsweise können für Überlastungsspiele, in denen reine Gleichgewichte existieren und deren Berechnung PLS-vollständig ist, Strategieprofile, die die potenzielle Funktionsvertiefung approximieren, sehr schlechte ungefähre Gleichgewichte sein. Für einige Einstellungen kann eine konstante Faktor-Näherungsgleichheit in Polynomzeit berechnet werden, selbst wenn die Berechnung eines exakten Gleichgewichts PLS-schwer ist, für andere Einstellungen ist es PLS-schwer, ein ungefähres Gleichgewicht für eine beliebige Polynomzeit-berechenbare nicht-triviale Näherung zu berechnen Faktor, wie in der folgenden Ankündigung Papier erklärt.

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin und Alexander Skopalik: Berechnung der ungefähren reinen Nash-Gleichgewichte in Überlastungsspielen. SIGecom Exchanges 11 (1): 26-29 (2012).

Hinweis: PLS ist möglicherweise viel einfacher als FNP.

Rahul Savani
quelle