Vi avancerar betydligt bortom den senaste tidens framsteg på algoritmisk komplexitet Nash Equilibria genom att lösa två stora öppna problem i approximationen av Nash Equilibria och i den utjämnade analysen av algoritmer. • Vi visar att ingen algoritm med komplexitet poly(n, 1 ) kan beräkna en -ungefärlig Nash jämvikt i ett tvåspelarspel, där varje spelare har n rena strategier, om inte PPAD  på P. Med andra ord, problemet med att beräkna en Nash jämvikt i ett tvåspelarspel inte har en helt polynom-tid approximation system om inte PPAD P. • Vi bevisar att ingen algoritm för att beräkna en Nash jämvikt i ett tvåspelarspel kan ha utjämnad komplexitet poly(n, 1 σ ) under inmatning perturbation av magnitud σ, om inte PPAD  till RP. I synnerhet är den utjämnade komplexiteten hos den klassiska Lemke-howson algoritmen inte polynom om inte PPAD  på RP. Instrumental till vårt bevis, introducerar vi ett nytt diskret fast punkt problem på en högdimensionell hypergrid med konstant sidlängd, och visa att det kan vara värd för inbäddning av bevisstrukturen i alla PPAD-problem. Vi bevisar en viktig geometrisk lemma för att hitta en diskret fast punkt, ett nytt koncept som definieras på n + 1 hörn av en enhet hyperkub. Denna lemma gör det möjligt för oss att övervinna dimensionalitetens förbannelse i resonemanget om fasta punkter i höga dimensioner. 1 Som en - ungefärlig Nash jämvikt (x, y) i spelet (A, B) blir en c · - ungefärlig Nash jämvikt i spelet (cA, cB) för c > 0. Efter Lipton, Markakis och Mehta [16] normaliserar vi matriserna A och B så att alla deras poster ligger mellan 0 och 1, eller mellan -1 och 1 när vi studerar -ungefär Nash equilibria.
Chen, Deng och Teng REF visade att detta problem inte har polynom utjämnad komplexitet om inte RP=PPAD.
Computing Nash Equilibria: Approximation and Smoothed Complexity
{'venue': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'journal': "2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)", 'mag_field_of_study': ['Computer Science', 'Mathematics']}